Jaka jest różnica między analizą LL i LR?

225

Czy ktoś może podać prosty przykład analizy LL w porównaniu z analizą LR?

Kreatywność 2345
źródło

Odpowiedzi:

483

Na wysokim poziomie różnica między analizowaniem LL i analizowaniem LR polega na tym, że parsery LL zaczynają się od symbolu początkowego i próbują zastosować produkcje, aby dotrzeć do ciągu docelowego, podczas gdy parsery LR zaczynają się od ciągu docelowego i próbują wrócić do początku symbol.

Analiza składniowa LL jest pochodną od lewej do prawej, skrajnie lewą. Oznacza to, że bierzemy pod uwagę symbole wejściowe od lewej do prawej i próbujemy skonstruować lewą pochodną. Odbywa się to, rozpoczynając od symbolu początkowego i kilkakrotnie rozszerzając lewy nieterminalny, aż dojdziemy do ciągu docelowego. Analiza LR jest pochodną od lewej do prawej, skrajnie prawą, co oznacza, że ​​skanujemy od lewej do prawej i próbujemy skonstruować pochodną najbardziej po prawej stronie. Analizator składni w sposób ciągły wybiera podciąg danych wejściowych i próbuje odwrócić je z powrotem do nieterminala.

Podczas parsowania LL analizator składniowy nieustannie wybiera między dwiema akcjami:

  1. Przewidywanie : w oparciu o lewostronne nieterminalne i pewną liczbę tokenów wyprzedzających, wybierz, która produkcja powinna zostać zastosowana, aby zbliżyć się do ciągu wejściowego.
  2. Dopasuj : Dopasuj lewy zgadnięty symbol terminala z lewym skrajnym nieużywanym symbolem wejścia.

Jako przykład, biorąc pod uwagę tę gramatykę:

  • S → E
  • E → T + E
  • E → T
  • T → int

Następnie biorąc pod uwagę ciąg int + int + int, parser LL (2) (który wykorzystuje dwa tokeny lookahead) parsowałby ciąg w następujący sposób:

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

Zauważ, że na każdym kroku patrzymy na lewy symbol w naszej produkcji. Jeśli jest to terminal, dopasowujemy go, a jeśli jest to nieterminalny, przewidujemy, co to będzie, wybierając jedną z reguł.

W parserze LR istnieją dwie akcje:

  1. Shift : Dodaj następny token wejścia do bufora do rozważenia.
  2. Zmniejsz : Zredukuj zbiór terminali i nieterminali w tym buforze z powrotem do niektórych nieterminali, cofając produkcję.

Na przykład analizator składni LR (1) (z jednym tokenem lookahead) może przeanalizować ten sam ciąg w następujący sposób:

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

Dwa wspomniane algorytmy analizujące (LL i LR) mają różne właściwości. Parsery LL są zwykle łatwiejsze do ręcznego pisania, ale są mniej wydajne niż parsery LR i akceptują znacznie mniejszy zestaw gramatyk niż parsery LR. Parsery LR występują w wielu odmianach (LR (0), SLR (1), LALR (1), LR (1), IELR (1), GLR (0) itd.) I są znacznie bardziej wydajne. Mają też tendencję do bycia znacznie bardziej złożonymi i prawie zawsze są generowane przez narzędzia takie jak yacclub bison. Parsery LL występują również w wielu odmianach (w tym LL (*), który jest używany przez ANTLRnarzędzie), chociaż w praktyce LL (1) jest najczęściej używany.

Jako bezwstydną wtyczkę, jeśli chcesz dowiedzieć się więcej o analizie LL i LR, właśnie skończyłem uczyć kurs kompilatora i mam kilka materiałów informacyjnych i slajdów z wykładów na temat parsowania na stronie kursu. Z przyjemnością omówię którekolwiek z nich, jeśli uważasz, że byłoby to przydatne.

templatetypedef
źródło
40
Slajdy z wykładami są fenomenalne, z pewnością najzabawniejsze wyjaśnienie, jakie widziałem :) To jest coś, co wzbudza zainteresowanie.
kizzx2,
1
Muszę również komentować slajdy! Przechodzę teraz przez wszystkie z nich. Bardzo pomaga! Dzięki!
kornfridge
Bardzo lubię też slajdy. Nie sądzę, żebyś mógł opublikować wersję projektu inną niż Windows plików projektu (i plik scanner.l dla pp2)? :)
Erik P.,
1
Jedyną rzeczą, którą mogę wnieść do doskonałej podsumowującej odpowiedzi Matta, jest to, że każda gramatyka, która może zostać przeanalizowana przez analizator składni LL (k) (tj. Patrząc na terminale „k”, aby zdecydować o następnej akcji), może zostać przeanalizowana przez LR ( 1) parser. To daje wskazówkę dotyczącą niesamowitej mocy analizy LR w porównaniu z analizą LL. Źródło: kurs kompilatora na UCSC prowadzony przez dr F. DeRemera, twórcę analizatorów LALR ().
JoGusto
1
Doskonały zasób! Dziękujemy za udostępnienie slajdów, materiałów informacyjnych, projektów.
P. Hinker,
58

Josh Haberman w swoim artykule LL i LR Parsing Demystified twierdzi, że parsowanie LL bezpośrednio koresponduje z polską notacją , podczas gdy LR odpowiada odwrotnej notacji polskiej . Różnica między PN i RPN polega na kolejności przechodzenia przez drzewo binarne równania:

binarne drzewo równania

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

Według Habermana ilustruje to główną różnicę między parserami LL i LR:

Podstawowa różnica między działaniem parserów LL i LR polega na tym, że parser LL wysyła przechodzenie drzewa analizy w przedsprzedaży, a parser LR wysyła przechodzenie po zamówieniu.

Szczegółowe wyjaśnienie, przykłady i wnioski można znaleźć w artykule Habermana .

msiemens
źródło
9

LL wykorzystuje podejście z góry na dół, podczas gdy LR stosuje podejście z dołu do góry.

Jeśli przeanalizujesz język programowania:

  • LL widzi kod źródłowy, który zawiera funkcje, które zawierają wyrażenie.
  • LR widzi wyrażenie, które należy do funkcji, co daje pełne źródło.
betontalpfa
źródło
6

Analiza LL jest upośledzona w porównaniu z LR. Oto gramatyka, która jest koszmarem dla generatora analizatora składni 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 wygląda dokładnie jak FunctionDecl, dopóki „;” lub napotkano „{”.

Parser LL nie może obsługiwać dwóch reguł jednocześnie, dlatego musi wybrać FunctionDef lub FunctionDecl. Ale żeby wiedzieć, co jest poprawne, trzeba szukać „;” lub „{”. W czasie analizy gramatycznej lookahead (k) wydaje się być nieskończony. W czasie analizy jest skończony, ale może być duży.

Parser LR nie musi patrzeć w przód, ponieważ może obsługiwać dwie reguły jednocześnie. Tak więc generatory parsera LALR (1) z łatwością poradzą sobie z tą gramatyką.

Biorąc pod uwagę kod wejściowy:

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

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

}

Parser LR może analizować plik

int main (int na, char** arg)

bez względu na to, jaką zasadę uznaje się, dopóki nie napotka znaku „;” lub „{”.

Parser LL rozłącza się przy „int”, ponieważ musi wiedzieć, która reguła jest rozpoznawana. Dlatego musi szukać „;” lub „{”.

Drugim koszmarem dla parserów LL jest pozostawienie rekurencji w gramatyce. Rekurencja w lewo jest normalną rzeczą w gramatyce, nie ma problemu dla generatora parsera LR, ale LL nie może sobie z tym poradzić.

Więc musisz pisać swoje gramatyki w nienaturalny sposób z LL.


źródło
0

Wyprowadzenie z lewej strony Przykład: Gramatyka G, która jest pozbawiona kontekstu, ma produkcje

z → xXY (reguła: 1) X → Ybx (reguła: 2) Y → bY (reguła: 3) Y → c (reguła: 4)

Oblicz ciąg w = 'xcbxbc' z najbardziej lewą pochodną.

z ⇒ xXY (reguła: 1) ⇒ xYbxY (reguła: 2) ⇒ xcbxY (reguła: 4) ⇒ xcbxbY (reguła: 3) ⇒ xcbxbc (reguła: 4)


Prawa Najbardziej pochodna Przykład: K → aKK (Reguła: 1) A → b (Reguła: 2)

Oblicz ciąg w = „aababbb” z najbardziej odpowiednią pochodną.

K ⇒ aKK (Reguła: 1) ⇒ aKb (Reguła: 2) ⇒ aaKKb (Reguła: 1) ⇒ aaKaKKb (Reguła: 1) ⇒ aaKaKbb (Reguła: 2) ⇒ aaKabbb (Reguła: 2) ⇒ aababbb (Reguła: 2)

Anupama Thathsarani
źródło