IB102 – úkol 7, příklad 1 – řešení Odevzdání: 23. 11. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B}, {a, b}, P, S),
P = { S → Bb | bB | AB,
A → Sab | BB | AS,
B → AbA | ab}.
Pomocí algoritmu z přednášky zkonstruujte ke gramatice G ekvivalentní nelevorekurzivní
gramatiku. Uveďte, jaké uspořádání neterminálů jste zvolili při odstraňování nepřímé levé
rekurze a rovněž celý postup převodu. Nezapomeňte stručně zdůvodnit, proč gramatika
G splňuje vstupní podmínku uvedeného algoritmu.
K odstranění levé rekurze v gramatice G využijeme algoritmu ze šesté přednášky (slajd
16). Vstupní podmínkou algoritmu je, že gramatika musí být vlastní. Gramatika G neobsahuje
epsilon pravidla, nepoužitelné symboly a zjevně je necyklická, jelikož neobsahuje
ani jednoduchá pravidla. Gramatika G tedy splňuje vstupní podmínku.
Zvolíme uspořádání neterminálů S B A. Nyní se podíváme na každý z neterminálů
X ∈ {S, A, B} samostatně (ve výše zvoleném pořadí). Pokud se pro něj vyskytuje
pravidlo tvaru X → Y α, kde Y X, Y ∈ {S, A, B} a α ∈ {S, A, B, a, b}∗
, tato pravidla
podle algoritmu nahradíme, abychom odstranili případný výskyt nepřímé levé rekurze.
Nakonec se podíváme, jestli se na neterminálu X nevyskytuje přímá levá rekurze, kterou
také odstraníme. Závislosti neterminálů můžeme znázornit následově:
S B A
• neterminál S:
Množina P neobsahuje žádná pravidla tvaru S → Y α ani S → Sα. Žádné úpravy
tedy nejsou potřeba a množinu pravidel neměníme.
• neterminál B:
Podobně množina P neobsahuje žádná pravidla tvaru B → Y α ani B → Bα. Žádné
úpravy tedy nejsou potřeba a množinu pravidel neměníme.
• neterminál A:
Z obrázku vidíme rekurzivní závislost na neterminálech S a B a přímou rekurzivní
závislost na A. Podle algoritmu odstraníme všechny závislosti směřující doleva, tedy
postupně upravíme problémová pravidla A → Sab, A → BB, A → AS. Pravidlo
A → Sab nahradíme pravidly A → βiab, kde S → βi jsou všechna pravidla neterminálu
S.
Pravidla pro A nyní vypadají následovně:
A → Bbab | bBab | ABab | BB | AS
IB102 – úkol 7, příklad 1 – řešení Odevzdání: 23. 11. 2015
Vypracoval(a): UČO:
Skupina:
Přidáním těchto pravidel se nám však na neterminálu A objevila další problémová
pravidla A → Bbab a A → ABab. Vypustíme další pravidlo A → Bbab.
Pravidla pro A nyní vypadají následovně:
A → AbAbab | abbab | bBab | ABab | BB | AS
Odstraníme poslední pravidlo způsobující nepřímou levou rekurzi A → BB.
Pravidla pro A nyní vypadají následovně:
A → AbAbab | abbab | bBab | ABab | AbAB | abB | AS
Zbývající problémová pravidla na neterminálu A jsou A → AbAbab, A → ABab
a A → AS, která způsobují přímou levou rekurzi. Tu vyřešíme tak, že všechna
pravidla pro A odstraníme a podle algoritmu z přednášky 6 (slajd 13) je nahradíme
novými pravidly pro A a nově vzniklý neterminál A :
A → abbab | bBab | abB | abbabA | bBabA | abBA ,
A → bAbab | Bab | bAB | S | bAbabA | BabA | bABA | SA
Pozn: Pravidla, která nezpůsobovala přímou levou rekurzi, (dle notace z uvedeného
algoritmu) byla A → βi, kde β1 = abbab, β2 = bBab a β3 = abB.
Výsledná gramatika G tedy vypadá následovně:
G = ({S, A, A , B}, {a, b}, P , S)
P = {S → Bb | bB | AB,
A → abbab | bBab | abB | abbabA | bBabA | abBA ,
A → bAbab | Bab | bAB | S | bAbabA | BabA | bABA | SA ,
B → AbA | ab}.