Transformace na LL(1)

Transformace na LL(1) gramatiku je postup, jak gramatiku upravit na gramatiku LL(1). To je taková gramatika, která nemá konflikty v rozkladové tabulce. Ne všechny gramatiky lze převést na LL(1), takže aplikace této transformace nemusí vést k požadovanému výsledku.

Pravidla transformace

Pro transformaci se používají čtyři pravidla, každé pravidlo odstraňuje nějaký konflikt v rozkladové tabulce.

1. odstranění levé rekurze

Levá rekurze se pozná tak, že pravidlo začínající Neterminálem má tento Neterminál na prvním místě na pravé straně pravidla.
Mějme následující gramatická pravidla (Neterminály: {A,B} Terminály {a,b,c}) :

pravidlo	first	poznámka
A → AaB	b,c	zde je levá rekurze
A → b	b
A → c	c
B → c	c
B → ac	a

Postup:

1. V pravidle, kde se vyskytuje levá rekurze vyjmu Neterminál na první pozici v pravé straně pravidla (v tomto případě A) a na konec pravidla dám nový Neterminál (v tomto případě A') a na začátek pravidla místo (A) dám (A')
2. Ostatní pravidla začínající tímto Neterminálem (A) opíšu a nakonec jim přidám nový Neterminál (A')
3. Doplním epsilon pravidlo pro nový Neterminál (A')

Upravená gramatická pravidla (Neterminály: {A,A',B} Terminály {a,b,c,epsilon}) :

pravidlo	first	poznámka
A' → aBA'	a	I. odebral se Neterminál A a nakonec se přidal Neterminál A', upravení first
A → bA'	b	II. přidal se neterminál A'
A → cA'	c	II. přidal se neterminál A'
B → c	c
B → ac	a
A' → epsilon	epsilon	III. nové epsilon pravidlo

2. levá faktorizace

Tímto pravidlem se odstraňuje konflikt first-first
Mějme následující gramatická pravidla (Neterminál: {A} Terminály {a,b,c}) :

pravidlo	first	poznámka
A → ab	a
A → ac	a

Postup:
Z konfliktních pravidel utvořím nové ponecháním konfliktního Terminálu (v tomto případě a) a přidáním nového Neterminálu (v tomto případě A')
Pro nový Neterminál (A') vytvořím nová pravidla z původních konfliktních, tím že z nich odstraním konfliktní Terminál (a)

Upravená gramatická pravidla (Neterminály: {A,A'} Terminály {a,b,c}) :

pravidlo	first	poznámka
A → aA'	a	použil se konfliktní Terminál a přidal se Neterminál A'
A' → b	b	odstraněn konfliktní Terminál a
A' → c	c	odstraněn konfliktní Terminál a

3. levá rohová substituce / extrakce pravého kontextu (dosazení)

Mějme následující gramatická pravidla (Neterminál: {A,B} Terminály {a,b,c,d}) :

pravidlo	first	poznámka
A → ab	a
A → Bc	a,c	zde se musí upravit
B → ab	a
B → cd	c

Postup:
V nevyhovujícím pravidle nahradíme Neterminál na pravé straně (v tomto případě B) pravou stranou pravidel pro pravidlo B (v tomto případě ab, cd).

Upravená gramatická pravidla (Neterminály: {A,B} Terminály {a,b,c,d}) :

pravidlo	first	poznámka
A → ab	a
A → abc	a	náhrada Neterminálu B pravou stranou z B → ab
A → cdc	c	náhrada Neterminálu B pravou stranou z B → cd
B → ab	a
B → cd	c

Pro danou gramatiku jsou již pravidla pro B nedostupná a tudíž se mohou kompletně vynechat. Po aplikaci pravidla nám vznikl konflikt first-first a ten odstraníme aplikací 2. pravidla

Gramatická pravidla po odstranění first-first konfliktu (Neterminály: {A,A'} Terminály {a,b,c,d,epsilon}) :

pravidlo	first	poznámka
A → abA'	a	použili se konfliktní Terminály ab a přidal se Neterminál A'
A → cdc	c
A' → epsilon	epsilon	odstranění konfliktních Terminálů ab
A' → c	c	odstranění konfliktních Terminálů ab

4. Pohlcení Terminálu (řetězce)

Odstraňuje first-follow konflikt

Mějme následující gramatická pravidla (Neterminál: {A,B} Terminály {a,c,d,epsilon}) :

pravidlo	first	follow	poznámka
A → aBc	a		odtud se dostalo c do follow B
B → epsilon	epsilon	c
B → cd	c

Postup:
V pravidle odkud se dostal konfliktní Terminál (v tomto případě c) do follow sloučím s předcházejícím Neterminálem (v tomto případě B) tuto sloučeninu označím jako nový Neterminál (v tomto případě [Bc])
Pro nový Neterminál vytvořím pravidla ze stávajících pravidel pro Neterminál (B) a na jejich konec přidám Terminál (c)

Upravená gramatická pravidla (Neterminály: {A,B,[Bc]} Terminály {a,c,d,epsilon}) :

pravidlo	first	follow	poznámka
A → a[Bc]	a		sloučeni Neterminálu B s Terminálem c v nový Neterminál
B → epsilon	epsilon	epsilon
B → cd	c
[Bc] → c	c		pravidlo B → epsilon doplněné o Terminál c
[Bc] → cdc	c		pravidlo B → cd doplněné o Terminál c

Pro danou gramatiku jsou již pravidla pro B nedostupná a tudíž se mohou kompletně vynechat. Po aplikaci pravidla nám vznikl konflikt first-first a ten odstraníme aplikací 2. pravidla

pravidlo	first	follow	poznámka
A → a[Bc]	a
[Bc] → cB'	c		použil se konfliktní Terminál c přidal se Neterminál B'
B' → epsilon	epsilon	epsilon	odstranění konfliktního Terminálu c
B' → dc	d		odstranění konfliktního Terminálu c