Analiza LL

W informatyce , parsowanie LL jest top - down analizy skadniowej dla niektórych nie - kontekstowych gramatyk , zwany gramatyki LL . Analizuje si sowo wejciowe od strony lewej do prawej ( L EFT do prawej w jzyku angielskim) i konstruuje wyprowadzenie w lewo ( L eftmost derywacji w jzyku angielskim). Drzewo skadni jest budowane od korzenia, a nastpnie w dó do drzewa.

Analiza LL wykonuje pojedyncze przejcie na sowie wejciowym. Analiza LL nazywana jest analiz LL ( k ), gdy wykorzystuje okno k leksemów, aby zdecydowa, jak skonstruowa drzewo skadni sowa wejciowego.

Architektura analizatora LL

Poniej opisano analiz lewostronn z góry na dó w oparciu o tabel analityczn . Pojcie lewostronnej derywacji oznacza, e w procesie stosowania regu wybierany i przepisywany jest skrajny lewy nieterminal. Ten aspekt skutkuje zastosowaniem stosu w algorytmie analizatora.

Przypadek ogólny dla analizy LL (1)

Analizator skada si z:

Bufor wejciowy, zawierajcy cig znaków, które maj by analizowane, wyposaone w dwie operacje: odczyt biecej znak i przejcia do nastpnego znaku;

stos , na których mona umieci zaciski i s w zaciski gramatyki, które pozostaj do analizy;

stó analiza , która mówi, które rzdz uy (jeli istnieje) na podstawie symboli na wierzchu stosu i poniszego leksemu.

Parser stosuje regu znalezion w tabeli, dopasowujc wierzchoek stosu (wiersza) do biecego symbolu w buforze wejciowym (kolumnie).

Na pocztku analizy stos zawiera dwa symbole:

[ S, $ ]

Gdzie $ jest symbolem koca stosu i koca bufora wejciowego, a S jest aksjomatem gramatyki.
Parser spróbuje przepisa zawarto swojego stosu do tego, co widzi w buforze wejciowym. Jednak zachowuje na stosie tylko to, co naley przepisa.

Obliczanie tabeli analitycznej

Pozwoli jak algebraiczny gramatyki (gdzie V oznacza zbiór zmiennych nieterminalnych lub symboli, znaków alfabetu zacisk lub zestawu symboli kocowych P zestaw regu, s Aksjomat gramatyki która regua P). W celu obliczenia tabeli analizy , wprowadzamy funkcje , i . ${\ Displaystyle G = (V, A, S, P)}$ ${\ displaystyle Eps}$ ${\ displaystyle First}$ ${\ displaystyle Next}$

Eps

Dla kadej wypowiedzi , to prawda, jeli mona rozwiza, co jest równoznaczne ze stwierdzeniem, czy jest prawd (wyraenie przepisuje do pustego acucha ) i false w przeciwnym wypadku. Obliczenia te odpowiadaj reguom , jak w przypadku konwersji do postaci normalnej Chomsky'ego . ${\ Displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ Displaystyle Eps (\ alfa)}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ alpha ~ {\ xrightarrow {*}} ~ \ varepsilon}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ varepsilon}$

Pierwszy

Dla kadego wyraenia definiujemy jako zbiór terminali, które mog rozpoczyna sowo pochodzce od . Bardziej formalnie: ${\ Displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Premier (\ alpha)}$

 $Premier(\alpha )=\{a\in A^{*}\mid \exists \beta \in (V\cup A)^{*},\alpha {\xrightarrow {*}}a\beta \}$ .

Jeli tak . ${\ Displaystyle \ alpha = \ varepsilon}$ ${\ displaystyle Premier (\ alpha) = \ varnothing}$

nastpujcy

Dla kadego wyraenia definiujemy jako zbiór terminali, które prawdopodobnie nastpuj po sowie pochodzcym z . Bardziej formalnie: ${\ Displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Next (\ alpha)}$

 $Suivant(\alpha )=\{a\in Premier(\gamma )\mid \exists \beta ,\gamma \in (V\cup A)^{*},S{\xrightarrow {*}}\beta \alpha \gamma \}$ .

Tak wic . Dodajemy równie do wszystkich symbol $ , aby móc wskaza koniec kodu. ${\ Displaystyle \ alpha = \ varepsilon}$ ${\ displaystyle Next (\ alpha) = \ varnothing}$ ${\ Displaystyle \ {\ alpha \ in (V \ cup A) ^ {+} \ mid \ exist \ beta \ in (V \ cup A) ^ {*} S {\ xrightarrow {*}} \ beta \ alfa \ }}$

Wypenianie tabeli analitycznej

Tabela analizy to dwuwymiarowa macierz, której wiersze s indeksowane przez Non-terminale, a kolumny przez Terminals . Wypenienie odbywa si w ten sposób:

  Pour toute règle de la forme X 
     Pour tout aPremier()
        Ajouter X à la case d'indice (a,X)
     Si Eps() vaut vrai Alors
        Pour tout bSuivant() 
           Ajouter X à la case d'indice (b,X)
        Fin pour
     Fin pour
  Fin pour

Przykad bez reguy

Inicjalizacja

Aby wyjani, jak to dziaa, uyjemy nastpujcej gramatyki:

{\ Displaystyle S \ do F}

{\ Displaystyle S \ do (S + F)}

{\ displaystyle F \ do 1}

i przeanalizuj nastpny cig

(1 + 1)

Obliczamy EPS:

adna regua nie daje , wic adne Eps () nie jest zawsze faszywe. ${\ displaystyle \ varepsilon}$

Obliczamy Prime:

Premier(F) = { 1 }
Premier((S + F)) = { (}
Premier(1) = { 1 }

Obliczamy tabel analityczn:

On prend S  F, Premier(F) = { 1 } donc on ajoute ' $S\to F$ ' à la case (S , 1).
On prend S  (S + F), Premier((S + F)) = { (} donc on ajoute ' $S\to (S+F)$ ' à la case (S  , ().
On prend F  1, Premier(1)= { 1 } donc on ajoute ' $F\to 1$ ' à la case (F , 1).

	(	)	1	+	$
S	${\ Displaystyle S \ do (S + F)}$	-	${\ Displaystyle S \ do F}$	-	-
fa	-	-	${\ displaystyle F \ do 1}$	-	-

Przykad analizy LL ze sowem, drzewem pochodnym i stosem.

Analiza sów ${\ displaystyle (1 + 1)}$
Parser odczytuje pierwszy znak ( z bufora wejciowego i wierzchoka stosu (S). Patrzc na tabel, wie, e musi zastosowa regu ; musi teraz przepisa S w (S + F) na swoim stosie i zapisz regu zastosowan do wyniku. Stos staje si (szczyt stosu jest po lewej stronie, symbole s oddzielone przecinkami): ${\ Displaystyle S \ do (S + F)}$ [ (, S, +, F, ), $ ] Moemy zauway, e nieterminalne S zostanie usunite ze stosu, a zatem przepisane przed F. Jest to rzeczywicie ostatnia skrajna lewa strona w wyraeniu '(S + F)'. To ilustruje pojcie lewostronnego wyprowadzenia . W nastpnym kroku, poniewa zarówno wierzchoek stosu, jak i bufor przedstawiaj terminal '(', ten symbol jest zdejmowany i usuwany z bufora wejciowego. Stos staje si: [ S, +, F, ), $ ] Teraz bufor ma symbol 1, a szczyt stosu to S. Zgodnie z tabel parser stosuje regu , która umieszcza F na szczycie stosu. Analizator wywietla zastosowan regu na wyjciu. Stos staje si: ${\ Displaystyle S \ do F}$ [ F, +, F, ), $ ] Poniewa bufor zawsze ma symbol 1, regu do zastosowania zgodnie z tabel jest . Analizator wywietla zastosowan regu na wyjciu. Stos staje si: ${\ displaystyle F \ do 1}$ [ 1, +, F, ), $ ] Podczas nastpnych dwóch kroków (dla symboli 1 i +) symbol gowicy bufora odpowiada wierzchokowi stosu. Kady jest usuwany z bufora i rozkadany na stos. Stos staje si: [ F, ), $ ] W ostatnich 3 krokach F zostanie zastpione na stosie przez 1, dlatego na wyjciu zostanie zapisana regua . Nastpnie 1 i ) s usuwane z bufora wejciowego i stosu. Analiza koczy si zatem, poniewa na stosie i buforze wejciowym zostao tylko $. W tym przypadku parser akceptuje cig i wywietla list na wyjciu: ${\ displaystyle F \ do 1}$ [ , , , ] ${\ Displaystyle S \ rightarrow (S + F)}$ ${\ Displaystyle S \ do F}$ ${\ displaystyle F \ do 1}$ ${\ displaystyle F \ do 1}$ Co jest w rzeczywistoci wyprowadzeniem na lewo od acucha pocztkowego. Widzimy, e wyprowadzenie po lewej stronie acucha to: S (S + F) (F + F) (1 + F) (1 + 1)

Uwagi

Jak wida, parser wykonuje trzy rodzaje kroków w zalenoci od szczytu stosu (nieterminalowe, terminalowe, symbol '$'):

jeli wierzchoek stosu jest symbolem nieterminalowym, to sprawdza w tablicy parsowania na podstawie tego symbolu nieterminalowego i symbolu w buforze wejciowym, której reguy uy do zastpienia go na stosie. Numer reguy jest zapisywany na wyjciu. Jeli tabela analizy mówi, e nie ma reguy dopasowania, generuje bd i zatrzymuje si;
jeli wierzchoek stosu jest symbolem terminala, porównuje go z symbolem w buforze wejciowym. Jeli s równe, usuwa je, w przeciwnym razie zgasza bd i zatrzymuje si;
jeli wierzchokiem stosu jest $, a bufor wejciowy równie zawiera $, wówczas parser mówi, e przeanalizowa acuch poprawnie, w przeciwnym razie zgasza bd. W obu przypadkach zatrzymuje si.

Te kroki s powtarzane do zatrzymania analizatora; albo poprawnie przeanalizuje acuch i zapisze pochodn po lewej stronie cigu na wyjciu, albo wywietli bd.

Przykad z regu

Inicjalizacja

Aby wyjani, jak to dziaa, uyjemy nastpujcej uproszczonej gramatyki LISP / Scheme:

{\ Displaystyle S \ do (L)}

{\ Displaystyle S \ do a}

{\ Displaystyle L \ do SL}

{\ Displaystyle L \ do \ varepsilon}

i przeanalizuj nastpny cig

{\ Displaystyle (a ())}

Obliczamy EPS:

Tylko L mona anulowa, wic jest prawdziwe i jest faszywe w pozostaych przypadkach. ${\ Displaystyle EPS (\ varepsilon) = EPS (L) =}$

Obliczamy Prime:

Premier(a) = { a }
Premier((L)) = { (}
Premier(SL) = { (, a }
Premier() =

Obliczamy nastpujce:

Suivant(S) = { $, a, (, ) }
Suivant(L) = { ) }

Obliczamy tabel analityczn:

On prend S  (L), Premier((L)) = { (} donc on ajoute ' $S\to (L)$ ' à la case (S , ().
On prend S  a, Premier(a) = { a } donc on ajoute ' $S\to a$ ' à la case (S , a).
On prend L  SL, Premier(SL)={ (, a } donc on ajoute ' $L\to SL$ ' aux cases (L , () et (L, a). 
On prend L  , Premier() =  et Eps() = vrai et Suivant(L)={ ) }, donc on ajoute ' $L\to \varepsilon$ ' à la case (L ,)).

Przykad konstrukcji drzewa derywacji podczas analizy LL

	(	)	w	$
S	${\ Displaystyle S \ do (L)}$	-	${\ Displaystyle S \ do a}$	-
L	${\ Displaystyle L \ do SL}$	${\ Displaystyle L \ do \ varepsilon}$	${\ Displaystyle L \ do SL}$	-

Przypominamy, e analizator obsuguje stos i bufor wejciowy, który moe dostarczy symbole cigu znaków. Odczytanie bufora nie oznacza przejcia do nastpnego symbolu. Odczytanie bufora oznacza tylko dostp do aktualnego symbolu. Przechodzimy do nastpnego symbolu w buforze tylko wtedy, gdy symbol spitrzony jest terminalem równym aktualnemu symbolowi bufora. Ta równo przekada si na fakt, e na obecnym etapie odczytany napis jest zgodny z gramatyk. Postp w buforze nie jest odwracalny (analizator nigdy nie wraca w acuchu). Moe to by reprezentowane przez gowic odczytujc wyposaon w pami. Gdy ta gowica odczytu przesuwa si w buforze, pami przechowuje odczytany znak. Pami t mona przeglda dowoln liczb razy. Ta konsultacja odpowiada operacji odczytu bufora. Gowica odtwarzania moe przej do nastpujcego symbolu: co jest okrelane jako postp w buforze.

Analiza sów ${\ Displaystyle (a ())}$
[ S, $ ] Parser odczytuje pierwszy znak ( z bufora wejciowego i zdejmuje szczyt stosu (S). Patrzc na tabel, wie, e musi zastosowa regu 1; teraz musi przepisa S w '(L)' na swoim stosie, wic stos staje si: [ (, L,), $ ] Na szczycie stosu znajduje si symbol terminala '('. Poniewa odpowiada on aktualnemu symbolowi bufora (a wic acuch poda w tej chwili za gramatyk), ten symbol jest zdejmowany i przechodzi do nastpnego symbolu w bufor, który jest 'a' Stos sta si: [ L,), $ ] Pojawia si L i czyta liter a, musi zastosowa regu 3; przepisuje L na SL: [S, L,), $ ] Pojawia si S i czyta liter a, musi zastosowa zasad 2; przepisuje S na a, a nastpnie w dodatkowym kroku usuwa a ze wzgldu na zgodno z wierzchokiem stosu. Nastpnie biecym symbolem bufora jest drugi '(', a stos sta si: [ L,), $ ] Teraz wyskakuje L i czyta liter (, przepisuje L na SL (regua 3), a nastpnie S na (L) (regua 1), dziki czemu mona usun '('. Biecy symbol jest pierwszym ')', a stos sta si: [ L,), L,), $ ] Wbija L i odczytuje liter ), wic moe usun L za pomoc reguy 4, a nastpnie moe usun ). Biecy symbol to drugi znak ), a stos sta si: [ L,), $ ] W taki sam sposób jak wczeniej, regua 4 pozwala mu usun L, a nastpnie moe usun ). Stos sta si pusty: [ $ ] Algorytm zatem wnioskuje pozytywnie i stosujc sekwencj lewej pochodnej: $S\rightarrow (L)\rightarrow (SL)\rightarrow (aL)\rightarrow (aSL)\rightarrow (a(L)L)\rightarrow (a()L)\rightarrow (a())$ .

Generatory parserów LL ( k )

ANTLR : (en) Oficjalna strona
Coco / R : (en) Oficjalna strona internetowa
JavaCC : (en) Oficjalna strona
PCCTS : stara nazwa ANTLR, (en) zarchiwizowana strona
Ocaml Genlex Module : (en) Oficjalna strona

Uwagi i odniesienia

Romain Legendre i François Schwarzentruber, Kompilacja: analiza leksykalna i syntaktyczna - od tekstu do jego struktury w informatyce , Pary, elipsy ,31 marca 2015 r, 312 pkt. ( ISBN 978-2-340-00366-8 ).

Powizane artykuy

[1] Romain Legendre i François Schwarzentruber, Kompilacja: analiza leksykalna i syntaktyczna - od tekstu do jego struktury w informatyce , Pary, elipsy ,31 marca 2015 r, 312 pkt. ( ISBN 978-2-340-00366-8 ).

Analiza LL

streszczenie

Architektura analizatora LL

Przypadek ogólny dla analizy LL (1)

Obliczanie tabeli analitycznej

Eps

Pierwszy

nastpujcy

Wypenianie tabeli analitycznej

Przykad bez reguy

Inicjalizacja

Uwagi

Przykad z regu

Inicjalizacja

Generatory parserów LL ( k )

Uwagi i odniesienia

Powizane artykuy

Opiniones de nuestros usuarios

Anita Wawrzyniak

Ala Borkowski

Zbigniew Orzechowski

Elzbieta Piekarski

Enciclo

Wikious

Sapientia

Scientia

Boobota