Syntaktická analýza zdola nahoru

Syntaktická analýza zdola nahoru je v informatice postup syntaktické analýzy, při kterém se derivační strom sestavuje odspodu – tj. nejdříve se identifikují jednotlivé symboly, z nichž je složen vstupní text, a z nich se následně vytvářejí složitější struktury.

V souladu s tím, jak se kreslí stromy v lingvistice a informatice, je kořen derivačního stromu nahoře, a je tvořen symbolem, který symbolizuje celou analyzovanou větu; jednotlivá slova, z nichž je věta složena, a ze kterých se postupně vytvářejí složitější struktury, jsou na konci větví (odtud název terminální symboly) zcela dole.

Opačným postupem je syntaktická analýza shora dolů, při které se komplexní jednotky rozdělují na jednodušší části, až se dospěje k symbolům, z nichž je složen analyzovaný řetězec. Oba postupy lze použít jak pro věty přirozeného jazyka, tak pro texty programů v nějakém programovacím jazyce.

V lingvistice lze syntaktickou analýzu zdola nahoru použít pro analýzu vět. Nejprve identifikujeme jednotlivá slova a jejich vlastnosti poté použijeme k odvození gramatických vztahů a frázové struktury, kterou využijeme pro vytvoření derivačního stromu celé věty podle gramatiky daného jazyka.^[1]

Ukážeme analýzu anglické věty „John hit the ball“ metodou zdola nahoru. V tomto případě jsou základní jednotky jednotlivá slova „John“, „hit“, „the“ a „ball“ (při ignorování konjugace a deklinace).

Pro analýzu této věty dostačuje tato zjednodušená gramatika angličtiny:

1. věta se skládá ze jmenné fráze následované slovesnou frází (S → NP VP),
2. vlastní jméno samo o sobě je jmennou frází (NP → „John“),
3. jmenná fráze může být také determinátor následovaný podstatným jménem (NP → Det N),
4. slovesná fráze může být sloveso následované jmennou frází (VP → V NP),
5. „ball“ je podstatné jméno, „the“ je determinátor a „hit“ je sloveso (N → „ball“, Det → „the“, V → „hit“).

Při zpracování těchto slov od zdola nahoru dostáváme:

Použité pravidlo	Zpracovávaná část textu	Současná věta
-		John hit the ball
2	„John“ je jmenná fráze sama o sobě	NP hit the ball
5	zbývající slova nahradíme jejich syntaktickými kategoriemi	NP V Det N
3	„the ball“ je jmenná fráze	NP V NP
4	„hit the ball“ je slovesná fráze	NP VP
1	„John hit the ball“ je celá věta	S

Existují i jiné způsoby zpracování, např. slovo „ball“ může být zpracováno jako jmenná fráze. Žádné jiné zpracování však nemůže použitím těchto zjednodušených pravidel vést k celé větě (symbolu S). Jak je jednou „ball“ vybráno jako jmenná fráze, tak neexistuje pravidlo, které by umožnilo zpracovat „the“. K nalezení všech možných zpracování věty může být použita „hrubá vyhledávací síla“. Pokud je možné více než jedno zpracování, znamená to, že věta je dvojznačná nebo víceznačná, což je v přirozených jazycích běžné.

Překladače programovacích jazyků založené na syntaktické analýze zdola nahoru používají metodu, která identifikuje nejdříve terminální symboly. Poté je kombinuje postupně tak, že produkuje neterminální symboly. Produkt zpracování může být použit k vytvoření derivačního stromu z textu programu napsaného v člověku čitelné formě zdrojového kódu tak, že může být zkompilován, aby vznikl program, který může provádět procesor nebo který lze interpretovat virtuálním procesorem.

Různé programovací jazyky vyžadují různé techniky zpracování. Není běžné používat techniku zpracování, která je silnější, než je potřeba.

Při syntaktické analýze zdola nahoru je běžné použít formu obecného prostředku pro zpracování, který buď zpracovává, nebo generuje analyzátor pro specifický programovací jazyk daný specifikací jeho gramatiky. Pravděpodobně nejznámějšími obecnými generátory syntaktických analyzátorů jsou Yacc a GNU bison.

Tato jednoduchá gramatika definuje prostý součet výrazů:

1. kompletní výraz (suma) může být sčítanec, znaménko plus a plus jiný sčítanec (S → A “+” A),
2. sčítanec může být písmeno, resp. proměnná (A → P),
3. sčítanec rovněž může být číslo (A → C),
4. sčítanec může být rovněž suma jako taková (A → S),
5. číslo tvoří jedna číslice nebo více číslic (C → cislice+).

Znaménko plus v pravidlu č. 5 značí opakovatelnost „jedna nebo více číslic“. Pro rozlišení tohoto použití od speciálního použití je znaménko plus v pravidlu č. 1, které je umístěno uvnitř uvozovek.

Základní jednotky (terminální symboly) gramatiky jsou jednotlivá písmena, znaménko plus a skupiny s jednou nebo více číslicemi. Proto jsou na vstupu „a + x + 12“ základní jednotky „a“, „+“, „x“, „+“ a „12“. Zpracování může vypadat například takto:

Použité pravidlo	Zpracovaný symbol	Současný výraz
5	„12“ je číslo	a + x + C
2, 2, 3	„a“, „x“ a „12“ jsou sčítance	A + A + A
1	„a + x“ je celá suma	S + A
4	suma „a + x“ je také sčítanec	A + A
1	„a + x + 12“ je celá suma	S

Na rozdíl od přirozených jazyků existuje pro mnoho programovacích jazyků jednoznačná gramatika. Proto zpracování zdola nahoru musí mít pro počítačový jazyk dodatečná pravidla jako „je vybráno první možné nahrazení odleva“. Počítačové zpracování zřídkakdy prozkoumává celý vstup najednou (vstup může být velmi rozsáhlý počítačový program). Většina analyzátorů čte vstup po symbolech od začátku do konce (tj. „zleva doprava“). Vyjadřovací sílu gramatiky zvyšuje možnost využít při analýze před aplikováním pravidel jeden nebo více následujících symbolů („lookahead“).

Nejběžnější zpracování zdola nahoru představuje metoda přesun-redukce. Tyto analyzátory načítají vstupní symboly (anglicky token) a přesunují je na vrchol zásobníku (push), nebo redukují elementy na vrcholu zásobníku, které tvoří pravou stranu přepisovacího pravidla, jejich nahrazením levou stranou pravidla.

Často je konstruována tabulka činností, která pomáhá analyzátoru určit co zpracovat příště. Následuje popis toho, co může být uvedeno tabulce činností.

• Přesun – přesun symbolu ze vstupního řetězce na zásobník
• Redukce – nahrazení jednoho nebo více symbolů na zásobníku odpovídajícím neterminálem
• Přijetí – úspěšné ukončení analýzy věty, kdy zásobník obsahuje pouze počáteční symbol a vstupní řetězec je celý přečten
• Chyba – pokud není ani jedno z výše uvedeného možné, znamená to, že původní vstup nebyla gramaticky správná věta

Analyzátor pracující metodou přesun-redukce používá zásobník pro ukládání symbolů gramatiky, na které bude později provedena redukce. V průběhu analýzy jsou symboly ze vstupu přesouvány na zásobník. Pokud prefix symbolů na vrcholu zásobníku souhlasí s pravou stranou (anglicky right-hand side, RHS) nějakého pravidla gramatiky, analyzátor může tyto symboly nahradit levou stranou (anglicky left-hand side, LHS) příslušného pravidla (redukce). Kroky přesun a redukce se provádějí tak dlouho, dokud analýza neskončí úspěšným přijetím nebo selháním. Skončí-li analýza přijetím, pak vstupní řetězec lze vygenerovat příslušnou gramatikou; skončí-li selháním, pak vstupní řetězec není možné danou gramatikou vygenerovat.

Analyzátor je zásobníkový automat, který se nachází v jednom z několika diskrétních stavů. V případě analyzátoru LR obsahuje zásobník analyzátoru ve skutečnosti spíše stavy než symboly gramatiky. Nicméně pokud každý stav odpovídá unikátnímu symbolu gramatiky, stav zásobníku, může být namapován na gramatické symboly dříve zmíněného zásobníku.

Algoritmus analyzátoru pracujícího metodou přesun-redukce:

1. začneme se vstupem tvořeným analyzovanou větou a prázdným zásobníkem
2. dokud větná forma není tvořena pouze startovacím symbolem:
   1. načítá symboly ze vstupu (přesun)
   2. pokud jeden nebo více naposledy načtených symbolů odpovídá pravé straně některého produkčního pravidla (toto se nazývá anglicky handle), pak lze tyto symboly nahradit levou stranou pravidla (akce známá jako redukce).

V kroku 2.1 se přesouvá první dosud nenačtený vstupní symbol na zásobník. Proto analyzátory, které operují opakovaně aplikováním předešlých kroků 2.1 a 2.2, jsou známé jako analyzátory pracující metodou přesun-redukce.

Metoda přesun-redukce se převážně implementuje pomocí zásobníku, kde postupujeme takto:

• Začneme s prázdným zásobníkem.
• „Přesun“ odpovídá přesunu současného vstupního symbolu na zásobník.
• „Redukce“ je nahrazení jednoho nebo více symbolů na vrcholu zásobníku, které tvoří pravou stranu nějakého pravidla gramatiky, levou stranou tohoto pravidla.

V tomto článku byl použit překlad textu z článku Bottom-up parsing na anglické Wikipedii.

• Syntaktická analýza
• Syntaktická analýza shora dolů
• Konstrukce LR analyzátorů

• Simulátor syntaktické analýzy (tento simulátor je použit pro generování příkladů analýzy metodou přesun-redukce)
• Příklad analýzy metodou přesun-redukce (která je typem analýzy zdola nahoru)
• Kurz analýzy metodou přesun-redukce
• Netechnický tutoriál v kontextu přirozených jazyků
• Diskuze na téma konfliktů při analýze zdola nahoru metodami přesun-redukce (odborný článek)
• Další příklad analýzy zdola nahoru