Syntaktická analýza zdola nahoru
Celou dobu budeme pracovat s následující gramatikou ze cviká z příkladu 8.6:
G = ({S, A, B}, {a, b}, P, S), kde p = {S      abAS | 66,
A A6B aB | a, B —> 655 | aB e}.
Intuice: Podívejme se na následující (PRAVÉ) odvození v G:
S => abAS => a6A66      abaBbb      ababSSbb      ababSbbbb a&a&7.
Automat provádějící analýzu zdola nahoru bude konstruovat toto odvození ale pozpátku. Bude tedy postupně načítat do zásobníku písmena ze slova abab7 a když se na vrcholu zásobníku objeví řetězec, který je pravou stranou nějakého pravidla, tak ho odstraní a místo něj tam napíše neterminál z levé strany pravidla.
Praktická ukázka: Odvození tedy vypadá tak, že nejprve načítáme do zásobníku písmena našeho slova abab7, dokud nedojdeme do situace, která nám umožní se dostat před poslední derivaci. Je to situace, kdy nemáme načteno jen 64. V tuto chvíli zpětně provedeme poslední derivaci a načteme další dvě béčka, abychom mohli udělat předposlední derivaci, atd. Níže vidíte, jak to vypadá na příkladu. Pod odvozením najdete pár dalších technických poznámek k tomu, jak je to formálně provedeno.
(q, Z, abab )
h	(q, Za, bab7)	(1)
h	(q, Zab, ab7)	(2)
h	(q, Zaba, b7)	(3)
h	(q,Zabab,b6)	(4)
h	{q, Z abab2,ŕ)	(5)
h	(q, Z abab3, b4)	(6)
h	(q, ZababS, b4)	(7)
h	(q, ZababSb, 63)	(8)
h	(q, ZababSbb, b2)	(9)
h	(q, ZababSS, b2)	(10)
h	(q, ZabaB, b2)	(H)
h	{q, Zab A, b2)	(12)
h	(q, ZabAb, 6)	(13)
h	(q, ZabAbb, e)	(14)
h	(q, ZabAS, e)	(15)
h	(q, ZS, e)	(16)
h	(r, e, e).	(17)
1
1. Podle definice ze skript má výsledný automat dva stavy q,r, kde druhý slouží pouze proto, aby byl koncový.
2. V konfiguracích platí:
• první složka v konfiguraci je stav;
• druhá je obsah zásobníku (s vrcholem značeným vpravo!);
• třetí doposud nepřečtená část vstupu.
3. Náš automat je tzv. rozšířený PDA! To znamená, že v jednom kroku může načíst nějaké konečné slovo na vrcholu zásobníku (a ne jenom jeden symbol). Toto můžeme vidět např na řádku 15, kde automat načte abAS a vrátí na zásobník S.
4. Kdybychom formálně chtěli definovat automat, který syntaktickou analýzu provádí, tak bychom museli uvážit reverse pravých stran pravidel (toto souvisí s tím, že vrchol zásobníku píšeme v konfiguracích pravo, ale jindy (např. při analýze shoda dolů) se píše vlevo). Pro víc informací se podívejte na Příklad 3.56 ze skript.
2