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

Кто-нибудь может дать мне простой пример анализа LL по сравнению с LR?

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

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

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

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

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

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

Джош Хаберман в своей статье LL and 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.

Самый левый пример деривации: грамматика G, не зависящая от контекста, имеет произведения

z → xXY (Правило: 1) X → Ybx (Правило: 2) Y → bY (Правило: 3) Y → c (Правило: 4)

Вычислить строку w = 'xcbxbc' с самым левым выводом.

z ⇒ xXY (Правило: 1) ⇒ xYbxY (Правило: 2) ⇒ xcbxY (Правило: 4) ⇒ xcbxbY (Правило: 3) ⇒ xcbxbc (Правило: 4)

Самый правый пример вывода: K → aKK (Правило: 1) A → b (Правило: 2)

Вычислите строку w = 'aababbb' с наиболее правым выводом.

K ⇒ aKK (Правило: 1) ⇒ aKb (Правило: 2) ⇒ aaKKb (Правило: 1) ⇒ aaKaKKb (Правило: 1) ⇒ aaKaKbb (Правило: 2) ⇒ aaKabbb (Правило: 2) ⇒ aababbb (Правило: 2)