Transformace na LL(1)

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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 jdou převést na LL(1), takže aplikace této transformace nemusí vést k požadovanému výsledku.

Pravidla transformace[editovat | editovat zdroj]

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 | editovat zdroj]

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:
I. 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')
II. Ostatní pravidla začínající tímto Neterminálem (A) opíšu a nakonec jim přidám nový Neterminál (A')
III. 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' b,c I. odebral se Neterminál A a nakonec se přidal Neterminál A'
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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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