IB102 – úkol 7, příklad 1 – řešení Odevzdání: 18. 11. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažme následující bezkontextovou gramatiku:
G = ({S, A, B, C, D, E}, {x, y, z}, P, S)
P = {S → ε | Bx,
A → Sx | DS,
B → Ay | AB | Ez,
C → xxz,
D → ε | y | ExC | ExS,
E → Ex | EA}
Převeďte gramatiku G na ekvivalentní vlastní gramatiku neobsahující levou rekurzi. Do řešení
uveďte celý postup převodu, zejména následující mezivýsledky:
• gramatiku G1 (ekvivalentní G), která neobsahuje nepoužitelné symboly;
• gramatiku G2 (ekvivalentní G1), která neobsahuje nepoužitelné symboly ani εpravidla
(nezapomeňte uvést množinu Nε obsahující všechny neterminály, které se
dají přepsat na ε);
• gramatiku G3 (ekvivalentní G2), která neobsahuje nepoužitelné symboly, ε-pravidla
ani jednoduchá pravidla;
• výslednou gramatiku G4 (ekvivalentní G3), která neobsahuje nepoužitelné symboly,
ε-pravidla, jednoduchá pravidla, nepřímou ani přímou levou rekurzi (uveďte, jaké
uspořádání neterminálů jste zvolili při odstraňování nepřímé levé rekurze).
Prvním krokem je eliminace nepoužitelných symbolů. Postupujeme podle algoritmu z přednášky
(6. přednáška, slide 9): nejdříve odstraníme nenormované symboly (slide 3), poté
odstraníme nedosažitelné symboly (slide 7). Výsledná gramatika G1 vypadá následovně:
G1 = ({S, A, B, D}, {x, y}, P1, S)
P1 = {S → ε | Bx,
A → Sx | DS,
B → Ay | AB,
D → ε | y}
Druhým krokem je odstranění ε-pravidel. Postupujeme podle algoritmu z přednášky (6.
přednáška, slide 13). Množina Nε neterminálů, které se dají přepsat na ε, je Nε =
{S, D, A}. Jelikož S ∈ Nε, musíme zavést nový iniciální neterminál S , který se bude
1
IB102 – úkol 7, příklad 1 – řešení Odevzdání: 18. 11. 2013
Vypracoval(a): UČO:
Skupina:
moct přepsat na původní iniciální neterminál S nebo na ε. Výsledná gramatika G2 vypadá
následovně:
G2 = ({S , S, A, B, D}, {x, y}, P2, S )
P2 = {S → S | ε,
S → Bx,
A → Sx | x | D | S | DS,
B → Ay | y | AB | B,
D → y}
Dalším krokem je eliminace jednoduchých pravidel. Opět použijeme algoritmus z přednášky
(6. přednáška, slide 17). Výsledkem algoritmu bude gramatika G3:
G3 = ({S , S, A, B, D}, {x, y}, P3, S )
P3 = {S → Bx | ε,
S → Bx,
A → Sx | x | y | Bx | DS,
B → Ay | y | AB,
D → y}
Zbývá nám už jenom odstranit levou rekurzi (nepřímou a přímou), opět se inspirujeme
přednáškou (7. přednáška, slidy 3–5). Neterminální symboly uspořádáme například následovně:
S < S < A < B < D.
• neterminál S :
Hledáme všechna pravidla tvaru S → Xα kde X je neterminál nacházející se v uspořádání
před S a α ∈ {S , S, A, B, D, x, y}∗
. Jelikož takové neterminály nejsou, nic
se nezmění. S nemá ani přímou levou rekurzi, množinu pravidel tedy neměníme.
• neterminál S:
Hledáme všechna pravidla tvaru S → Xα kde X je neterminál nacházející se v uspořádání
před S a α ∈ {S , S, A, B, D, x, y}∗
. Máme jedinou možnost: X = S . Jelikož
žádné pravidlo takového tvaru nemáme, nic se nezmění. S nemá ani přímou levou
rekurzi, množinu pravidel tedy neměníme.
• neterminál A:
Hledáme všechna pravidla tvaru A → Xα kde X je neterminál nacházející se v uspořádání
před A, přičemž tyto neterminály uvažujeme v pořadí daném uspořádáním,
tedy nejprve X = S , potom X = S a α ∈ {S , S, A, B, D, x, y}∗
. Pro S žádné takové
pravidlo neexistuje, pro S takové pravidlo existuje jedno (A → Sx), nahradíme
jej tedy pravidlem A → Bxx (za S jsme dosadili pravou stranu všech pravidel tvaru
S → β, β ∈ {S , S, A, B, D, x, y}∗
). Původní pravidlo A → Sx vypustíme.
Neterminál A přímou levou rekurzi nemá, další změny tedy neprovádíme.
2
IB102 – úkol 7, příklad 1 – řešení Odevzdání: 18. 11. 2013
Vypracoval(a): UČO:
Skupina:
A pravidla tedy nyní vypadají takto:
A → Bxx | x | y | Bx | DS
• neterminál B:
Hledáme všechna pravidla tvaru B → Xα kde X je neterminál nacházející se v uspořádání
před B, tedy postupně X = S , X = S, X = A a α ∈ {S , S, A, B, D, x, y}∗
.
Pro S a S taková pravidla nemáme, pro A taková pravidla máme dvě (B → Ay
a B → AB). Každé z nich nahradíme sadou pravidel vzniklých substitucí prvního
neterminálu A za pravé strany pravidel A → β, β ∈ {S , S, A, B, D, x, y}∗
. Pozor,
pravidla pro přepis neterminálu A jsme v předešlém kroku měnili, musíme použít
tuto novou množinu pravidel! Po substituci dostáváme:
B → Bxxy | xy | yy | Bxy | DSy | y | BxxB | xB | yB | BxB | DSB
Nyní musíme odstranit přímou levou rekurzi na neterminálu B. Zavedeme nový neterminál
B a podle předpisu (7. přednáška, slide 3) vytvoříme pro B a B následující
množiny pravidel:
B → xy | yy | DSy | y | xB | yB | DSB |
xyB | yyB | DSyB | yB | xBB | yBB | DSBB
B → xxy | xy | xxB | xB | xxyB | xyB | xxBB | xBB
• neterminál D:
Hledáme všechna pravidla tvaru D → Xα kde X je neterminál nacházející se
v uspořádání před D, tedy postupně X = S , X = S, X = A, X = B a α ∈
{S , S, A, B, D, x, y}∗
. Jelikož žádné pravidlo takového tvaru nemáme, nic se nezmění.
D nemá ani přímou levou rekurzi, množinu pravidel tedy neměníme.
Výsledná gramatika G4 tedy vypadá následovně:
G4 = ({S , S, A, B, B , D}, {x, y}, P4, S )
P4 = {S → Bx | ε,
S → Bx,
A → Bxx | x | y | Bx | DS,
B → xy | yy | DSy | y | xB | yB | DSB |
xyB | yyB | DSyB | yB | xBB | yBB | DSBB ,
B → xxy | xy | xxB | xB | xxyB | xyB | xxBB | xBB ,
D → y}
3