Ответ 1
На высоком уровне разница между разбором LL и анализом LR заключается в том, что синтаксические анализаторы LL начинаются с символа начала и пытаются применить производные для достижения целевой строки, тогда как парсеры LR начинаются с целевой строки и пытаются вернуться на значке начала.
Разбор LL - левый-правый, самый левый вывод. То есть мы рассмотрим входные символы слева направо и попытаемся построить левый вывод. Это делается, начиная с символа начала и многократно расширяя крайний левый нетерминал, пока мы не достигнем целевой строки. Параметр LR - это левый справа, самый правый вывод, что означает, что мы сканируем слева направо и пытаемся построить самый правый вывод. Анализатор непрерывно выбирает подстроку входа и пытается отменить его обратно к нетерминальному.
Во время анализа LL парсер непрерывно выбирает между двумя действиями:
- Предсказать. Основываясь на самом левом нетерминале и некотором количестве токенов, выберите, какое производство следует применять, чтобы приблизиться к входной строке.
- Соответствие. Сопоставьте крайний левый конец символа терминала с самым левым неиспользованным символом ввода.
В качестве примера, учитывая эту грамматику:
- S → E
- E → T + E
- E → Т
- T →
int
Затем, задав строку int + int + int, синтаксический анализатор LL (2) (который использует два токена lookahead) будет анализировать строку следующим образом:
Production Input Action
---------------------------------------------------------
S int + int + int Predict S -> E
E int + int + int Predict E -> T + E
T + E int + int + int Predict T -> int
int + E int + int + int Match int
+ E + int + int Match +
E int + int Predict E -> T + E
T + E int + int Predict T -> int
int + E int + int Match int
+ E + int Match +
E int Predict E -> T
T int Predict T -> int
int int Match int
Accept
Обратите внимание, что на каждом шаге мы смотрим на самый левый символ в нашей постановке. Если это терминал, мы сопоставляем его, и если это нетерминал, мы прогнозируем, что это будет, выбирая одно из правил.
В парсер LR есть два действия:
- Shift: добавьте следующий токен ввода в буфер для рассмотрения.
- Уменьшить. Уменьшите сбор терминалов и нетерминалов в этом буфере обратно к некоторому нетерминалу, изменив процесс производства.
В качестве примера, парсер LR (1) (с одним маркером lookahead) может анализировать ту же строку, что и в следующем:
Workspace Input Action
---------------------------------------------------------
int + int + int Shift
int + int + int Reduce T -> int
T + int + int Shift
T + int + int Shift
T + int + int Reduce T -> int
T + T + int Shift
T + T + int Shift
T + T + int Reduce T -> int
T + T + T Reduce E -> T
T + T + E Reduce E -> T + E
T + E Reduce E -> T + E
E Reduce S -> E
S Accept
Известно, что два алгоритма синтаксического анализа (LL и LR) имеют разные характеристики. Анализаторы LL, как правило, легче писать вручную, но они менее эффективны, чем парсеры LR, и принимают гораздо меньший набор грамматик, чем LR parsers. Анализаторы LR представлены во многих вариантах (LR (0), SLR (1), LALR (1), LR (1), IELR (1), GLR (0) и т.д.) И являются гораздо более мощными. Они также имеют гораздо более сложный характер и почти всегда генерируются такими инструментами, как yacc или bison. Анализаторы LL также представлены во многих вариантах (включая LL (*), который используется инструментом ANTLR), хотя на практике LL (1) широко используется.
Как бесстыдный плагин, если вы хотите больше узнать о разборе LL и LR, я только что закончил обучение курсу компиляторов и некоторые раздаточные материалы и слайды для лекций по разбору на веб-сайте курса. Я был бы рад разработать любой из них, если вы считаете, что это было бы полезно.
