IB102 – úkol 7, příklad 2 – řešení Odevzdání: 10. 11. 2014
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B}, {a, b}, P, S),
P = { S → Bb | Aa,
A → Sb | a | Bb | aA,
B → BA | Aa | b}.
Pomocí algoritmu z přednášky zkonstruujte ke gramatice G ekvivalentní nelevorekurzivní
gramatiku bez ε-pravidel. 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
15). 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řádaní neterminálů S < A < B. 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.
• 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 A:
Problémovým pravidlem je A → Sb (A → Bb je v pořádku, jelikož A < B). Toto
pravidlo tedy vypustíme a nahradíme jej pravidly A → βib, kde S → βi jsou všechna
pravidla neterminálu S . Pravidla pro A nyní vypadají následovně:
A → Bbb | Aab | a | Bb | aA
Přidáním těchto pravidel se nám však na neterminálu A objevila přímá levá rekurze
(A → Aα, kde α = ab). 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 → Bbb | a | Bb | aA | BbbA | aA | BbA | aAA ,
A → ab | abA
Pozn: Pravidla, která nezpůsobovala přímou levou rekurzi (dle notace z uvedeného
algoritmu) byli A → βi, kde β1 = Bbb, β2 = a, β3 = Bb a β4 = aA.
IB102 – úkol 7, příklad 2 – řešení Odevzdání: 10. 11. 2014
Vypracoval(a): UČO:
Skupina:
• neterminál B:
Pravidlem, které může způsobovat nepřímou levou rekurzi, je B → Aa. Po jeho
nahrazení dle algoritmu jsou pravidla pro B následující:
B → BA | Bbba | aa | Bba | aAa | BbbA a | aA a | BbA a | aAA a | b
Nyní už zbývá jenom odstranit přímou levou rekurzi na B. Postupujeme analogicky
jako při neterminálu A, čímž dostáváme:
B → aa | aAa | aA a | aAA a | b | aaB | aAaB | aA aB | aAA aB | bB ,
B → A | bba | ba | bbA a | bA a | AB | bbaB | baB | bbA aB | bA aB
Výsledná gramatika G tedy vypadá následovně:
G = ({S, A, A , B, B }, {a, b}, P , S)
P = {S → Bb | Aa,
A → Bbb | a | Bb | aA | BbbA | aA | BbA | aAA ,
A → ab | abA ,
B → aa | aAa | aA a | aAA a | b | aaB | aAaB | aA aB | aAA aB | bB ,
B → A | bba | ba | bbA a | bA a | AB | bbaB | baB | bbA aB | bA aB }.