V některých případech, kdy gramatika není LL1, jsme schopni tuto gramatiku zmodifikovat takovým způsobem, aby LL1 byla.

Eliminace levé rekurze

Pokud obsahuje gramatika pravidlo ve tvaru A => Ab, pak se vždy jedná o gramatiku, která není LL1. Tuto vadu na kráse lze však poměrně jenoduše vyřešit.

Mějme tedy pravidlo

A => Ab1 | Ab2 | Ab3 | c1 | c2

Tato pravidla transformujme na

A => c1A' | c2A'
A' => b1A' | b2A' | b3A' | ε

Pokud se podíváme na původní pravidlo, tak vidíme, že řetězec generovaný touto gramatikou bude vždy začínat terminálem „c1“ nebo „c2“ a za ním budou následovat terminály „b1“, „b2“ nebo „b3“. Přesně toho dosáhneme, pokud řekneme, že A přepíšeme na „c1“ nebo „c2“ a zbytek, kde zbytek (A') je buď prázdný řetězec, nebo „b1“, „b2“, „b3“ a opět zbytek (pro změnu pravá rekurze, ale ta nám nevadí).


Příklad

A => Ab | B
B => c

Řešení:
A => BA'
A' => bA'
A' => ε
B => c

Levá faktorizace

Dalším neduhem, který může naši gramatiku postihnout je kolize FIRST-FIRST způsobená stejným počátečním znakem na pravé straně (A => aB | aC). Zde je řešení ještě snazší. Stačí nám pokud všechny symboly, které nejsou první, vyčleníme pod vlastní neterminál.


Příklad

A => aB | aC | aD | ae

Transformujeme na:
A => aA'
A' => B | C | D | e

Rohová substituce

Občas se nám stane, že nelze udělat faktorizaci přímo, protože problém vede skrz další neterminál, pak není nic snazšího, než tento neterminál substituovat za jeho pravou stranu (všechny výskyty neterminálu X nahradit všemi jeho pravými stranami (často vznikne velké množství nových pravidel)).


Příklad

A => CB | aD
B => Ce
C => a | b
D => e

Řešení:
A => aB | bB | aD
B => Ce
D => e

Nyní můžeme provést levou faktorizaci:
A => aA' | bB
A' => B | D
B => Ce
C => a | b
D => e







Doporučujeme