Как преобразовать неоднозначную грамматику с кванторами в LL1?

Question

Я не могу разобраться с разрешением этой грамматики (? Означает ноль или одно вхождение, + означает хотя бы одно вхождение) в некоторый эквивалент, который можно проанализировать с помощью LL (1):

S -> X? Y+
X -> aU
Y -> aV

проблема в том, что: когда я вижу «а», это произвело X или Y?Есть идеи?

РЕДАКТИРОВАТЬ: U и V могут начинаться с одного и того же символа ...

Answer 1

Вам необходимо оставить фактор правил, чтобы создать грамматику LL (1). Пока U и V не могут начинаться с одного и того же символа (и не могут иметь значения NULL), вы можете начать с эквивалентного регулярного выражения a(Ua)?V(aV)*.

Если U и V могут начинаться с одного и того же символа, вам также необходимо выделить общий префикс (ы).