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

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

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.

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:

+ 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 .

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.

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.

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)