IB102 - úkol 10, příklad 1
Odevzdání: 3.12. 2012
Vypracoval (a): UČO: Skupina:
1. [2 body] Z následující vlastní bezkontextové gramatiky odstraňte levou rekurzi.
G=({S,A,B},{a,b},P,S)
P = {   S  -+  SAb | SaS | aB, A  ->•  AAa | SS | a, B  ->  Aab | SaS | 6}
Řešení:  Zvolíme uspořádání A < B < S.
• U neterminálu A nemáme nepřímou levou rekurzi, máme zde však přímou. Tu odstraníme.
A  ->  SS | a | SSA' | a A',
Nový neterminál A' zařadíme do našeho uspořádání: A' < A < B < S.
• U neterminálu B nejprve odstraníme nepřímou levou rekurzi a dostáváme:
B —>  SSab | aab | SSA'ab | aA'ab | SaS \ b, Nemáme zde žádnou přímou levou rekurzi a tudíž jsme hotovi.
• U neterminálu S nemáme nepřímou levou rekurzi a odstraníme tedy rovnou přímou levou rekurzi:
S  ->  aB | aBS',
S'  -> |      | a^S" | aS
Nový neterminál S" zařadíme do našeho uspořádání: S' < A' < A < B < S.
Celkově vypadá gramatika po odstranění levé rekurze takto:
G = ({S, A, B, A', S'}, {a, b}, P, S)
P = {   S -> aB | aBS',
S' -> AbS' | Ab | aSS' | aS,
A -> 55 | a | SSA' | aA',
A' ->• AaA' | Aa,
-B —y SSab \ aab \ SSA'ab | aA'ab \ SaS \ b}