7.10 Odstraňte levou rekurzi a transformujte do GNF G = ({S.A,B}.{a.b}.P.S), kde P = { S -» Aa j Bb | aaA A -» AAh | (té | .SUfr, b -> bm I bbs I 6.46 ' | SaA | SbB, Odstranění levé rekurze 1. Zkontroluj, že na vstupu je vlastní gramatika; pokud ne, nejprve transformuj vstupní gramatiku na vlastní - ,/ > Gramatika je OK 2. Uspořádej neterminály a nakresli si pomocný graf > Pomocný graf: neterminály nakreslit pod sebe ve zvoleném uspořádání, „nejmenší" je nahoře; hrana vede z X do Y, pokud pro X existuje pravidlo, v němž nejlevější symbol je Y > Neterminály lze uspořádat libovolně, ale hodí se zvolit uspořádání s co nejmenším počtem „zpětných šipek" v grafu ">- Volím uspořádání S \>;r,A' 7.10 Odstraňte levou rekurzi a transformujte do GNF (t = ;{>'..I./.'}.{.;./,}./" s\i. kde P-{S -» Áa | B6 | ««.4 ' .4 -» .4-46 \ ab | SB6. d -f sm i /;/;/.; | háb) I I ShB. Odstranění levé rekurze 3. Procházej neterminály v daném uspořádání od nejmenšího („nahoře" v grafu) a hledej pravidla začínající menším neterminálem - ta potřebujeme transformovat, aby se zamezilo vzniku rekurze. V grafu to odpovídá hledání zpětných šipek. Nejprve odstraňujeme nejdelší zpětnou šipku, pak další. > U prvního neterminálu nemůže být zpětná šipka, ale může být přímá rekurze. > L) S Je přímá levá rekurze, odstraníme dle algoritmu a upravíme graf. Nový neterminál S' zařadíme na začátek uspořádání, protože tím nám nemůže vzniknout žádná zpětná hrana - S' nikdy není nejlevějšim symbolem pravidla P = { S .4 B Au .4.46 b66 ah j SBb, BBB I bAb } SaA | SbB. ÍS S' A Aa | Bb | aaA | AaS' | BbS' | aaAS', aA j W ] aAS' | bBS', AAb | ab \ SBb, Bbb | BBB | bAb} Algoritmus odstranění levé rekurze Vstup: Vlastni CFG £ = (N. Z. P. S) Výstup: Ekvivalentní neievorekursívní gramatika bez s-pravidel Uspořádej libovolně N, N = {A,.....Ar) for /«-1 to ndo for y *- 1 to i - 1 do for all pravidlo tvaru A, -i A,r> do přidej pravidla A, -»[... |,%« (kde A/ -* -;\ j... j ii* jsou všechna pravidla pro A) vypusť pravidlo A; -» Á/u end for end for odstraň případnou přímou levou rekursi na A, end for Algoritmus odstranění přímé levé rekurze Nechť CFG Q = (N. I. P. S) je necyklická a bez .--pravidel, v niž všechna A-pravidla (pravidla majicí na levé straně A) jsou tvaru A~f Ai, | ... | Artm | 7, | ... i i„, kde každý řetěz tfj začíná symbolem různým od A. Nechf e' = (Wu {A'}. Z. P, S), kde F obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly: a, j. . I "m I '>,A' . | .í„A' Pak L(c?) = L(rj') a i,' je necyklická a bez r-pravidel. 7.10 Odstraňte levou rekurzi a transformujte do GNF O = ({$, A,B}.{u.b}.P. Sj, kde /' = { $ > M \ Bb | 0aA A -> AAb I ab | SBh. B -+ £M< I /J/JC | 6.46 } | SuA | 56C. Odstranění levé rekurze 3. Procházej neterminály v daném uspořádání od nejmenšího („nahoře" v grafu) a hledej pravidla začínající menším neterminálem - ta potřebujeme transformovat, aby se zamezilo vzniku rekurze. V grafu to odpovídá hledání zpětných šipek. Nejprve odstraňujeme nejdelší zpětnou šipku, pak další. > Po zpracování S je na řade A, nejdřív řešíme nejdelší zpětnou šipku do S. Jejím odstraněním vznikne nová šipka z A do B. P=(S S' A B Art | Bb | aaA | AaS' \ BbS' | aaAS', aA | bB | MS' | bBS', AAb | ab | SBb, Bbb | BBB | bAb} ÍS S' A Aa | Bb | aaA | AaS' | BbS' | rtrtAS', aA | M | rzAS' | bBS', AAb | rtb | ArtBb | BbBb \ aaABb \ AaS'Bb | BbS'Bb | rtrtAS'Bb, Bbb | BBB | bAb j S' A B Algoritmus odstranění levé rekurze Vstup: Vlastni CFG 5 = (W. I. PS) Výstup: Ekvivalentní nelevorekursivní gramatika bez ^-pravidel Uspořádej iibovolné N, N = {A,.....A,,} for / «- 1to n do for / 1 to i - 1 do for all pravidlo tvaru A, -* A,n do 5: přidej pravidla Aj -* tv j... j %« 6: (kde A; -> j... i -i* jsou všechna pravidla pro A) 7: vypusť pravidlo A, -> Aja end for end for odstraň připadnou přímou levou rekursi na A end for Algoritmus odstranění přímé levé rekurze Necht CFG Q = (M I. P. S) je necyklická a bez i-pravidel, v níž všechna A-pravidía (pravidla mající na levé strane A) jsou tvaru a-, Ai, | ... I Ai,„| í, |... | in, kde každý řetěz ^ začíná symbolem různým od a. Nechť Q1 - (A/u {a1}. Z. P. S), kde P' obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly: a > J, | ... , i„ M? I V*' /#->«,;)... i <■„, i .,,a ... i ,,,„a' Pak /.(£?) = L(í') a e' je necyklická a bez .-pravidel. 7.10 Odstraňte Levou rekurzi a transformujte do GNF G = ({S. A,B},{a.b}.P.S), kde P = { S -» Aíí ! Bft | ««.4 A -í AAb i «/- | SB4, /; -i Bbb \ BBB \ b Ah } SbB, I. Odstranění levé rekurze 3. Procházej neterminály v daném uspořádání od nejmenšího („nahoře" v grafu) a hledej pravidla začínající menším neterminálem - ta potřebujeme transformovat, aby se zamezilo vzniku rekurze. V grafu to odpovídá hledání zpětných šipek. Nejprve odstraňujeme nejdelší zpětnou šipku, pak další. > V dalším kroku řešíme přímou rekurzi na A, nový neterminál A' opět zařadíme na začátek uspořádání ,-------------, (S S' A B Art | Bb | rtrtA | AaS' | BbS' | aaAS', aA | bB | rtAS' | bBS', AAb | ab \ AaBb \ BbBb | aaABb | ArtS'Bb BbS'Bb I rtrtAS'Bb, Bbb I BBB | bAb} {$ -S' -A ■ A' Aa | Bb | rtrtA | ArtS' | BbS' | rtrtAS', rtA | bB | nAS' | bBS', ab I BbBb | rtnABb | BbS'Bb | rtrtAS'Bb | rtbA' BbBbA' | aaABbA' | BbS'Bb A^. \ íuiAS'jjbA', Ab | rtBb | rtS'Bb | AbA' \ aBbA1 \ aS'BbA', Bbb | BBB | bAb} S' Algoritmus odstranění levé rekurze Vstup: Vlastní CFG Q = [N.Z.P, S) Výstup: Ekvivalentní nelevorekursivní gramatika bez .-pravidel Uspořádej libovolné /V. n = {at.....A) for ŕ«-1 to n do tor/*- 1 to/ —1 do for all pravidlo tvaru A, — An do přidej pravidla A; —^ - * i *.i i... | akt* (kde a. ^ j... i jsou všechna pravidla pro A) vypusť pravidlo a{ -> A(.,i end for end for odstraň připadnou přímou levou rekursi na A, end for Algoritmus odstranění přímé levé rekurze Nechť CFG Q - (N. Z. P. S) je necyklická a bez -pravidel, v níž všechna A-pravidla (pravidla mající na levé straně A) jsou tvaru A ~r Ai, | .. j A,,,,! i, | ... | ■;„, kde každý řetěz :* začíná symbolem různým od A. Nechť g' = (Nu {A'}. Z. P. S), kde P' obdržíme z P tak, že všechna výše uvedena pravidla nahradíme pravidly: A -» A' -ř ' . líMřMn I <„A' Pak - /.((?') a Q' je necyklická a bez r-pravidel. 7.10 Odstraňte levou rekurzi a transformujte do GNF G = ({S.A,B}.{u.h}.P.S), kde p = { s -> Aa | Db | aaA A AAb | ab | SDb. D -t Bbb i BBB | 6.46 } | SaA | SbB I. Odstranění levé rekurze 3. Procházej neterminály v daném uspořádání od nejmenšího („nahoře" v grafu) a hledej pravidla začínající menším neterminálem - ta potřebujeme transformovat, aby se zamezilo vzniku rekurze. V grafu to odpovídá hledání zpětných šipek. Nejprve odstraňujeme nejdelší zpětnou šipku, pak další. Poslední krok - přímá rekurze na B P = (S -§' -A - A' - Aa | Bb | aaA \ AaS' \ BbS' | aaAS', aA I bB | aAS' \ bBS', ab | BbBb \ aaABb \ BbS'Bb | aaAS'Bb \ abA' \ BbBbA' | aaABbA' \ BbS'BbA' \ aaAS'BbA', Ab | aBb \ aS'Bb | AbA' | aBbA' \ aS'BbA', Bbb | BBB I bAb} (S S' ■ A A' - Aa | Bb | aaA | AaS' | BbS' | aaAS', aA \ bB \ aAS' \ bBS', ab | BbBb \ aaABb \ BbS'Bb \ aaAS'Bb | abA' \ BbBbA' | aaABbA' \ BbS'BbA' \ aaAS'BbA', Ab | aBb \ aS'Bb | AbA' \ aBbA' \ aS'BbA', bAb | bAbB', bb | BB | bbB' | BBB'} Algoritmus odstranění levé rekurze Vstup: Vlastní CFG g = (N, E. P. S) Výstup: Ekvivalentní nelevorekursivní gramatika bez '-pravidel i: Uspořádej libovolně N, N - {A.....A„\ 2. for / *- 1 to n do 3: for /«- 1 to / - 1 do 4: for all pravidlo tvaru A A'1 do 5: přidej pravidla A — i?" i ■ ■ ■ í 6: (kde Aj -> ^ |... i ik jsou všechna pravidla pro A) 7: vypusť pravidlo A, -> A(-.> 8: end for 9: end for 10: odstraň připadnou přímou levou rekursi na A; 11: end for Algoritmus odstranění přímé levé rekurze Nechť CFG g = {N. Z. P. S) je necyklická a bez :-pravjdel. v niž všechna Apravídla (pravidla majicí na levé straně A) jsou tvaru A^A,U |...|A,,„j *,),..) kde každý řetěz začíná symbolem různým od A. Nechť g' = {Nu {A'). I. P. S), kde P obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly: A- Ä - f,A |... | ;i„A' ■,,A j... | ,imA Pak L{G) - L{Q') a Q' je necyklická a bez .--pravidel. 7.10 Odstraňte levou rekurzi a transformujte do GNF = {{s..(./;}.{..'./.../'. kde P = { S -i Aa \ Bb | -m.4 .4 .4.46 j ab | s7;.'.. B -> i /;/;/; j bAb} Transformace do GNF 1. Použij uspořádání z předchozího kroku. Postupně ber neterminály od největšího a zpracovávej jejich pravidla tak, že pokud pravidlo začíná neterminálem X, tento neterminál se nahradí všemi pravými stranami pravidel pro X. > Největší neterminál v našem uspořádání je B. Po odstranění rekurzí z něj nemohou vést zpětné šípky ani smyčky, takže B nemůže mít pravidlo začínající neterminálem. Pravidla pro B se nemění. > Dalším neterminálem je A. A může mít pravidla začínající B. Taková pravidla transformujeme: P = {S S' A A' B B' P = {S S' A A' B B' Aa | Bb | aaA | AaS' \ BbS' | aaAS', aA | bB | aAS' | bBS', ab | BbBb \ aaABb | BbS'Bb \ aaAS'Bb | abA' BbBbA' | aaABbA' | BbS'BbA' \ aaAS'BbA', Ab | íiBb | aS'Bb | AbA' \ aBbA' | aS'BbA', bAb | bAbB', bb \ BB | bbB' | BBB' j Aa | Bb | aaA | AaS' | BbS' | íí«AS', nA | bB | íl4S' I bBS', ab | MbbBb | bAbB'bBb \ aaABb \ bAbbS'Bb \ bAbB'bS'Bb \ aaAS'Bb | abA' | bAbBbA' | bAbB'bBbA' | aaABbA' | bAbbS'BbA' \ bAbB'bS'BbA' | aaAS'BbA', Ab | aBb | nS'Bfc | AM' | flB6A' | flS'BfcA', bAb | bAbB', bb | BB | bbB' | BBB' / B' - A' S' A < B «" 7.10 Odstraňte levou rekurzi a transformujte do GNF G = {{S. A, £?}.{«. b}.P, 5), kde P=(S -+ .4,; i Db ' | AAb | ab | &B6. ZJ -+ Bbb D D H bAb } SW3, Transformace do GNF 1. Použij uspořádání z předchozího kroku. Postupně ber neterminály od největšího a zpracovávej jejich pravidla tak, že pokud pravidlo začíná neterminálem X, tento neterminál se nahradí všemi pravými stranami pravidel pro X. > ... (zpracuj zbvté neterminály) .—..........., ! B' : A' | S' S A B 2. Všechny terminály s výjimkou terminálů na začátcích pravidel nahraď novými neterminály a doplň potřebná pravidla pro nové neterminály > Výsledné pravidla pro B: B -* bA | bAB', -» b vw ■