Cesko.wiki Transformace na LL(1)
Author
Albert FloresTransformace 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. +more 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 |