LL syntaktický analyzátor

LL syntaktický analyzátor (parser, překladový automat) je syntaktický analyzátor shora-dolů pro bezkontextové gramatiky. Analyzuje vstup zleva (Left) doprava a konstruuje nejlevější derivaci (Leftmost) věty. Gramatiky, které jsou takto analyzovatelné, se nazývají LL gramatiky.

[editovat] LL(k) gramatiky

LL(k) gramatika generuje jazyk typu LL(k). LL parser se nazývá LL(k), jestliže pro deterministickou analýzu věty je potřeba znát maximálně k následujících symbolů a není nutné použít backtracking.

Nejpoužívanější gramatikou je LL(1) gramatika, protože i přes jistá omezení této gramatiky stačí k deterministické analýze znát maximálně jeden následující symbol, což významně zjednodušuje konstrukci parseru. Naopak LL(0) gramatiky jsou nevhodné, protože mohou generovat jen jazyk s konečným počtem slov a není zde možná rekurze. Existují nedeterministické postupy, jak transformovat gramatiky LL(k) na gramatiky LL(1).

[editovat] Překladový automat (parser)

Překladový automat je upravený zásobníkový automat. Má navíc výstupní pásku, na kterou se zapisuje levý rozklad a má k dispozici deterministickou možnost rozhodování, když k symbolu na vrcholu zásobníku existuje více možných přepisovacích pravidel gramatiky.

Části překladového automatu:

• vstupní buffer – zde je uložen vstupní řetězec
• zásobník – slouží k uložení terminálů a neterminálů z derivované gramatiky
• parsovací tabulka – určuje gramatické pravidlo, které bude použito, máme-li k dispozici daný symbol na vstupu a daný symbol na vrcholu zásobníku
• výstupní páska – zachycuje levý rozklad, tj. seznam použitých přepisovacích pravidel gramatiky

Parser aplikuje pravidlo z tabulky na průsečíku nejlevějšího symbolu na zásobníku a aktuálního vstupního symbolu. Když parser startuje, zásobník obsahuje 2 znaky:

[S, $]

kde S je startovní symbol gramatiky a $ je speciální znak indikující dno zásobníku (a také konec vstupu).

[editovat] Příklad

Mějme následující gramatiku:

1. S → F
2. S → ( S + F )
3. F → 1

a chceme analyzovat vstup:

( 1 + 1 )

Parsovací tabulka pro takovouto gramatiku bude vypadat následovně:

	(	)	1	+	$
S	2	-	1	-	-
F	-	-	3	-	-

[editovat] Proces analýzy

Analyzátor přečte první znak ze vstupního bufferu, v našem případě '(', a 'S' ze zásobníku. Z tabulky je jasné, že je potřeba použít pravidlo (2). Na zásobníku se tedy 'S' přepíše na '( S + F )' a na výstup se zapíše číslo pravidla. Zásobník tedy vypadá následovně:

[ (, S, +, F, ), $ ]

V dalším kroku odstraníme ze zásobníku terminál '(':

[ S, +, F, ), $ ]

Nyní máme na vstupu '1' takže musíme použít pravidlo (1) a pravidlo (3) z gramatiky a vypsat jejich čísla na výstup. zásobník pak bude postupně vypadat následovně:

[ F, +, F, ), $ ]
[ 1, +, F, ), $ ]

V dalších dvou krocích opět odstraníme ze zásobníku terminální symboly '1' a '+', protože v tabulce neexistují pravidla na jejich přepsání. V zásobníku je tedy následující:

[ F, ), $ ]

V dalším kroku se použije pravidlo (3) a na výstup se zapíše číslo pravidla. Zásobník pak vypadá následovně:

[ 1, ), $ ]

Opět odebereme ze zásobníku a ze vstupního bufferu terminální symboly '1' a ')'. Analyzátor tedy končí se symbolem '$' na zásobníku i ve vstupním bufferu.

Tím byl vstup akceptován a na výstupu jsou zapsána čísla [ 2, 1, 3, 3 ], která identifikují potřebná přepisovací pravidla, podle kterých je sestavena levá derivace vstupního řetězce. Přepis tedy vypadá následovně:

S → ( S + F ) → ( F + F ) → ( 1 + F ) → ( 1 + 1 )

[editovat] Operace prováděné překladovým automatem

Jak je vidět z příkladu, parser provádí tři typy operací v závislosti na tom, zda na vrcholu je terminál, neterminál nebo speciální symbol $:

1. je-li na vrcholu zásobníku neterminál, potom se podívá do parsovací tabulky, do průsečíko tohoto neterminálu a symbolu na vstupu, které přepisovací pravidlo má použít. Pokud v tabulce není nic uvedeno, pak došlo k chybě a proces se zastaví.
2. je-li na vrcholu zásobníku terminál, porovná ho se symbolem na vstupu. Jsou-li tyto dva symboly stejné, pak je oba odstraní. Pokud se liší, došlo k chybě a proces se zastaví.
3. je-li na vrcholu zásobníku $ a na vstupu je také $ potom byla analýza úspěšně dokončena, jinak nastala chyba. V obou případech se analýza zastaví.

Tyto kroky se opakují dokud parser nezastaví. Výstupem je derivační strom nebo je ohlášena chyba.

[editovat] Související články

• Syntaktická analýza
• Formální gramatika
• Zásobníkový automat