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 editovat
Pro transformaci se používají čtyři pravidla, každé pravidlo odstraňuje nějaký konflikt v rozkladové tabulce.
1. odstranění levé rekurze editovat
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 editovat
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í) editovat
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) editovat
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 |