Greibachové normální forma
Dalším kanonickým tvarem, kterým se budeme zabývat, je bezkontextová gramatika v Greibachové
normální formě (dále též GNF). Nejdříve si uvedeme definici této formy.
Definice – CFG v Greibachové normální formě
Buď G = (N, Σ, P, S) bezkontextová gramatika. Řekněme, že G je v Greibachové normální
formě právě tehdy, když je bez ε-pravidel a každé pravidlo z P je tvaru A → aα, kde A ∈ N, a ∈
Σ, α ∈ N∗
.
Poznámka.
Převod do GNF vyžaduje znalost několika operací. Uvedeme si je nejdříve v souhrnu a pak si
je popíšeme:
1. substituce nějakého pravidla obsahujícího neterminál A (více viz Lemma o substituci)
2. eliminace bezprostřední levé rekurze – odstranění pravidel A → Aα, kde α ∈ (N ∪ Σ)∗
3. eliminace levé rekurze (neboli nepřímé levé rekurze)
4. algoritmus pro převod do GNF
Poznámka.
Ještě než se začneme zabývat jednotlivými algoritmy, měli bychom si vysvětlit, proč je užitečné
převést si nějakou bezkontextovou gramatiku do Greibachové normální formy. Představte
si nějaký imaginární nástroj, který bude pracovat dle pravidel gramatiky a číst vstupní slovo.
V závislosti na něm bude používat jednotlivá pravidla. Je patrné, že takovému „stroji bude
platnější, když pravidla budou ve tvaru odpovídajícímu GNF, tj. jejich pravé strany budou
začínat terminálem. Bude totiž moci porovnat aktuálně čtený symbol vstupního slova s počátečním
terminálem každého pravidla. Zvolí poté to pravidlo, které začíná stejným terminálem
jako aktuálně čtený vstupní symbol.
Každopádně, předchozí idea nemusí platit v případě, že gramatika v GNF obsahuje dvě
A-pravidla začínající stejným terminálem. V tu chvíli už se stroj opět musí chovat nedeterministicky,
tj. volit, jaké pravidlo má použít.
Lemma (o substituci)
Buď G = (N, Σ, P, S) bezkontextová gramatika. Mějme pravidlo
A → xBy, B ∈ N, x, y ∈ (N ∪ Σ)∗
a B-pravidla
B → β1 | β2 | · · · | βn, β1, β2, . . . , βn ∈ (N ∪ Σ)∗
.
Pak gramatika G1 = (N, Σ, P , S), kde
P = P \ {A → xBy} ∪ {A → xβ1y | xβ2y | · · · | xβny},
je jazykově ekvivalentní gramatice G.
1
Příklad 1.
Buď dána bezkontextová gramatika G = ({S, A, B}, {a, b}, P, S) s pravidly
P = {S → aAb | bB
A → aaAb | Baa
B → bBb | aSb}
Uvažujme např. pravidlo A → Baa. Pokud bychom místo pravé strany Baa dosadili bBbaa, aSbaa
(tj. nahradili symbol B všemi B-pravidly), tak jazyk generovaný novou gramatikou se nezmění.
Tj. pomocí pravidel
P = {S → aAb | bB
A → aaAb | bBbaa | aSbaa
B → bBb | aSb}
dostaneme stejná slova jako v případě pravidel P.
Definice – rekurzivní neterminál
Neterminál A ∈ N v gramatice G = (N, Σ, P, S) se nazývá rekurzivní, právě když v G existuje
derivace tvaru A ⇒+
αAβ, kde α, β ∈ (N ∪ Σ)∗
. Navíc,
• je-li α = ε (tedy A ⇒+
Aβ), pak A se nazývá levorekurzivní.
• pokud β = ε (tedy A ⇒+
αA), pak A se nazývá pravorekurzivní.
Poznámka.
Jistě vás napadne, že pro převod do GNF je potřeba odstranit levorekurzivní neterminály.
K tomu slouží algoritmus pro odstranění levé rekurze, který využívá postupu pro odstranění
tzv. přímé (neboli bezprostřední) levé rekurze.
Přímou levou rekurzi představují pravidla, která jsou tvaru A → Aα, kde α ∈ (N ∪ Σ)∗
.
Nepřímou levou rekurzí rozumíme derivaci ve více než jednom kroku, která vede k levé rekurzi.
Například derivace A ⇒ BaaB ⇒ AbaaB je příčinou toho, že neterminál A je levorekurzivní,
avšak daná rekurze není přímá.
Lemma (o odstranění přímé levé rekurze)
Buď G = (N, Σ, P, S) bezkontextová gramatika v níž všechna A-pravidla (A ∈ N) jsou tvaru:
(∗) A → Aα1 | Aα2 | · · · | Aαn | β1 | β2 | · · · | βk,
kde každý řetěz βi začíná jiným symbolem než A.
Nechť G = (N ∪ {A }, Σ, P , S), kde pravidla (∗) nahradíme takto:
A → β1 | β2 | · · · | βk | β1A | β2A | · · · | βkA
A → α1 | α2 | · · · | αn | α1A | α2A | · · · | αnA
Pak L(G) = L(G ).
2
Příklad 2.
Eliminujte přímou levou rekurzi z gramatiky G = ({E, T, F}, {+, ∗, i, (, )}, P, E), kde množina
pravidel
P = {E → E + T | T
T → T ∗ F | F
F → (E) | i}
Řešení. Po pozorném prozkoumání pravidel zjistíme, že přímá levá rekurze je u pravidel
E → E + T, T → T ∗ F.
1. Místo E-pravidel E → E + T | T dosadíme nová E a E -pravidla:
E → T | TE
E → +T | +TE
2. Místo T-pravidel T → T ∗ F | F dosadíme nová T a T -pravidla:
T → F | FT
E → ∗F | ∗FT
Výsledná gramatika G = ({E, T, F, E , T }, {+, ∗, i, (, )}, P , E), kde množina pravidel
P = {E → T | TE
E → +TE | +T
T → F | FT
T → ∗F | ∗FT
F → (E) | i}
neobsahuje přímou levou rekurzi a platí L(G) = L(G ).
Poznámka.
Je důležité si uvědomit, že použitý algoritmus funguje tak, že zachovává jazyk obou gramatik,
tj. L(G) = L(G ). V původní gramatice G jsme mohli mít např. tuto derivaci:
(1) E ⇒ E + T ⇒ E + T + T ⇒ T + T + T
Tedy: používali jsme pravidlo E → E + T, které zapřičiňuje, že E je levorekurzivní. Derivaci
(1) nahradíme v nové gramatice takto:
(2) E ⇒ TE ⇒ T + TE ⇒ T + T + T
Snad je zřejmě, že pravidlo E +T můžeme používat, kolikrát chceme, avšak poté stejně musíme
zvolit jiné nerekurzivní pravidlo (E → T), abychom směřovali k výsledku, tj. terminálnímu
řetězu.
Nová pravidla fungují opačně: nejdříve použijeme nerekurzivní pravidlo (E → TE ) a poté
původní levou rekurzi nahrazujeme odvozením pomocí pravidla (E → +TE ), kde E je pravorekurzivní.
Nahrazujeme tedy levou rekurzi za pravou...
3
Příklad 3.
Eliminujte přímou levou rekurzi z gramatiky G = ({S, A, B, C}, {a, b}, P, S), kde
P = {S → AB | ε,
A → abB | Aa | AbbC | aC | BC | ba
B → BC | BbA | Ab | bbb,
C → CAb | AAA | aba}
Algoritmus (odstranění levé rekurze)
Vstup: Vlastní CFG G = (N, Σ, P, S)
Výstup: Ekvivalentní gramatika bez levorekurzivních neterminálů
Uspořádej libovolně množinu N – N = {A1, A2, . . . , An}
for i := 1 to n do
for j := 1 to i − 1 do
foreach pravidlo tvaru Ai → Ajα do
použij lemma o substituci a přidej pravidlo Ai → β1α | β2α | · · · | βkα
(kde Aj → β1 | β2 | · · · | βk jsou všechna Aj-pravidla);
vypusť pravidlo Ai → Ajα.
od
od
foreach pravidlo tvaru Ai → Aiα do
odstraň přímou levou rekurzi
od
od
Poznámka.
1. V předchozím algoritmu byly použity symboly α, β1, . . . , βk, které značí libovolný řetězec
terminálů a neterminálů.
2. Algoritmus je korektní v tom smyslu, že nemění jazyk generovaný původní gramatikou.
Vysvětlení je nasnadě: používá pouze lemma o substituci a lemma o odstranění přímé levé
rekurze. O těchto dvou postupech víme, že zachovávají jazyk.
Poznámka.
Ještě si algoritmus slovně popíšeme. Skládá se v podstatě ze tří částí:
1. uspořádání neterminálů – není důležité, jakým způsobem neterminály uspořádáme, musíme
však toto pořadí v další části algoritmu dodržet.
2. procházení množiny neterminálů od prvního k poslednímu a aplikace následujících dvou
kroků:
2a) lemma o substituci: máme-li množinu neterminálů uspořádanou (N = {A1, A2, . . . , An}),
pak tento krok nemusíme dělat pro A1. U ostatních neterminálů Ai (2 ≤ i ≤ n) postupujeme
tak, že sledujeme všechna Ai-pravidla tvaru Ai → Ajα, kde j < i, tj.
hledáme pravé strany Ai-pravidel začínající na nějaký neterminál v uspořádání před
Ai. Pokud takové pravidlo najdeme, provedeme jeho substituci. Velmi důležité je,
4
že pravé strany nahrazujeme postupně od 1. do i − 1-tého neterminálu, nemůžeme
měnit pořadí substitucí. Neméně podstatný je fakt, že každá nová množina pravidel
vzniklá díky substituci již slouží jako vstup pro další substituci.
2b) odstranění přímé levé rekurze: po provedení kroku 2a může neterminál Ai obsahovat
pouze přímou levou rekurzi, tj. pravidla tvaru Ai → Aiα. Tento druh rekurze
odstraníme pomocí lemmatu o odstranění přímé levé rekurze.
Příklad 4.
Odstraňte levou rekurzi z gramatiky G = ({S, X, Y }, {a, b, c, d}, P, S), kde množina pravidel
P = {S → Xc | Y d | Y b
X → Xd | a
Y → SaS}
Řešení. Nejdříve uspořádáme množinu neterminálů. Protože nezáleží na pořadí, ponecháme
jej takto: N = {S, X, Y }. Poté provádíme kroky 2a, 2b postupně pro neterminály S, X, Y :
1. Pro první neterminál S nemusíme dělat krok 2a. Ověříme tedy pouze, zda v S-pravidlech
není přítomna přímá levá rekurze. Zjistíme, že nikoliv, proto S-pravidla zůstávají beze
změny.
2. Zkoumáme další neterminál X. Zjišťujeme, že ani pro něj není třeba provést krok 2a.
Krok 2b je však nutno provést, protože je v pravidlech X → Xd. Vytvoříme tedy nový
neterminál X a původní X-pravidla nahradíme. Nová pravidla vypadají takto:
P = {S → Xc | Y d | Y b
X → a | aX
X → d | dX
Y → SaS}
3. Posledním neterminálem v pořadí je Y a jediné pravidlo Y → SaS. S je uspořádán před
Y , takže použijeme lemma o substituci. Výsledkem je:
P = {S → Xc | Y d | Y b
X → a | aX
X → d | dX
Y → XcaS | Y daS | Y baS}
Všimněte si nyní nového pravidla Y → XcaS. X je v pořadí před neterminálem Y ,
provedeme tedy ještě jednu substituci:
P = {S → Xc | Y d | Y b
X → a | aX
X → d | dX
Y → acaS | aX caS | Y daS | Y baS}
Krok 2a je hotov, přistoupíme ke kroku 2b. U pravidel Y →| Y daS | Y baS můžeme
sledovat přímou levou rekurzi. Vytvoříme nový neterminál Y a změníme Y -pravidla tak,
5
abychom rekurzi odstranili:
P = {S → Xc | Y d | Y b
X → a | aX
X → d | dX
Y → acaS | aX caS | acaSY | aX caSY
Y → daS | baS | daSY | baSY }
Výsledná gramatika G = ({S, X, X , Y, Y }, {a, b, c, d}, P , S) je bez levé rekurze a platí
L(G) = L(G ).
Poznámka.
Ještě jednou zdůrazníme, že krok 2a provádíme dle pořadí neterminálů a tak dlouho, dokud
můžeme. V předchozím příkladu 4 jste si mohli všimnout, že pro poslední neterminál Y jsme
substituci prováděli dvakrát.
Příklad 5.
Eliminujte levou rekurzi u bezkontextové gramatiky G = ({S, A, B}, {a, b}, P, S), kde množina
pravidel
P = {S → Aa | Bb | aaA | SaA | SbB
A → AAb | ab | SBb
B → Bbb | BBB | bAb}
Algoritmus (převod do GNF)
Vstup: vlastní CFG G = (N, Σ, P, S) bez levé rekurze.
Výstup: CFG G v GNF taková, že L(G) = L(G ).
Uspořádej libovolné dva neterminály A, B množiny N tak, že A << B, právě když existuje
pravidlo A → Bα, kde α ∈ (N ∪ Σ)∗
. Nechť tedy množina N = {A1, A2, . . . , An} je uspořádaná
dle <<.
for i := n − 1 downto 1 do
foreach pravidlo tvaru Ai → Ajα (j > i)
použij lemma o substituci a přidej pravidlo Ai → β1α, . . . , βkα,
kde Aj → β1 | · · · | βk jsou všechna Aj-pravidla;
vypusť pravidlo Ai → Ajα
od
od
Pro každé pravidlo nahraď libovolný terminál a ∈ Σ na 2. až poslední pozici novým neterminálem
a a přidej pravidlo a → a.
Poznámka.
Předchozí algoritmus si opět slovně popíšeme. Můžeme si jej pracovně rozdělit do tří částí,
přičemž ta prostřední bude pravděpodobně nejnáročnější.
6
1. uspořádání neterminálů – při aplikaci algoritmu pro převod do GNF již neterminály neřadíme
libovolně, avšak podle určitého pravidla. Je doporučeno, abyste si prošli celou množinu
pravidel a kdykoliv naleznete pravidlo tvaru A → Bα, kde A, B ∈ N, α ∈ (N ∪ Σ)∗
,
tak si zapište nerovnost A << B. Jakmile budete mít souhrn všech nerovností <<, můžete
přistoupit k vytvoření uspořádání.
2. aplikace lemmatu o substituci – procházíme neterminály v opačném pořadí, tj. od posledního
n-tého k prvnímu. Začínáme (n − 1)-tým neterminálem v pořadí a hledáme pravidlo
tvaru An−1 → Anα. Pokud jej nalezneme, uplatníme lemma o substituci a místo pravé
strany Anα vložíme β1α | · · · | βkα, kde An → β1 | · · · | βk jsou všechna An-pravidla.
Podobným způsobem postupujeme dále. Je potřeba mít neustále na paměti, že každou
substituci pro i-tý neterminál je potřeba uvažovat pro neterminály s nižším číslem. Tj.
novou množinu pravidel vždy zahrneme do dalších operací!
3. „očárkování – výsledná gramatika může obsahovat pravidla, která mají na 2. až poslední
pozici pravé strany libovolný terminál x ∈ Σ. To nevyhovuje definici Greibachové normální
formy. Pravidla tedy upravíme tak, že každý výskyt x nahradíme novým neterminálem x
a přidáme pravidlo x → x.
Příklad 6.
Převeďte gramatiku G = ({A, B, C, D}, {a, b}, P, A) do Greibachové normální formy.
P = {A → BC,
B → CD | AB,
C → Aa | b,
D → ba | DD}
Řešení. Pozorný čtenář si zajisté všimne, že gramatika G obsahuje levou rekurzi. Např. pravidlo
D → DD je ukázkou přímé levé rekurze. Převodem na gramatiku bez levé rekurze dostaneme
následující gramatiku G1 = ({A, B, C, D}, {a, b}, P1, A), kde
P1 = {A → BC
B → CD | CDB
B → CB | CBB
C → b | bC
C → DCa | DB Ca | DCaC | DB CaC
D → ba | baD
D → D | DD }
Nyní nás čekají postupně 3 úkoly: uspořádání, poté substituce a na konci očárkování.
1. Postupným procházením pravidel P1 zjistíme následující nerovnosti:
A << B, B << C, B << C, C << D, D << D. Všimněte si nyní, že neterminály
C, D jsou v nerovnostech vždy napravo, tudíž by měly být největší. Následné uspořádání
můžeme provést například takto: N = {A, B, B , C , D , C, D}.
2. Nyní postupujeme od neterminálu D až k neterminálu A. Neterminál D ponecháme beze
změny. Taktéž C není potřeba upravovat, obsahuje pravidla začínající terminály. Dalším v
7
pořadí je D . U něj již budeme muset použít substituci, protože pro pravidla D → D | DD
platí, že D << D. Zapišme tedy D -pravidla znovu:
D → ba | baD | baD D
Přecházíme k neterminálu C . I zde musíme použít substituci, a to hned u všech 4 C -
pravidel:
C → baCa | baB Ca | baCaC | baB CaC | baD Ca | baD B Ca | baD CaC | baD B CaC
Nyní neterminál B a jeho pravidla B → CB | CBB . Z uspořádání je patrné, že B << C,
použijeme tedy opět substituci:
B → bB | bC B | bBB | bC BB
Pokračujeme neterminálem B a je to obdobné jako u B . Pravidla B → CD | CDB
nahradíme:
B → bD | bC D | bDB | bC DB
Posledním neterminál, který máme prozkoumat, je A. Jeho jediné pravidlo A → BC
splňuje nerovnost A << B, tj. musíme jej nahradit. Za neterminál B však dosadíme
postupně 4 nové pravé strany B-pravidel!
A → bDC | bC DC | bDB C | bC DB C
3. Třetím krokem je očárkování, které provedeme a rovnou podáme výslednou množinu pravidel
P :
A → bDC | bC DC | bDB C | bC DB C
B → bD | bC D | bDB | bC DB
B → bB | bC B | bBB | bC BB
C → ba Ca | ba B Ca | ba Ca C | ba B Ca C | ba D Ca | ba D B Ca | ba D Ca C | ba D B Ca C
D → ba | ba D | ba D D
C → b | bC
D → ba | ba D
Příklad 7.
Převeďte bezkontextovou gramatiku G = ({S, X, Y }, {5, 6}, P, S) do Greibachové normální
formy.
P = {S → 55 | X66
X → 56 | S6
Y → 65 | S5Y }
Věta.
K libovolné bezkontextové gramatice existuje jazykově ekvivalentní CFG v Greibachové normální
formě.
8