Transformace bezkontextových gramatik
Algoritmy a postupy pro úpravu bezkontextových gramatik: odstranění nedostupných a zbytečných symbolů, eliminace epsilon pravidel a levé rekurze.
Transformace bezkontextových gramatik
V tomto cvičení se budeme zabývat základními transformacemi bezkontextových gramatik - BKG (též CFG, context-free grammar). Popsané postupy a myšlenky jsou jednoduché a vcelku přímočaré, leč začátečník se může na chvíli v záplavě písmenek ztratit. Stane-li se vám to, nezoufejte. Zkuste na věc přijít selským rozumem a uvidíte, že na tom nic není :).Nechť G je bezkontextová gramatika daná čtveřicí (N, T, P, S), kde N je množina neterminálních symbolů, T množina terminálních symbolů, P přepisovací pravidla a S startovací symbol. Připomeňme si, že gramatika je bezkontextová, tvoří-li levou stranu všech přepisovacích pravidel právě jeden neterminální symbol, tj. pravidla jsou ve tvaru X --> w, kde X je neterminální symbol a w řetězec složený z terminálních i neterminálních symbolů.
Gramatika generuje nějaký jazyk, tj. množinu řetězců terminálních symbolů. Tato množina může být konečná, nekonečná nebo i prázdná. Postupně se budeme zabývat těmito otázkami: Je generovaný jazyk prázdný? Jsou v gramatice takové symboly, které by v ní být nemusely? Dá se něco udělat s přepisovacími pravidly, aby gramatika vypadala "lépe"?
Nedostupné symboly
Začneme-li vytvářet ze startovacího symbolu S gramatiky G větné formy, může se stát, že k některým symbolům (terminálním či neterminálním) vůbec nedojdeme. Takové symboly nazveme nedostupné. Základem algoritmu k jejich vyhledání je přímočarý postup, kterým "prolézáme" pravidla a sespisujeme symboly, na které jsme narazili.Algoritmus
1) V0 = {S}, i=1
2) Vi = {X: A --> a X b je přepisovací pravidlo, a a b jsou řetězce symbolů, A náleží Vi-1} + Vi-1
3) Je-li Vi != Vi-1, pak i++ a jdi na (2), jinak
VD = Vi (dostupné symboly)
VN = N + T - VD (nedostupné symboly)
Příklady
- G = (N, T, P, S), N = {S, A, B}, T = {a, b}, P:
Ukázka kódu
S --> aB | bB A --> a | BA B --> aS | bBZobrazit postup a řešení
Postupujeme podle algoritmu:Potom G' = {N', T', P', S}, kde N' = {S, B}, T' = {a, b} a P:Ukázka kóduV0 = {S} V1 = {S, B, a, b} V2 = {S, B, a, b} = V1, tj. VD = {S, B, a, b}Ukázka kóduS --> aB | bB B --> aS | bB - G = (N, T, P, S), N = {S, A, B, C}, T = {a, b}, P:
Ukázka kódu
S --> A | aB A --> a | BA B --> bB | e C --> ABC | SZobrazit postup a řešení
Postupujeme podle algoritmu:Potom G' = {N', T', P', S}, kde N' = {S, A, B}, T' = {a, b} a P:Ukázka kóduV0 = {S} V1 = {S, A, B, a} V2 = {S, A, B, a, b} V3 = V2, tj. VD = {S, A, B, a, b}Ukázka kóduS --> A | aB A --> a | BA B --> bB | e
Je jazyk prázdný?
Díky předchozímu textu umíme vyloučit z gramatiky takové symboly, které v ní nejsou evidentně užitečné. Za chvíli si ukážeme, že existuje ještě jeden typ takových symbolů. K tomu budeme potřebovat vědět, zda jazyk generovaný gramatikou G není prázdný, respektive budeme potřebovat algoritmus, který to zjistí.Jazyk L(G) je množina řetězců terminálních symbolů. Gramatika může mít ale takovou vlastnost, že při derivacích (přepisování) nebudou ubývat neterminální symboly. Nyní tedy chceme zjistit, zda z gramatiky G vůbec lze takový řetězec generovat.
Algoritmus:
1) N0 = {}, i = 1
2) Ni = {A: A --> a, a je řetězec složený ze symbolů Ni-1 a T} + Ni-1
3) Je-li Ni != Ni-1, i++ a jdi na (2), jinak
Nt = Ni
4) Je-li S prvkem Nt, je L(G) neprázdný, v opačném případě je prázdný.
Příklady
- gramatika G z příkladu 1 bez nedostupných symbolů, tj. G = (N, T, P, S), N = {S, B}, T = {a, b}, P:
Ukázka kódu
S --> aB | bS B --> aS | bBZobrazit postup a řešení
Postupujeme podle algoritmu:Jazyk L(G) je tedy prázdný.Ukázka kóduN0 = {} N1 = N0, protože P neobsahuje žádné "dobré" pravidlo - G = (N, T, P, S), N = {S, A, B}, T = {a, b}, P:
Ukázka kódu
S --> A | aB A --> a | BA B --> bB | eZobrazit postup a řešení
Postupujeme podle algoritmu:Startovací symbol je "dobrý", tj. náleží do množiny Nt, tj. L(G) je neprázdný.Ukázka kóduN0 = {} N1 = {A, B} N2 = {S, A, B} = Nt - G = (N, T, P, S), N = {S, A, B, C, D}, T = {a, b}, P:
Ukázka kódu
S --> aAB | A A --> bC | D B --> A | b C --> SZobrazit postup a řešení
Připadá-li vám, že je v zadání chyba, neboť pravidla nedefinují přepisovací pravidla pro symbol D, dáváte pozor. Ale ne úplně, protože není nikde řečeno, že se všechny neterminální symboly musí vyskytovat na levé straně! Asi cítíte, že symbol D je v této gramatice zbytečný, tím se ale budeme zabývat až za chvíli. Nyní jen zjistíme, zda je L(G) prázdný nebo ne.Nejenže gramatika obsahuje zbytečný symbol, gramatika je nějak zbytečná celá, protože generuje prázdný jazyk.Ukázka kóduN0 = {} N1 = {B} N2 = {B} = N1 = Nt
Zbytečné symboly
Víme, že některé symboly gramatiky mohou být nedostupné. Ty jsou zbytečné automaticky. V posledním příkladu jsme viděli, že symbol D byl také zbytečný, protože pro něj neexistovalo přepisovací pravidlo. Pokud si celý problém formalizujeme, zjistíme, že přepisování probíhá asi takto:S -->* a X b -->* a c b
Odstranění zbytečných symbolů probíhá ve dvou krocích. Nejprve najdeme množinu Nt. Nová gramatika bude obsahovat jen tyto "dobré" neterminální symboly. Z nich je ale zapotřebí vyházet všechny nedostupné symboly. Snadné, že?
Příklady
- G = (N, T, P, S), N = {S, A, B}, T = {a, b}, P:
Ukázka kódu
S --> ab | AB A --> AB B --> bZobrazit postup a řešení
Nejprve najdeme Nt:Pomocná gramatika je:Ukázka kóduN0 = {} N1 = {S, B} N2 = N1 = NtVyloučíme nedostupné symboly:Ukázka kóduS --> ab B --> bGramatika bez zbytečných symbolů obsahuje jen jedno pravidlo, a to:Ukázka kóduV0 = {S} V1 = {S, a, b} = VDUkázka kóduS --> ab - G = (N, T, P, S), N = {S, A, B, C, D}, T = {a, b, c}, P:
Ukázka kódu
S --> aB | bD A --> aB | bCD B --> ABCD C --> cC | A D --> aD | eZobrazit postup a řešení
Najdeme Nt:Nová gramatika má dvě pravidla (všechny symboly jsou dostupné):Ukázka kóduN0 = {} N1 = {D} N2 = {S, D} N3 = N2 = NtUkázka kóduS --> bD D --> aD | e
Vyloučení pravidla
V tomto okamžiku umíme z gramatiky vyloučit všechny nepotřebné symboly. Někdy je také vhodné upravit či vyloučit nějaká pravidla. Princip je prostý: místo toho, aby se přepisování provedlo při derivaci větné formy, provedeme ho už v zápisu gramatiky. Potřebujeme-li pozměnit pravidlo A --> aBb a všechna pravidla pro B jsou B --> c1, c2, ..., cn, přepíšeme pravidlo pro A na A --> ac1b, ac2b, ..., acnb (a, b, c jsou řetězce terminálních symbolů)Speciálními pravidly, kterých se někdy potřebujeme zbavit, jsou tzv. e-pravidla, tj. přepsání neterminálního symbolu na prázdný řetězec. Gramatikou bez e-pravidel pak budeme rozumět takovou gramatiku, ve které nejsou žádná e-pravidla, až na jednu výjimku. Tou je pravidlo S --> e, které do gramatiky zahrneme v případě, že gramatika generuje prázdný řetězec (S je startovací symbol). Potom se ovšem nesmí symbol S objevit na žádné z pravých stran přepisovacích pravidel.
Algoritmus:
1) Způsobem podobným jako při hledání Nt najdeme Ne, množinu symbolů, které se dají přepsat na e.
2) Pravidlo A --> a0 B1 a1 B2 a2 ... Bn an nahradíme pravidly A --> a0 X1 a1 X2 a2 ... Xn an, kde Xi je buď e nebo Bi (vystřídáme všech 2i možností). Pravidlo typu A --> e pochopitelně zapisovat nebudeme, protože takových pravidel se snažíme zbavit.
3) Patří-li startovací symbol S do množiny Ne, zařadíme do gramatiky pravidlo S' --> S | e. Novým startovacím symbolem pak bude S'.
Příklady
- G = (N, T, P, S), N = {S, A}, T = {a, b}, P:
Ukázka kódu
S --> aSbS | aSbA | A A --> aA | eZobrazit postup a řešení
Najdeme množinu Ne:Nyní budeme postupně vynechávat v pravidlech ty symboly, které se dají přepsat na e:Ukázka kóduN0 = {} N1 = {A} (protože A se dá přepsat na e) N2 = {A, S} (protože S se dá přepsat na A) Ne = N2Ukázka kóduS --> aSbS | aSb | abS | ab | aSbA | abA | A A --> aA | a S' --> S | e (protože S patří do Ne) - G = (N, T, P, S), N = {S, A, B}, T = {a, b}, P:
Ukázka kódu
S --> aB | bA A --> aA | B | e B --> bB | A | eZobrazit postup a řešení
Najdeme množinu Ne:Po přepisu:Ukázka kóduN0 = {} N1 = {A, B} N2 = N1 = NeUkázka kóduS --> aB | bA | a | b A --> aA | a | B B --> bB | b | A
Jednoduchá pravidla
Jednoduché pravidlo ja takové, při kterém se neterminální symbol přepisuje na jiný neterminální symbol, tedy pravidlo typu A --> B. Sama o sobě by taková pravidla v gramatice nevadila, i když se dá diskutovat nad tím, zda jsou skutečně nutná. Hlavní motivací jejich odstranění je vedlejší jev, a to cykly. Na gramatice v posledním příkladu můžeme takový cyklus vidět: A se přepisuje na B a to opět na A. Odstraněním jednoduchých pravidel tedy odstraníme i cykly, které jsou nežádoucí při syntaktické analýze.Nejprve pro každý neterminální symbol zjistíme, na jaké neterminální symboly se může přepsat pomocí jednoduchých pravidel. To se dá zjistit postupem podobným jako při hledání dostupných symbolů. Pro neterminální symbol A zařadíme do množiny NA jak symbol A, tak všechny "jednoduše dostupné" symboly.
V dalším kroku již píšeme nová pravidla. Pro neterminální symbol A napíšeme vechna pravidla A --> a, kde a jsou ne-jednoduchá pravidla pro všechny symboly z NA.
Příklady
- G = (N, T, P, E), N = {E, T, F}, T = {+, *, (, ), i}, P:
Ukázka kódu
E --> E + T | T T --> T * F | F F --> (E) | iZobrazit postup a řešení
V této gramatice se sice cykly nevyskytují, ale z cvičných důvodů jednoduchá pravidla odstraníme:Nová gramatika je tedy:Ukázka kóduNE = {E, T, F} NT = {T, F} NF = {F}Ukázka kóduE --> E + T | T * F | (E) | i T --> T * F | (E) | i F --> (E) | i - G = (N, T, P, S), N = {A, B, S}, T = {a, b}, P:
Ukázka kódu
S --> aB | bA A --> aA | a | B B --> bB | b | AZobrazit postup a řešení
Sestavíme množiny N?:Nová gramatika je:Ukázka kóduNS = {S} (zajímají nás jen jednoduchá pravidla!) NA = {A, B} NB = {A, B}Ukázka kóduS --> aB | bA A --> a | aA | b | bB B --> a | aA | b | bB
Odstranění levé rekurze
Pravidlo je levorekurzivní, je-li ve tvaru A --> A.... Gramatiky s levorekurzivními pravidly jsou nevhodné pro některé typy syntaktické analýzy. Jsou-li všechna pravidla pro neterminální symbol A zapsána jakoA --> Aa1 | Aa2 | ... | Aam |
b1 | b2 | ... | bn
A --> b1 | b2 | ... | bn |
b1A' | b2A' | ... | bnA'
A' --> a1 | a2 | ... | am |
a1A' | a2A' | ... | amA'
A --> b1A' | b2A' | ... | bnA'
A' --> e | a1A' | a2A' | ... | amA'
Nepřímá levá rekurze je například toto: A --> B..., B --> A.... Její odstranění funguje podobně jako u přímé rekurze. Je velmi vhodné si do odstraňování zavést nějaký systém, jinak je slušná šance, že se v záplavě písmenek člověk ztratí!
Jeden ze systémů je následující. Označíme si neterminální symboly jako N1, N2, ..., Nn. Jsou-li v gramatice pravidla typu Ni --> Nj..., budeme se snažit, aby pokud možno i<j, tj. aby se přepisování neodkazovalo na předcházející symboly. Není to nutné, ale může to ušetřit práci. Pro pravidlo Ni --> ... nejprve zajistíme, aby se neodkazovalo na předcházející symboly. I v tom je třeba zavést pořádek, proto nejdříve odstraníme odkaz na N1, pak na N2 atd. Až na závěr si necháme odstranění přímé levé rekurze Ni --> Ni. Toto "čištění" pravidel provedeme postupně pro N1, N2 atd.
Příklady
- G = (N, T, P, E), N = {E, T, F}, T = {+, *, (, ), i}, P:
Ukázka kódu
E --> E + T | T T --> T * F | F F --> (E) | iZobrazit postup a řešení
Vidíme, že zde nepřímá levá rekurze není, budeme mít méně práce. Nejprve bez e-pravidel:V dalším cvičení zjistíme, že pro syntaktickou analýzu je vhodnější zavedení e-pravidel:Ukázka kóduE --> T | TE' E' --> + T | + TE' T --> F | FT' T' --> * F | * FT' F --> (E) | iUkázka kóduE --> TE' E' --> e | + TE' T --> FT' T' --> e | * FT' F --> (E) | i - G = (N, T, P, A), N = {A, B, C}, T = {a, b}, P:
Ukázka kódu
A --> AB | C | Bb B --> Ab | Ca C --> Aa | bZobrazit postup a řešení
Zde se nepřímá levá rekurze vyskytuje. Při uspořádání symbolů A-B-C se B i C odkazují na předešlý symbol, A. V uspořádání B-C-A se na předešlý symbol odkazuje jen A. Použijeme tedy pořadí B-C-A.S e-pravidly:Ukázka kóduB --> Ab | Ca (první pravidlo se nemůže odkazovat na předešlé symboly, přímá levá rekurze zde není) C --> Aa | b (neodkazuje se na B, přímá levá rekurze zde není) A --> AB | C | Bb (původní pravidla) A --> AB | C | Abb | Cab (odstranili jsme odkaz na B) A --> AB | Aa | b | Abb | Aaab | bab (odstranili jsme odkaz na C) A --> b | bab | bA' | babA' (nyní už píšeme definitivní pravidla) A' --> B | a | bb | aab | BA' | aA' | bbA' | aabA'Ukázka kóduB --> Ab | Ca C --> Aa | b A --> AB | C | Bb (původní pravidla) A --> AB | C | Abb | Cab (odstranili jsme odkaz na B) A --> AB | Aa | b | Abb | Aaab | bab (odstranili jsme odkaz na C) A --> bA' | babA' (definitivní pravidla) A' --> e | BA' | aA' | bbA' | aabA'