Syntaktická analýza slouží k zodpovězení otázky, zda dané slovo w e S* je generováno danou bezkon-textovou gramatikou G nad abecedou E.
Pokud w opravdu je generováno gramatikou G, pak existuje derivační strom v G, kterého výsledkem je w. Syntaktická analýza je metoda, která sestrojí zásobníkový automat, který akceptuje jazyk L (G). Rozlišujeme syntaktickou analýzu shora dolů (automat simuluje budování derivačních stromů od počátečního neterminálu směrem dolů, ke slovu) a zdola nahoru (automat simuluje procházení derivačních stromů od slova směrem nahoru, k počátečnímu neterminálu).
Příklad 8.6.
Pro danou G navrhněte (rozšířený) ZA, který provádí syntaktickou analýzu:
a) shora dolů,
b) zdola nahoru.
V obou případech proveďte analýzu slova ababaa. G = ({S, A, B},{a, b},P, S), kde P = { S -> e       I abSA,
A ->• AaB j aB      \ a,
B -> aSS   j bA }
Shora dolů
• simuluje levou derivaci
• jediný stav q, akceptuje prázdným zásobníkem
• zásobníková abeceda jsou terminály i neterminály gramatiky
• za každé pravidlo tvaru i^av gramatice přidáme (q, a) do S(q, e, A)
• pro každý terminál a G S přidáme přechod S(q, a, a) — {(q, e)}
• začínáme s kořenovým neterminálem na zásobníku
• gramatika střídavě „expanduje pravidla na zásobníku" a „kontroluje, že písmeno na vrcholu zásobníku sedí se vstupem"
M = {{q},{a,b},{a,b,S,A,B},5,q,S,%) akceptuje prázdným zásobníkem
S(q, e, S) = {(q, e), (q, abSA)} S(q, a, a) = {(q, e)}
5(q, e, A) = {(q, AaB), (q, aB), (q, a)} 5(q, b, b) = {(q, e)}
ô(q,S,B) = {(q,aSS),(q,bA)}
Analýza ababaa:
(q, ababaa, S) Ig^a&gÁ (9, ababaa, abSA) ŕ (q, babaa, bSA) ŕ (q, abaa, SA) Ig^a&gÁ (9, abaa, abSAA) ŕ (q, baa, bSAA) ŕ (q, aa, SAA) Isl^£ (q, aa, AA) \^l^a (q, aa, aA) ^ (q, a, A) h^- (q, a, a) ŕ (q, e, e)
Akceptovali jsme. Symboly na odvozovací relaci jsou jen pomocné, nahoře uvádíme znak vstupu, který se načetl, dole případné pravidlo, jehož expanze proběhla.
Zdola nahoru
• simuluje pravou derivaci v obráceném pořadí
• rozšířený PDA, zásobník píšeme obráceně (vrchol vpravo)
• zásobníková abeceda jsou terminály, neterminály a speciální symbol _L umožňující nám poznat dno zásobníku
• má dva stavy q, kde probíhá výpočet, a r, který slouží jen k akceptování
• pro každý terminál a G S přidáme do přechodové funkce S(q, a, e) — {(q, a)}
• pro každé pravidlo A —>• a přidáme do S(q, e, a) dvojici (q, A)
• speciální pravidlo S(q, e, ±S) — {(r, e)} slouží k akceptování (pokud vstup nebyl dočten automat se zasekne)
• automat střídavě „přesouvá znaky ze vstupu na zásobník" a „provádí redukci pravidel gramatiky na zásobníku z jejich pravé strany na levou"
R = ({q, r}, {a, b}, {a, b, S, A, B, _L}, ô, q, _L, {r})
Rozšířený PDA akceptuje vždy akceptujícím stavem. Pozor, vrchol zásobníku je v analýze zdola nahoru otočen vpravo.
ô(q,e,e)	= {(q,s)}	S(q,a,e)	= {(<?,«)}
ô(q, e, abSÄ)	= {(q,s)}	5(q,b,e)	= {M)}
S(q, e, AaB)	= {(q,A)}	ô(q,S,±S)	= {(r,e)}
ô(q, e, aB)	= {(q,A)}		
S(q,e,a)	= {(<?, A)}		
ô(q, e, aSS)	= {(q,B)}		
5(q,e,bA)	= {(q,B)}		
Pravidla redukují větnou formu na zásobníku. Pokud se nějaká pravá strana v gramatice objevuje opakovaně, pak jí musí odpovídat jedno pravidlo s více možnostmi přechodu. Analýza ababaa:
(q, ababaa, _L) ŕ- (q, babaa, _La) ŕ (q, abaa, _La6) ŕ- (q, baa, _La6a) ŕ (q, aa, .Labab)
lgf>e (q, aa, J-ababS) ŕ (q, a, J-ababSa) Uf»a (q, a, J-ababSA) Ig^a&gÁ (q, a, -LabS) ŕ (q, e, ±abSa) h^- (q, e, LabS A) Ig^abgA {i, £, -LS) ^ačč (r, £,
Akceptovali jsme. Opět platí, že symboly na odvozovací relaci jsou jen pomocné, nahoře uvádíme znak vstupu, který se načetl, dole případné pravidlo, jehož redukce proběhla.