В чем разница между парсингом LL и LR?

На высоком уровне разница между синтаксическим анализом LL и синтаксическим анализом LR заключается в том, что синтаксические анализаторы LL начинают с начального символа и пытаются применить продукцию для достижения целевой строки, тогда как синтаксические анализаторы LR начинают с целевой строки и пытаются вернуться к началу. символ.

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

Во время синтаксического анализа LL синтаксический анализатор постоянно выбирает одно из двух действий:

1. Прогноз: исходя из крайнего левого нетерминала и некоторого количества предварительных токенов, выберите, какое производство следует применить, чтобы приблизиться к входной строке.
2. Соответствие: сопоставьте крайний левый предполагаемый символ терминала с крайним левым неиспользованным символом ввода.

В качестве примера, учитывая эту грамматику:

• S E
• E T + E
• E T
• Т 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 есть два действия:

1. Shift: добавьте следующий токен ввода в буфер для рассмотрения.
2. Уменьшить: уменьшите набор терминалов и нетерминалов в этом буфере до некоторого нетерминала, изменив производство.

Например, синтаксический анализатор LR (1) (с одним токеном просмотра вперед) может проанализировать ту же строку следующим образом:

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, я только что закончил преподавать курс компиляторов и получил раздаточные материалы и слайды лекций по синтаксическому анализу на веб-сайте курса. Я был бы рад подробнее остановиться на любом из них, если вы считаете, что это будет полезно.

Джош Хаберман в своей статье LL и LR Parsing Demystified утверждает, что анализ LL напрямую соответствует польской нотации, тогда как LR соответствует Обратная польская нотация. Разница между PN и RPN заключается в порядке обхода двоичного дерева уравнения:

+ 1 * 2 3  // Polish (prefix) expression; pre-order traversal.
1 2 3 * +  // Reverse Polish (postfix) expression; post-order traversal.

По словам Хабермана, это иллюстрирует основное различие между парсерами LL и LR:

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

Подробное объяснение, примеры и выводы можно найти в Хабермана. статья.

LL использует нисходящий подход, а LR - восходящий подход.

Если вы разбираете язык программирования:

• LL видит исходный код, который содержит функции, которые содержат выражение.
• LR видит выражение, которое принадлежит функциям, что приводит к полному исходному тексту.

Разбор LL затруднен по сравнению с LR. Вот грамматика, которая является кошмаром для генератора парсеров LL:

Goal           -> (FunctionDef | FunctionDecl)* <eof>                  

FunctionDef    -> TypeSpec FuncName '(' [Arg/','+] ')' '{' '}'       

FunctionDecl   -> TypeSpec FuncName '(' [Arg/','+] ')' ';'            

TypeSpec       -> int        
               -> char '*' '*'                
               -> long                 
               -> short                   

FuncName       -> IDENTIFIER                

Arg            -> TypeSpec ArgName         

ArgName        -> IDENTIFIER 

FunctionDef выглядит точно так же, как FunctionDecl, до символа ';' или встречается '{'.

Анализатор LL не может обрабатывать два правила одновременно, поэтому он должен выбрать либо FunctionDef, либо FunctionDecl. Но чтобы узнать, какой из них правильный, нужно искать впереди ';' или '{'. Во время анализа грамматики прогноз (k) кажется бесконечным. Во время синтаксического анализа он конечен, но может быть большим.

Парсеру LR не нужно смотреть вперед, потому что он может обрабатывать два правила одновременно. Таким образом, генераторы синтаксического анализатора LALR (1) могут легко справиться с этой грамматикой.

Учитывая входной код:

int main (int na, char** arg); 

int main (int na, char** arg) 
{

}

Парсер LR может анализировать

int main (int na, char** arg)

не заботясь о том, какое правило распознается, пока не встретит ';' или '{'.

Парсер LL зависает на int, потому что ему нужно знать, какое правило распознается. Следовательно, он должен искать впереди ';' или '{'.

Другой кошмар для парсеров LL - это левосторонняя рекурсия в грамматике. Левая рекурсия - нормальное явление в грамматиках, не проблема для генератора парсеров LR, но LL не справляется с этим.

Таким образом, вы должны писать свои грамматики неестественным образом с LL.