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, 12.11.2018 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, 12.11.2018 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, 12.11.2018 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, 12.11.2018 4/15 A ->• Bd B Bdd C ^ Aa Ccc aAd IB102 Automaty a gramatiky, 12.11.2018 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, 12.11.2018 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, 12.11.2018 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, 12.11.2018 A ->■ Ba | Db | c B ^ CC C aE D ->• CDa I Eb IB102 Automaty a gramatiky, 12.11.2018 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 / ' 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, 12.11.2018 10/15 Korektnost algoritmu Konečnost. Ekvivalence gramatik. Výsledná gramatika je v GNF. IB102 Automaty a gramatiky, 12.11.2018 11/15 Zásobníkové automaty IB102 Automaty a gramatiky, 12.11.2018 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, ■ ľ 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, 12.11.2018 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, 12.11.2018 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 qf e F, a e P} a jazyk akceptovaný PDA M prázdným zásobníkem definujeme jako Le(M) = {w e I* | (qo, w, Z0) ^- (q, s, s), kde q e Q}. IB102 Automaty a gramatiky, 12.11.2018 15/15