LALR vs LL parser

Я использую lex/yacc, и теперь я пытаюсь переключиться на ANTLR. Основная проблема заключается в том, что ANTLR является парсером LL (*), в отличие от yacc, который является LALR. Я привык думать о снизу вверх, и я точно не знаю, в чем преимущество LL-грамматик. Люди говорят, что грамматики LL легче понять и более популярны в наши дни. Но кажется, что парсители LR более мощные, например. Анализаторы LL неспособны иметь дело с левыми рекурсиями, хотя, похоже, некоторые способы обхода.

Итак, вопрос в чем заключается преимущество LL-грамматик над LALR? Я был бы признателен, если бы кто-нибудь мог привести несколько примеров. Ссылки на полезные статьи были бы замечательными.

Спасибо за вашу помощь заранее!

(Я вижу, что это отличный ресурс: Какие преимущества у парсеров LL есть у парсеров LR?, но с некоторыми примерами было бы лучше).

Ответ 1

Самое большое преимущество, которое я вижу в партерах LL, заключается в том, что их так легко понять и реализовать! Вы можете написать парсер рекурсивный спуск с кодом, который точно соответствует грамматике.

LR обычно считаются более мощными, а также намного быстрее, но есть несколько компромиссов, которые я знаю:

Партеры LR могут использовать только синтезированные атрибуты; они не могут передать унаследованные атрибуты.
Действия в грамматике LR могут вызывать нетерминизм грамматики, но не в LL.

Однако вы обнаружите, что LL (*) также очень эффективны.

Ответ 2

Анализаторы LR строго более мощные, чем LL-парсеры, и, кроме того, парсер LALR может работать в O (n), как парсы LL. Таким образом, вы не найдете никаких функциональных преимуществ LL над LR.

Таким образом, единственным преимуществом LL является то, что конечные машины LR довольно сложны и трудны для понимания, а сами пармеры LR не особенно интуитивны. С другой стороны, код парсера LL, который автоматически генерируется, может быть очень легким для понимания и отладки.