На высоком уровне разница между разбором LL и разбором LR заключается в том, что парсеры LL начинаются с начального символа и пытаются применить продукцию для достижения целевой строки, тогда как парсеры LR начинаются с целевой строки и пытаются вернуться назад. на начальном символе.
Разбор LL - слева направо, крайний левый вывод. То есть мы рассматриваем входные символы слева направо и пытаемся построить крайний левый вывод. Это делается, начиная с начального символа и многократно расширяя крайний левый нетерминал, пока мы не достигнем целевой строки. Разбор LR - это вывод слева направо, крайний справа, это означает, что мы сканируем слева направо и пытаемся построить крайний вывод справа. Анализатор непрерывно выбирает подстроку ввода и пытается вернуть ее обратно к нетерминалу.
Во время анализа LL анализатор постоянно выбирает между двумя действиями:
- Predict : На основе крайнего левого нетерминала и некоторого числа лексем предпросмотра выберите, какое произведение следует применить, чтобы приблизиться к входной строке.
- Сопоставление : сопоставление крайнего левого угаданного символа терминала с крайним левым неиспользованным символом ввода.
В качестве примера приведем следующую грамматику:
- S & rarr; E
- E & rarr; Т + Е
- E & rarr; T
- T & rarr;
int
Затем, учитывая строку int + int + int, синтаксический анализатор LL (2) (который использует два токена предвидения) проанализирует строку следующим образом:
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. Парсеры LR бывают разных типов (LR (0), SLR (1), LALR (1), LR (1), IELR (1), GLR (0) и т. Д.) И являются гораздо более мощными. Они также имеют тенденцию быть намного более сложными и почти всегда генерируются такими инструментами, как yacc или bison. Парсеры LL также выпускаются во многих вариантах (включая LL (*), который используется инструментом ANTLR), хотя на практике LL (1) используется наиболее широко.
Как бесстыдный плагин, если вы хотите больше узнать о LL и LR, я только что закончил преподавать курс компиляторов и у меня есть некоторые раздаточные материалы и слайды с лекциями по синтаксическому анализу на сайте курса. Я был бы рад уточнить любой из них, если вы считаете, что это будет полезно.