Kanonické tvary bezkontextových gramatik
■ redukované bezkontextové gramatiky
■ gramatiky bez ^-pravidel
■ gramatiky bez jednoduchých pravidel
■ vlastní gramatiky
■ Chomského normálni forma
■ gramatiky bez levé rekurze
■ Greibachové normální forma
IB102 Automaty a gramatiky, 13.11.2017
1/15
Rekurzivní neterminály a gramatiky
Definice 3.28. Neterminál A v CFG Q = (A/, Z, P, S) se nazývá levorekurzivní jestliže v Q existuje derivace A =4>+ Af3.
CFG bez levorekurzivních neterminálů se nazývá nelevorekurzivní.
Je-li v CFG pravidlo tvaru A -> Aa, hovoříme o přímé levé rekurzi na A.
Praktický význam: některé nástroje pro automatickou tvorbu parserů k zadaným gramatikám vyžadují na vstupu nelevorekurzivní gramatiku (např. ANTLR).
IB102 Automaty a gramatiky, 13.11.2017
2/15
Algoritmus odstraněni prime leve rekurze
Nechť CFG Q = (A/, Z, P, S) je necyklická a bez ^-pravidel, v níž všechna /A-pravidla (pravidla mající na levé straně A) jsou tvaru
A    Aol\   ...  Aam /3i
kde každý retez /3, začíná symbolem různým od A.
Nechť = (N (J {A'}, Z, P', S), kde P' obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly:
A' ->■
I Ä A'
am ol\AI
PnA'
amÄ
Pak L(Q) = /_(£') a Q' je necyklická a bez ^-pravidel.
IB102 Automaty a gramatiky, 13.11.2017
3/15
Lemma o substituci
Lemma 3.20. (o substituci)
Nechť g = {N, E, P, S) je CFG. Nechť A^a, Ba2 e P. Nechť B ->• /?i | ... | /3r jsou všechna pravidla v P tvaru S -> o.
Definujme £' = (A/, E, P', S), kde
P' = (P \ {/A    «iBa2}) u {/A ->■ OL\ß^a2
a-\ßra2}
Pak /_(£) = /.(£')■
IB102 Automaty a gramatiky, 13.11.2017
4/15
A ->• Bd B Bdd C ^ Aa
Ccc aAd
IB102 Automaty a gramatiky, 13.11.2017
5/15
Algoritmus odstranění levé rekurze
Vstup:   Vlastní CFG Q = (A/, Z, P, S)
Výstup: Ekvivalentní nelevorekurzivní gramatika bez ^-pravidel
Uspořádej libovolně N, N = {A|,..., An} for / <- 1 to n do for / <- 1 to / - 1 do
for all pravidlo tvaru A, -> Aja do přidej pravidla Ai -> faa \ ... \ fS^a (kde Aj ^ fa \ ... \ f3k jsou všechna pravidla pro Aj) vypusť pravidlo A\ Aja end for end for
odstraň případnou přímou levou rekurzi na A\ end for
IB102 Automaty a gramatiky, 13.11.2017
6/15
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 nelevorekurzivní:
D po Mé iteraci vnějšího cyklu začíná každé A-pravidlo buď terminálem nebo neterminálem Ak, kde k > i.
H po /-té iteraci vnitřního cyklu začíná každé A-pravidlo buď terminálem nebo neterminálem Ak, kde k > j.
Výsledná gramatika je bez ^-pravidel.
IB102 Automaty a gramatiky, 13.11.2017
7/15
Greibachové normální forma
Definice 3.33. Bezkontextová gramatika Q = (A/, Z, P, S) je v Greibachové normální formě (GNF), právě když
■ g je bez ^-pravidel a
■ každé pravidlo z P je tvaru A    aa, kde a g Z a a g A/* (s případnou výjimkou pravidla S e).
Věta 3.34. Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Greibachové normální formě.
Důkaz.
L = 0: zřejmé (S^aS)
L ^ 0: 1. z vlastní gramatiky eliminujeme levou rekurzi 2. pak převedeme do GNF
IB102 Automaty a gramatiky, 13.11.2017
A ->■ Ba | Db | c
B ^ CC
C aE
D ->• CDa I Eb
IB102 Automaty a gramatiky, 13.11.2017
9/15
Algoritmus transformace do GNF
Vstup: Nelevorekurzivní CFG Q = (A/, Z, P, S) bez ^-pravidel Výstup: Ekvivalentní gramatika v GNF
Najdi lineární uspořádání -< splňující (A    Ba) e P =4> A -< B Označme N = {A,..., An | A_i -< A, 1 < / < n} for / <r- n - 1 downto 1 do
for all pravidlo tvaru A    A'a' kcle J > ' 0,0 přidej pravidlo Aj -> faa \ ... \ ^a (kde A ~^ /5i I • • • I Pk jsou všechna A-pravidla) vypusť pravidlo A A'a
end for end for
Nahraď potřebné terminály novými neterminály a přidej příslušná pravidla
IB102 Automaty a gramatiky, 13.11.2017
10/15
Korektnost algoritmu
Konečnost.
Ekvivalence gramatik.
Výsledná gramatika je v GNF.
IB102 Automaty a gramatiky, 13.11.2017 11/15
Zásobníkové automaty
IB102 Automaty a gramatiky, 13.11.2017
12/15
Definice zásobníkového automatu
Definice 3.36. Nedeterministický zásobníkový automat (PushDown Automaton, PDA) je sedmice M = (Q, Z, r, 5, q0, Z0, F), kde
■ Q je konečná množina, jejíž prvky nazýváme stavy,
■ Z je konečná množina, tzv. vstupní abeceda,
■ r je konečná množina, tzv. zásobníková abeceda,
■ S : Q x (Z u {s}) xľ4 VFin{0 x r*), tzv. (parciální) přechodová funkce1,
■ Qo e Q je počáteční stav,
■ Zq g r je počáteční symbol v zásobníku,
■ F c Q je množina koncových stavů.
1 Zápis VFin{Q x r*) značí množinu všech konečných podmnožin množiny Q x r*.
IB102 Automaty a gramatiky, 13.11.2017 13/15
Výpočet zásobníkového automatu
Definice 3.37. Nechť M = (Q, Z, r, 6, q0, Z0, F) je PDA.
Konfigurací nazveme libovolný prvek (p, w, a) e Q x Z* x r*.
Na množině všech konfigurací automatu M definujeme binární relaci krok výpočtu takto:
(p,aw,Za) ^ (q,w,-ya) ^ 3(q,-y) e 5(p,a,Z) pro aeluje}
Reflexivní a tranzitivní uzávěr relace hn- značíme
M ----| ^ ■
V      ■  _ _   ' l^-i-       ■ _ ' V   _    _ _   _      _   _ _        I ____ I*
Je-li .M zrejmý z kontextu, píšeme pouze |— resp.
IB102 Automaty a gramatiky, 13.11.2017 14/15
Akceptující výpočet zásobníkového automatu
Definice 3.37. (pokračování)
Jazyk akceptovaný PDA M koncovým stavem definujeme jako
L(m) = {weZ*\ (qo, w, Zq) ^- (qf, e,a), kde qfeF,aeť} a jazyk akceptovaný PDA M prázdným zásobníkem definujeme jako
Le(M) = {w e Z* | (qo, w, Z0) ^- (q, s, s), kde q e Q}.
IB102 Automaty a gramatiky, 13.11.2017
15/15