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.

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.

LL(0) gramatiky jsou nevhodné pro popis programovacích jazyků, protože zde není možná rekurze a pro každý neterminál existuje právě jedno pravidlo (důsledek faktu, že gramatika se nemůže rozhodnout podle následujícího vstupního symbolu), tudíž mohou generovat jen jazyk s jediným slovem.

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. Existují nedeterministické postupy, jak transformovat gramatiky LL(k) na gramatiky LL(1).

Jednoduchá LL(1) gramatika (simple LL(1)) je taková gramatika, kde každá pravá strana začíná terminálním symbolem. Pokud se levé strany shodují, potom každá pravá strana začíná jiným terminálním symbolem.

q-gramatika je rozšíření jednoduché gramatiky o ɛ pravidla (prázdné řetězce):

  • pravá strana každého pravidla je buď prázdná nebo začíná terminálním symbolem;
  • jestliže dvě pravidla mají stejnou levou stranu, pak pravá strana začíná různým terminálním symbolem, pokud některá z nich není prázdný řetězec ;
  • jestliže se vyskytne pravidlo , pak musí platit, že terminály vyskytující se na pravých stranách A se neshodují s terminály ve FOLLOW(A) -- množině následovníků (terminálů) neterminálního symbolu A, tedy všechny terminály, které se mohou vyskytovat za A.

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

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+$
S2-1--
F--3--

Proces analýzy

Na počátku zásobník vypadá následovně:

[ S, $ ]

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 )

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číku tohoto neterminálu a symbolu na vstupu, které přepisovací pravidlo má použít (expanze). 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í (srovnání). 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.

Literatura

  • VAVREČKOVÁ, Šárka. Programování překladačů. Opava: Slezská univerzita, 2008. 218 s. ISBN 978-80-7248-493-5. 

Související články