Разница между парсером LL и LR

Опубликовано: 17 Февраля, 2022

LL Parser включает в себя как рекурсивный синтаксический анализатор спуска, так и нерекурсивный анализатор спуска. Один его тип использует отслеживание с возвратом, а другой использует таблицу синтаксического анализа. Тезисы - синтаксический анализатор сверху вниз.
Пример: данная грамматика

 S -> Ac
А -> ab

где S - начальный символ, A - нетерминал, а a, b, c - терминалы.

Строка ввода: abc
Дерево синтаксического анализа, сгенерированное парсером LL:



LR Parser - это один из парсеров снизу вверх, который использует таблицу синтаксического анализа (динамическое программирование) для получения формы дерева синтаксического анализа заданной строки с использованием грамматических построений.

Пример: В приведенном выше примере дерево синтаксического анализа, созданное парсером LR:



Разница между парсером LL и LR:

LL парсер LR Parser
Первый L в LL предназначен для слева направо, а второй L для самого левого вывода. L в LR находится слева направо, а R - для самого правого вывода.
Он следует за крайним левым выводом. Это следует за обратным правым выводом.
Дерево парсера с использованием LL-парсера строится сверху вниз. Дерево парсера строится снизу вверх.
В парсере LL расширяются нетерминалы. В парсере LR терминалы сжимаются.
Начинается со стартового символа (S). Заканчивается символом начала (S).
Заканчивается, когда используемый стек становится пустым. Начинается с пустой стопкой.
Предварительный заказ обхода дерева синтаксического анализа. Пост-заказный обход дерева парсера.
Терминал читается после выхода из стека. Терминал считывается перед помещением в стек.
Он может использовать поиск с возвратом или динамическое программирование. Он использует динамическое программирование.
LL писать проще. LR сложно писать.
Пример: LL (0), LL (1). Пример: LR (0), SLR (1), LALR (1), CLR (1).

Вниманию читателя! Не переставай учиться сейчас. Ознакомьтесь со всеми важными концепциями теории CS для собеседований по SDE с помощью курса теории CS по доступной для студентов цене и будьте готовы к работе в отрасли.

РЕКОМЕНДУЕМЫЕ СТАТЬИ