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:
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') Ostatní pravidla začínající tímto Neterminálem (A) opíšu a nakonec jim přidám nový Neterminál (A') 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
Kategorie:Formální jazyky