Преобразование грамматики в LL (1), определить, является ли это LL (1)

Question

Я не могу понять, как определить, является ли грамматика LL (1) или нет. Я получил следующую грамматику:

S → Y | 1X 
X → 1X | 0 
Y → Y0|1X1|2X2 

Я сказал, что эта грамматика не LL (1), потому что Y0 остается рекурсивным.

Так что я придумал следующее решение:

S → Y | 1X 
X → 1X | 0 
Y → 1X1F | 2X2F 
F → ε | 0F 

Но все же я не уверен, что это правильно. Я все еще думаю, что, должно быть, я пропустил какое-то правило, подобное факторингу. Должен ли я взять 1X и 2X в другую переменную?

Благодарим за помощь. Я также хотел бы знать, есть ли более простые способы определить, является ли грамматика LL (1). Я столкнулся с множеством «первых» и «последующих» таблиц, но на самом деле им не удалось создать ее самостоятельно.

Answer 1

Грамматика LL (1) должна быть в состоянии предсказать производство на основе одного ((1)) токена. Однако и Y, и 1X могут начинаться с 1, поэтому невозможно предсказать, следует ли использовать S→Y или S→1X с учетом первого символа ввода 1. Таким образом, ни оригинальная грамматика, ни преобразованная грамматика не являются LL (1).

Answer 2

Если фактор нашего 1X, то я получаю следующее:

S → Y | Z 
X → Z | 0 
Y → Z1F | 2X2F 
F → ε | 0F 
Z → 1X | ε 

Это означает, что S → Y | Z, и я считаю, что это запрещено.