LL syntaktický analyzátor
Z Wikipedie, otevřené encyklopedie
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.
Obsah |
[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:
- S → F
- S → ( S + F )
- 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 $:
- 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í.
- 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í.
- 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.
