Является ли эта грамматика БНФ LL(1)?

Может ли кто-нибудь подтвердить для меня, является ли следующая грамматика BNF LL (1):

S ::= A B B A
A ::= a
A ::=
B ::= b
B ::=

где S — начальный символ, а нетерминалы A и B могут быть преобразованы в эпсилон. Я знаю, что если в одной ячейке таблицы синтаксического анализа есть 2 или более производных, то грамматика не является LL (1). Но если ячейка уже содержит эпсилон, можем ли мы безопасно заменить ее новой продукцией при построении таблицы синтаксического анализа?


parsing ebnf grammar ll bnf
person Decade Moon    schedule 16.09.2012    source источник
comment
Хм, может быть, это не LL (1). Если мне разрешено заменить ячейку в таблице синтаксического анализа, содержащую эпсилон, как я уже упоминал в вопросе, тогда она не обнаружит конфликты FIRST/FOLLOW.   -  person Decade Moon    schedule 16.09.2012

Ответы (1)


arrow_upward
2
arrow_downward

Эта грамматика неоднозначна и, следовательно, не является ни LL(1), ни LL(k) для любого k.

Возьмите один a или b в качестве входных данных и убедитесь, что ему может соответствовать любая из ссылок A или B из S. Таким образом, есть два разных дерева синтаксического анализа, что доказывает неоднозначность грамматики.

person Gunther    schedule 17.09.2012