Analýza LL

V počítačové vědě je analýza LL syntaktickou analýzou shora dolů pro některé bezkontextové gramatiky , která se nazývá gramatiky LL . Analyzuje vstupní slovo zleva doprava ( L EFT doprava v angličtině) a buduje původ v levém ( L eftmost derivací v angličtině). Strom syntaxe je sestaven z kořene a poté dolů do stromu.

Analýza LL provádí jeden vstup vstupního slova. Analýza LL se nazývá analýza LL ( k ), když používá okno k lexémům k rozhodnutí, jak sestavit syntaxový strom vstupního slova.

Architektura analyzátoru LL

Následující text popisuje analýzu derivace zleva shora dolů na základě analytické tabulky . Pojem derivace vlevo znamená, že během procesu aplikace pravidla je vybrán a přepsán neterminál nejvíce vlevo. Tento aspekt má za následek použití zásobníku v algoritmu analyzátoru.

Obecný případ pro analýzu LL (1)

Analyzátor se skládá z:

vstupní vyrovnávací paměti, obsahující řetězec znaků, které mají být analyzovány a vybavené dvěma operacemi: čtení aktuální znak a pohybuje se na další znak;
zásobník , na kterém dát svorky a non-terminálů gramatiky, jež mají být analyzovány;
analýza tabulka , která říká, které pravidlo použít (pokud existuje) na základě symbolů na vrcholu zásobníku a následujícím lexeme.

Analyzátor použije pravidlo nalezené v tabulce porovnáním horní části zásobníku (řádku) s aktuálním symbolem ve vstupní vyrovnávací paměti (sloupci).

Když začne analýza, zásobník obsahuje dva symboly:

[ S, $ ]

Kde '$' je symbol pro spodní část zásobníku a konec vstupní vyrovnávací paměti a 'S' je axiom gramatiky.
Analyzátor se pokusí přepsat obsah svého zásobníku na to, co vidí ve vstupní vyrovnávací paměti. Udržuje však na zásobníku pouze to, co je třeba přepsat.

Výpočet analytické tabulky

Nechť je algebraický gramatiku (kde V znamená atom sadu neterminálních proměnných nebo symboly, A terminál abeceda nebo množina terminálních symbolů, P soubor pravidel, S axiom gramatiky, který je pravidlo P). Aby bylo možné vypočítat na stůl analýzu , jsme zavedli funkce , a . ${\ displaystyle G = (V, A, S, P)}$ ${\ displaystyle Eps}$ ${\ displaystyle Premier}$ ${\ displaystyle Další}$

Eps

U jakéhokoliv výrazu , je pravda, pokud je zrušit, což je ekvivalentní k říká platí, pokud (výraz přepisuje na prázdný řetězec ) a je falešný jinak. Tento výpočet odpovídá výpočtu pravidel ε , jako v případě převodu do Chomského normální formy . ${\ displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Eps (\ alpha)}$ $\ alfa$ ${\ displaystyle \ alpha ~ {\ xrightarrow {*}} ~ \ varepsilon}$ $\ alfa$ $\ varepsilon$

První

Pro jakýkoli výraz definujeme jako množinu terminálů, které pravděpodobně začnou slovo odvozené od α. Více formálně: ${\ 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 \}

Pokud ano . ${\ displaystyle \ alpha = \ varepsilon}$ ${\ displaystyle Premier (\ alpha) = \ varnothing}$

Následující

Pro jakýkoli výraz definujeme jako sadu terminálů, které budou pravděpodobně následovat slovo odvozené od α. Více formálně: ${\ displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Další (\ alpha)}$

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

Ano , tedy . Ke všem přidáme také symbol „$“ , abychom mohli označit konec kódu. ${\ displaystyle \ alpha = \ varepsilon}$ ${\ displaystyle Další (\ alpha) = \ varnothing}$ ${\ displaystyle \ {\ alpha \ in (V \ cup A) ^ {+} \ mid \ existuje \ beta \ in (V \ cup A) ^ {*} S {\ xrightarrow {*}} \ beta \ alpha \ }}$

Vyplnění analytické tabulky

Analytická tabulka je dvourozměrná matice, jejíž řádky jsou indexovány Non-terminály a sloupce Terminály . Plnění se provádí takto:

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

Příklad bez pravidla ε

Inicializace

Abychom vysvětlili, jak to funguje, použijeme následující gramatiku:

{\ displaystyle S \ až F}

{\ displaystyle S \ to (S + F)}

{\ displaystyle F \ až 1}

a analyzovat další řetězec

(1 + 1)

Počítáme Eps:

Žádné pravidlo nedává , proto žádná Eps (α) není vždy falešná. $\ varepsilon$

Počítáme Prime:

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

Vypočítáme analytickou tabulku:

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 \ to (S + F)}$	-	${\ displaystyle S \ až F}$	-	-
F	-	-	${\ displaystyle F \ až 1}$	-	-

Analýza slov ${\ displaystyle (1 + 1)}$
Analyzátor načte první '(' ze vstupní vyrovnávací paměti a horní části zásobníku ('S'). Při pohledu na tabulku ví, že musí použít pravidlo ' '; nyní musí přepsat 'S' en '(S + F)' na jeho zásobníku a zapsat pravidlo aplikované na výstup. Zásobník se stane (horní část zásobníku je vlevo, symboly jsou odděleny čárkami): ${\ displaystyle S \ to (S + F)}$ [ (, S, +, F, ), $ ] Můžeme si všimnout, že neterminální S bude rozbaleno, a proto bude přepsáno před F. Je to skutečně nejvíce neterminální terminál v termínu '(S + F)'. To ilustruje pojem derivace vlevo . V dalším kroku, protože horní část zásobníku a vyrovnávací paměť představují terminál '(', je tento symbol vysunut a odstraněn ze vstupní vyrovnávací paměti. Zásobník se stává: [ S, +, F, ), $ ] Nyní má vyrovnávací paměť symbol '1' a horní část zásobníku je 'S'. Podle tabulky analyzátor použije pravidlo ' ', které umístí 'F' do horní části zásobníku. Analyzátor zobrazí použité pravidlo na výstupu. Zásobník se stává: ${\ displaystyle S \ až F}$ [ F, +, F, ), $ ] Jelikož vyrovnávací paměť má vždy symbol „1“, použije se pravidlo podle tabulky „ “. Analyzátor zobrazí použité pravidlo na výstupu. Zásobník se stává: ${\ displaystyle F \ až 1}$ [ 1, +, F, ), $ ] Během následujících dvou kroků (pro symboly „1“ a „+“) odpovídá symbol hlavy vyrovnávací paměti horní části zásobníku. Každý je odstraněn z vyrovnávací paměti a unstacked. Zásobník se stává: [ F, ), $ ] U posledních 3 kroků bude 'F' na zásobníku nahrazeno '1', pravidlo ' ' bude proto zapsáno na výstup. Poté se ze vstupní vyrovnávací paměti a zásobníku odstraní „1“ a „)“. Analýza proto končí, protože v zásobníku a vstupní vyrovnávací paměti zbývá pouze '$'. V tomto případě analyzátor přijme řetězec a zobrazí seznam na výstupu: ${\ displaystyle F \ až 1}$ [ , , , ] ${\ displaystyle S \ rightarrow (S + F)}$ ${\ displaystyle S \ až F}$ ${\ displaystyle F \ až 1}$ ${\ displaystyle F \ až 1}$ Což je ve skutečnosti větev nalevo od startovacího řetězce. Vidíme, že derivace nalevo od řetězce je: S → (S + F) → (F + F) → (1 + F) → (1 + 1)

Poznámky

Jak je vidět, analyzátor provádí tři typy kroků v závislosti na horní části zásobníku (neterminál, terminál, symbol '$'):

pokud je horní část zásobníku neterminální symbol, vypadá to v tabulce analýzy na základě tohoto neterminálního symbolu a symbolu ve vstupní vyrovnávací paměti, které pravidlo se má použít k jeho nahrazení v zásobníku. Číslo pravidla je zapsáno na výstup. Pokud tabulka analýzy říká, že neexistuje žádné odpovídající pravidlo, vydá chybu a zastaví se;
pokud je horní část zásobníku symbol terminálu, porovná jej se symbolem ve vstupní vyrovnávací paměti. Pokud jsou si rovni, odstraní je, jinak vydá chybu a zastaví se;
pokud je horní část zásobníku '$' a vstupní vyrovnávací paměť obsahuje také '$', pak analyzátor říká, že správně analyzoval řetězec, jinak způsobí chybu. V obou případech se zastaví.

Tyto kroky se opakují, dokud se analyzátor nezastaví; bude buď správně analyzovat řetězec a zapíše derivaci nalevo od řetězce na výstup, nebo vydá chybu.

Příklad s ε-pravidlem

Inicializace

Abychom vysvětlili, jak to funguje, použijeme následující zjednodušenou gramatiku LISP / Scheme:

{\ displaystyle S \ do (L)}

{\ displaystyle S \ to a}

{\ displaystyle L \ to SL}

{\ displaystyle L \ to \ varepsilon}

a analyzovat další řetězec

{\ displaystyle (a ())}

Počítáme Eps:

Pouze L lze zrušit, takže v ostatních případech je pravda a je nepravdivá. ${\ displaystyle EPS (\ varepsilon) = EPS (L) =}$

Počítáme Prime:

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

Počítáme následující:

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

Vypočítáme analytickou tabulku:

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 ,)).

	(	)	na	$
S	${\ displaystyle S \ do (L)}$	-	${\ displaystyle S \ to a}$	-
L	${\ displaystyle L \ to SL}$	${\ displaystyle L \ to \ varepsilon}$	${\ displaystyle L \ to SL}$	-

Připomínáme, že analyzátor zpracovává zásobník a vstupní vyrovnávací paměť, které mohou dodávat symboly řetězce znaků. Čtení vyrovnávací paměti neznamená postup k dalšímu symbolu. Čtení vyrovnávací paměti znamená pouze přístup k aktuálnímu symbolu. K dalšímu symbolu ve vyrovnávací paměti postoupíme, pouze když je neskládaný symbol terminál rovnající se aktuálnímu symbolu vyrovnávací paměti. Tato rovnost překládá skutečnost, že v aktuálním kroku je přečtený řetězec v souladu s gramatikou. Záloha ve vyrovnávací paměti není reverzibilní (analyzátor se nikdy nevrátí zpět do řetězce). To může být reprezentováno čtecí hlavou vybavenou pamětí. Jak tato čtecí hlava postupuje ve vyrovnávací paměti, paměť ukládá načtený znak. Tuto paměť lze zobrazit tolikrát, kolikrát chcete. Tato konzultace odpovídá operaci čtení vyrovnávací paměti. Přehrávací hlava může postoupit k následujícímu symbolu: co se v bufferu označuje jako postup.

Analýza slov ${\ displaystyle (a ())}$
[ S, $ ] Analyzátor načte první '(' ze vstupní vyrovnávací paměti a vysune horní část zásobníku ('S'). Při pohledu na tabulku ví, že musí použít pravidlo 1; nyní musí přepsat 'S' v '(L)' na svém zásobníku, takže zásobník se stane: [ (, L,), $ ] V horní části zásobníku je symbol terminálu '('. Jelikož odpovídá aktuálnímu symbolu vyrovnávací paměti (řetězec následuje, pro tuto chvíli gramatiku), je tento symbol vysunut a postupuje k dalšímu symbolu v vyrovnávací paměť, která je 'a' Zásobník se stal: [ L,), $ ] Vyskočí „L“ a přečte písmeno „a“, musí platit pravidlo 3; přepisuje z „L“ na „SL“: [S, L,), $ ] Vyskočí „S“ a přečte písmeno „a“, musí platit pravidlo 2; přepíše znak „S“ na znak „a“ a v dalším kroku odstraní znak „a“ z důvodu korespondence s horní částí zásobníku. Poté je aktuální symbol vyrovnávací paměti druhý '(' a zásobník se stal: [ L,), $ ] Nyní zobrazí písmeno „L“ a přečte písmeno „(“, přepíše „L“ na „SL“ (pravidlo 3) a poté „S“ na „(L)“ (pravidlo 1), takže může odstranit '('. Aktuální symbol je první ')' a zásobník se stal: [ L,), L,), $ ] Vyskočí na „L“ a přečte písmeno „)“, takže může odstranit „L“ pomocí pravidla 4, poté může odstranit „)“. Aktuální symbol je druhý ')' a zásobník se stal: [ L,), $ ] Pravidlo 4 mu stejně jako dříve umožňuje odstranit „L“ a poté může odstranit „)“. Zásobník je prázdný: [ $ ] Algoritmus proto končí pozitivně a použitím levé derivační sekvence: $S\rightarrow (L)\rightarrow (SL)\rightarrow (aL)\rightarrow (aSL)\rightarrow (a(L)L)\rightarrow (a()L)\rightarrow (a())$ .

Generátory syntaktického analyzátoru LL ( k )

ANTLR : (en) Oficiální stránky
Coco / R : (en) Oficiální webové stránky
JavaCC : (en) Oficiální stránky
PCCTS : starý název ANTLR, (en) archivovaný web
Modul Ocaml Genlex : (en) Oficiální stránky

Poznámky a odkazy

Romain Legendre a François Schwarzentruber, Kompilace: Lexikální a syntaktická analýza - od textu po jeho strukturu v informatice , Paříž, Elipsy ,31. března 2015, 312 s. ( ISBN 978-2-340-00366-8 ).

Související články