Разница между парсером LL и LR
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 по доступной для студентов цене и будьте готовы к работе в отрасли.