Ограничения парсеров LL против LR?

Question

Я знаю основные отличия парсера LL от LR.Я также знаю, что GLR, SLR и LALR являются расширениями парсеров LR.Итак, мой вопрос более подробно: ...

Учитывая парсер LL (*) и любые вариации парсера LR, есть ли какой-нибудь язык, который можно описать в одном, а не в другом?Или, проще говоря, есть ли какая-либо особенность или свойство, которое нельзя выразить ни одним из них?

В качестве конкретного примера.Если бы я должен был создать язык с использованием синтаксического анализатора LL (*), столкнусь ли я когда-нибудь с желаемой функцией / свойством, которое я мог бы добавить к своему языку, который был бы возможен только с анализатором LR (или наоборот)?

Answer 1

Вот пара мнений, вы можете считать их точкой и контрапунктом:

• Анализ должен быть проще - в пользу LL
• Почему я предпочитаю парсеры LALR - в пользу LR

Answer 2

Вы можете найти интересным этот параграф в Википедии, где говорится, что грамматики LL (*) являются подмножеством грамматик LR (k): http://en.wikipedia.org/wiki/Context-free_grammar#Restrictions Таким образом, вы можете анализировать больше языков, используя методы синтаксического анализа LR.

Answer 3

Конечно. LL-парсеры не могут обрабатывать грамматики с левой рекурсией. Парсеры L (AL) R (k) для фиксированного k не смогут проанализировать некоторые вещи, которые может обрабатывать парсер LL (*), потому что k <*. </p>

Answer 4

Есть некоторые грамматики, которые не могут быть «переписаны» для анализа парсерами LL, которые могут быть проанализированы парсерами LR. Один пример: дана простая грамматика, которая строит термины с вычитаниями:

S -> S - S | num

Вы, очевидно, имеете здесь левую рекурсию, которая не может быть обработана LL-парсерами. Чтобы сделать эту грамматику доступной для LL, вы должны исключить левую рекурсию:

S -> num S'

S' -> - num S' | epsilon

Теперь ваш анализатор LL может обрабатывать эту грамматику. Но при построении вашего синтаксического дерева для термина, подобного 4 - 2 -1, поиск по глубине, выполняемый в дереве, даст вам 4 - (2 - 1) = 3 вместо (4 - 2) - 1 = 3 как и следовало ожидать.

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

Итак, у вас есть класс языков, которые не могут быть обработаны LL.

Answer 5

LR парсер может принимать больший класс языков, чем LL. В LL (k) и LR (k) k означает количество символов с предварительным ожиданием, которые необходимо знать, чтобы он мог применить соответствующее производство / сокращение. Чем больше k, тем больше таблицы разбора. Таким образом, k не ограничивает только парсеры LR, но также ограничивает парсеры LL. Причина, по которой LR-парсер может принимать больший класс языков, заключается в левой рекурсии, которая проблематична при работе с LL-парсерами. Но это не совсем так, потому что прямая рекурсия разрешима, что означает, что вы можете переписать грамматику в LL грамматику. Прямая рекурсия - это что-то вроде A -> Abc. Когда у вас есть косвенная рекурсия, для которой вы, вероятно, теперь знаете, как она выглядит, тогда у вас есть проблема. Парсер LR может решить эту проблему, потому что он создает дерево синтаксического анализа снизу вверх. Вам нужно будет немного глубже проанализировать LR, чтобы понять, почему это именно так. Но парсеры LR не все могучие, у них тоже есть ограничения. Некоторые грамматики очень трудно усваиваются, и коэффициент k не помогает. Для этого вида грамматик необходим синтаксический анализатор GLR, который фактически имитирует синтаксический анализатор LR (k), но использует обратную трассировку для анализа всего пространства синтаксического анализа, когда возникает неоднозначность производства / сокращения.

Answer 6

Разбор LL теоретически O (n ^ 4) или довольно медленный. Разбор LR быстрее, O (n ^ 3) или довольно медленный. https://en.wikipedia.org/wiki/Top-down_parsing

Хотя я бы хотел увидеть доказательства этого.