Rekursivní neterminály a gramatiky
Definice 3.28. Neterminál A v CFG Q — (iV, £, P, 5) se nazývá levorekursivní jestliže v Q existuje derivace A =^>+ A/3.
CFG bez levorekursivních neterminálů se nazývá nelevorekursivní.
Praktický význam: některé nástroje pro automatickou tvorbu parserů k zadaným gramatikám vyžadují na vstupu nelevorekursivní gramatiku (např. ANTLR).
IB102 Automaty, gramatiky a složitost, 4.11.2013
1
Lemma o substituci (pro připomenutí)
Lemma 3.20.   (o substituci)
Necht G = (N, E, P, S) je CFG. Necht A -> aľBa2 G P. Necht B —> fii I ... I (3r jsou všechna pravidla v P tvaru B
a,
Definujme Q1 = (N, E, P', 5), kde
P' = (P \ {A     a1Ba2\) U {A ai/3ia2
aißra2}
PakL(0) = L(0')-
IB102 Automaty, gramatiky a složitost, 4.11.2013
2
Algoritmus odstranění přímé levé rekurze
Necht CFG Q = (iV, S) je necyklická a bez e-pravidel, v níž všechna A-pravidla (pravidla mající na levé straně A) jsou tvaru
A -> Aai
Aam fii
kde každý řetěz    začíná symbolem různým od A.
Necht g'=(NU {A'}, £, P', 5), kde P' obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly
A'
Qái
a
m
aľA'
amAf
Pak L (Q) = L(Qr) a Q' je necyklická a bez e-pravidel.
IB102 Automaty, gramatiky a složitost, 4.11.2013
3
Příklad
A B
C
Bd
Bdd
Aa
c
Ccc aAd
IB102 Automaty, gramatiky a složitost, 4.11.2013
4
Algoritmus odstranění levé rekurze
Vstup: Vlastní CFG g = (iV, E, P, 5)
Výstup: Ekvivalentní nelevorekursivní gramatika bez e-pravidel
1 Uspořádej libovolně iV, N = {Ai,..., An}
2 for i <— 1 to n do for j     1 to i — 1 do
foreach pravidlo tvaru A{ přidej pravidla Ai —> fiia
3
4
5
6
7
8
AjOt do
(kde Aj -> fa výpust pravidlo A,
(3 k jsou všechna A^-pravidla)
Aja
od
g od
io odstraň případnou přímou levou rekurzi na A,t u od
IB102 Automaty, gramatiky a složitost, 4.11.2013
5
Korektnost algoritmu
Konečnost.
Ekvivalence gramatik: Všechny úpravy jsou dle Lemmatu o substituci nebo odstraňují přímou levou rekurzi.
Výsledná gramatika je nelevorekursivní:
1. po i-té  iteraci vnějšího cyklu  začíná  každé A^-pravidlo bud terminálem nebo neterminálem A^, kde k > i.
2. po j-té iteraci vnitřního cyklu začíná každé A^-pravidlo bud terminálem nebo neterminálem A^, kde k > j.
Výsledná gramatika je bez e-pravidel.
IB102 Automaty, gramatiky a složitost, 4.11.2013
6
Greibachové normální forma
Definice 3.33. Bezkontextová gramatika Q — (iV,       S) je
v Greibachové normální formě (GNF) právě když
• Q je bez e-pravidel a
• každé pravidlo z P je tvaru A —> aa, kde a G S a a G iV* (s případnou výjimkou pravidla S —> e).
Věta 3.34. Každý bez kontextový jazyk lze generovat bezkontextovou gramatikou v Greibachové normální formě.
IB102 Automaty, gramatiky a složitost, 4.11.2013
7
Zásobníkové automaty
IB102 Automaty, gramatiky a složitost, 4.11.2013
8
Definice zásobníkového automatu
Definice 3.36. Nedeterministický zásobníkový automat (PushDown
Automatem, PDA) je sedmice M = (Q, S, r, 5, qo, Z$, F), kde
• Q je konečná množina, jejíž prvky nazývame stavy,
• S je konečná množina, tzv. vstupní abeceda,
• T je konečná množina, tzv. zásobníková abeceda,
• 5 : Q x (S U {e}) xT^ Vfíu(Q x T*), tzv. (parciální) přechodová funkce1,
• Qo £ Q Je počáteční stav,
• Zq g T je počáteční symbol v zásobníku,
• F C Q je množina koncových stavů.
1Zápis Vfíu(Q x T*) značí množinu všech konečných podmnožin množiny Q x r*.
IB102 Automaty, gramatiky a složitost, 4.11.2013
9
Výpočet zásobníkového automatu
Definice 3.37.    Necht M = (Q, £, I\ 5, q0, Z0, F) je PDA. Konfigurací nazveme libovolný prvek (p,w,a) £ Q x S* x T*
Na množině všech konfigurací automatu      definujeme binární relaci
krok výpočtu
M
takto
(p, <m>, Za)
(g, i/;, 7a) 3(#, 7) G 5(p, a, Z) pro a G S U {e}
Reflexivní a tranzitivní uzávěr relace
M
značíme
Je-li Ai zřejmý z kontextu, píšeme pouze I— resp
M
*
IB102 Automaty, gramatiky a složitost, 4.11.2013
10
Akceptující výpočet zásobníkového automatu
Definice 3.37.(pokračování)
Jazyk akceptovaný PDA Ai koncovým stavem definujeme jako
L(M) = {w G E* I (q0, w, Z0)       (qf, e, a), kde qf G F, a G T*}
a jazyk akceptovaný PDA Ai prázdným zásobníkem definujeme
Le(M) = {w G S* I (q0,w,Z0) kde g G Q}.
IB102 Automaty, gramatiky a složitost, 4.11.2013
11
Příklad
M = ({q0,p, /}, {a, b}, {A, B, Z}, S, q0, Z, {/}), kde
o
6(q0,a,Z) a, A)
a, B)
b, Z) b,A) b,B) e,Z) e,A) e,B)
5(p, a, A) 6(p, b, B) S(p,e,Z)
S(q
S(qo
%o %o S(qo
S(qo
S(q
o
{(9o {(9o {(9o {(9o
{(</ {(9o
= UQO
AZ)} A A)} AB)} BZ)}
BA) }
BB) }
{(P,B)}
{(P,e)} {(f,Z)}
IB102 Automaty, gramatiky a složitost, 4.11.2013
12
Příklad
M = ({q0}, {a, b}, {Z, A}, S, q0, Z, 0), kde
S(q0,a,Z) = {(qo,A)} S(q0,a,A) = {(q0,AA)} 6(q0,b,A) = {(q0,e)}
IB102 Automaty, gramatiky a složitost, 4.11.2013
13
Ekvivalence dvou způsobů akceptování
Věta 3.39.   Pro každý jazyk L platí:
L = L (AT) pro nějaký PDA M        L = Le(M) pro nějaký PDA M.
Důkaz,  koncový stav =^> prázdný zásobník
Intuice:
K danému AT zkonstruujeme Ai simulující jeho činnost.
Vejde-li Af do koncového stavu, Ai se nedeterministicky rozhodne
• pokračovat v simulaci automatu AT nebo
• přejít do nově přidaného stavu q£l v němž vyprázdní zásobník.
IB102 Automaty, gramatiky a složitost, 4.11.2013
14
Komplikace
Řešení: před zahájením simulace bude u Ai na dně zásobníku nový symbol, který nedovolíme odstranit jinde, než ve stavu q£.
IB102 Automaty, gramatiky a složitost, 4.11.2013
15
Konstrukce: Necht N = (Q, S, T, S, q0, Z0, F).
Klademe M = (Q U {q'0,qe} , S, T U {Z'} , 5', q'0, Z', 0), kde Z' ^ r, gó?9e ^ Q a 5' je definována takto:
. S'(q>0}s}Z') = {(qo,Z0Z')}
• jestliže 5{q,a,Z) obsahuje (r,7), pak Sf(q:a:Z) obsahuje (r,7)
• S'(q,e,Z) obsahuje (q£,Z)
pro všechny geFaZeTU {Z'}
• S'(qe,e,Z) = {(qe,e)} pro všechny Z G T U {Z'}
IB102 Automaty, gramatiky a složitost, 4.11.2013
16
Korektnost:
IB102 Automaty, gramatiky a složitost, 4.11.2013
17
prázdný zásobník =^> koncový stav
Intuice
K danému Ai zkonstruujeme Af simulující jeho činnost.
• Af si před simulací přidá na dno zásobníku nový symbol.
• Je-li Af schopen číst tento symbol (tj. zásobník automatu Ai je prázdný) tak AT přejde do nově přidaného stavu qf, který je koncovým stavem.
IB102 Automaty, gramatiky a složitost, 4.11.2013
18
Konstrukce: Necht M = (Q,E,r,S,q0,Z0,^).
Klademe N = (Q U {q'0} qf} , S , V U {Z'} , S', q'0, Z', {qf}), kde Z7 ^ T,     Qf Č Q a ^ Je definována takto:
• jestliže 5(q,a,Z) obsahuje (r,7), pak 8'(q,a,Z) obsahuje (r,7)
. <5'(g, e, Z') = {(«/, e)}
pro všechny q <E Q □
IB102 Automaty, gramatiky a složitost, 4.11.2013
19
Grafická reprezentace konfigurací
IB102 Automaty, gramatiky a složitost, 4.11.2013
20