Разбор контекстно-свободных грамматик

Question

Я знаю, что анализатор «снизу вверх» лучше, чем анализатор «сверху вниз», потому что он может принимать леворекурсивную грамматику, по каким другим причинам мы предпочитаем анализ «снизу вверх» вместо анализа «сверху вниз»?

Answer 1

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

Кроме того, хитрое доказательство показывает, что любой детерминированный CFL (CFL, принятый детерминированным автоматом нажатия) имеет грамматику LR (1), что означает, что грамматики LR точно соответствуют тем языкам, которые имеют эффективные алгоритмы синтаксического анализа на основе стека. .

Тем не менее, если вы разрешите использовать более общие алгоритмы синтаксического анализа, такие как алгоритм Унгера, алгоритм Эрли или алгоритм CYK, то существуют методы нисходящего и восходящего методов для анализа произвольных CFG. Эти алгоритмы могут быть намного медленнее, чем методы прогнозирования, поэтому они обычно не используются для языков программирования.

Надеюсь, это поможет!

Answer 2

У нас есть генераторы синтаксического анализатора снизу вверх, такие как byson. Использовать их намного проще, чем писать парсеры вручную.
Кроме того, парсеры рекурсивного спуска по умолчанию делают все операции ассоциативно правыми, что неверно для арифметики. Возвращение их в левоассоциативное состояние требует дополнительных шагов при разборе.