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

Question

Допустим, у меня есть эта грамматика:

S -> A C x | u B A
A -> z A y | S u | ε
B -> C x | y B u
C -> B w B | w A

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

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

Заранее спасибо.

Answer 1

Обе S / A и B / C включают косвенную левую рекурсию .

Поскольку леворекурсивная грамматика (прямая или косвенная) не является LL(k) для любого k вы можете доказать, что грамматика не является LL (1), просто показав леворекурсивный цикл.(С другой стороны, если у вас есть инструмент, который вычисляет наборы FIRST и FOLLOW, «классический» метод действительно очень прост.)

Устранение косвенной левой рекурсии включает в себя сначала поиск одного возможного топологического вида нетерминалы и затем прерывая цикл деривации, подставляя некоторые использования нетерминала с его правой стороны.После этого можно применить простой алгоритм исключения левой рекурсии.

Конкретные примеры этого преобразования можно найти здесь, в StackOverflow , или здесь , или в любом другом.учебник по теории парсинга.(Или, конечно, путем поиска термина «косвенная левая рекурсия» и поиска страниц с некоторой достоверностью.)