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:
Jako przykład, biorąc pod uwagę tę gramatykę:
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:
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 yacc
lub bison
. Parsery LL występują również w wielu odmianach (w tym LL (*), który jest używany przez ANTLR
narzę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:
Według Habermana ilustruje to główną różnicę między parserami LL i LR:
Szczegółowe wyjaśnienie, przykłady i wnioski można znaleźć w artykule Habermana .
źródło
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:
ź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:
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:
Parser LR może analizować plik
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
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)
źródło