Fordítóprogramok feladatgyűjtemény

Aszalós, László

Herendi, Tamás

DEIK
Debreceni Egyetem
Informatikai Kar


            Debrecen
            4032
            Egyetem tér 1
          

Új Széchenyi Terv logó.

A tananyag a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-magyarországi Informatika Tananyag Tárház projekt keretében készült. A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával valósult meg.

A Kelet-magyarországi Informatika Tananyag Tárház logója.

Magyarország megújul logó.

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

Az EU logója.

2010


Tartalom

Előszó
1. Feladatok
Reguláris kifejezések
Reguláris kifejezéseket felismerő nemdeterminisztikus automaták
Nemdeterminisztikus automaták determinizálása
Determinisztikus automaták minimalizálása
Balrekurzió megszüntetése
Általános felülről-lefelé elemzés
LL(1) elemzés
Általános alulról-felfelé elemzés
Operátorprecedencia elemzés
Egyszerű precendecia elemzés
LR(0) elemzés
SLR elemzés
LR(1) elemzés
LALR elemzés
2. Megoldások
Reguláris kifejezések
Reguláris kifejezéseket felismerő nemdeterminisztikus automaták
Nemdeterminisztikus automaták determinizálása
Determinisztikus automaták minimalizálása
Balrekurzió megszüntetése
Általános felülről-lefelé elemzés
LL(1) elemzés
Általános alulról-felfelé elemzés
Operátorprecedencia elemzés
Egyszerű precedencia elemzés
LR(0) elemzés
SLR elemzés
LR(1) elemzés
LALR elemzés
Bibliográfia

Végszó

A tananyag a Kelet-magyarországi Informatika Tananyag Tárház projekt keretében készült.

A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával valósult meg.

Kelet-magyarországi Informatika Tananyag Tárház logója

Az Európai Únió logója

Előszó

Az elmúlt negyven évben szinte megszámlálhatatlanul sok olyan program készült, melyekkel fordítóprogramokat vagy értelmezőket készíthetünk, forrásprogramok szövegét alakíthatjuk, formálhatjuk át. Ezen programok hatékony használatához elengedhetetlen a fordítóprogramok elméleti alapjainak készségszintű ismerete. Napjainkban nagy számban férhetünk hozzá magyar és angol nyelvű szakirodalomhoz a témakörben, az így megszerzett elméleti ismeretek elmélyítéséhez szükséges feladatgyűjtemények létezéséről viszont nem tudunk. Ezt a hiányt szeretnénk a jelen kiadvánnyal pótolni.

A példatár létrehozása során a Debreceni Egyetemen tartott gyakorlatok tematikáját követtük, az ott előforduló feladatokat válogattuk a kötetbe. Az elektronikus megjelenési forma lehetőségeit kihasználva apróbb filmekkel mutatjuk be az egyes típusfeladatok megoldásait, vagy a megoldások kezdő lépéseit.

A tananyag önálló feldolgozása esetén javasoljuk a JFLAP valamint Parsing Simulator programok használatát. Az előbbi programrendszer Java alapú, így szinte mindenütt futtatható és igen szemléletesen ábrázolja az automatákat és a gráfokat. A jelölésrendszere és a benne megvalósított algoritmusok sok helyen eltérnek az általunk használtaktól, az eltérésekre a kellő helyeken kitérünk.

Várjuk az olvasók megjegyzéseit, a hibák bejelentését, hogy a további kiadásokat ezek szerint javíthassuk.

1. fejezet - Feladatok

Reguláris kifejezések

  1. Adjon meg egy {a,b} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv szavai pontosan két a betűt tartalmaznak! Megoldás

  2. Adjon meg egy {a,b} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv szavai legalább két a betűt tartalmaznak! Megoldás

  3. Adjon meg egy {a,b} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv szavai legfeljebb két a betűt tartalmaznak! Megoldás

  4. Adjon meg egy {a,b} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv szavainak harmadik betűje b! Megoldás

  5. Adjon meg egy {a,b,c} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv szavainak hossza legalább kettő és második betűje nem b! Megoldás

  6. Adjon meg egy {a,b,c} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv szavai páros sok mássalhangzót tartalmaznak! Megoldás

  7. Adjon meg egy {a,b} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv szavaiban a b betű páros hosszú sorozatokban fordul elő! Megoldás

  8. Adjon meg egy {p,k,d,[,]} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv a diszjunktív normálformák nyelve! Jelölje a literálokat a p, a konjunkció és diszjunkció műveletét a k és d! Az elemi konjunkciókat záró zárójeleket szögletes zárójelekkel jelöljük. Megoldás

  9. Adjon meg egy {a,b,c} ábécé feletti reguláris kifejezést, amely által reprezentált nyelv szavai a betűvel kezdődnek és nem tartalmaznak dupla betűt! Megoldás

Reguláris kifejezéseket felismerő nemdeterminisztikus automaták

[Megjegyzés]Megjegyzés

Thompson algoritmusát igen sok módon írják le, s így bár ekvivalens, de eltérő méretű nemdeterminisztikus automatákat kapunk. Például a JFLAP algoritmusa a következő megoldást generálja az (ab+a)* reguláris kifejezés esetén:

JFLAP által generált nemdeterminisztikus automata 12 állapottal

Az általunk követett algoritmus ennél kicsit takarékosabb, ezért is javasoljuk ezt a módszert.

Mi módszerünkkel készített automata 9 állapottal

Először lássuk, hogy hogyan kell elkészíteni az (ab+a)* reguláris kifejezést felismerő nemdeterminisztikus automatát! (www.inf.unideb.hu/~aszalos/diak/fordito/re.html)

  1. Készítsen el egy az ab*+a*b reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  2. Készítsen el egy az ab*+bc*+ca* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  3. Készítsen el egy az a(a*+b*)b reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  4. Készítsen el egy az (a+b)*(b+a)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  5. Készítsen el egy az (a*ba*b)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  6. Készítsen el egy a b*ab*ab* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  7. Készítsen el egy az ((a+b)(b+a))* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  8. Készítsen el egy az a*b*c reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  9. Készítsen el egy az ((a*+b)*c)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  10. Készítsen el egy az ab*a+a*ba* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  11. Készítsen el egy az (a+bb)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  12. Készítsen el egy az a*((b+c)a*(b+c)a*)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  13. Készítsen el egy az (a+b+c)(a+c)(a+b+c)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  14. Készítsen el egy az (a+b)(a+b)b(a+b)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  15. Készítsen el egy a b*ab*a(a+b)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  16. Készítsen el egy a b*(a+λ)b*(a+λ)b* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  17. Készítsen el egy a [p(kp)*](d[p(kp)*])* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  18. Készítsen el egy az (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

Nemdeterminisztikus automaták determinizálása

[Megjegyzés]Megjegyzés

A JFLAP program ismeri a determinizálás algoritmusát, gombnyomásra újabb és újabb állapotait készíti el a determinisztikus automatának. Ha a korábbi automatánkból indulunk ki, a JFLAP futásának végeredménye a következő lesz:

JFLAP által generált determinisztikus automata

Érzésünk szerint ebben az esetben, a megoldások során kényelmesebben használható a táblázat, melyet a nemdeterminisztikus automata alapján készítünk el, és nincs szükség arra, hogy rajzos formában ábrázoljuk. A megoldásainkat is táblázatként adjuk meg. Persze előnyös a gráfok használata, segít megérteni az automaták működését.

Az alábbi feladatokban zöld színnel jelöltük a kezdőállapotot és pirossal a végállapotot. A λ-átmeneteknél nem írtuk ki a λ jelet a nyilakra.

Nézzük először, hogy az előző szakasz bemutató példájában megoldásként kapott nemdeterminisztikus automatát hogyan lehet determinizálni! (www.inf.unideb.hu/~aszalos/diak/fordito/re2fsa.html)

  1. Determinizálja az alábbi automatát! Megoldás

    ab*+a*b reguláris kifejezés automatája

  2. Determinizálja az alábbi automatát! Megoldás

    ab*+bc*+ca* reguláris kifejezés automatája

  3. Determinizálja az alábbi automatát! Megoldás

    a(a*+b*)b reguláris kifejezés automatája

  4. Determinizálja az alábbi automatát! Megoldás

    (a+b)*(b+a)* reguláris kifejezés automatája

  5. Determinizálja az alábbi automatát! Megoldás

    (a*ba*b)* reguláris kifejezés automatája

  6. Determinizálja az alábbi automatát! Megoldás

    b*ab*ab* reguláris kifejezés automatája

  7. Determinizálja az alábbi automatát! Megoldás

    ((a+b)(b+a))* reguláris kifejezés automatája

  8. Determinizálja az alábbi automatát! Megoldás

    a*b*c reguláris kifejezés automatája

  9. Determinizálja az alábbi automatát! Megoldás

    ((a*+b)*c)* reguláris kifejezés automatája

  10. Determinizálja az alábbi automatát! Megoldás

    ab*a+a*ba* reguláris kifejezés automatája

  11. Determinizálja az alábbi automatát! Megoldás

    (a+bb)* reguláris kifejezés automatája

  12. Determinizálja az alábbi automatát! Megoldás

    a*((b+c)a*(b+c)a*)* reguláris kifejezés automatája

  13. Determinizálja az alábbi automatát! Megoldás

    (a+b+c)(a+c)(a+b+c)* reguláris kifejezés automatája

  14. Determinizálja az alábbi automatát! Megoldás

    (a+b)(a+b)b(a+b)* reguláris kifejezés automatája

  15. Determinizálja az alábbi automatát! Megoldás

    b*ab*a(a+b)* reguláris kifejezés automatája

  16. Determinizálja az alábbi automatát! Megoldás

    b*(a+λ)b*(a+λ)b* reguláris kifejezés automatája

  17. Determinizálja az alábbi automatát! Megoldás

    [p(kp)*](d[p(kp)*])* reguláris kifejezés automatája

  18. Determinizálja az alábbi automatát! Megoldás

    (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a reguláris kifejezés automatája

Determinisztikus automaták minimalizálása

[Megjegyzés]Megjegyzés

A JFLAP programban lépésről lépésre követhetjük az állapothalmazok felbontását az általunk követett táblázatos módszer helyett gráffal ábrázolva. A program ezután elvárja az állapothalmazok közti átmenetek megadását. A korábbi bemutató feladatunk esetén a következő ábrát kapjuk:

Determinisztikus automatánk minimalizáltja

Lássuk először, hogy a korábbi bemutató példánk determinisztikus automatája hogyan is minimalizálható! (www.inf.unideb.hu/~aszalos/diak/fordito/fsamin.html)

  1. Minimalizálja az alábbi automatát!

     ab
    123
    *245
    *366
    443
    *567
    666
    *767

    Megoldás

  2. Minimalizálja az alábbi automatát!

     abc
    1234
    *2565
    *3557
    *4855
    5555
    *6565
    *7557
    *8855

    Megoldás

  3. Minimalizálja az alábbi automatát!

     ab
    123
    245
    333
    446
    *535
    *633

    Megoldás

  4. Minimalizálja az alábbi automatát!

     ab
    *123
    *223
    *323

    Megoldás

  5. Minimalizálja az alábbi automatát!

     ab
    *123
    223
    345
    445
    *523

    Megoldás

  6. Minimalizálja az alábbi automatát!

     ab
    123
    245
    323
    *467
    545
    666
    *767

    Megoldás

  7. Minimalizálja az alábbi automatát!

     ab
    *123
    245
    345
    *423
    *523

    Megoldás

  8. Minimalizálja az alábbi automatát!

     abc
    1234
    2234
    3534
    *4555
    5555

    Megoldás

  9. Minimalizálja az alábbi automatát!

     abc
    *1234
    2234
    3234
    *4234

    Megoldás

  10. Minimalizálja az alábbi automatát!

     ab
    123
    245
    *367
    *483
    *5910
    *667
    777
    883
    *967
    101110
    *1177

    Megoldás

  11. Minimalizálja az alábbi automatát!

     ab
    *123
    *223
    345
    444
    *523

    Megoldás

  12. Minimalizálja az alábbi automatát!

     abc
    *1234
    *2234
    3567
    4567
    5567
    *6834
    *7834
    *8834

    Megoldás

  13. Minimalizálja az alábbi automatát!

     abc
    1234
    2567
    3567
    4567
    *58910
    6666
    *78910
    *88910
    *98910
    *108910

    Megoldás

  14. Minimalizálja az alábbi automatát!

     ab
    123
    245
    345
    467
    567
    666
    *789
    *889
    *989

    Megoldás

  15. Minimalizálja az alábbi automatát!

     ab
    123
    245
    323
    *467
    545
    *667
    *767

    Megoldás

  16. Minimalizálja az alábbi automatát!

     ab
    *123
    *245
    *323
    *467
    *545
    666
    *767

    Megoldás

  17. Minimalizálja az alábbi automatát!

     []dkp
    123333
    233334
    333333
    435363
    *533733
    633338
    793333
    835363
    9333310
    103113123
    *1133733
    12333313
    133113123

    Megoldás

  18. Minimalizálja az alábbi automatát!

     abc
    *1233
    *2345
    3333
    *4637
    *5683
    *6345
    *7693
    *86310
    *9637
    *10683

    Megoldás

Balrekurzió megszüntetése

[Megjegyzés]Megjegyzés

A JFLAP sajnos nem tartalmaz ilyen algoritmust.

Lássuk először a mintapéldánkat! (www.inf.unideb.hu/~aszalos/diak/fordito/balrek.html)

  1. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → AA | Ba
    A → BA | AB | a
    B → SS | b

    Megoldás

  2. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → ABC
    A → BC | CB
    B → Ca | Ab
    C → CC | A | a

    Megoldás

  3. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → aA | bB | SS
    A → Aa | b
    B → Bb | a

    Megoldás

  4. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → BB
    A → SAS | ASA | a
    B → b | Ba | Bb

    Megoldás

  5. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → ABC
    A → Sa | Bb
    B → Aa | bb

    Megoldás

  6. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → ABA | BAB
    A → SS | BB
    B → SS | bb | a

    Megoldás

  7. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → AaA
    A → BB | b
    B → CaC | aCa
    C → SBS | cc

    Megoldás

  8. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → SS | CA | AC
    A → BB | a
    B → Cb | bC
    C → a | BC | CB

    Megoldás

  9. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → ASA | BSB
    A → a | B
    B → A | b

    Megoldás

  10. Szüntesse meg a balrekurziót az alábbi nyelvtanban!

    S → ABc
    A → a | Ba
    B → b | Sb

    Megoldás

Általános felülről-lefelé elemzés

[Megjegyzés]Megjegyzés

Ez az elemzési módszer nincs implementálva se a JFLAP, se a Parsing Simulator programban.

Lássuk először a mintapéldánkat! (www.inf.unideb.hu/~aszalos/diak/fordito/afl.html)

A következőkben feladatonként megadunk egy-egy nyelvtant, majd két elemzendő karaktersorozatot. Miután néha több száz lépés is lehet a megoldás, felsorolunk pár állapot, melynek 5-6 rákövetkező állapotát meg kell határozni. Ezeket az állapotokat igyekeztünk úgy kiválogatni, hogy minden lényeges eset előforduljon, ezért ezen részfeladatok megoldása is elegendő lehet önálló felkészülés során. Természetesen a megoldások részben a teljes levezetés szerepel.

  1. E → T | TE'
    E' → +T | +TE'
    T → F | FT'
    T' → *F | *FT'
    F → i | (E)
    1. Elemezze az i*i+ inputot a megadott nyelvtan esetén! Határozza meg a (q,3,E1T2F1iT'1*F1,i), (q,5,E2T2F1iT'1*F1iE'1+T2F2,(E)T') és (b,2,E2T2F1i,T'E') állapotok rákövetkezőit! Megoldás

    2. Elemezze az i*+ inputot a megadott nyelvtan esetén! Határozza meg a (b,1,E2T1F2,(E)E'), (q,3,E2T2F1iT'2*F2,(E)T'E') és (q,1,E1T1F1,i) állapotok rákövetkezőit! Megoldás

  2. S → aAbB
    A → aAc
    A → λ
    B → bB
    B → c
    1. Elemezze az abab inputot a megadott nyelvtan esetén! Határozza meg a (q,1,S1,aAbB), (b,3,S1aA2bB2,c) és (q,2,S1aA2,bB) állapotok rákövetkezőit! Megoldás

    2. Elemezze az aabc inputot a megadott nyelvtan esetén! Határozza meg a (q,2,S1aA2,bB), (b,3,S1aA1aA1,aAccbB) és (q,1,S1,aAbB) állapotok rákövetkezőit! Megoldás

  3. S → AB
    A → aAb
    A → aA
    A → b
    B → AA
    1. Elemezze az abbab inputot a megadott nyelvtan esetén! Határozza meg a (b,4,S1A1aA3bbB1A2,aAA), (b,5,S1A2aA3bB1A3bA1aA2,aAb) és (b,5,S1A1aA3bbB1A1aA1,aAbbA) állapotok rákövetkezőit! Megoldás

    2. Elemezze a bbbb inputot az előbbi nyelvtan esetén! Határozza meg a (b,2,S1A3bB1A3,bA), (b,1,S1A1,aAbB) és (q,2,S1A3bB1A3,bA) állapotok rákövetkezőit! Megoldás

  4. S → (S)S
    S → λ
    1. Elemezze az (()) inputot a megadott nyelvtan esetén! Határozza meg a (b,4,S1(S1(S2)S1,(S)S)S), (q,1,S1,(S)S) és (b,3,S1(S1(S1,(S)S)S)S) állapotok rákövetkezőit! Megoldás

    2. Elemezze az ())) inputot a megadott nyelvtan esetén! Határozza meg a (q,1,S1,(S)S), (q,3,S1(S2),S) és (b,3,S1(S2),S) állapotok rákövetkezőit! Megoldás

  5. S → aSa
    S → bSb
    S → a
    S → b
    S → λ
    1. Elemezze az abbb inputot a megadott nyelvtan esetén! Határozza meg a (b,3,S1aS2bS1,aSaba), (b,4,S1aS2bS2bS3,abba) és (q,3,S1aS2bS5,ba) állapotok rákövetkezőit! Megoldás

    2. Elemezze az abab inputot a megadott nyelvtan esetén! Határozza meg a (q,4,S1aS2bS1aS1,aSaaba), (q,3,S1aS4b,a) és (b,5,S1aS2bS1aS2bS5,baba) állapotok rákövetkezőit! Megoldás

LL(1) elemzés

[Megjegyzés]Megjegyzés

A JFLAP program a nyelvtan megadása után lehetővé teszi, hogy a felhasználó sorra beírja az egyes First és Follow halmazok értékeit, majd ezután elkészítse az elemző táblázatot. Hiba esetén a szoftver figyelmeztet a nem megfelelő megoldásra. A Parsing Simulator esetén nincs lehetőség a megoldásunk tesztelésére. A program külön-külön megadja a First és Follow halmazokat, valamint az elemző táblázatot.

Nézzük először, hogyan készül az LL(1) elemző táblázat! (www.inf.unideb.hu/~aszalos/diak/fordito/ll.html)

  1. Készítse el az S → Sa|a nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  2. Készítse el az S → Aa|Bb, A → cA|c, B→cB|c nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  3. Készítse el az S → aA|bBc, A → Bd|Cc, B → e|λ, C → f|λ nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  4. Készítse el az S → AaS|A, A → bcA|b nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  5. Készítse el az E → TE', E' → +TE', E' → λ, T → FT', T' → *FT', T' → λ, F → (E), F → i nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  6. Készítse el az S → a|ibtS|ibtSeS nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  7. Készítse el az S → aAab|bAbb, A → λ|a nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  8. Készítse el az S → ABA|cC, A → λ|a, B → λ|bD, C → AD|b, D → aAc nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  9. Készítse el az S → AB, A → aAb|ab, B → bBc|λ nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  10. Készítse el az S → Aa|b, A → bdB|B, B → abB|cB|λ nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  11. Készítse el az S → ABBA, A → a|λ, B → b|λ nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  12. Készítse el az S → aAb|aBbb, A → aAb|c, B → aBbb|d nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  13. Készítse el az S → AB, A → aAb|b, B → bBc|c nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  14. Készítse el az S → Ba, A → aa|bb, B → BB|bA nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  15. Készítse el az S → AB, A → a|cB, B → c|aA|bB nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  16. Készítse el az S → aA|bB, A → λ|ba, B → AB|a nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  17. Készítse el az S → AA|c, A → Bc|a, B → b|bb nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  18. Készítse el az S → ABc, A → bA|λ, B → c nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  19. Készítse el az S → BaB, A → a|bab|λ, B → bB|a nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

  20. Készítse el az S → AcB, A → aAb|ba, B → aBb|cba nyelvtanhoz tartozó LL(1) elemző táblázatot! Megoldás

Általános alulról-felfelé elemzés

[Megjegyzés]Megjegyzés

Az általános alulról-felfele haladó elemzési módszer sem része a JFLAP programnak.

Lássuk először a mintapéldánkat! (www.inf.unideb.hu/~aszalos/diak/fordito/aaf.html)

A következőkben az általános felülről-lefelé elemzéshez hasonlóan megadunk egy-egy nyelvtant, majd nyelvtanonként két elemzendő karaktersorozatot.

  1. E → E+T
    E → T
    T → T*F
    T → F
    F → i
    F → (E)
    1. Elemezze az i*i+ inputot a megadott nyelvtan esetén! Határozza meg a (b,2,E,245s), (q,4,i*T,45sss) és (b,3,T*,s45s) állapotok rákövetkezőit! Megoldás

    2. Elemezze az i*i inputot a megadott nyelvtan esetén! Határozza meg a (b,2,E,245s), (q,2,T,45s) és (q,4,E*T,45ss245s) állapotok rákövetkezőit! Megoldás

  2. S → aAbB
    A → aAc
    A → B
    B → bB
    B → c
    1. Elemezze az abab inputot a megadott nyelvtan esetén! Határozza meg a (q,3,ab,ss) és (q,5,abab,ssss) állapotok rákövetkezőit! Megoldás

    2. Elemezze az aabc inputot a megadott nyelvtan esetén! Határozza meg a (b,5,aabB,5ssss), (b,5,aabA,35ssss) és (q,2,a,s) állapotok rákövetkezőit! Megoldás

  3. S → AB
    A → aAb
    A → aA
    A → b
    B → AA
    1. Elemezze az abbab inputot a megadott nyelvtan esetén! Határozza meg a (q,3,ab,ss), (q,5,AAa,s4s34ss) és (q,6,Bab,ss54s34ss) állapotok rákövetkezőit! Megoldás

    2. Elemezze a bbbb inputot a megadott nyelvtan esetén! Határozza meg a (q,5,AAB,54s4s4s4s), (b,5,bAAA,4s4s4ss) és (b,3,B,54s4s) állapotok rákövetkezőit! Megoldás

  4. S → SS
    S → ()
    1. Elemezze az (()) inputot a megadott nyelvtan esetén! Határozza meg a (q,1,λ,λ) és (b,4,(S,2sss) állapotok rákövetkezőit! Megoldás

    2. Elemezze az ())) inputot a megadott nyelvtan esetén! Határozza meg a (q,2,(,s), (q,5,())),ssss) és (q,5,S)),ss2ss) állapotok rákövetkezőit! Megoldás

  5. S → aSa
    S → bSb
    S → a
    S → b
    S → aa
    S → bb
    1. Elemezze az abba inputot a megadott nyelvtan esetén! Határozza meg a (q,5,aSba,ss4ss), (b,5,SSba,ss4s3s) és (q,4,abS,4sss) állapotok rákövetkezőit! Megoldás

    2. Elemezze az abab inputot a megadott nyelvtan esetén! Határozza meg a (q,5,aSSb,s3s4ss), (b,5,SbSb,s3ss3s) és (q,5,SSSb,s3s4s3s) állapotok rákövetkezőit! Megoldás

Operátorprecedencia elemzés

[Megjegyzés]Megjegyzés

Ebben az esetben sem a JFLAP, sem a Parsing Simulator nem segít rajtunk, ez a régimódi elemzés egyikben sem került implementálásra.

Nézzük először, hogyan történik az operátorprecedencia elemző táblázat készítése! (www.inf.unideb.hu/~aszalos/diak/fordito/op.html)

  1. Készítse el az S → Sa|a nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  2. Készítse el az S → Aa|Bb, A → cA|c, B→cB|c nyelvtanhoz tartozó operátor precedencia elemző táblázatot! Megoldás

  3. Készítse el az S → aA|bec|bc, A → ed|d|fc|c nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  4. Készítse el az S → AaS|A, A → bcA|b nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  5. Készítse el az E → E+T|T, T → T*F|F, F → (E)|i nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  6. Készítse el az S → a|ibtS|ibtSeS nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  7. Készítse el az S → AA, A → b|aA nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  8. Készítse el az S → aBa|cC, B → b|bD, C → aD|b, D → ac|aac nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  9. Készítse el az S → A|AB, A → aAb|ab, B → bBc|bc nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  10. Készítse el az S → Aa|b, A → bdB|B, B → abB|cB|ab|c nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  11. Készítse el az S → aAb|bBc|aBd|bAd, A → f, B → f nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  12. Készítse el az S → aAb|aBbb, A → aAb|c, B → aBbb|d nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  13. Készítse el az S → AB, A → aAb|b, B → bBc|c nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  14. Készítse el az S → Ba, A → aa|bb, B → BB|bA nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  15. Készítse el az S → AB, A → a|cB, B → c|aA|bB nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  16. Készítse el az S → A|bB, A → a|ba, B → AB|a nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  17. Készítse el az S → AA|c, A → Bc|a, B → b|bb nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  18. Készítse el az S → ABc, A → bA|b, B → c nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  19. Készítse el az S → BaB, A → a|bab, B → bB|a nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

  20. Készítse el az S → AcB, A → aAb|ba, B → aBb|cba nyelvtanhoz tartozó operátorprecedencia elemző táblázatot! Megoldás

Egyszerű precendecia elemzés

[Megjegyzés]Megjegyzés

A JFLAP és a Parsing Simulator programok egyike sem implementálta ezt az algoritmust.

Nézzük először, hogyan történik az egyszerű precedencia elemző táblázat készítése! (www.inf.unideb.hu/~aszalos/diak/fordito/epp.html)

  1. Készítse el az S → Sa|a nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  2. Készítse el az S → Aa|Bb, A → cA|c, B→cB|c nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  3. Készítse el az S → aA|bec|bc, A → ed|d|fc|c nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  4. Készítse el az S → AaS|A, A → bcA|b nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  5. Készítse el az E → E+T|T, T → T*F|F, F → (E)|i nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  6. Készítse el az S → a|ibtS|ibtSeS nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  7. Készítse el az S → AA, A → b|aA nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  8. Készítse el az S → aBa|cC, B → b|bD, C → aD|b, D → ac|aac nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  9. Készítse el az S → A|AB, A → aAb|ab, B → bBc|bc nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  10. Készítse el az S → Aa|b, A → bdB|B, B → abB|cB|ab|c nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  11. Készítse el az S → aAb|bBc|aBd|bAd, A → f, B → f nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  12. Készítse el az S → aAb|aBbb, A → aAb|c, B → aBbb|d nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  13. Készítse el az S → AB, A → aAb|b, B → bBc|c nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  14. Készítse el az S → Ba, A → aa|bb, B → BB|bA nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  15. Készítse el az S → AB, A → a|cB, B → c|aA|bB nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  16. Készítse el az S → A|bB, A → a|ba, B → AB|a nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  17. Készítse el az S → AA|c, A → Bc|a, B → b|bb nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  18. Készítse el az S → ABc, A → bA|b, B → c nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  19. Készítse el az S → BaB, A → a|bab, B → bB|a nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

  20. Készítse el az S → AcB, A → aAb|ba, B → aBb|cba nyelvtanhoz tartozó egyszerű precedencia elemző táblázatot! Megoldás

LR(0) elemzés

[Megjegyzés]Megjegyzés

A JFLAP program a grammatika megadása után generálja az SLR elemzőt, amely tartalmazza a számunkra szükséges LR(0) elemeket. Ezekből viszont már nekünk kell az elemző táblázatot elkészíteni. A Parsing Simulator képes generálni az LR(0) elemeket és az elemző táblázatot is, csak figyelni kell arra, hogy itt a kiegészített nyelvtan a kiindulópont.

Nézzük először, hogyan történik az LR(0) elemző táblázat készítése! (www.inf.unideb.hu/~aszalos/diak/fordito/lr0.html)

  1. Készítse el az S → Sa|a nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  2. Készítse el az S → Aa|Bb, A → cA|c, B→cB|c nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  3. Készítse el az S → aA|bec|bc, A → ed|d|fc|c nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  4. Készítse el az S → AaS|A, A → bcA|b nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  5. Készítse el az E → E+T|T, T → T*F|F, F → (E)|i nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  6. Készítse el az S → a|ibtS|ibtSeS nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  7. Készítse el az S → AA, A → b|aA nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  8. Készítse el az S → aBa|cC, B → b|bD, C → aD|b, D → ac|aac nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  9. Készítse el az S → A|AB, A → aAb|ab, B → bBc|bc nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  10. Készítse el az S → Aa|b, A → bdB|B, B → abB|cB|ab|c nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  11. Készítse el az S → aAb|bBc|aBd|bAd, A → f, B → f nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  12. Készítse el az S → aAb|aBbb, A → aAb|c, B → aBbb|d nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  13. Készítse el az S → AB, A → aAb|b, B → bBc|c nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  14. Készítse el az S → Ba, A → aa|bb, B → BB|bA nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  15. Készítse el az S → AB, A → a|cB, B → c|aA|bB nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  16. Készítse el az S → A|bB, A → a|ba, B → AB|a nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  17. Készítse el az S → AA|c, A → Bc|a, B → b|bb nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  18. Készítse el az S → ABc, A → bA|b, B → c nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  19. Készítse el az S → BaB, A → a|bab, B → bB|a nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

  20. Készítse el az S → AcB, A → aAb|ba, B → aBb|cba nyelvtanhoz tartozó LR(0) elemző táblázatot! Megoldás

SLR elemzés

[Megjegyzés]Megjegyzés

A JFLAP program a grammatika megadása után generálja az SLR elemzőt. A Parsing Simulator hasonló eredményt szolgáltat, ám az LR(0) elemzésnél leírtaknak megfelelően itt is a kiegészített nyelvtan a kiindulópont.

Nézzük először, hogyan történik az SLR(1) elemző táblázat készítése! (www.inf.unideb.hu/~aszalos/diak/fordito/slr.html)

  1. Készítse el az S → Sa|a nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  2. Készítse el az S → Aa|Bb, A → cA|c, B→cB|c nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  3. Készítse el az S → aA|bBc, A → Bd|Cc, B → e|λ, C → f|λ nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  4. Készítse el az S → AaS|A, A → bcA|b nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  5. Készítse el az E → TE', E' → +TE', E' → λ, T → FT', T' → *FT', T' → λ, F → (E), F → i nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  6. Készítse el az S → a|ibtS|ibtSeS nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  7. Készítse el az S → aAab|bAbb, A → λ|a nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  8. Készítse el az S → ABA|cC, A → λ|a, B → λ|bD, C → AD|b, D → aAc nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  9. Készítse el az S → AB, A → aAb|ab, B → bBc|λ nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  10. Készítse el az S → Aa|b, A → bdB|B, B → abB|cB|λ nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  11. Készítse el az S → ABBA, A → a|λ, B → b|λ nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  12. Készítse el az S → aAb|aBbb, A → aAb|c, B → aBbb|d nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  13. Készítse el az S → AB, A → aAb|b, B → bBc|c nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  14. Készítse el az S → Ba, A → aa|bb, B → BB|bA nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  15. Készítse el az S → AB, A → a|cB, B → c|aA|bB nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  16. Készítse el az S → aA|bB, A → λ|ba, B → AB|a nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  17. Készítse el az S → AA|c, A → Bc|a, B → b|bb nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  18. Készítse el az S → ABc, A → bA|λ, B → c nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  19. Készítse el az S → BaB, A → a|bab|λ, B → bB|a nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

  20. Készítse el az S → AcB, A → aAb|ba, B → aBb|cba nyelvtanhoz tartozó SLR elemző táblázatot! Megoldás

LR(1) elemzés

[Megjegyzés]Megjegyzés

A JFLAP program nem képes generálni az LR(1) elemeket, így a Parsing Simulator programot javasoljuk használni. Ismételten felhívjuk a figyelmet, hogy a program számára a kiegészített nyelvtan a kiindulópont.

Nézzük először, hogyan történik az LR(1) elemző táblázat készítése! (www.inf.unideb.hu/~aszalos/diak/fordito/lr1.html)

  1. Készítse el az S → Sa|a nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  2. Készítse el az S → Aa|Bb, A → cA|c, B→cB|c nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  3. Készítse el az S → aA|bec|bc, A → ed|d|fc|c nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  4. Készítse el az S → AaS|A, A → bcA|b nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  5. Készítse el az E → E+T|T, T → T*F|F, F → (E)|i nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  6. Készítse el az S → a|ibtS|ibtSeS nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  7. Készítse el az S → AA, A → b|aA nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  8. Készítse el az S → aBa|cC, B → b|bD, C → aD|b, D → ac|aac nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  9. Készítse el az S → A|AB, A → aAb|ab, B → bBc|bc nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  10. Készítse el az S → Aa|b, A → bdB|B, B → abB|cB|ab|c nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  11. Készítse el az S → aAb|bBc|aBd|bAd, A → f, B → f nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  12. Készítse el az S → aAb|aBbb, A → aAb|c, B → aBbb|d nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  13. Készítse el az S → AB, A → aAb|b, B → bBc|c nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  14. Készítse el az S → Ba, A → aa|bb, B → BB|bA nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  15. Készítse el az S → AB, A → a|cB, B → c|aA|bB nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  16. Készítse el az S → A|bB, A → a|ba, B → AB|a nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  17. Készítse el az S → AA|c, A → Bc|a, B → b|bb nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  18. Készítse el az S → ABc, A → bA|b, B → c nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  19. Készítse el az S → BaB, A → a|bab, B → bB|a nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

  20. Készítse el az S → AcB, A → aAb|ba, B → aBb|cba nyelvtanhoz tartozó LR(1) elemző táblázatot! Megoldás

LALR elemzés

[Megjegyzés]Megjegyzés

A JFLAP program nem képes generálni az LR(1) elemeket, ezeknél a feladatoknál is a Parsing Simulator programot javasoljuk használni. Továbbra is a kiegészített nyelvtant kell megadni a szoftver számára.

Nézzük először, hogyan történik az LALR(1) elemző táblázat készítése! (www.inf.unideb.hu/~aszalos/diak/fordito/lalr.html)

  1. Készítse el az S → Sa|a nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  2. Készítse el az S → Aa|Bb, A → cA|c, B→cB|c nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  3. Készítse el az S → aA|bec|bc, A → ed|d|fc|c nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  4. Készítse el az S → AaS|A, A → bcA|b nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  5. Készítse el az E → E+T|T, T → T*F|F, F → (E)|i nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  6. Készítse el az S → a|ibtS|ibtSeS nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  7. Készítse el az S → AA, A → b|aA nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  8. Készítse el az S → aBa|cC, B → b|bD, C → aD|b, D → ac|aac nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  9. Készítse el az S → A|AB, A → aAb|ab, B → bBc|bc nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  10. Készítse el az S → Aa|b, A → bdB|B, B → abB|cB|ab|c nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  11. Készítse el az S → aAb|bBc|aBd|bAd, A → f, B → f nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  12. Készítse el az S → aAb|aBbb, A → aAb|c, B → aBbb|d nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  13. Készítse el az S → AB, A → aAb|b, B → bBc|c nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  14. Készítse el az S → Ba, A → aa|bb, B → BB|bA nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  15. Készítse el az S → AB, A → a|cB, B → c|aA|bB nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  16. Készítse el az S → A|bB, A → a|ba, B → AB|a nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  17. Készítse el az S → AA|c, A → Bc|a, B → b|bb nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  18. Készítse el az S → ABc, A → bA|b, B → c nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  19. Készítse el az S → BaB, A → a|bab, B → bB|a nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

  20. Készítse el az S → AcB, A → aAb|ba, B → aBb|cba nyelvtanhoz tartozó LALR(1) elemző táblázatot! Megoldás

2. fejezet - Megoldások

Reguláris kifejezések

[Megjegyzés]Megjegyzés

A feladatmegoldások során a szorzást (konkatenációt) nem jelöljük.

  1. A reguláris kifejezésben mindenképpen jelölni kell a két a betűt. Ezek előtt, között és mögött tetszőleges számú b szerepelhet: b*ab*ab*.

  2. Jelöljük az első két a betűt. Ezek előtt és között tetszőleges számú b szerepelhet, végül a második a-t bármi követheti: b*ab*a(a+b)*.

  3. Az első megoldáshoz képest az az eltérés, hogy bármely a eltűnhet, így ezeket a+λ-val helyettesítjük: b*(a+λ)b*(a+λ)b*.

  4. Az első két betű bármi lehet, ezt követi a b, majd ezt bármi követheti: (a+b)(a+b)b(a+b)*.

  5. Az első betű bármi lehet, a második csak a vagy c, majd ezt bármi követheti: (a+b+c)(a+c)(a+b+c)*.

  6. Ha a mássalhangzók száma páros, akkor a szót olyan részekre lehet bontani, melyek mássalhangzókkal kezdődnek és pontosan két mássalhangzót tartalmaznak. A két mássalhangzó között és a második mögött tetszőleges számú a betű szerepelhet. Viszont a teljes szó kezdődhet tetszőleges számú a betűvel: a*((b+c)a*(b+c)a*)*.

  7. Mivel a b csakis duplán szerepelhet, a tetszőleges szót leíró reguláris kifejezést kell egy kicsit átírni: (a+bb)*. Más irányból megközelítve a b-k sorozatai között tetszőleges számú a lehet: (a*(bb))*.

  8. Egy elemi konjunkció egy literál vagy literálok konjunkciója, tehát az első literált operátor-literál párosok követik: p(kp)*. A diszjunktív normálforma egy elemi konjunkció vagy azok diszkunkciója, azaz a szerkezet nagyon hasonló. Mivel a diszjunkció és konjunkció azonos precedenciájú, az elemi konjunkciókat zárójelezzük: [p(kp)*](d[p(kp)*])*. A kerek zárójeleknek speciális szerepe van a reguláris kifejezésekben, ezért használunk szögletes zárójeleket. Természetesen az egy literálból álló elemi konjunkciót felesleges zárójelezni, ám ezzel a [p(kp)*] reguláris kifejezés helyett p+[pkp(kp)*]-t kellett volna írni az előbbi megoldásba, amit felesleges elbonyolításnak érzünk.

  9. A szó mindenképpen a betűvel kezdődik, így bontsuk olyan részekre melynek a kezdőbetűje a, és nem tartalmaz újabb a-t. Mivel páros betű nem fordulhat elő a szóban, a kezdő a betűt felváltva követheti b és c tetszőleges hosszan, de legalább egy betűnek kell itt szerepelni, mert a két a-t el kell választani egymástól. Az utolsó rész állhat egy darab a betűből is: (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a. Természetesen létezik más megoldás is, amely egyeseknek egyszerűbbnek tűnhet.

Reguláris kifejezéseket felismerő nemdeterminisztikus automaták

[Megjegyzés]Megjegyzés

Ebben és azt ezt követő fejezetekben Thompson algoritmusát [Thompson68] alkalmazzuk kisebb lépésekben ugyanarra a 18 feladatra.

A feladatok megoldásait jelentő nemdeterminisztikus automatákat a következőképpen adjuk meg: zöld színnel jelöljük a kiinduló állapotot, és pirossal az egyedüli végállapotot. A λ-átmenetnél a nyilat nem címkézzük az egyszerűség kedvéért.

  1. ab*+a*b

    ab*+a*b nemdeterminisztikus automatája

  2. ab*+bc*+ca*

    ab*+bc*+ca* nemdeterminisztikus automatája

  3. a(a*+b*)b

    a(a*+b*)b nemdeterminisztikus automatája

  4. (a+b)*+(b+a)*

    (a+b)*+(b+a)* nemdeterminisztikus automatája

  5. (a*ba*b)*

    (a*ba*b)* nemdeterminisztikus automatája

  6. b*ab*ab*

    b*ab*ab* nemdeterminisztikus automatája

  7. ((a+b)(b+a))*

    ((a+b)(b+a))* nemdeterminisztikus automatája

  8. a*b*c

    a*b*c nemdeterminisztikus automatája

  9. ((a*+b)*c)*

    ((a*+b)*c)* nemdeterminisztikus automatája

  10. ab*a+a*ba*

    ab*a+a*ba* nemdeterminisztikus automatája

  11. (a+bb)*

    (a+bb)* nemdeterminisztikus automatája

  12. a*((b+c)a*(b+c)a*)*

    a*((b+c)a*(b+c)a*)* nemdeterminisztikus automatája

  13. (a+b+c)(a+b)(a+b+c)*

    (a+b+c)(a+b)(a+b+c)* nemdeterminisztikus automatája

  14. (a+b)(a+b)b(a+b)*

    (a+b)(a+b)b(a+b)* nemdeterminisztikus automatája

  15. b*ab*a(a+b)*

    b*ab*a(a+b)* nemdeterminisztikus automatája

  16. b*(a+λ)b*(a+λ)b*

    b*(a+λ)b*(a+λ)b* nemdeterminisztikus automatája

  17. [p(kp)*](d[p(kp)*])*

    [p(kp)*](d[p(kp)*])* nemdeterminisztikus automatája

  18. (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a

    (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a nemdeterminisztikus automatája

Nemdeterminisztikus automaták determinizálása

[Megjegyzés]Megjegyzés

Minden megoldást két formában is megadunk. Első esetben a nemdeterminisztikus automata állapotainak halmaza lesz az új automa egy-egy állapota. Az ezeket az állapotokat tartalmazó táblázatban nem jelöltük külön a kezdő és végállapotokat, csupán az átmeneteket. Kezdőállapot az, mely az A-val jelölt állapotot tartalmazza (vagyis az első), és végállapot mindaz, amely a rajzon pirossal jelölt állapotot tartalmazza.

  1. Determinisztikus automata állapothalmazokkal.

     ab
    ABGHJCDFHIJLKL
    CDFHIJLHIJDEFKL
    KL  
    HIJHIJKL
    DEFKL DEFL
       
    DEFL DEFL

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    *245
    *366
    443
    *567
    666
    *767
  2. Determinisztikus automata állapothalmazokkal.

     abc
    ABCHNDEGMSIJLMSOPRS
    DEGMS EFGMS 
    IJLMS  JKLMS
    OPRSPQRS  
        
    EFGMS EFGMS 
    JKLMS  JKLMS
    PQRSPQRS  

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    1234
    *2565
    *3557
    *4855
    5555
    *6565
    *7557
    *8855
  3. Determinisztikus automata állapothalmazokkal.

     ab
    ABCDFGHJK 
    BCDFGHJKDEFKHIJKL
       
    DEFKDEFKL
    HIJKL HIJKL
    L  

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    333
    446
    *535
    *633
  4. Determinisztikus automata állapothalmazokkal.

     ab
    ABCDFIJKLNQRCDEFHIKLNOPQRCDFGHIKLMNPQR
    CDEFHIKLNOPQRCDEFHIKLNOPQRCDFGHIKLMNPQR
    CDFGHIKLMNPQRCDEFHIKLNOPQRCDFGHIKLMNPQR

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    *223
    *323
  5. Determinisztikus automata állapothalmazokkal.

     ab
    ABCEKCDEFGI
    CDECDEFGI
    FGIGHIBCEJK
    GHIGHIBCEJK
    BCEJKCDEFGI

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    223
    345
    445
    *523
  6. Determinisztikus automata állapothalmazokkal.

     ab
    ABDEFHBCD
    EFHIJLFGH
    BCDEFHBCD
    IJL JKL
    FGHIJLFGH
       
    JKL JKL

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    323
    *467
    545
    666
    *767
  7. Determinisztikus automata állapothalmazokkal.

     ab
    ABCEMDGHJFGHJ
    DGHJBCEKLMBCEILM
    FGHJBCEKLMBCEILM
    BCEKLMDGHJFGHJ
    BCEILMDGHJFGHJ

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    245
    345
    *423
    *523
  8. Determinisztikus automata állapothalmazokkal.

     abc
    ABDEGBCDEGEFGH
    BCDEGBCDEGEFGH
    EFG EFGH
    H   
        

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    1234
    2234
    3534
    *4555
    5555
  9. Determinisztikus automata állapothalmazokkal.

     abc
    ABCDEGHJKMCDEFGHJKCDEGHIJKBCDEGHJKLM
    CDEFGHJKCDEFGHJKCDEGHIJKBCDEGHJKLM
    CDEGHIJKCDEFGHJKCDEGHIJKBCDEGHJKLM
    BCDEGHJKLMCDEFGHJKCDEGHIJKBCDEGHJKLM

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    *1234
    2234
    3234
    *4234
  10. Determinisztikus automata állapothalmazokkal.

     ab
    ABHIKCDFIJKLMOP
    CDFIJKGIJKPDEFLMOP
    LMOPMNOP 
    GIJKPIJKLMOP
    DEFLMOPGMNOPDEF
    MNOPMNOP 
       
    IJKIJKLMOP
    GMNOPMNOP 
    DEFGPDEF
    GP  

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    *367
    *483
    *5910
    *667
    777
    883
    *967
    101110
    *1177
  11. Determinisztikus automata állapothalmazokkal.

     ab
    ABCEIBCDEHIF
    BCDEHIBCDEHIF
    F BCEGHI
       
    BCEGHIBCDEHIF

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    *223
    345
    444
    *523
  12. Determinisztikus automata állapothalmazokkal.

     abc
    ABDEFHVBCDEFHVGJKMNPIJKMNP
    BCDEFHVBCDEFHVGJKMNPIJKMNP
    GJKMNPKLMNPEFHORSUVEFHQRSUV
    IJKMNPKLMNPEFHORSUVEFHQRSUV
    KLMNPKLMNPEFHORSUVEFHQRSUV
    EFHORSUVEFHSTUVGJKMNPIJKMNP
    EFHQRSUVEFHSTUVGJKMNPIJKMNP
    EFHSTUVEFHSTUVGJKMNPIJKMNP

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    *1234
    *2234
    3567
    4567
    5567
    *6834
    *7834
    *8834
  13. Determinisztikus automata állapothalmazokkal.

     abc
    ABCEHDGJKMFGJKMIJKM
    DGJKMLOPQRTWZ NOPQRTWZ
    FGJKMLOPQRTWZ NOPQRTWZ
    IJKMLOPQRTWZ NOPQRTWZ
    LOPQRTWZPQRSTVWYZPQRTUVWYZPQRTWXYZ
        
    NOPQRTWZPQRSTVWYZPQRTUVWYZPQRTWXYZ
    PQRSTVWYZPQRSTVWYZPQRTUVWYZPQRTWXYZ
    PQRTUVWYZPQRSTVWYZPQRTUVWYZPQRTWXYZ
    PQRTWXYZPQRSTVWYZPQRTUVWYZPQRTWXYZ

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    1234
    2567
    3567
    4567
    *58910
    6666
    *78910
    *88910
    *98910
    *108910
  14. Determinisztikus automata állapothalmazokkal.

     ab
    ABDCFGIEFGI
    CFGIHKJK
    EFGIHKJK
    HK LMNPS
    JK LMNPS
       
    LMNPSMNOPRSMNPQRS
    MNOPRSMNOPRSMNPQRS
    MNPQRSMNOPRSMNPQRS

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    345
    467
    567
    666
    *789
    *889
    *989
  15. Determinisztikus automata állapothalmazokkal.

     ab
    ABDEFHBCD
    EFHIJKMPFGH
    BCDEFHBCD
    IJKMPJKLMOPJKMNOP
    FGHIJKMPFGH
    JKLMOPJKLMOPJKMNOP
    JKMNOPJKLMOPJKMNOP

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    323
    *467
    545
    *667
    *767
  16. Determinisztikus automata állapothalmazokkal.

     ab
    ABDEGHIJLMOPQRTFIJLMNOPQRTBCDEGHIJKLMOPQRST
    FIJLMNOPQRTNQRTJKLMOPQRST
    BCDEGHIJKLMOPQRSTFIJLMNOPQRTBCDEGHIJKLMOPQRST
    NQRT RST
    JKLMOPQRSTNQRTJKLMOPQRST
       
    RST RST

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    *245
    *323
    *467
    *545
    666
    *767
  17. Determinisztikus automata állapothalmazokkal.

     []dkp
    AB    
    B    CDG
          
    CDG HIR E 
    HIR  J  
    E    DFG
    JK    
    DFG HIR E 
    K    LMP
    LMP IQR N 
    IQR  J  
    N    MOP
    MOP IQR N 

    Ugyanaz az automata hagyományos jelöléssel.

     []dkp
    123333
    233334
    333333
    435363
    *533733
    633338
    793333
    835363
    9333310
    103113123
    *1133733
    12333313
    133113123
  18. Determinisztikus automata állapothalmazokkal.

     abc
    ABCbcefghjDEPdgij  
    DEPdgij CFGJKMNOabcefgjCQRUVXYZabcefgj
        
    CFGJKMNOabcefgjDEPdgj CHLOabcefgj
    CQRUVXYZabcefgjDEPdgjCSWZabcefgj 
    DEPdgj CFGJKMNOabcefgjCQRUVXYZabcefgj
    CHLOabcefgjDEPdgjCGIJKMNOabcefgj 
    CSWZabcefgjDEPdgj CRTUVXYZabcefgj
    CGIJKMNOabcefgjDEPdgj CHLOabcefgj
    CRTUVXYZabcefgjDEPdgjCSWZabcefgj 

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    *1233
    *2345
    3333
    *4637
    *5683
    *6345
    *7693
    *86310
    *9637
    *10683

Determinisztikus automaták minimalizálása

  1. végállapotoknem végállapotok
    2,3,5,71,4,6
    2,5,73146
    25,7

  2. végállapotoknem végállapotok
    2,3,4,6,7,81,5
    2,63,74,815

  3. végállapotoknem végállapotok
    5,61,2,3,4
    561,324
    13

  4. végállapotoknem végállapotok
    1,2,3 

  5. végállapotoknem végállapotok
    1,52,3,4
    23,4

  6. végállapotoknem végállapotok
    4,71,2,3,5,6
    1,3,62,5
    1,36

  7. végállapotoknem végállapotok
    1,4,52,3

  8. végállapotoknem végállapotok
    41,2,3,5
    1,2,35
    1,23

  9. végállapotoknem végállapotok
    1,42,3

  10. végállapotoknem végállapotok
    3,4,5,6,9,111,2,7,8,10
    3,5,6,94111,82710
    3,6,95

  11. végállapotoknem végállapotok
    1,2,53,4
    34

  12. végállapotoknem végállapotok
    1,2,6,7,83,4,5

  13. végállapotoknem végállapotok
    5,7,8,9,101,2,3,4,6
    1,62,3,4
    16

  14. végállapotoknem végállapotok
    7,8,91,2,3,4,5,6
    1,2,3,64,5
    1,62,3
    16

  15. végállapotoknem végállapotok
    4,6,71,2,3,5
    1,32,5

  16. végállapotoknem végállapotok
    1,2,3,4,5,76
    1,2,3,54,7
    1,32,5

  17. végállapotoknem végállapotok
    5,111,2,3,4,6,7,8,9,10,12,13
    1,2,3,6,7,9,124,8,10,13
    1,3,72,6,9,12
    1,73

  18. végállapotoknem végállapotok
    1,2,4,5,6,7,8,9,103
    12,64,8,95,7,10

Balrekurzió megszüntetése

    1. közvetlen balrekurzió megszüntetése: A

      S → AA | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → SS | b
    2. balrekurzió megszüntetése: S

      S → AA | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → AAS | BaS | b
    3. közvetlen balrekurzió megszüntetése: B

      S → AA | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → AASB' | bB'
      B' → aSB' | λ
    4. balrekurzió megszüntetése: A

      S → BAA'A | aA'A | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → BAA'ASB' | aA'ASB' | bB'
      B' → aSB' | λ
    5. közvetlen balrekurzió megszüntetése:B

      S → BAA'A | aA'A | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → aA'ASB'B'' | bB'B''
      B' → aSB' | λ
      B'' → AA'ASB'B'' | λ
    1. közvetlen balrekurzió megszüntetése: C

      S → ABC
      A → BC | CB
      B → Ca | Ab
      C → AC' | aC'
      C' → CC' | λ
    2. balrekurzió megszüntetése: A

      S → BCBC | CBBC
      A → BC | CB
      B → Ca | BCb | CBb
      C → BCC' | CBC' | aC'
      C' → CC' | λ
    3. közvetlen balrekurzió megszüntetése: B

      S → BCBC | CBBC
      A → BC | CB
      B → CaB' | CBbB'
      B' → CbB' | λ
      C → BCC' | CBC' | aC'
      C' → CC' | λ
    4. közvetlen balrekurzió megszüntetése: C

      S → BCBC | CBBC
      A → BC | CB
      B → CaB' | CBbB'
      B' → CbB' | λ
      C → BCC'C'' | aC'C''
      C' → CC' | λ
      C'' → BC'C'' | λ
    5. balrekurzió megszüntetése: B

      S → CaB'CBC | CBbB'CBC | CBBC
      A → CaB'C | CBbB'C | CB
      B → CaB' | CBbB'
      B' → CbB' | λ
      C → CaB'CC'C'' | CBbB'CC'C'' | aC'C''
      C' → CC' | λ
      C'' → CaB'C'C'' | CBbB'C'C'' | λ
    6. közvetlen balrekurzió megszüntetése: C

      S → CaB'CBC | CBbB'CBC | CBBC
      A → CaB'C | CBbB'C | CB
      B → CaB' | CBbB'
      B' → CbB' | λ
      C → aC'C''C3
      C' → CC' | λ
      C'' → CaB'C'C'' | CBbB'C'C'' | λ
      C3 → aB'CC'C''C3 | BbB'CC'C''C3 | λ
    1. közvetlen balrekurzió megszüntetése: S

      S → aAS' | bBS'
      S' → SS' | λ
      A → Aa | b
      B → Bb | a
    2. közvetlen balrekurzió megszüntetése: A

      S → aAS' | bBS'
      S' → SS' | λ
      A → bA'
      A' → aA' | λ
      B → Bb | a
    3. közvetlen balrekurzió megszüntetése: B

      S → aAS' | bBS'
      S' → SS' | λ
      A → bA'
      A' → aA' | λ
      B → aB'
      B' → bB' | λ
    1. közvetlen balrekurzió megszüntetése: A

      S → BB
      A → SASA' | aA'
      A' → SAA' | λ
      B → b | Ba | Bb
    2. közvetlen balrekurzió megszüntetése: B

      S → BB
      A → SASA' | aA'
      A' → SAA' | λ
      B → bB'
      B' → aB' | bB' | λ
    1. balrekurzió megszüntetése: S

      S → ABC
      A → ABCa | Bb
      B → Aa | bb
    2. közvetlen balrekurzió megszüntetése: A

      S → ABC
      A → BbA'
      A' → BCaA' | λ
      B → Aa | bb
    3. balrekurzió megszüntetése: A

      S → BbA'BC
      A → BbA'
      A' → BCaA' | λ
      B → BbA'a | bb
    4. közvetlen balrekurzió megszüntetése: B

      S → BbA'BC
      A → BbA'
      A' → BCaA' | λ
      B → bbB'
      B' → bA'aB' | λ
    1. balrekurzió megszüntetése: S

      S → ABA | BAB
      A → ABAS | BABS | BB
      B → ABAS | BABS | bb | a
    2. közvetlen balrekurzió megszüntetése: A

      S → ABA | BAB
      A → BABSA' | BBA'
      A' → BASA' | λ
      B → ABAS | BABS | bb | a
    3. közvetlen balrekurzió megszüntetése: B

      S → ABA | BAB
      A → BABSA' | BBA'
      A' → BASA' | λ
      B → ABASB' | bbB' | aB'
      B' → ABSB' | λ
    4. balrekurzió megszüntetése: A

      S → BABSA'BA | BBA'BA | BAB
      A → BABSA' | BBA'
      A' → BASA' | λ
      B → BABSA'BASB' | BBA'BASB' | bbB' | aB'
      B' → BABSA'BSB' | BBA'BSB' | λ
    5. közvetlen balrekurzió megszüntetése: B

      S → BABSA'BA | BBA'BA | BAB
      A → BABSA' | BBA'
      A' → BASA' | λ
      B → bbB'B'' | aB'B''
      B' → BABSA'BSB' | BBA'BSB' | λ
      B'' → ABSA'BASB'B'' | BA'BASB'B'' | λ
    1. balrekurzió megszüntetése: S

      S → AaA
      A → BB | b
      B → CaC | aCa
      C → AaABS | cc
    2. balrekurzió megszüntetése: A

      S → BBaA | baA
      A → BB | b
      B → CaC | aCa
      C → BBaABS | baABS | cc
    3. balrekurzió megszüntetése: B

      S → CaCBaA | aCaBaA | baA
      A → CaCB | aCaB | b
      B → CaC | aCa
      C → CaCBaABS | aCaBaABS | baABS | cc
    4. közvetlen balrekurzió megszüntetése: C

      S → CaCBaA | aCaBaA | baA
      A → CaCB | aCaB | b
      B → CaC | aCa
      C → aCaBaABSC' | baABSC' | ccC'
      C' → aCBaABSC' | λ
    1. közvetlen balrekurzió megszüntetése: S

      S → CAS' | ACS'
      S' → SS' | λ
      A → BB | a
      B → Cb | bC
      C → a | BC | CB
    2. közvetlen balrekurzió megszüntetése: C

      S → CAS' | ACS'
      S' → SS' | λ
      A → BB | a
      B → Cb | bC
      C → aC' | BCC'
      C' → BC' | λ
    3. balrekurzió megszüntetése: B

      S → CAS' | ACS'
      S' → SS' | λ
      A → CbB | bCB | a
      B → Cb | bC
      C → aC' | CbCC' | bCCC'
      C' → CbC' | bCC' | λ
    4. közvetlen balrekurzió megszüntetése: C

      S → CAS' | ACS'
      S' → SS' | λ
      A → CbB | bCB | a
      B → Cb | bC
      C → aC'C'' | bCCC'C''
      C' → CbC' | bCC' | λ
      C'' → bCC'C'' | λ
    1. balrekurzió megszüntetése: A

      S → aSa | BSA | BSB
      A → a | B
      B → a | B | b
    2. közvetlen balrekurzió megszüntetése: B

      S → aSa | BSA | BSB
      A → a | B
      B → aB' | bB'
      B' → B' | λ

      Kicsit szokatlan az utolsó előtti szabály, melynek a bal és a jobb oldala megegyezik. Akár el is hagyható, mert nélküle is ugyanazt a nyelvet generálhatjuk a nyelvtannal.

    1. balrekurzió megszüntetése: S

      S → ABc
      A → a | Ba
      B → b | ABcb
    2. balrekurzió megszüntetése: A

      S → aBc | BaBc
      A → a | Ba
      B → b | aBcb | BaBcb
    3. közvetlen balrekurzió megszüntetése: B

      S → aBc | BaBc
      A → a | Ba
      B → bB' | aBcbB'
      B' → aBcbB' | λ

Általános felülről-lefelé elemzés

[Megjegyzés]Megjegyzés

A feladatmegoldások során felső indexként adjuk meg a lépések Fülöp Zoltán jegyzete [Fülöp99] szerinti sorszámát. A sikertelen megoldást jelző 6.2 esetet viszont sosem írtuk ki, mert ekkor nincs átmenet.

    1. (q,1,λ,E), 1(q,1,E1,T), 1(q,1,E1T1,F), 1(q,1,E1T1F1,i), 2(q,2,E1T1F1i,λ), 4(b,2,E1T1F1i,λ), 5(b,1,E1T1F1,i), 6.1(q,1,E1T1F2,(E)), 4(b,1,E1T1F2,(E)), 6.3(b,1,E1T1,F), 6.1(q,1,E1T2,FT'), 1(q,1,E1T2F1,iT'), 2(q,2,E1T2F1i,T'), 1(q,2,E1T2F1iT'1,*F), 2(q,3,E1T2F1iT'1*,F), 1(q,3,E1T2F1iT'1*F1,i), 2(q,4,E1T2F1iT'1*F1i,λ), 4(b,4,E1T2F1iT'1*F1i,λ), 5(b,3,E1T2F1iT'1*F1,i), 6.1(q,3,E1T2F1iT'1*F2,(E)), 4(b,3,E1T2F1iT'1*F2,(E)), 6.3(b,3,E1T2F1iT'1*,F), 5(b,2,E1T2F1iT'1,*F), 6.1(q,2,E1T2F1iT'2,*FT'), 2(q,3,E1T2F1iT'2*,FT'), 1(q,3,E1T2F1iT'2*F1,iT'), 2(q,4,E1T2F1iT'2*F1i,T'), 1(q,4,E1T2F1iT'2*F1iT'1,*F), 4(b,4,E1T2F1iT'2*F1iT'1,*F), 6.1(q,4,E1T2F1iT'2*F1iT'2,*FT'), 4(b,4,E1T2F1iT'2*F1iT'2,*FT'), 6.3(b,4,E1T2F1iT'2*F1i,T'), 5(b,3,E1T2F1iT'2*F1,iT'), 6.1(q,3,E1T2F1iT'2*F2,(E)T'), 4(b,3,E1T2F1iT'2*F2,(E)T'), 6.3(b,3,E1T2F1iT'2*,FT'), 5(b,2,E1T2F1iT'2,*FT'), 6.3(b,2,E1T2F1i,T'), 5(b,1,E1T2F1,iT'), 6.1(q,1,E1T2F2,(E)T'), 4(b,1,E1T2F2,(E)T'), 6.3(b,1,E1T2,FT'), 6.3(b,1,E1,T), 6.1(q,1,E2,TE'), 1(q,1,E2T1,FE'), 1(q,1,E2T1F1,iE'), 2(q,2,E2T1F1i,E'), 1(q,2,E2T1F1iE'1,+T), 4(b,2,E2T1F1iE'1,+T), 6.1(q,2,E2T1F1iE'2,+TE'), 4(b,2,E2T1F1iE'2,+TE'), 6.3(b,2,E2T1F1i,E'), 5(b,1,E2T1F1,iE'), 6.1(q,1,E2T1F2,(E)E'), 4(b,1,E2T1F2,(E)E'), 6.3(b,1,E2T1,FE'), 6.1(q,1,E2T2,FT'E'), 1(q,1,E2T2F1,iT'E'), 2(q,2,E2T2F1i,T'E'), 1(q,2,E2T2F1iT'1,*FE'), 2(q,3,E2T2F1iT'1*,FE'), 1(q,3,E2T2F1iT'1*F1,iE'), 2(q,4,E2T2F1iT'1*F1i,E'), 1(q,4,E2T2F1iT'1*F1iE'1,+T), 2(q,5,E2T2F1iT'1*F1iE'1+,T), 1(q,5,E2T2F1iT'1*F1iE'1+T1,F), 1(q,5,E2T2F1iT'1*F1iE'1+T1F1,i), 4(b,5,E2T2F1iT'1*F1iE'1+T1F1,i), 6.1(q,5,E2T2F1iT'1*F1iE'1+T1F2,(E)), 4(b,5,E2T2F1iT'1*F1iE'1+T1F2,(E)), 6.3(b,5,E2T2F1iT'1*F1iE'1+T1,F), 6.1(q,5,E2T2F1iT'1*F1iE'1+T2,FT'), 1(q,5,E2T2F1iT'1*F1iE'1+T2F1,iT'), 4(b,5,E2T2F1iT'1*F1iE'1+T2F1,iT'), 6.1(q,5,E2T2F1iT'1*F1iE'1+T2F2,(E)T'), 4(b,5,E2T2F1iT'1*F1iE'1+T2F2,(E)T'), 6.3(b,5,E2T2F1iT'1*F1iE'1+T2,FT'), 6.3(b,5,E2T2F1iT'1*F1iE'1+,T), 5(b,4,E2T2F1iT'1*F1iE'1,+T), 6.1(q,4,E2T2F1iT'1*F1iE'2,+TE'), 2(q,5,E2T2F1iT'1*F1iE'2+,TE'), 1(q,5,E2T2F1iT'1*F1iE'2+T1,FE'), 1(q,5,E2T2F1iT'1*F1iE'2+T1F1,iE'), 4(b,5,E2T2F1iT'1*F1iE'2+T1F1,iE'), 6.1(q,5,E2T2F1iT'1*F1iE'2+T1F2,(E)E'), 4(b,5,E2T2F1iT'1*F1iE'2+T1F2,(E)E'), 6.3(b,5,E2T2F1iT'1*F1iE'2+T1,FE'), 6.1(q,5,E2T2F1iT'1*F1iE'2+T2,FT'E'), 1(q,5,E2T2F1iT'1*F1iE'2+T2F1,iT'E'), 4(b,5,E2T2F1iT'1*F1iE'2+T2F1,iT'E'), 6.1(q,5,E2T2F1iT'1*F1iE'2+T2F2,(E)T'E'), 4(b,5,E2T2F1iT'1*F1iE'2+T2F2,(E)T'E'), 6.3(b,5,E2T2F1iT'1*F1iE'2+T2,FT'E'), 6.3(b,5,E2T2F1iT'1*F1iE'2+,TE'), 5(b,4,E2T2F1iT'1*F1iE'2,+TE'), 6.3(b,4,E2T2F1iT'1*F1i,E'), 5(b,3,E2T2F1iT'1*F1,iE'), 6.1(q,3,E2T2F1iT'1*F2,(E)E'), 4(b,3,E2T2F1iT'1*F2,(E)E'), 6.3(b,3,E2T2F1iT'1*,FE'), 5(b,2,E2T2F1iT'1,*FE'), 6.1(q,2,E2T2F1iT'2,*FT'E'), 2(q,3,E2T2F1iT'2*,FT'E'), 1(q,3,E2T2F1iT'2*F1,iT'E'), 2(q,4,E2T2F1iT'2*F1i,T'E'), 1(q,4,E2T2F1iT'2*F1iT'1,*FE'), 4(b,4,E2T2F1iT'2*F1iT'1,*FE'), 6.1(q,4,E2T2F1iT'2*F1iT'2,*FT'E'), 4(b,4,E2T2F1iT'2*F1iT'2,*FT'E'), 6.3(b,4,E2T2F1iT'2*F1i,T'E'), 5(b,3,E2T2F1iT'2*F1,iT'E'), 6.1(q,3,E2T2F1iT'2*F2,(E)T'E'), 4(b,3,E2T2F1iT'2*F2,(E)T'E'), 6.3(b,3,E2T2F1iT'2*,FT'E'), 5(b,2,E2T2F1iT'2,*FT'E'), 6.3(b,2,E2T2F1i,T'E'), 5(b,1,E2T2F1,iT'E'), 6.1(q,1,E2T2F2,(E)T'E'), 4(b,1,E2T2F2,(E)T'E'), 6.3(b,1,E2T2,FT'E'), 6.3(b,1,E2,TE'), 6.3(b,1,λ,E)
    2. (q,1,λ,E), 1(q,1,E1,T), 1(q,1,E1T1,F), 1(q,1,E1T1F1,i), 2(q,2,E1T1F1i,λ), 4(b,2,E1T1F1i,λ), 5(b,1,E1T1F1,i), 6.1(q,1,E1T1F2,(E)), 4(b,1,E1T1F2,(E)), 6.3(b,1,E1T1,F), 6.1(q,1,E1T2,FT'), 1(q,1,E1T2F1,iT'), 2(q,2,E1T2F1i,T'), 1(q,2,E1T2F1iT'1,*F), 2(q,3,E1T2F1iT'1*,F), 1(q,3,E1T2F1iT'1*F1,i), 4(b,3,E1T2F1iT'1*F1,i), 6.1(q,3,E1T2F1iT'1*F2,(E)), 4(b,3,E1T2F1iT'1*F2,(E)), 6.3(b,3,E1T2F1iT'1*,F), 5(b,2,E1T2F1iT'1,*F), 6.1(q,2,E1T2F1iT'2,*FT'), 2(q,3,E1T2F1iT'2*,FT'), 1(q,3,E1T2F1iT'2*F1,iT'), 4(b,3,E1T2F1iT'2*F1,iT'), 6.1(q,3,E1T2F1iT'2*F2,(E)T'), 4(b,3,E1T2F1iT'2*F2,(E)T'), 6.3(b,3,E1T2F1iT'2*,FT'), 5(b,2,E1T2F1iT'2,*FT'), 6.3(b,2,E1T2F1i,T'), 5(b,1,E1T2F1,iT'), 6.1(q,1,E1T2F2,(E)T'), 4(b,1,E1T2F2,(E)T'), 6.3(b,1,E1T2,FT'), 6.3(b,1,E1,T), 6.1(q,1,E2,TE'), 1(q,1,E2T1,FE'), 1(q,1,E2T1F1,iE'), 2(q,2,E2T1F1i,E'), 1(q,2,E2T1F1iE'1,+T), 4(b,2,E2T1F1iE'1,+T), 6.1(q,2,E2T1F1iE'2,+TE'), 4(b,2,E2T1F1iE'2,+TE'), 6.3(b,2,E2T1F1i,E'), 5(b,1,E2T1F1,iE'), 6.1(q,1,E2T1F2,(E)E'), 4(b,1,E2T1F2,(E)E'), 6.3(b,1,E2T1,FE'), 6.1(q,1,E2T2,FT'E'), 1(q,1,E2T2F1,iT'E'), 2(q,2,E2T2F1i,T'E'), 1(q,2,E2T2F1iT'1,*FE'), 2(q,3,E2T2F1iT'1*,FE'), 1(q,3,E2T2F1iT'1*F1,iE'), 4(b,3,E2T2F1iT'1*F1,iE'), 6.1(q,3,E2T2F1iT'1*F2,(E)E'), 4(b,3,E2T2F1iT'1*F2,(E)E'), 6.3(b,3,E2T2F1iT'1*,FE'), 5(b,2,E2T2F1iT'1,*FE'), 6.1(q,2,E2T2F1iT'2,*FT'E'), 2(q,3,E2T2F1iT'2*,FT'E'), 1(q,3,E2T2F1iT'2*F1,iT'E'), 4(b,3,E2T2F1iT'2*F1,iT'E'), 6.1(q,3,E2T2F1iT'2*F2,(E)T'E'), 4(b,3,E2T2F1iT'2*F2,(E)T'E'), 6.3(b,3,E2T2F1iT'2*,FT'E'), 5(b,2,E2T2F1iT'2,*FT'E'), 6.3(b,2,E2T2F1i,T'E'), 5(b,1,E2T2F1,iT'E'), 6.1(q,1,E2T2F2,(E)T'E'), 4(b,1,E2T2F2,(E)T'E'), 6.3(b,1,E2T2,FT'E'), 6.3(b,1,E2,TE'), 6.3(b,1,λ,E)
    1. (q,1,λ,S), 1(q,1,S1,aAbB), 2(q,2,S1a,AbB), 1(q,2,S1aA1,aAcbB), 4(b,2,S1aA1,aAcbB), 6.1(q,2,S1aA2,bB), 2(q,3,S1aA2b,B), 1(q,3,S1aA2bB1,bB), 4(b,3,S1aA2bB1,bB), 6.1(q,3,S1aA2bB2,c), 4(b,3,S1aA2bB2,c), 6.3(b,3,S1aA2b,B), 5(b,2,S1aA2,bB), 6.3(b,2,S1a,AbB), 5(b,1,S1,aAbB), 6.3(b,1,λ,S)
    2. (q,1,λ,S), 1(q,1,S1,aAbB), 2(q,2,S1a,AbB), 1(q,2,S1aA1,aAcbB), 2(q,3,S1aA1a,AcbB), 1(q,3,S1aA1aA1,aAccbB), 4(b,3,S1aA1aA1,aAccbB), 6.1(q,3,S1aA1aA2,cbB), 4(b,3,S1aA1aA2,cbB), 6.3(b,3,S1aA1a,AcbB), 5(b,2,S1aA1,aAcbB), 6.1(q,2,S1aA2,bB), 4(b,2,S1aA2,bB), 6.3(b,2,S1a,AbB), 5(b,1,S1,aAbB), 6.3(b,1,λ,S)
    1. (q,1,λ,S), 1(q,1,S1,AB), 1(q,1,S1A1,aAbB), 2(q,2,S1A1a,AbB), 1(q,2,S1A1aA1,aAbbB), 4(b,2,S1A1aA1,aAbbB), 6.1(q,2,S1A1aA2,aAbB), 4(b,2,S1A1aA2,aAbB), 6.1(q,2,S1A1aA3,bbB), 2(q,3,S1A1aA3b,bB), 2(q,4,S1A1aA3bb,B), 1(q,4,S1A1aA3bbB1,AA), 1(q,4,S1A1aA3bbB1A1,aAbA), 2(q,5,S1A1aA3bbB1A1a,AbA), 1(q,5,S1A1aA3bbB1A1aA1,aAbbA), 4(b,5,S1A1aA3bbB1A1aA1,aAbbA), 6.1(q,5,S1A1aA3bbB1A1aA2,aAbA), 4(b,5,S1A1aA3bbB1A1aA2,aAbA), 6.1(q,5,S1A1aA3bbB1A1aA3,bbA), 2(q,6,S1A1aA3bbB1A1aA3b,bA), 4(b,6,S1A1aA3bbB1A1aA3b,bA), 5(b,5,S1A1aA3bbB1A1aA3,bbA), 6.3(b,5,S1A1aA3bbB1A1a,AbA), 5(b,4,S1A1aA3bbB1A1,aAbA), 6.1(q,4,S1A1aA3bbB1A2,aAA), 2(q,5,S1A1aA3bbB1A2a,AA), 1(q,5,S1A1aA3bbB1A2aA1,aAbA), 4(b,5,S1A1aA3bbB1A2aA1,aAbA), 6.1(q,5,S1A1aA3bbB1A2aA2,aAA), 4(b,5,S1A1aA3bbB1A2aA2,aAA), 6.1(q,5,S1A1aA3bbB1A2aA3,bA), 2(q,6,S1A1aA3bbB1A2aA3b,A), 1(q,6,S1A1aA3bbB1A2aA3bA1,aAb), 4(b,6,S1A1aA3bbB1A2aA3bA1,aAb), 6.1(q,6,S1A1aA3bbB1A2aA3bA2,aA), 4(b,6,S1A1aA3bbB1A2aA3bA2,aA), 6.1(q,6,S1A1aA3bbB1A2aA3bA3,b), 4(b,6,S1A1aA3bbB1A2aA3bA3,b), 6.3(b,6,S1A1aA3bbB1A2aA3b,A), 5(b,5,S1A1aA3bbB1A2aA3,bA), 6.3(b,5,S1A1aA3bbB1A2a,AA), 5(b,4,S1A1aA3bbB1A2,aAA), 6.1(q,4,S1A1aA3bbB1A3,bA), 4(b,4,S1A1aA3bbB1A3,bA), 6.3(b,4,S1A1aA3bbB1,AA), 6.3(b,4,S1A1aA3bb,B), 5(b,3,S1A1aA3b,bB), 5(b,2,S1A1aA3,bbB), 6.3(b,2,S1A1a,AbB), 5(b,1,S1A1,aAbB), 6.1(q,1,S1A2,aAB), 2(q,2,S1A2a,AB), 1(q,2,S1A2aA1,aAbB), 4(b,2,S1A2aA1,aAbB), 6.1(q,2,S1A2aA2,aAB), 4(b,2,S1A2aA2,aAB), 6.1(q,2,S1A2aA3,bB), 2(q,3,S1A2aA3b,B), 1(q,3,S1A2aA3bB1,AA), 1(q,3,S1A2aA3bB1A1,aAbA), 4(b,3,S1A2aA3bB1A1,aAbA), 6.1(q,3,S1A2aA3bB1A2,aAA), 4(b,3,S1A2aA3bB1A2,aAA), 6.1(q,3,S1A2aA3bB1A3,bA), 2(q,4,S1A2aA3bB1A3b,A), 1(q,4,S1A2aA3bB1A3bA1,aAb), 2(q,5,S1A2aA3bB1A3bA1a,Ab), 1(q,5,S1A2aA3bB1A3bA1aA1,aAbb), 4(b,5,S1A2aA3bB1A3bA1aA1,aAbb), 6.1(q,5,S1A2aA3bB1A3bA1aA2,aAb), 4(b,5,S1A2aA3bB1A3bA1aA2,aAb), 6.1(q,5,S1A2aA3bB1A3bA1aA3,bb), 2(q,6,S1A2aA3bB1A3bA1aA3b,b), 4(b,6,S1A2aA3bB1A3bA1aA3b,b), 5(b,5,S1A2aA3bB1A3bA1aA3,bb), 6.3(b,5,S1A2aA3bB1A3bA1a,Ab), 5(b,4,S1A2aA3bB1A3bA1,aAb), 6.1(q,4,S1A2aA3bB1A3bA2,aA), 2(q,5,S1A2aA3bB1A3bA2a,A), 1(q,5,S1A2aA3bB1A3bA2aA1,aAb), 4(b,5,S1A2aA3bB1A3bA2aA1,aAb), 6.1(q,5,S1A2aA3bB1A3bA2aA2,aA), 4(b,5,S1A2aA3bB1A3bA2aA2,aA), 6.1(q,5,S1A2aA3bB1A3bA2aA3,b), 2(q,6,S1A2aA3bB1A3bA2aA3b,λ)
    2. (q,1,λ,S), 1(q,1,S1,AB), 1(q,1,S1A1,aAbB), 4(b,1,S1A1,aAbB), 6.1(q,1,S1A2,aAB), 4(b,1,S1A2,aAB), 6.1(q,1,S1A3,bB), 2(q,2,S1A3b,B), 1(q,2,S1A3bB1,AA), 1(q,2,S1A3bB1A1,aAbA), 4(b,2,S1A3bB1A1,aAbA), 6.1(q,2,S1A3bB1A2,aAA), 4(b,2,S1A3bB1A2,aAA), 6.1(q,2,S1A3bB1A3,bA), 2(q,3,S1A3bB1A3b,A), 1(q,3,S1A3bB1A3bA1,aAb), 4(b,3,S1A3bB1A3bA1,aAb), 6.1(q,3,S1A3bB1A3bA2,aA), 4(b,3,S1A3bB1A3bA2,aA), 6.1(q,3,S1A3bB1A3bA3,b), 2(q,4,S1A3bB1A3bA3b,λ), 4(b,4,S1A3bB1A3bA3b,λ), 5(b,3,S1A3bB1A3bA3,b), 6.3(b,3,S1A3bB1A3b,A), 5(b,2,S1A3bB1A3,bA), 6.3(b,2,S1A3bB1,AA), 6.3(b,2,S1A3b,B), 5(b,1,S1A3,bB), 6.3(b,1,S1,AB), 6.3(b,1,λ,S)
    1. (q,1,λ,S), 1(q,1,S1,(S)S), 2(q,2,S1(,S)S), 1(q,2,S1(S1,(S)S)S), 2(q,3,S1(S1(,S)S)S), 1(q,3,S1(S1(S1,(S)S)S)S), 4(b,3,S1(S1(S1,(S)S)S)S), 6.1(q,3,S1(S1(S2,)S)S), 2(q,4,S1(S1(S2),S)S), 1(q,4,S1(S1(S2)S1,(S)S)S), 4(b,4,S1(S1(S2)S1,(S)S)S), 6.1(q,4,S1(S1(S2)S2,)S), 2(q,5,S1(S1(S2)S2),S), 1(q,5,S1(S1(S2)S2)S1,(S)S), 4(b,5,S1(S1(S2)S2)S1,(S)S), 6.1(q,5,S1(S1(S2)S2)S2,λ)
    2. (q,1,λ,S), 1(q,1,S1,(S)S), 2(q,2,S1(,S)S), 1(q,2,S1(S1,(S)S)S), 4(b,2,S1(S1,(S)S)S), 6.1(q,2,S1(S2,)S), 2(q,3,S1(S2),S), 1(q,3,S1(S2)S1,(S)S), 4(b,3,S1(S2)S1,(S)S), 6.1(q,3,S1(S2)S2,λ), 4(b,3,S1(S2)S2,λ), 6.3(b,3,S1(S2),S), 5(b,2,S1(S2,)S), 6.3(b,2,S1(,S)S), 5(b,1,S1,(S)S), 6.1(q,1,S2,λ), 4(b,1,S2,λ), 6.3(b,1,λ,S)
    1. (q,1,λ,S), 1(q,1,S1,aSa), 2(q,2,S1a,Sa), 1(q,2,S1aS1,aSaa), 4(b,2,S1aS1,aSaa), 6.1(q,2,S1aS2,bSba), 2(q,3,S1aS2b,Sba), 1(q,3,S1aS2bS1,aSaba), 4(b,3,S1aS2bS1,aSaba), 6.1(q,3,S1aS2bS2,bSbba), 2(q,4,S1aS2bS2b,Sbba), 1(q,4,S1aS2bS2bS1,aSabba), 4(b,4,S1aS2bS2bS1,aSabba), 6.1(q,4,S1aS2bS2bS2,bSbbba), 2(q,5,S1aS2bS2bS2b,Sbbba), 1(q,5,S1aS2bS2bS2bS1,aSabbba), 4(b,5,S1aS2bS2bS2bS1,aSabbba), 6.1(q,5,S1aS2bS2bS2bS2,bSbbbba), 4(b,5,S1aS2bS2bS2bS2,bSbbbba), 6.1(q,5,S1aS2bS2bS2bS3,abbba), 4(b,5,S1aS2bS2bS2bS3,abbba), 6.1(q,5,S1aS2bS2bS2bS4,bbbba), 4(b,5,S1aS2bS2bS2bS4,bbbba), 6.1(q,5,S1aS2bS2bS2bS5,bbba), 4(b,5,S1aS2bS2bS2bS5,bbba), 6.3(b,5,S1aS2bS2bS2b,Sbbba), 5(b,4,S1aS2bS2bS2,bSbbba), 6.1(q,4,S1aS2bS2bS3,abba), 4(b,4,S1aS2bS2bS3,abba), 6.1(q,4,S1aS2bS2bS4,bbba), 2(q,5,S1aS2bS2bS4b,bba), 4(b,5,S1aS2bS2bS4b,bba), 5(b,4,S1aS2bS2bS4,bbba), 6.1(q,4,S1aS2bS2bS5,bba), 2(q,5,S1aS2bS2bS5b,ba), 4(b,5,S1aS2bS2bS5b,ba), 5(b,4,S1aS2bS2bS5,bba), 6.3(b,4,S1aS2bS2b,Sbba), 5(b,3,S1aS2bS2,bSbba), 6.1(q,3,S1aS2bS3,aba), 4(b,3,S1aS2bS3,aba), 6.1(q,3,S1aS2bS4,bba), 2(q,4,S1aS2bS4b,ba), 2(q,5,S1aS2bS4bb,a), 4(b,5,S1aS2bS4bb,a), 5(b,4,S1aS2bS4b,ba), 5(b,3,S1aS2bS4,bba), 6.1(q,3,S1aS2bS5,ba), 2(q,4,S1aS2bS5b,a), 4(b,4,S1aS2bS5b,a), 5(b,3,S1aS2bS5,ba), 6.3(b,3,S1aS2b,Sba), 5(b,2,S1aS2,bSba), 6.1(q,2,S1aS3,aa), 4(b,2,S1aS3,aa), 6.1(q,2,S1aS4,ba), 2(q,3,S1aS4b,a), 4(b,3,S1aS4b,a), 5(b,2,S1aS4,ba), 6.1(q,2,S1aS5,a), 4(b,2,S1aS5,a), 6.3(b,2,S1a,Sa), 5(b,1,S1,aSa), 6.1(q,1,S2,bSb), 4(b,1,S2,bSb), 6.1(q,1,S3,a), 2(q,2,S3a,λ), 4(b,2,S3a,λ), 5(b,1,S3,a), 6.1(q,1,S4,b), 4(b,1,S4,b), 6.1(q,1,S5,λ), 4(b,1,S5,λ), 6.3(b,1,λ,S)
    2. (q,1,λ,S), 1(q,1,S1,aSa), 2(q,2,S1a,Sa), 1(q,2,S1aS1,aSaa), 4(b,2,S1aS1,aSaa), 6.1(q,2,S1aS2,bSba), 2(q,3,S1aS2b,Sba), 1(q,3,S1aS2bS1,aSaba), 2(q,4,S1aS2bS1a,Saba), 1(q,4,S1aS2bS1aS1,aSaaba), 4(b,4,S1aS2bS1aS1,aSaaba), 6.1(q,4,S1aS2bS1aS2,bSbaba), 2(q,5,S1aS2bS1aS2b,Sbaba), 1(q,5,S1aS2bS1aS2bS1,aSababa), 4(b,5,S1aS2bS1aS2bS1,aSababa), 6.1(q,5,S1aS2bS1aS2bS2,bSbbaba), 4(b,5,S1aS2bS1aS2bS2,bSbbaba), 6.1(q,5,S1aS2bS1aS2bS3,ababa), 4(b,5,S1aS2bS1aS2bS3,ababa), 6.1(q,5,S1aS2bS1aS2bS4,bbaba), 4(b,5,S1aS2bS1aS2bS4,bbaba), 6.1(q,5,S1aS2bS1aS2bS5,baba), 4(b,5,S1aS2bS1aS2bS5,baba), 6.3(b,5,S1aS2bS1aS2b,Sbaba), 5(b,4,S1aS2bS1aS2,bSbaba), 6.1(q,4,S1aS2bS1aS3,aaba), 4(b,4,S1aS2bS1aS3,aaba), 6.1(q,4,S1aS2bS1aS4,baba), 2(q,5,S1aS2bS1aS4b,aba), 4(b,5,S1aS2bS1aS4b,aba), 5(b,4,S1aS2bS1aS4,baba), 6.1(q,4,S1aS2bS1aS5,aba), 4(b,4,S1aS2bS1aS5,aba), 6.3(b,4,S1aS2bS1a,Saba), 5(b,3,S1aS2bS1,aSaba), 6.1(q,3,S1aS2bS2,bSbba), 4(b,3,S1aS2bS2,bSbba), 6.1(q,3,S1aS2bS3,aba), 2(q,4,S1aS2bS3a,ba), 2(q,5,S1aS2bS3ab,a), 4(b,5,S1aS2bS3ab,a), 5(b,4,S1aS2bS3a,ba), 5(b,3,S1aS2bS3,aba), 6.1(q,3,S1aS2bS4,bba), 4(b,3,S1aS2bS4,bba), 6.1(q,3,S1aS2bS5,ba), 4(b,3,S1aS2bS5,ba), 6.3(b,3,S1aS2b,Sba), 5(b,2,S1aS2,bSba), 6.1(q,2,S1aS3,aa), 4(b,2,S1aS3,aa), 6.1(q,2,S1aS4,ba), 2(q,3,S1aS4b,a), 2(q,4,S1aS4ba,λ), 4(b,4,S1aS4ba,λ), 5(b,3,S1aS4b,a), 5(b,2,S1aS4,ba), 6.1(q,2,S1aS5,a), 4(b,2,S1aS5,a), 6.3(b,2,S1a,Sa), 5(b,1,S1,aSa), 6.1(q,1,S2,bSb), 4(b,1,S2,bSb), 6.1(q,1,S3,a), 2(q,2,S3a,λ), 4(b,2,S3a,λ), 5(b,1,S3,a), 6.1(q,1,S4,b), 4(b,1,S4,b), 6.1(q,1,S5,λ), 4(b,1,S5,λ), 6.3(b,1,λ,S)

LL(1) elemzés

[Megjegyzés]Megjegyzés

A feladatmegoldások során az input végét a $ jellel jelöljük.

  1. Maga a nyelvtan balrekurzív, így biztos nem LL(1) nyelvtan. Ennek ellenére meg tudjuk határozni a megfelelő halmazokat: First(S)={a} és Follow(S)={a,$}. Így a táblázat a következő:

     a$
    Sa, Sa 
  2. A nyelv már nem balrekurzív. Lássuk a halmazokat:

     FirstFollow
    S{c}{$}
    A{c}{a}
    B{c}{b}

    Ennek alapján elkészítve a táblázatot, láthatjuk, hogy miért nem LL(1) nyelvtanról van szó.

     abc$
    S  Aa, Bb 
    A  c, cA 
    B  c, cB 
  3. Lássuk először a halmazokat:

     FirstFollow
    S{a,b}{$}
    A{c,d,e,f}{$}
    B{e,λ}{c,d}
    C{f,λ}{c}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     abcdef$
    SaAbBc     
    A  CcBdBdCc 
    B  λλe  
    C  λ  f 
  4. Lássuk először a halmazokat:

     FirstFollow
    S{b}{$}
    A{b}{$,a}

    Készítsük el az elemző táblázatot! Az ütközés miatt a nyelvtan nem LL(1).

     ab$
    S A, AaS 
    A b, bcA 
  5. Lássuk először a halmazokat:

     FirstFollow
    E{(,i}{$,)}
    E'{λ,+}{$,)}
    T{(,i}{$,+,)}
    T'{λ,*}{$,+,)}
    F{(,i}{$,+,*,)}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     ()*+i$
    ETE'   TE' 
    E' λ +TE' λ
    TFT'   FT' 
    T' λ*FT'λ λ
    F(E)   i 
  6. Lássuk először a halmazokat:

     FirstFollow
    S{a,i}{e,$}

    Készítsük el az elemző táblázatot! Mint látjuk, van ütközés, a nyelvtan nem LL(1). Ez a csellengő else problémája.

     abeit$
    Sa  ibtS, ibtSeS  
  7. Lássuk először a halmazokat:

     FirstFollow
    S{a,b}{$}
    A{λ,a}{a,b}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     ab$
    SaAabbAbb 
    Aλ, aλ 
  8. Lássuk először a halmazokat:

     FirstFollow
    S{λ,a,b,c}{$}
    A{λ,a}{$,a,b,c}
    B{λ,b}{$,a}
    C{a,b}{$}
    D{a}{$,a}

    Készítsük el az elemző táblázatot! Mint látjuk, az [A,a] pozícióban ütközés van.

     abc$
    SABAABAcCABA
    Aλ, aλλλ
    BλbD λ
    CADb  
    DaAc   
  9. Lássuk először a halmazokat:

     FirstFollow
    S{a}{$}
    A{a}{b,$}
    B{λ,b}{c,$}

    Készítsük el az elemző táblázatot!

     abc$
    SAB   
    AaAb, ab   
    B bBcλλ
  10. Lássuk először a halmazokat:

     FirstFollow
    S{a,b,c}{$}
    A{λ,a,b,c}{a}
    B{λ,a,c}{a}

    Készítsük el az elemző táblázatot!

     abcd$
    SAaAa, bAa  
    ABbdBB  
    Bλ, abB cB  
  11. Lássuk először a halmazokat:

     FirstFollow
    S{λ,a,b}{$}
    A{λ,a}{$,a,b}
    B{λ,b}{$,a,b}

    Készítsük el az elemző táblázatot!

     ab$
    SABBAABBAABBA
    Aλ, aλλ
    Bλλ, bλ
  12. Lássuk először a halmazokat:

     FirstFollow
    S{a}{$}
    A{a,c}{b}
    B{a,d}{b}

    Készítsük el az elemző táblázatot!

     abcd$
    SaAb, aBbb c  
    AaAb  d 
    BaBbb    
  13. Lássuk először a halmazokat:

     FirstFollow
    S{a,b}{$}
    A{a,b}{b,c}
    B{b,c}{$,c}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     abc$
    SABAB  
    AaBbb  
    B bBcc 
  14. Lássuk először a halmazokat:

     FirstFollow
    S{b}{$}
    A{a,b}{a,b}
    B{b}{a,b}

    Készítsük el az elemző táblázatot!

     ab$
    S Ba 
    Aaabb 
    B BB, bA 
  15. Lássuk először a halmazokat:

     FirstFollow
    S{a,c}{$}
    A{a,c}{$,a,b,c}
    B{a,b,c}{$,a,b,c}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     abc$
    SAB AB 
    Aa cB 
    BaAbBc 
  16. Lássuk először a halmazokat:

     FirstFollow
    S{a,b}{$}
    A{λ,b}{$,a,b}
    B{a,b}{$}

    Készítsük el az elemző táblázatot!

     ab$
    SaAbB 
    Aλλ, baλ
    BAB, aAB 
  17. Lássuk először a halmazokat:

     FirstFollow
    S{a,b,c}{$}
    A{a,b}{$,a,b}
    B{b}{c}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     abc$
    SAAAAc 
    AaBc  
    B b, bb  
  18. Lássuk először a halmazokat:

     FirstFollow
    S{b,c}{$}
    A{λ,b}{c}
    B{c}{c}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     bc$
    SABcABc 
    AbAλ 
    B c 
  19. Lássuk először a halmazokat:

     FirstFollow
    S{a,b}{$}
    A{λ,a,b}{}
    B{a,b}{$,a}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     ab$
    SBaBBaB 
    Aabab 
    BabB 
  20. Lássuk először a halmazokat:

     FirstFollow
    S{a,b}{$}
    A{a,b}{b,c}
    B{a,c}{$,b}

    Készítsük el az elemző táblázatot! Mint látjuk, nincs ütközés, így a nyelvtan LL(1).

     abc$
    SAcBAcB  
    AaAbba  
    BaBbcba  

Általános alulról-felfelé elemzés

[Megjegyzés]Megjegyzés

A feladatmegoldások során felső indexként jelöljük a lépések Fülöp Zoltán jegyzete [Fülöp99] szerinti sorszámát.

    1. (q,1,λ,λ), 2(q,2,i,s), 1(q,2,F,5s), 1(q,2,T,45s), 1(q,2,E,245s), 2(q,3,E*,s245s), 2(q,4,E*i,ss245s), 1(q,4,E*F,5ss245s), 1(q,4,E*T,45ss245s), 1(q,4,E*E,245ss245s), 2(q,5,E*E+,s245ss245s), 4(b,5,E*E+,s245ss245s), 5.4(b,4,E*E,245ss245s), 5.3(q,5,E*T+,s45ss245s), 4(b,5,E*T+,s45ss245s), 5.4(b,4,E*T,45ss245s), 5.3(q,5,E*F+,s5ss245s), 4(b,5,E*F+,s5ss245s), 5.4(b,4,E*F,5ss245s), 5.3(q,5,E*i+,sss245s), 4(b,5,E*i+,sss245s), 5.4(b,4,E*i,ss245s), 5.4(b,3,E*,s245s), 5.4(b,2,E,245s), 5.3(q,3,T*,s45s), 2(q,4,T*i,ss45s), 1(q,4,T*F,5ss45s), 1(q,4,T,35ss45s), 1(q,4,E,235ss45s), 2(q,5,E+,s235ss45s), 4(b,5,E+,s235ss45s), 5.4(b,4,E,235ss45s), 5.3(q,5,T+,s35ss45s), 4(b,5,T+,s35ss45s), 5.4(b,4,T,35ss45s), 5.1(q,4,T*T,45ss45s), 1(q,4,T*E,245ss45s), 2(q,5,T*E+,s245ss45s), 4(b,5,T*E+,s245ss45s), 5.4(b,4,T*E,245ss45s), 5.3(q,5,T*T+,s45ss45s), 4(b,5,T*T+,s45ss45s), 5.4(b,4,T*T,45ss45s), 5.3(q,5,T*F+,s5ss45s), 4(b,5,T*F+,s5ss45s), 5.4(b,4,T*F,5ss45s), 5.3(q,5,T*i+,sss45s), 4(b,5,T*i+,sss45s), 5.4(b,4,T*i,ss45s), 5.4(b,3,T*,s45s), 5.4(b,2,T,45s), 5.3(q,3,F*,s5s), 2(q,4,F*i,ss5s), 1(q,4,F*F,5ss5s), 1(q,4,F*T,45ss5s), 1(q,4,F*E,245ss5s), 2(q,5,F*E+,s245ss5s), 4(b,5,F*E+,s245ss5s), 5.4(b,4,F*E,245ss5s), 5.3(q,5,F*T+,s45ss5s), 4(b,5,F*T+,s45ss5s), 5.4(b,4,F*T,45ss5s), 5.3(q,5,F*F+,s5ss5s), 4(b,5,F*F+,s5ss5s), 5.4(b,4,F*F,5ss5s), 5.3(q,5,F*i+,sss5s), 4(b,5,F*i+,sss5s), 5.4(b,4,F*i,ss5s), 5.4(b,3,F*,s5s), 5.4(b,2,F,5s), 5.3(q,3,i*,ss), 2(q,4,i*i,sss), 1(q,4,i*F,5sss), 1(q,4,i*T,45sss), 1(q,4,i*E,245sss), 2(q,5,i*E+,s245sss), 4(b,5,i*E+,s245sss), 5.4(b,4,i*E,245sss), 5.3(q,5,i*T+,s45sss), 4(b,5,i*T+,s45sss), 5.4(b,4,i*T,45sss), 5.3(q,5,i*F+,s5sss), 4(b,5,i*F+,s5sss), 5.4(b,4,i*F,5sss), 5.3(q,5,i*i+,ssss), 4(b,5,i*i+,ssss), 5.4(b,4,i*i,sss), 5.4(b,3,i*,ss), 5.4(b,2,i,s), 5.4(b,1,λ,λ)
    2. (q,1,λ,λ), 2(q,2,i,s), 1(q,2,F,5s), 1(q,2,T,45s), 1(q,2,E,245s), 2(q,3,E*,s245s), 2(q,4,E*i,ss245s), 1(q,4,E*F,5ss245s), 1(q,4,E*T,45ss245s), 1(q,4,E*E,245ss245s), 4(b,4,E*E,245ss245s), 5.2(b,4,E*T,45ss245s), 5.2(b,4,E*F,5ss245s), 5.2(b,4,E*i,ss245s), 5.4(b,3,E*,s245s), 5.4(b,2,E,245s), 5.3(q,3,T*,s45s), 2(q,4,T*i,ss45s), 1(q,4,T*F,5ss45s), 1(q,4,T,35ss45s), 1(q,4,E,235ss45s)
    1. (q,1,λ,λ), 2(q,2,a,s), 2(q,3,ab,ss), 2(q,4,aba,sss), 2(q,5,abab,ssss), 4(b,5,abab,ssss), 5.4(b,4,aba,sss), 5.4(b,3,ab,ss), 5.4(b,2,a,s), 5.4(b,1,λ,λ)
    2. (q,1,λ,λ), 2(q,2,a,s), 2(q,3,aa,ss), 2(q,4,aab,sss), 2(q,5,aabc,ssss), 1(q,5,aabB,5ssss), 1(q,5,aabA,35ssss), 4(b,5,aabA,35ssss), 5.1(q,5,aaB,45ssss), 1(q,5,aaA,345ssss), 4(b,5,aaA,345ssss), 5.2(b,5,aaB,45ssss), 5.2(b,5,aabB,5ssss), 5.2(b,5,aabc,ssss), 5.4(b,4,aab,sss), 5.4(b,3,aa,ss), 5.4(b,2,a,s), 5.4(b,1,λ,λ)
    1. (q,1,λ,λ), 2(q,2,a,s), 2(q,3,ab,ss), 1(q,3,aA,4ss), 1(q,3,A,34ss), 2(q,4,Ab,s34ss), 1(q,4,AA,4s34ss), 1(q,4,B,54s34ss), 2(q,5,Ba,s54s34ss), 2(q,6,Bab,ss54s34ss), 1(q,6,BaA,4ss54s34ss), 1(q,6,BA,34ss54s34ss), 4(b,6,BA,34ss54s34ss), 5.2(b,6,BaA,4ss54s34ss), 5.2(b,6,Bab,ss54s34ss), 5.4(b,5,Ba,s54s34ss), 5.4(b,4,B,54s34ss), 5.3(q,5,AAa,s4s34ss), 2(q,6,AAab,ss4s34ss), 1(q,6,AAaA,4ss4s34ss), 1(q,6,AAA,34ss4s34ss), 1(q,6,AB,534ss4s34ss), 1(q,6,S,1534ss4s34ss)
    2. (q,1,λ,λ), 2(q,2,b,s), 1(q,2,A,4s), 2(q,3,Ab,s4s), 1(q,3,AA,4s4s), 1(q,3,B,54s4s), 2(q,4,Bb,s54s4s), 1(q,4,BA,4s54s4s), 2(q,5,BAb,s4s54s4s), 1(q,5,BAA,4s4s54s4s), 1(q,5,BB,54s4s54s4s), 4(b,5,BB,54s4s54s4s), 5.2(b,5,BAA,4s4s54s4s), 5.2(b,5,BAb,s4s54s4s), 5.4(b,4,BA,4s54s4s), 5.3(q,5,Bbb,ss54s4s), 1(q,5,BbA,4ss54s4s), 4(b,5,BbA,4ss54s4s), 5.2(b,5,Bbb,ss54s4s), 5.4(b,4,Bb,s54s4s), 5.4(b,3,B,54s4s), 5.3(q,4,AAb,s4s4s), 1(q,4,AAA,4s4s4s), 1(q,4,AB,54s4s4s), 1(q,4,S,154s4s4s), 2(q,5,Sb,s154s4s4s), 1(q,5,SA,4s154s4s4s), 4(b,5,SA,4s154s4s4s), 5.2(b,5,Sb,s154s4s4s), 5.4(b,4,S,154s4s4s), 5.3(q,5,ABb,s54s4s4s), 1(q,5,ABA,4s54s4s4s), 4(b,5,ABA,4s54s4s4s), 5.2(b,5,ABb,s54s4s4s), 5.4(b,4,AB,54s4s4s), 5.3(q,5,AAAb,s4s4s4s), 1(q,5,AAAA,4s4s4s4s), 1(q,5,AAB,54s4s4s4s), 1(q,5,AS,154s4s4s4s), 4(b,5,AS,154s4s4s4s), 5.2(b,5,AAB,54s4s4s4s), 5.2(b,5,AAAA,4s4s4s4s), 5.2(b,5,AAAb,s4s4s4s), 5.4(b,4,AAA,4s4s4s), 5.3(q,5,AAbb,ss4s4s), 1(q,5,AAbA,4ss4s4s), 4(b,5,AAbA,4ss4s4s), 5.2(b,5,AAbb,ss4s4s), 5.4(b,4,AAb,s4s4s), 5.4(b,3,AA,4s4s), 5.3(q,4,Abb,ss4s), 1(q,4,AbA,4ss4s), 2(q,5,AbAb,s4ss4s), 1(q,5,AbAA,4s4ss4s), 1(q,5,AbB,54s4ss4s), 4(b,5,AbB,54s4ss4s), 5.2(b,5,AbAA,4s4ss4s), 5.2(b,5,AbAb,s4ss4s), 5.4(b,4,AbA,4ss4s), 5.3(q,5,Abbb,sss4s), 1(q,5,AbbA,4sss4s), 4(b,5,AbbA,4sss4s), 5.2(b,5,Abbb,sss4s), 5.4(b,4,Abb,ss4s), 5.4(b,3,Ab,s4s), 5.4(b,2,A,4s), 5.3(q,3,bb,ss), 1(q,3,bA,4ss), 2(q,4,bAb,s4ss), 1(q,4,bAA,4s4ss), 1(q,4,bB,54s4ss), 2(q,5,bBb,s54s4ss), 1(q,5,bBA,4s54s4ss), 4(b,5,bBA,4s54s4ss), 5.2(b,5,bBb,s54s4ss), 5.4(b,4,bB,54s4ss), 5.3(q,5,bAAb,s4s4ss), 1(q,5,bAAA,4s4s4ss), 1(q,5,bAB,54s4s4ss), 1(q,5,bS,154s4s4ss), 4(b,5,bS,154s4s4ss), 5.2(b,5,bAB,54s4s4ss), 5.2(b,5,bAAA,4s4s4ss)ű, 5.2(b,5,bAAb,s4s4ss), 5.4(b,4,bAA,4s4ss), 5.3(q,5,bAbb,ss4ss), 1(q,5,bAbA,4ss4ss), 4(b,5,bAbA,4ss4ss), 5.2(b,5,bAbb,ss4ss), 5.4(b,4,bAb,s4ss), 5.4(b,3,bA,4ss), 5.3(q,4,bbb,sss), 1(q,4,bbA,4sss), 2(q,5,bbAb,s4sss), 1(q,5,bbAA,4s4sss), 1(q,5,bbB,54s4sss), 4(b,5,bbB,54s4sss), 5.2(b,5,bbAA,4s4sss), 5.2(b,5,bbAb,s4sss), 5.4(b,4,bbA,4sss), 5.3(q,5,bbbb,ssss), 1(q,5,bbbA,4ssss), 4(b,5,bbbA,4ssss), 5.2(b,5,bbbb,ssss), 5.4(b,4,bbb,sss), 5.4(b,3,bb,ss), 5.4(b,2,b,s), 5.4(b,1,λ,λ)
    1. (q,1,λ,λ), 2(q,2,(,s), 2(q,3,((,ss), 2(q,4,((),sss), 1(q,4,(S,2sss), 2(q,5,(S),s2sss), 4(b,5,(S),s2sss), 5.4(b,4,(S,2sss), 5.3(q,5,(()),ssss), 4(b,5,(()),ssss), 5.4(b,4,((),sss), 5.4(b,3,((,ss), 5.4(b,2,(,s), 5.4(b,1,λ,λ)
    2. (q,1,λ,λ), 2(q,2,(,s), 2(q,3,(),ss), 1(q,3,S,2ss), 2(q,4,S),s2ss), 2(q,5,S)),ss2ss), 4(b,5,S)),ss2ss), 5.4(b,4,S),s2ss), 5.4(b,3,S,2ss), 5.3(q,4,()),sss), 2(q,5,())),ssss), 4(b,5,())),ssss), 5.4(b,4,()),sss), 5.4(b,3,(),ss), 5.4(b,2,(,s), 5.4(b,1,λ,λ)
    1. (q,1,λ,λ), 2(q,2,a,s), 1(q,2,S,3s), 2(q,3,Sb,s3s), 1(q,3,SS,4s3s), 2(q,4,SSb,s4s3s), 1(q,4,SSS,4s4s3s), 2(q,5,SSSa,s4s4s3s), 1(q,5,SSSS,3s4s4s3s), 4(b,5,SSSS,3s4s4s3s), 5.2(b,5,SSSa,s4s4s3s), 5.4(b,4,SSS,4s4s3s), 5.3(q,5,SSba,ss4s3s), 1(q,5,SSbS,3ss4s3s), 4(b,5,SSbS,3ss4s3s), 5.2(b,5,SSba,ss4s3s), 5.4(b,4,SSb,s4s3s), 5.4(b,3,SS,4s3s), 5.3(q,4,Sbb,ss3s), 1(q,4,SbS,4ss3s), 2(q,5,SbSa,s4ss3s), 1(q,5,SbSS,3s4ss3s), 4(b,5,SbSS,3s4ss3s), 5.2(b,5,SbSa,s4ss3s), 5.4(b,4,SbS,4ss3s), 5.1(q,4,SS,6ss3s), 2(q,5,SSa,s6ss3s), 1(q,5,SSS,3s6ss3s), 4(b,5,SSS,3s6ss3s), 5.2(b,5,SSa,s6ss3s), 5.4(b,4,SS,6ss3s), 5.3(q,5,Sbba,sss3s), 1(q,5,SbbS,3sss3s), 4(b,5,SbbS,3sss3s), 5.2(b,5,Sbba,sss3s), 5.4(b,4,Sbb,ss3s), 5.4(b,3,Sb,s3s), 5.4(b,2,S,3s), 5.3(q,3,ab,ss), 1(q,3,aS,4ss), 2(q,4,aSb,s4ss), 1(q,4,aSS,4s4ss), 2(q,5,aSSa,s4s4ss), 1(q,5,aSSS,3s4s4ss), 4(b,5,aSSS,3s4s4ss), 5.2(b,5,aSSa,s4s4ss), 5.4(b,4,aSS,4s4ss), 5.3(q,5,aSba,ss4ss), 1(q,5,aSbS,3ss4ss), 4(b,5,aSbS,3ss4ss), 5.2(b,5,aSba,ss4ss), 5.4(b,4,aSb,s4ss), 5.4(b,3,aS,4ss), 5.3(q,4,abb,sss), 1(q,4,abS,4sss), 2(q,5,abSa,s4sss), 1(q,5,abSS,3s4sss), 4(b,5,abSS,3s4sss), 5.2(b,5,abSa,s4sss), 5.4(b,4,abS,4sss), 5.1(q,4,aS,6sss), 2(q,5,aSa,s6sss), 1(q,5,S,1s6sss)
    2. (q,1,λ,λ), 2(q,2,a,s), 1(q,2,S,3s), 2(q,3,Sb,s3s), 1(q,3,SS,4s3s), 2(q,4,SSa,s4s3s), 1(q,4,SSS,3s4s3s), 2(q,5,SSSb,s3s4s3s), 1(q,5,SSSS,4s3s4s3s), 4(b,5,SSSS,4s3s4s3s), 5.2(b,5,SSSb,s3s4s3s), 5.4(b,4,SSS,3s4s3s), 5.3(q,5,SSab,ss4s3s), 1(q,5,SSaS,4ss4s3s), 4(b,5,SSaS,4ss4s3s), 5.2(b,5,SSab,ss4s3s), 5.4(b,4,SSa,s4s3s), 5.4(b,3,SS,4s3s), 5.3(q,4,Sba,ss3s), 1(q,4,SbS,3ss3s), 2(q,5,SbSb,s3ss3s), 1(q,5,SS,2s3ss3s), 4(b,5,SS,2s3ss3s), 5.1(q,5,SbSS,4s3ss3s), 4(b,5,SbSS,4s3ss3s), 5.2(b,5,SbSb,s3ss3s), 5.4(b,4,SbS,3ss3s), 5.3(q,5,Sbab,sss3s), 1(q,5,SbaS,4sss3s), 4(b,5,SbaS,4sss3s), 5.2(b,5,Sbab,sss3s), 5.4(b,4,Sba,ss3s), 5.4(b,3,Sb,s3s), 5.4(b,2,S,3s), 5.3(q,3,ab,ss), 1(q,3,aS,4ss), 2(q,4,aSa,s4ss), 1(q,4,S,1s4ss), 2(q,5,Sb,s1s4ss), 1(q,5,SS,4s1s4ss), 4(b,5,SS,4s1s4ss), 5.2(b,5,Sb,s1s4ss), 5.4(b,4,S,1s4ss), 5.1(q,4,aSS,3s4ss), 2(q,5,aSSb,s3s4ss), 1(q,5,aSSS,4s3s4ss), 4(b,5,aSSS,4s3s4ss), 5.2(b,5,aSSb,s3s4ss), 5.4(b,4,aSS,3s4ss), 5.3(q,5,aSab,ss4ss), 1(q,5,aSaS,4ss4ss), 4(b,5,aSaS,4ss4ss), 5.2(b,5,aSab,ss4ss), 5.4(b,4,aSa,s4ss), 5.4(b,3,aS,4ss), 5.3(q,4,aba,sss), 1(q,4,abS,3sss), 2(q,5,abSb,s3sss), 1(q,5,aS,2s3sss), 4(b,5,aS,2s3sss), 5.1(q,5,abSS,4s3sss), 4(b,5,abSS,4s3sss), 5.2(b,5,abSb,s3sss), 5.4(b,4,abS,3sss), 5.3(q,5,abab,ssss), 1(q,5,abaS,4ssss), 4(b,5,abaS,4ssss), 5.2(b,5,abab,ssss), 5.4(b,4,aba,sss), 5.4(b,3,ab,ss), 5.4(b,2,a,s), 5.4(b,1,λ,λ)

Operátorprecedencia elemzés

[Megjegyzés]Megjegyzés

Az operátorprecedencia elemzés igen közismert, és szinte annyi megközelítése van, ahány szerző. Vannak irányzatok, ahol a precedencia az egyedüli vezérfonal, máshol kiemelik az operátorokat, és azok kapcsolata lényeges. Mivel a precedencia a feladatokban szereplő nyelvtanokban van elrejtve, így azt nem adjuk meg külön, hanem az elemzés során a Csörnyei Zoltán könyvében [Csörnyei06] szereplő módszert alkalmazzuk (amely Grune és Jacobs ötletén [Grune90] alapul). Az előbb említett szerzők jelöléseitől eltérően, az egyszerűség kedvéért ebben a fejezetben First(A)jelöli az A-ból levezethető (terminális és nemterminális) szimbólumok sorozatai első terminálisainak halmazát. (Az operátornyelvtan feltevései alapján egy ilyen szimbólum a szimbólumsorozat első vagy második karaktere lehet csak). Hasonlóan Last(A) jelöli az A-ból levezethető szimbólumsorozatok utolsó terminális karaktereinek halmazát. Mint a későbbiekben, itt is bevezetünk egy új S' mondatszimbólumot. Ha S az eredeti mondatszimbólum, a helyettesítési szabályokat kiegészítjük az S' → #S# szabállyal, ahol # jelöli az input elejét és végét.

A különböző fejezetekben rendszerint ugyanazokat a nyelvtanokat vizsgáljuk meg, többek között a módszerek összehasonlíthatósága érdekében. Ilyen módon igen sok feladat található a fejezetben, melyben nem operátornyelvtan szerepel. Ennek ellenére az elemző táblázat elkészíthető a nyelvtan minimális átalakításával.

A terminálisok között a következő relációkat definiáljuk:

  • a==b, ha van olyan szabály a nyelvtanban, hogy A → αabβ vagy A → αaBbβ;

  • a<<b, ha van olyan szabály a nyelvtanban, hogy A → αaBβ és b∈First(B);

  • a>>b, ha van olyan szabály a nyelvtanban, hogy A → αBbβ és a∈Last(B).

  1. A First és Last halmaz a következő lesz:

     FirstLast
    S{a}{a}

    Ez alapján az elemző táblázat:

     #a
    #acc<<
    a>>>>
  2. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b,c}{a,b}
    A{c}{c}
    B{c}{c}

    Ez alapján az elemző táblázat:

     #abc
    #acc  <<
    a>>   
    b>>   
    c >>>><<

    Noha a táblázat nem tartalmaz ellentmondást, az nyelvtanban két szabálynak is ugyaz a jobb oldala, így nem lehet egyértelmű az elemzés!

  3. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{a,c,d}
    A{c,d,e,f}{c,d}

    Ez alapján az elemző táblázat:

     #abcdef
    #acc<<<<    
    a>>  <<<<<<<<
    b   == == 
    c>>      
    d>>      
    e   ====  
    f   ==   
  4. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{a,b,c}
    A{b}{b,c}

    Ez alapján az elemző táblázat:

     #abc
    #acc<<<< 
    a>><<<< 
    b>>>> ==
    c>>>><< 
  5. A First és Last halmaz a következő lesz:

     FirstLast
    E{+,*,(,i}{+,*,),i}
    T{*,(,i}{*,),i}
    F{(,i}{),i}

    Ez alapján az elemző táblázat:

     #+*()i
    #acc<<<<<< <<
    +>>>><<<<>><<
    *>>>><<<<>><<
    ( <<<<<<==<<
    )>>>>>> >> 
    i>>>>>> >> 
  6. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,i}{a,t,e}

    Ez alapján az elemző táblázat:

     #abite
    #acc<< <<  
    a>>    >>
    b    == 
    i  ==   
    t>><< << >>, ==
    e>><< << >>

    A [t,e] mezőben szereplő ütközés a csellengő else problémára utal.

  7. Az eredeti nyelvtan nem operátor nyelvtan, ezért a balrekurzió megszüntetése feladatainál szereplő módon átalakíthatjuk a nyelvtant: S → Ab|AaA, A → b|aA. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{a,b}
    A{a,b}{a,b}

    Ez alapján az elemző táblázat:

     #ab
    #acc<<<<
    a>><<,>><<,>>
    b>>>>>>
  8. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,c}{a,b,c}
    B{b}{b,c}
    C{a,b}{a,b,c}
    D{a}{c}

    Ez alapján az elemző táblázat:

     #abc
    #acc<< <<
    a>><<,==<<==
    b>><<,>>  
    c>><<,>><< 
  9. Az eredeti nyelvtan nem operátor nyelvtan, ezért az alábbi alakra hozzuk:

    S → A|AbBc|Abc, A → aAb|ab, B → bBc|bc.

    A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{b,c}
    A{a}{b}
    B{b}{c}

    Ez alapján az elemző táblázat:

     #abc
    #acc<<<< 
    a <<== 
    b>> <<,>>==
    c>>  >>
  10. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b,c}{a,b}
    A{a,b,c}{b,c,d}
    B{a,c}{b,c}

    Ez alapján az elemző táblázat:

     #abcd
    #acc<<<<<< 
    a>> ==  
    b>><<,>> <<==
    c <<,>> << 
    d <<,>> << 
  11. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{b,c,d}
    A{f}{f}
    B{f}{f}

    Ez alapján az elemző táblázat:

     #abcdf
    #acc<<<<   
    a     <<
    b>>    <<
    c>>     
    d>>     
    f  >>>>>> 
  12. A First és Last halmaz a következő lesz:

     FirstLast
    S{a}{b}
    A{a,c}{b,c}
    B{a,d}{b,d}

    Ez alapján az elemző táblázat:

     #abcd
    #acc<<   
    a << <<<<
    b>> ==,>>  
    c  >>  
    d  >>  

    Az ütközésen kívül még vannak olyan szabályok is, melynek a jobb oldalai megegyeznek.

  13. Az eredeti nyelvtan nem operátor nyelvtan, ezért az alábbi alakra hozzuk:

    S → aAbB|bB, A → aAb|b, B → bBc|c.

    A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{b,c}
    A{a,b}{b}
    B{b,c}{c}

    Ez alapján az elemző táblázat:

     #abc
    #acc<<<< 
    a <<<<,== 
    b>> <<,>><<
    c>>  >>
  14. Az eredeti nyelvtan nem operátor nyelvtan, ezért az alábbi alakra hozzuk:

    S → Ba, A → aa|bb, B → baaB|bbbB|bA.

    A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{a}
    A{a,b}{a,b}
    B{b}{a,b}

    Ez alapján az elemző táblázat:

     #ab
    #acc<<<<
    a>>==,>><<
    b <<,==,>><<,==
  15. Az eredeti nyelvtan nem operátor nyelvtan, ezért az alábbi alakra hozzuk:

    S → Ac|AaA|AbB, A → a|cB, B → c|aA|bB.

    A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b,c}{a,b,c}
    A{a,c}{a,b,c}
    B{a,b,c}{a,b,c}

    Ez alapján az elemző táblázat:

     #abc
    #acc<<<<<<
    a>><<,>>>><<,>>
    b>><<,>><<,>><<,>>
    c>><<,>><<,>><<,>>
  16. Az eredeti nyelvtan nem operátor nyelvtan, az alábbi alakra hozzuk:

    S → A|bB, A → a|ba, B → aB|baB|a.

    A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{a,b}
    A{a,b}{a}
    B{a,b}{a}

    Ez alapján az elemző táblázat:

     #ab
    #acc<<<<
    a>><<<<
    b>><<,==<<
  17. Az eredeti nyelvtan nem operátor nyelvtan, ezért a következő alakra hozzuk:

    S → BcA|aA|c, A → Bc|a, B → b|bb.

    A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b,c}{a,c}
    A{a,b}{a,c}
    B{b}{b}

    Ez alapján az elemző táblázat:

     #abc
    #acc<<<<<<
    a>><<<<<<
    b  ==>>
    c>><<<<<<
  18. Az eredeti nyelvtan nem operátor nyelvtan, ezért az alábbi alakra hozzuk:

    S → Acc, A → bA|b.

    A First és Last halmaz a következő lesz:

     FirstLast
    S{b,c}{c}
    A{b}{b}

    Ez alapján az elemző táblázat:

     #bc
    #acc<<<<
    b <<>>
    c>> ==
  19. Az eredeti nyelvtanban az A felesleges szimbólum, így kihagyjuk a hozzá tartozó szabályokat. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{a,b}
    B{a,b}{a,b}

    Ez alapján az elemző táblázat:

     #ab
    #acc<<<<
    a>><<,>><<,==
    b>><<,>><<
  20. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b,c}{a,b,c}
    A{a,b}{a,b}
    B{a,c}{a,b}

    Ez alapján az elemző táblázat:

     #abc
    #acc<<<<<<
    a>><<<<,>>>>
    b>>==>>>>
    c>><<==<<

Egyszerű precedencia elemzés

[Megjegyzés]Megjegyzés

Az előző fejezethez hasonlóan itt is használjuk a First és Last halmazokat nemterminális szimbólumok esetén, viszont más jelentéssel. A First jelöli az adott nemterminálisból (legalább egy lépésben) levezethető szimbólumsorozatok kezdő szimbólumainak halmazát. Itt a szimbólumok lehetnek terminálisok és nemterminálisok is. A Last az adott nemterminálisból levezethető szimbólumsorozatok utolsó szimbólumainak halmazát jelenti. Itt is megengedjük mind a terminálisokat, mind a nemterminálisokat.

A terminálisok között következő relációkat definiáljuk:

  • X==Y, ha van olyan szabály a nyelvtanban, hogy A → αXYβ;

  • X<<Y, ha van olyan szabály a nyelvtanban, hogy A → αaXCβ és Y∈First(C);

  • X>>a, ha van olyan szabály a nyelvtanban, hogy A → αBYβ, X∈Last(B) és (a∈First(Y) vagy a=Y).

  1. A First és Last halmaz a következő lesz:

     FirstLast
    S{S,a}{a}

    Ez alapján az elemző táblázat:

     #aS
    # <<<<
    a>>>> 
    S == 
  2. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,B,c}{a,b}
    A{c}{A,c}
    B{c}{B,c}

    Ez alapján az elemző táblázat:

     #abcSAB
    #   << <<<<
    a>>      
    b>>      
    c >>>><< ====
    S       
    A ==,>>     
    B  ==,>>    

    A nyelvtanban két szabálynak is ugyaz a jobb oldala, sőt ütközéseket is tartalmaz a táblázat, így nem alkalmazhatjuk!

  3. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{A,d,c}
    A{c,d,e,f}{c,d}

    Ez alapján az elemző táblázat:

     #abcdefSA
    # <<<<      
    a   <<<<<<<< ==
    b   == ==   
    c>>        
    d>>        
    e   ====    
    f   ==     
    S         
    A>>        
  4. A First és Last halmaz a következő lesz:

     FirstLast
    S{b,A}{b,S,A}
    A{b}{b,A}

    Ez alapján az elemző táblázat:

     #abcSA
    #  <<  <<
    a  << ==<<
    b>>>> ==  
    c  <<  ==
    S>>     
    A>>==,>>    
  5. A First és Last halmaz a következő lesz:

     FirstLast
    E{E,T,F,),i}{T,F,),i}
    T{T,F,(,i}{F,),i}
    F{(,i}{),i}

    Ez alapján az elemző táblázat:

     #+*()iETF
    #   << <<<<<<<<
    +   << << <<,==<<
    *   << <<  ==
    (   << <<<<,==<<<<
    )>>>>>> >>    
    i>>>>>> >>    
    E ==  ==    
    T>>>>== >>    
    F>>>>>> >>    
  6. A First és Last halmaz a következő lesz:

     FirstLast
    S{i,a}{a,S}

    Ez alapján az elemző táblázat:

     #abiteS
    # << <<   
    a>>    >> 
    b    ==  
    i  ==    
    t << <<  ==
    e << <<  ==
    S>>    ==,>> 
  7. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,a,b}{A,b}
    A{a,b}{A,b}

    Ez alapján az elemző táblázat:

     #abSA
    # <<<< <<
    a <<<< ==
    b>>>>>>  
    S     
    A>><<,>><<,>> ==
  8. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,c}{C,D,a,b,c}
    B{b}{D,b,c}
    C{a,b}{D,b,c}
    D{a}{c}

    Ez alapján az elemző táblázat:

     #abcSBCD
    # << <<    
    a>><<,==<<== == ==
    b>><<,>>     ==
    c>><<,>><<   == 
    S        
    B ==      
    C>>       
    D>>>>      
  9. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,a}{A,B,b,c}
    A{a}{b}
    B{b}{c}

    Ez alapján az elemző táblázat:

     #abcSAB
    # <<   << 
    a <<==  == 
    b>> <<,>>==  ==
    c>>  >>   
    S       
    A>> <<,==   ==
    B>>  ==   
  10. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,B,a,b,c}{a,b}
    A{B,a,b,c}{B,b,c}
    B{a,c}{B,b,c}

    Ez alapján az elemző táblázat:

     #abcdSAB
    # <<<<<<  <<<<
    a>> ==     
    b>><<,>> <<==  ==
    c <<,>> <<   ==
    d << <<   ==
    S        
    A ==      
    B >>      
  11. A First és Last halmaz a következő lesz:

     FirstLast
    S{a,b}{b,c,d}
    A{f}{f}
    B{f}{f}

    Ez alapján az elemző táblázat:

     #abcdfSAB
    # <<<<      
    a     << ====
    b>>    << ====
    c>>        
    d>>        
    f  >>>>>>    
    S         
    A  == ==    
    B   ====    
  12. A First és Last halmaz a következő lesz:

     FirstLast
    S{a}{b}
    A{a,c}{b,c}
    B{a,d}{b,d}

    Ez alapján az elemző táblázat:

     #abcdSAB
    # <<      
    a << <<<< ====
    b>> ==,>>     
    c  >>     
    d  >>     
    S        
    A  ==     
    B  ==     

    Az ütközés mellett egyes szabályok jobb oldalai is egybeesnek, így nem egyszerű precedencia nyelvtan a feladatban szereplő nyelvtan.

  13. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,a,b}{B,c}
    A{a,b}{b}
    B{b,c}{c}

    Ez alapján az elemző táblázat:

     #abcSAB
    # <<<<  << 
    a <<<<  == 
    b  <<,>><<,>>  ==
    c>>  >>   
    S       
    A  ==   ==
    B>>  ==   
  14. A First és Last halmaz a következő lesz:

     FirstLast
    S{B,b}{a}
    A{a,b}{a,b}
    B{B,b}{A,B,a,b}

    Ez alapján az elemző táblázat:

     #abSAB
    #  <<  <<
    a>>==,>>>>   
    b <<,>><<,==,>> == 
    S      
    A >>>>   
    B ==,>><<,>>  <<,==
  15. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,a,c}{A,B,a,c}
    A{a,c}{A,B,a,c}
    B{a,b,c}{A,B,a,c}

    Ez alapján az elemző táblázat:

     #abcSAB
    # << << << 
    a>><<,>>>><<,>> == 
    b <<<<<<  ==
    c>><<,>><<,>><<,>>  ==
    S       
    A>><<,>><<,>><<,>>  ==
    B>>>>>>>>   
  16. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,a,b}{A,B,a}
    A{a,b}{a}
    B{A,a,b}{B,a}

    Ez alapján az elemző táblázat:

     #abSAB
    # <<<< << 
    a>>>>>>   
    b <<,==<< <<==
    S      
    A>><<<< <<==
    B>>     
  17. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,B,a,b,c}{A,a,c}
    A{B,a,b}{a,c}
    B{b}{b}

    Ez alapján az elemző táblázat:

     #abcSAB
    # <<<<<< <<<<
    a>>>>>>    
    b  ==>>   
    c>>>>>>    
    S       
    A>><<<<  ==<<
    B   ==   
  18. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,b}{c}
    A{b}{A,b}
    B{c}{c}

    Ez alapján az elemző táblázat:

     #bcSAB
    # <<  << 
    b <<>> == 
    c>> >>   
    S      
    A  <<,>>  ==
    B  ==   
  19. Az eredeti nyelvtanban az A felesleges szimbólum, így most is kihagyjuk. A First és Last halmaz a megmaradt nyelvtanban a következő lesz:

     FirstLast
    S{B,a,b}{B,a}
    B{a,b}{B,a}

    Ez alapján az elemző táblázat:

     #abSB
    # <<<< <<
    a>><<,>><< ==
    b <<<< ==
    S     
    B>>==,>>   
  20. A First és Last halmaz a következő lesz:

     FirstLast
    S{A,a,b}{B,a,b}
    A{a,b}{a,b}
    B{a,c}{a,b}

    Ez alapján az elemző táblázat:

     #abcSAB
    # <<<<  << 
    a>><<<<,>><<,>> ====
    b>>==>>    
    c <<==<<  ==
    S       
    A  ====   
    B>> ==    

LR(0) elemzés

  1. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → Sa

    • 2: S → a

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .Sa, S → .a}
    H1=V0(S)={S' → S., S → S.a}
    H2=V0(a)={S → a.}
    H3=V0(Sa)={S → Sa.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     a$S
    0s2 1
    1s3acc 
    2r2r2 
    3r1r1 

  2. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → Aa

    • 2: S → Bb

    • 3: A → cA

    • 4: A → c

    • 5: B → cB

    • 6: B → c

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .Aa, S → .Bb, A → .cA, A → .c, B → .cB, B → .c}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.a}
    H3=V0(B)={S → B.b}
    H4=V0(c)={A → c.A, A → c., B → c.B, B → c., A → .cA, A → .c, B → .cB, B → .c } =V0(cc)
    H5=V0(Aa)={S → Aa.}
    H6=V0(Bb)={S → Bb.}
    H7=V0(cA)={A → cA.}
    H8=V0(cB)={B → cB.}

    Ennek megfelelően a táblázat a következő:

     abc$SAB
    0  s4 123
    1accaccaccacc   
    2s5      
    3 s6     
    4r4/r6r4/r6s4/r4/r6r4/r6 78
    5r1r1r1r1   
    6r2r2r2r2   
    7r3r3r3r3   
    8r5r5r5r5   

  3. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → aA

    • 2: S → bec

    • 3: S → bc

    • 4: A → ed

    • 5: A → d

    • 6: A → fc

    • 7: A → c

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .aA, S → .bec, S → .bc}
    H1=V0(S)={S' → S.}
    H2=V0(a)={S → a.A, A → e.d, A → .d, A → .fc, A → .c}
    H3=V0(b)={S → b.ec, S → b.c}
    H4=V0(aA)={S → aA.}
    H5=V0(ad)={A → ed., A → d.}
    H6=V0(af)={A → f.c}
    H7=V0(ac)={A → c.}
    H8=V0(be)={S → be.c}
    H9=V0(bc)={S → bc.}
    H10=V0(afc)={A → fc.}
    H11=V0(bec)={bec.}

    Ennek megfelelően a táblázat a következő:

     abcdef$SA
    0s2s3     1 
    1      acc  
    2  s7s5 s6  4
    3  s9 s8    
    4r1r1r1r1r1r1r1  
    5r4/r5r4/r5r4/r5r4/r5r4/r5r4/r5r4/r5  
    6  s10      
    7r7r7r7r7r7r7r7  
    8  s11      
    9r3r3r3r3r3r3r3  
    10r6r6r6r6r6r6r6  
    11r2r2r2r2r2r2r2  

  4. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AaS

    • 2: S → A

    • 3: A → bcA

    • 4: A → b

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .AaS, S → .A, A → .bcA, A → .b}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.aS, S → A.}=V0(AaA)
    H3=V0(b)={A → b.cA, A → b.}=V0(Aab)=V0(bcb)
    H4=V0(Aa)={S → Aa.S, S → .AaS, S → .A, A → .bcA, A → .b}
    H5=V0(bc)={A → bc.A, A → .bcA, A → .b}
    H6=V0(bc)={S → AaS.}
    H7=V0(bcA)={A → bcA.}

    Ennek megfelelően a táblázat a következő:

     abc$SA
    0 s3  12
    1   acc  
    2s4/r2r2r2r2  
    3r4r4s5/r4r4  
    4 s3  62
    5 s3   7
    6r1r1r1r1  
    7r3r3r3r3  

  5. Tekintsük a kiegészített nyelvtant!

    • 0: S' → E

    • 1: E → E+T

    • 2: E → T

    • 3: T → T*F

    • 4: T → F

    • 5: F → (E)

    • 6: F → i

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .E, E → .E+T, E → .T, T → .T*F, T → .F, F → .(E), F → .i}
    H1=V0(E)={S' → E., E → E.+T}
    H2=V0(T)={E → T., T → T.*F}=V0( (T )
    H3=V0(F)={T → F.}=V0( (F )=V0( E+F )
    H4=V0( ( )={F → (.E), E → .E+T, E → .T, T → .T*F, T → .F, F → .(E), F → .i}=V0( E+( )=V0( T*( )
    H5=V0(i)={F → i.}=V0( E+i )=V0( T*i )
    H6=V0(E+)={E → E+.T, T → .T*F, T → .F, F → .(E), F → .i}=V0( (E+ )
    H7=V0(T*)={T → T*.F, F → .(E), F → .i}=V0(E+T*)
    H8=V0( (E )={F → (E.), E → E.+T}
    H9=V0(E+T)={E → E+T., T → T.*F}
    H10=V0(T*F)={T → T*F.}
    H11=V0( (E) )={F → (E).}

    Ennek megfelelően a táblázat a következő:

     ()*+i$ETF
    0s4   s5 123
    1   s6 acc   
    2r2r2s7/r2r2r2r2   
    3r4r4r4r4r4r4   
    4s4   s5 823
    5r6r6r6r6r6r6   
    6s4   s5  93
    7s4   s5   10
    8 s11 s6     
    9r1r1s7/r1r1r1r1   
    10r3r3r3r3r3r3   
    11r5r5r5r5r5r5   
  6. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → a

    • 2: S → ibtS

    • 3: S → ibtSeS

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .a, S → .ibtS, S → .ibtSeS}
    H1=V0(S)={S' → S.}
    H2=V0(a)={S → a.}=V0(ibta)=V0(ibtSea)
    H3=V0(i)={S → i.btS, S → i.btSeS}=V0(ibti)=V0(ibtSei)
    H4=V0(ib)={S → ib.tS, S → ib.tSeS}
    H5=V0(ibt)={S → ibt.S, S → ibt.SeS, S → .a, S → .ibtS, S → .ibtSeS}
    H6=V0(ibtS)={S → ibtS., S → ibtS.eS}
    H7=V0(ibtSe)={S → ibtSe.S, S → .a, S → .ibtS, S → .ibtSeS}
    H8=V0(a)={S → ibtSeS.}

    Ennek megfelelően a táblázat a következő:

     abeit$S
    0s2  s3  1
    1     acc 
    2r1r1r1r1r1r1 
    3 s4     
    4    s5  
    5s2  s3  6
    6r2r2s7/r2r2r2r2 
    7s2  s3  8
    8r3r3r3r3r3r3 
  7. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AA

    • 2: A → b

    • 3: A → aA

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .AA, A → .b, A → .aA}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.A, A → .b, A → .aA}
    H3=V0(b)={A → b.}=V0(ab)
    H4=V0(a)={A → a.A, A → .b, A → .aA}=V0(aa)
    H5=V0(A)={S → AA.}
    H6=V0(aA)={A → aA.}

    Ennek megfelelően a táblázat a következő:

     ab$SA
    0s4s3 12
    1  acc  
    2s4s3  5
    3r2r2r2  
    4s4s3  6
    5r1r1r1  
    6r3r3r3  
  8. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → aBa

    • 2: S → cC

    • 3: B → b

    • 4: B → bD

    • 5: C → aD

    • 6: C → b

    • 7: D → ac

    • 8: D → aac

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .aBa, S → .cC}
    H1=V0(S)={S' → S.}
    H2=V0(a)={S → a.Ba, B → .b, B → .bD}
    H3=V0(c)={S → c.C, C → .aD, C → .b}
    H4=V0(aB)={S → aB.a}
    H5=V0(ab)={B → b., B → b.D, D → .ac, D → .aac}
    H6=V0(cC)={S → cC.}
    H7=V0(ca)={C → a.D, D → .ac, D → .aac}
    H8=V0(cb)={C → b.}
    H9=V0(aBa)={S → aBa.}
    H10=V0(abD)={B → bD.}
    H11=V0(aba)={D → a.c, D → a.ac}
    H12=V0(caD)={C → aD.}
    H13=V0(abac)={D → ac.}
    H14=V0(abaa)={D → aa.c}
    H15=V0(abaac)={D → aac.}

    Ennek megfelelően a táblázat a következő:

     abc$SBCD
    0s2 s3 1   
    1   acc    
    2 s5   4  
    3s7s8    6 
    4s9       
    5r3/s11r3r3r3   10
    6r2r2r2r2    
    7s11      12
    8r6r6r6r6    
    9r1r1r1r1    
    10r4r4r4r4    
    11s14 s13     
    12r5r5r5r5    
    13r7r7r7r7    
    14  s15     
    15r8r8r8r8    
  9. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → A

    • 2: S → AB

    • 3: A → aAb

    • 4: A → ab

    • 5: B → bBc

    • 6: B → bc

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .A, S → .AB, A → .aAb, A → .ab}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A., S → A.B, B → .bBc, B → .bc}
    H3=V0(a)={A → a.Ab, A → a.b, A → .aAb, A → .ab}=V0(aa)
    H4=V0(AB)={S → AB.}
    H5=V0(Ab)={B → b.Bc, B → b.c, B → .bBc, B → .bc}=V0(Abb)
    H6=V0(aA)={A → aA.b}
    H7=V0(ab)={A → ab.}
    H8=V0(AbB)={B → bB.c}
    H9=V0(Abc)={B → bc.}
    H10=V0(aAb)={A → aAb.}
    H11=V0(AaBc)={B → bBc.}

    Ennek megfelelően a táblázat a következő:

     abc$SAB
    0s3   12 
    1   acc   
    2r1s5/r1r1r1  4
    3s3s7   6 
    4r2r2r2r2   
    5 s5s9   8
    6 s10     
    7r4r4r4r4   
    8  s11    
    9r6r6r6r6   
    10r3r3r3r3   
    11r5r5r5r5   
  10. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → Aa

    • 2: S → b

    • 3: A → bdB

    • 4: A → B

    • 5: B → abB

    • 6: B → cB

    • 7: B → ab

    • 8: B → c

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .Aa, S → .b, A → .bdB, A → .B, B → .abB, B → .cB, B → .ab, B → .c}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.a}
    H3=V0(b)={S → b., A → b.dB}
    H4=V0(B)={A → B.}
    H5=V0(a)={B → a.bB, B → a.b}=V0(bda)
    H6=V0(c)={B → c.B, B → c., B → .abB, B → .cB, B → .ab, B → .c}=V0(cc)=V0(bdc)=V0(abc)
    H7=V0(Aa)={S → Aa.}
    H8=V0(bd)={A → bd.B, B → .abB, B → .cB, B → .ab, B → .c}
    H9=V0(ab)={B → ab.B, B → ab., B → .abB, B → .cB, B → .ab, B → .c}
    H10=V0(cB)={B → cB.}
    H11=V0(bdB)={A → bdB.}
    H12=V0(abB)={B → abB.}

    Ennek megfelelően a táblázat a következő:

     abcd$SAB
    0s5s3s6  124
    1    acc   
    2s7       
    3r2r2r2s8/r2r2   
    4r4r4r4r4r4   
    5 s9      
    6s5/r8r8s6/r8r8r8  10
    7r1r1r1r1r1   
    8s5 s6    11
    9s5/r7r7s6/r7r7r7  12
    10r6r6r6r6r6   
    11r3r3r3r3r3   
    12r5r5r5r5r5   
  11. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → aAb

    • 2: S → bBc

    • 3: S → aBd

    • 4: S → bAd

    • 5: A → f

    • 6: B → f

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .aAb, S → .bBc, S → .aBd, S → .bAd}
    H1=V0(S)={S' → S.}
    H2=V0(a)={S → a.Ab, S → a.Bd, A → .f, B → .f}
    H3=V0(b)={S → b.Bc, S → b.Ad, B → .f, A → .f}
    H4=V0(aA)={S → aA.b}
    H5=V0(aB)={S → aB.d}
    H6=V0(af)={A → f., B → f.}
    H7=V0(bB)={S → bB.c}
    H8=V0(bA)={S → bA.d}
    H9=V0(aAb)={S → aAb.}
    H10=V0(aBd)={S → aBd.}
    H11=V0(bBc)={S → bBc.}
    H12=V0(bAd)={S → bAd.}

    Ennek megfelelően a táblázat a következő:

     abcdf$SAB
    0s2s3    1  
    1     acc   
    2    s6  45
    3    s6  87
    4 s9       
    5   s10     
    6r5/r6r5/r6r5/r6r5/r6     
    7  s11      
    8   s12     
    9r1r1r1r1r1    
    10r3r3r3r3r3    
    11r2r2r2r2r2    
    12r4r4r4r4r4    
  12. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → aAb

    • 2: S → aBbb

    • 3: A → aAb

    • 4: A → c

    • 5: B → aBbb

    • 6: B → d

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .aAb, S → .aBbb}
    H1=V0(S)={S' → S.}
    H2=V0(a)={S → a.Ab, S → a.Bbb, A → .aAb, A → .c, B → .aBbb, B → .d}
    H3=V0(aA)={S → aA.b}
    H4=V0(aB)={S → aB.bb}
    H5=V0(aa)={A → a.Ab, B → a.Bbb, A → .aAb, A → .c, B → .aBbb, B → .d}=V0(aaa)
    H6=V0(ac)={A → c.}
    H7=V0(ad)={B → d.}
    H8=V0(aAb)={S → aAb.}
    H9=V0(aAb)={S → aBb.b}
    H10=V0(aaA)={A → aA.b}
    H11=V0(aaB)={B → aB.bb}
    H12=V0(aAbb)={S → aBbb.}
    H13=V0(aaAb)={A → aAb.}
    H14=V0(aaBb)={B → aBb.b}
    H15=V0(aaBbb)={B → aBbb.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abcd$SAB
    0s2    1  
    1    acc   
    2s5 s6s7  34
    3 s8      
    4 s9      
    5s5 s6s7  1011
    6r4r4r4r4r4   
    7r6r6r6r6r6   
    8r1r1r1r1r1   
    9 s12      
    10 s13      
    11 s14      
    12r2r2r2r2r2   
    13r3r3r3r3r3   
    14 s15      
    15r5r5r5r5r5   
  13. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AB

    • 2: S → aAb

    • 3: A → aAb

    • 4: A → b

    • 5: B → bBc

    • 6: B → c

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .AB, S → .aAb, A → .b}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.B, B → .bBc, B → .c}
    H3=V0(a)={A → a.Ab, A → .aAb, A → .b}=V0(aa)
    H4=V0(b)={A → b.}
    H5=V0(AB)={S → AB.}
    H6=V0(Ab)={B → b.Bc, B → .bBc, B → .c}=V0(Abb)
    H7=V0(Ac)={B → c.}
    H8=V0(aA)={A → aA.b}
    H9=V0(AbB)={B → bB.c}
    H10=V0(aAb)={A → aAb.}
    H11=V0(AbBc)={B → bBc.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abc$SAB
    0s3s4  12 
    1   acc   
    2 s6s7   5
    3s3s4   8 
    4r3r3r3r3   
    5r1r1r1r1   
    6 s6s7   9
    7r5r5r5r5   
    8 s10     
    9  s11    
    10r2r2r2r2   
    11r4r4r4r4   
  14. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → Ba

    • 2: A → aa

    • 3: A → bb

    • 4: B → BB

    • 5: B → bA

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .Ba, B → .BB, B → .bA}
    H1=V0(S)={S' → S.}
    H2=V0(B)={S → B.a, B → B.B, B → .BB, B → .bA}
    H3=V0(b)={B → b.A, A → .aa, A → .bb}=V0(Bb)=V0(BBb)
    H4=V0(Ba)={S → Ba.}
    H5=V0(BB)={ B → BB., B → B.B, B → .BB, B → .bA}=V0(BBB)
    H6=V0(bA)={B → bA.}
    H7=V0(ba)={A → a.a}
    H8=V0(bb)={A → b.b}
    H9=V0(baa)={A → aa.}
    H10=V0(bbb)={A → bb.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     ab$SAB
    0 s3 1 2
    1  acc   
    2s5s3   4
    3s7s8  6 
    4r4r4r4  4
    5r1r1r1   
    6r5r5r5   
    7s9     
    8 s10    
    9r2r2r2   
    10r3r3r3   
  15. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AB

    • 2: A → a

    • 3: A → cB

    • 4: B → c

    • 5: B → aA

    • 6: B → bB

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .AB, A → .a, A → .cB}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.B, B → .c, B → .aA, B → .bB}
    H3=V0(a)={A → a.}=V0(Aaa)
    H4=V0(c)={A → c.B, B → .c, B → .aA, B → .bB}=V0(Aac)
    H5=V0(AB)={S → AB.}
    H6=V0(Aa)={B → a.A, A → .a, A → .cB}=V0(Aba)
    H7=V0(Ab)={B → b.B, B → .c, B → .aA, B → .bB}=V0(Abb)
    H8=V0(Ac)={B → c.}=V0(Abc)
    H9=V0(cB)={A → cB.}
    H10=V0(AaA)={B → aA.}
    H11=V0(AbB)={B → bB.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abc$SAB
    0s3 s4 12 
    1   acc   
    2s6s7s8   5
    3r2r2r2r2   
    4s6s7s8   9
    5r1r1r1r1   
    6s3 s4  10 
    7s6s7s8   11
    8r4r4r4r4   
    9r3r3r3r3   
    10r5r5r5r5   
    11r6r6r6r6   
  16. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → A

    • 2: S → bB

    • 3: A → a

    • 4: A → ba

    • 5: B → AB

    • 6: B → a

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .A, S → .bB, A → .a, A → .ba}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.}
    H3=V0(b)={S → b.B, A → b.a, B → .AB, B → .a, A → .a, A → .ba}
    H4=V0(a)={A → a.}
    H5=V0(bB)={S → bB.}
    H6=V0(ba)={A → ba., B → a., A → a.}
    H7=V0(bA)={B → A.B, B → .AB, B → .a, A → .a, A → .ba}=V0(bAA)
    H8=V0(bb)={A → b.a}
    H9=V0(bAB)={B → AB.}
    H10=V0(bAa)={B → a., A → a.}
    H11=V0(bba)={A → ba.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     ab$SAB
    0s4s3 12 
    1  acc   
    2r1r1r1   
    3s6s8  75
    4r3r3r3   
    5r2r2r2   
    6r3/r4/r6r3/r4/r6r3/r4/r6   
    7s10s8  79
    8s11     
    9r5r5r5   
    10r3/r6r3/r6r3/r6   
    11r4r4r4   
  17. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AA

    • 2: S → c

    • 3: A → Bc

    • 4: A → a

    • 5: B → b

    • 6: B → bb

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .AA, S → .c, A → .Bc, A → .a, B → .b, B → .bb}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.A, A → .Bc, A → .a, B → .b, B → .bb}
    H3=V0(c)={S → c.}
    H4=V0(B)={A → B.c}
    H5=V0(a)={A → a.}
    H6=V0(b)={B → b., B → b.b}
    H7=V0(AA)={S → AA.}
    H8=V0(Bb)={A → Bc.}
    H9=V0(bb)={B → bb.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abc$SAB
    0s5s6s3 124
    1   acc   
    2s5s6   74
    3r2r2r2r2   
    4  s8    
    5r4r4r4r4   
    6r5s9/r5r5r5   
    7r1r1r1r1   
    8r3r3r3r3   
    9r6r6r6r6   
  18. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → ABc

    • 2: A → bA

    • 3: A → b

    • 4: B → c

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .ABc, A → .bA, A → .b}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.Bc, B → .c}
    H3=V0(b)={A → b.A, A → b., A → .bA, A → .b}=V0(bb)
    H4=V0(AB)={S → AB.c}
    H5=V0(Ac)={B → c.}
    H6=V0(bA)={A → bA.}
    H7=V0(ABc)={S → ABc.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     bc$SAB
    0s3  12 
    1  acc   
    2 s5   4
    3s3/r3r3r3 6 
    4 s7    
    5r4r4r4   
    6r2r2r2   
    7r1r1r1   
  19. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → BaB

    • 2: A → a

    • 3: A → bab

    • 4: B → bB

    • 5: B → a

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .BaB, B → .bB, B → .a}
    H1=V0(S)={S' → S.}
    H2=V0(B)={S → B.aB}
    H3=V0(b)={B → b.B, B → .bB, B → .a}=V0(bb)=V0(Bab)
    H4=V0(a)={B → a.}=V0(ab)=V0(Bab)
    H5=V0(Ba)={S → Ba.B, B → .bB, B → .a}
    H6=V0(bB)={B → bB.}
    H7=V0(BaB)={S → BaB.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     ab$SAB
    0s4s3 1 2
    1  acc   
    2s5     
    3s4s3   6
    4r5r5r5   
    5s4s3   7
    6r4r4r4   
    7r1r1r1   
  20. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AcB

    • 2: A → aAb

    • 3: A → ba

    • 4: B → aBb

    • 5: B → cba

    Az LR(0) elemek a következőek lesznek:

    H0=V0(λ)={S' → .S, S → .AcB, A → .aAb, A → .ba}
    H1=V0(S)={S' → S.}
    H2=V0(A)={S → A.cB}
    H3=V0(a)={A → a.Ab, A → .aAb, A → .ba}=V0(aa)
    H4=V0(b)={A → b.a}=V0(ab)
    H5=V0(Ac)={S → Ac.B, B → .aBb, B → .cba}
    H6=V0(aA)={A → aA.b}
    H7=V0(ba)={A → ba.}
    H8=V0(AcB)={S → AcB.}
    H9=V0(Aca)={B → a.Bb, B → .aBb, B → .cba}
    H10=V0(Acc)={B → c.ba}
    H11=V0(aAb)={A → aAb.}
    H12=V0(AcaB)={B → aB.b}
    H13=V0(Accb)={B → cb.a}
    H14=V0(AcaBb)={B → aBb.}
    H15=V0(Accba)={B → cba.}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abc$SAB
    0s3s4  12 
    1   acc   
    2  s5    
    3s3s4   6 
    4s7      
    5s9 s10   8
    6 s11     
    7r3r3r3r3   
    8r1r1r1r1   
    9s9 s10   12
    10 s13     
    11r2r2r2r2   
    12 s14     
    13s15      
    14r4r4r4r4   
    15r5r5r5r5   

SLR elemzés

[Megjegyzés]Megjegyzés

Vannak olyan nyelvtanok, melyeket mind az LL(1), mind az LR(0) feladatoknál megvizsgálunk, így azok megoldásait most felhasználhatjuk az SLR elemzők megadásakor. A szükséges adatokat nem soroljuk fel újra, elérésük megkönnyítése érdekében viszont hivatkozunk rájuk. A Follow halmazok az LL(1) feladatok, az LR(0) elemek értelemszerűen az LR(0) feladatok megoldásainál találhatóak.

  1. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     a$S
    0s2 1
    1s3acc 
    2r2r2 
    3r1r1 
  2. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abc$SAB
    0  s4 123
    1   acc   
    2s5      
    3 s6     
    4r4r6s4  78
    5   r1   
    6   r2   
    7r3      
    8 r5     
  3. Korábbi részmegoldás: LR(0) elemző táblázat, és a Follow halmaza mind az S-nek és az A-nak csak a végjelet tartalmazza. Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abcdef$SA
    0s2s3     1 
    1      acc  
    2  s7s5 s6  4
    3  s9 s8    
    4      r1  
    5      r4/r5  
    6  s10      
    7      r7  
    8  s11      
    9      r3  
    10      r6  
    11      r2  
  4. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abc$SA
    0 s3  12
    1   acc  
    2s4/r2r2r2r2  
    3r4r4s5/r4r4  
    4 s3  62
    5 s3   7
    6r1r1r1r1  
    7r3r3r3r3  
  5. Korábbi részmegoldás: LR(0) elemző táblázat, míg Follow(E)={$,+,)} és Follow(T)=Follow(F)={$,*,+,)}. Ennek megfelelően az SLR elemző táblázat a következő lesz:

     ()*+i$ETF
    0s4   s5 123
    1   s6 acc   
    2 r2s7r2 r2   
    3 r4r4r4 r4   
    4s4   s5 823
    5 r6r6r6 r6   
    6s4   s5  93
    7s4   s5   10
    8 s11 s6     
    9 r1s7r1 r1   
    10 r3r3r3 r3   
    11 r5r5r5 r5   
  6. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abeit$S
    0s2  s3  1
    1     acc 
    2     r1 
    3 s4     
    4    s5  
    5s2  s3  6
    6  s7  r2 
    7s2  s3  8
    8     r3 
  7. Korábbi részmegoldások: LR(0) elemző táblázat, míg Follow(S)={$} és Follow(A)={$,a,b}. Ennek megfelelően az SLR elemző táblázat a következő lesz:

     ab$SA
    0s4s3 12
    1  acc  
    2s4s3  5
    3r2r2r2  
    4s4s3  6
    5  r1  
    6r3r3r3  
  8. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abc$SBCD
    0s2 s3 1   
    1   acc    
    2 s5   4  
    3s7s8    6 
    4s9       
    5r3/s11      10
    6   r2    
    7s11      12
    8   r6    
    9   r1    
    10r4       
    11s14 s13     
    12   r5    
    13r7  r7    
    14  s15     
    15r8  r8    
  9. Korábbi részmegoldás: LR(0) elemző táblázat valamint Follow(S)={$}, Follow(A)={$,b} és Follow(B)={$,c}. Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abc$SAB
    0s3   12 
    1   acc   
    2 s5 r1  4
    3s3s7   6 
    4   r2   
    5 s5s9   8
    6 s10     
    7 r4 r4   
    8  s11    
    9  r6r6   
    10 r3 r3   
    11  r5r5   
  10. Korábbi részmegoldás: LR(0) elemző táblázat, valamint Follow(S)={$} és Follow(A)=Follow(B)={a}; így az SLR elemző táblázat a következő lesz:

     abcd$SAB
    0s5s3s6  124
    1    acc   
    2s7       
    3   s8r2   
    4r4       
    5 s9      
    6s5/r8 s6    10
    7    r1   
    8s5 s6    11
    9s5/r7 s6    12
    10r6       
    11r3       
    12r5       
  11. Korábbi részmegoldás: LR(0) elemző táblázat, valamint Follow(S)={$}, Follow(A)={b,d} és Follow(B)={c,d}; így az SLR elemző táblázat a következő lesz:

     abcdf$SAB
    0s2s3    1  
    1     acc   
    2    s6  45
    3    s6  87
    4 s9       
    5   s10     
    6 r5r6r5/r6     
    7  s11      
    8   s12     
    9    r1    
    10    r3    
    11    r2    
    12    r4    
  12. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abcd$SAB
    0s2    1  
    1    acc   
    2s5 s6s7  34
    3 s8      
    4 s9      
    5s5 s6s7  1011
    6 r4      
    7 r6      
    8    r1   
    9 s12      
    10 s13      
    11 s14      
    12   r2    
    13 r3      
    14 s15      
    15 r5      
  13. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abc$SAB
    0s3s4  12 
    1   acc   
    2 s6s7   5
    3s3s4   8 
    4 r3r3    
    5   r1   
    6 s6s7   9
    7  r5r5   
    8 s10     
    9  s11    
    10 r2r2    
    11  r4r4   
  14. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     ab$SAB
    0 s3 1 2
    1  acc   
    2s5s3   4
    3s7s8  6 
    4r4r4   4
    5  r1   
    6r5r5    
    7s9     
    8 s10    
    9r2r2    
    10r3r3    
  15. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abc$SAB
    0s3 s4 12 
    1   acc   
    2s6s7s8   5
    3r2r2r2r2   
    4s6s7s8   9
    5   r1   
    6s3 s4  10 
    7s6s7s8   11
    8r4r4r4r4   
    9r3r3r3r3   
    10r5r5r5r5   
    11r6r6r6r6   
  16. Korábbi részmegoldás: LR(0) elemző táblázat, valamint Follow(S)=Follow(B)={$} és Follow(A)={$,a,b}. Ennek megfelelően az SLR elemző táblázat a következő lesz:

    {}ab$SAB
    0s4s3 12 
    1  acc   
    2  r1   
    3s6s8  75
    4r3r3r3   
    5  r2   
    6r3/r4r3/r4r4/r6   
    7s10s8  79
    8s11     
    9  r5   
    10r3r3r3/r6   
    11r4r4r4   
  17. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abc$SAB
    0s5s6s3 124
    1   acc   
    2s5s6   74
    3   r2   
    4  s8    
    5r4r4 r4   
    6 s9r5    
    7   r1   
    8r3r3 r3   
    9  r6    
  18. Korábbi részmegoldás: LR(0) elemző táblázat, valamint Follow(S)={$} és Follow(B)=Follow(C)={c}. Ennek megfelelően az SLR elemző táblázat a következő lesz:

     bc$SAB
    0s3  12 
    1  acc   
    2 s5   4
    3s3r3  6 
    4 s7    
    5 r4    
    6 r2    
    7  r1   
  19. Korábbi részmegoldás: LR(0) elemző táblázat, valamint Follow(S)={$} és Follow(B)={$,a}. Mivel A nem szerepelhet egyik mondatszimbólumból inuló levezetésben, így Follow(A) üres halmaz lesz. Ennek megfelelően az SLR elemző táblázat a következő lesz:

     ab$SAB
    0s4s3 1 2
    1  acc   
    2s5     
    3s4s3   6
    4r5 r5   
    5s4s3   7
    6r4 r4   
    7  r1   
  20. Korábbi részmegoldások: LR(0) elemző táblázat és Follow halmaz

    Ennek megfelelően az SLR elemző táblázat a következő lesz:

     abc$SAB
    0s3s4  12 
    1   acc   
    2  s5    
    3s3s4   6 
    4s7      
    5s9 s10   8
    6 s11     
    7 r3r3    
    8   r1   
    9s9 s10   12
    10 s13     
    11 r2r2    
    12 s14     
    13s15      
    14 r4r4    
    15 r5r5    

LR(1) elemzés

  1. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → Sa

    • 2: S → a

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .Sa, $a], [S → .a, $a]}
    I1=V1(S)={[S' → S., $], [S → S.a, $a]}
    I2=V1(a)={[S → a., $a]}
    I3=V1(Sa)={[S → Sa., $a]}

    Ezek alapján az elemző táblázat a következő lesz:

     a$S
    0s2 1
    1s3acc 
    2r2r2 
    3r1r1 
  2. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → Aa

    • 2: S → Bb

    • 3: A → cA

    • 4: A → c

    • 5: B → cB

    • 6: B → c

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .Aa, $], [S → .Bb, $], [A → .cA, a], [A → .c, a], [B → .cB, b], [B → .c, b]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A.a, $]}
    I3=V1(B)={[S → B.b, $]}
    I4=V1(c)={[A → c.A, a], [A → c., a], [B → c.B, b], [B → c., b], [A → .cA, a], [A → .c, a], [B → .cB, b], [B → .c, b]}=V1(cc)
    I5=V1(Aa)={[S → Aa., $]}
    I6=V1(Bb)={[S → Bb., $]}
    I7=V1(cA)={[A → cA., a]}
    I8=V1(cB)={[B → cB., b]}

    Ennek megfelelően a táblázat a következő:

     abc$SAB
    0  s4 123
    1   acc   
    2s5      
    3 s6     
    4r4r6s4  78
    5   r1   
    6   r2   
    7r3      
    8 r5     
  3. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → aA

    • 2: S → bec

    • 3: S → bc

    • 4: A → ed

    • 5: A → d

    • 6: A → fc

    • 7: A → c

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .aA, $], [S → .bec, $], [S → .bc, $]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(a)={[S → a.A, $], [A → e.d, $], [A → .d, $], [A → .fc, $], [A → .c, $]}
    I3=V1(b)={[S → b.ec, $], [S → b.c, $]}
    I4=V1(aA)={[S → aA., $]}
    I5=V1(ad)={[A → ed., $], [A → d., $]}
    I6=V1(af)={[A → f.c, $]}
    I7=V1(ac)={[A → c., $]}
    I8=V1(be)={[S → be.c, $]}
    I9=V1(bc)={[S → bc., $]}
    I10=V1(afc)={[A → fc., $]}
    I11=V1(bec)={[S → bec., $]}

    Ennek megfelelően a táblázat a következő:

     abcdef$SA
    0s2s3     1 
    1      acc  
    2  s7s5 s6  4
    3  s9 s8    
    4      r1  
    5      r4/r5  
    6  s10      
    7      r7  
    8  s11      
    9      r3  
    10      r6  
    11      r2  
  4. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AaS

    • 2: S → A

    • 3: A → bcA

    • 4: A → b

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .AaS, $], [S → .A, $], [A → .bcA, a$], [A → .b, a$]}
    I1=V1(S)={[I → S., $]}
    I2=V1(A)={[S → A.aS, $], [S → A., $]}=V1(AaA)
    I3=V1(b)={[A → b.cA, a$], [A → b., a$]}=V1(Aab)=V1(bcb)
    I4=V1(Aa)={[S → Aa.S, $], [S → .AaS, $], [S → .A, $], [A → .bcA, a$], [A → .b, a$]}
    I5=V1(bc)={[A → bc.A, a$], [A → .bcA, a$], [A → .b, a$]}
    I6=V1(AaS)={[S → AaS., $]}
    I7=V1(bcA)={[A → bcA., a$]}

    Ennek megfelelően a táblázat a következő:

     abc$SA
    0 s3  12
    1   acc  
    2s4  r2  
    3r4 s5r4  
    4 s3  62
    5 s3   7
    6   r1  
    7r3  r3  
  5. Tekintsük a kiegészített nyelvtant!

    • 0: S' → E

    • 1: E → E+T

    • 2: E → T

    • 3: T → T*F

    • 4: T → F

    • 5: F → (E)

    • 6: F → i

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .E, $], [E → .E+T, $+], [E → .T, $+], [T → .T*F, $+*], [T → .F, $+*], [F → .(E), $+*], [F → .i, $+*]}
    I1=V1(E)={[S' → E., $], [E → E.+T, $+]}
    I2=V1(T)={[E → T., $+], [T → T.*F, $+*]}
    I3=V1(F)={[T → F., $+*]}=V1(E+F)
    I4=V1( ( )={[F → (.E), $+*], [E → .E+T, )+], [E → .T, )+], [T → .T*F, )+*], [T → .F, )+*], [F → .(E), )+*], [F → .i, )+*]}=V1(E+( )=V1(T*( )
    I5=V1(i)={[F → i., $+*]}=V1(E+i)=V1(T*i)
    I6=V1(E+)={[E → E+.T, $+], [T → .T*F, $+*], [T → .F, $+*], [F → .(E), $+*], [F → .i, $+*]}
    I7=V1(T*)={[T → T*.F, $+*], [F → .(E), $+*], [F → .i, $+*]}
    I8=V1( (E )={[F → (E.), $+*], [E → E.+T, )+]}
    I9=V1( (T )={[E → T., )+], [T → T.*F, )+*]}=V1( ((T )
    I10=V1( (F )={[T → F., )+*]}=V1( ((F )=V1( (E+F )
    I11=V1( (( )={ [F → (.E), )+*], [E → .E+T, )+], [E → .T, )+], [T → .T*F, )+*], [T → .F, )+*], [F → .(E), )+*], [F → .i, )+*]}=V1( ((( )=V1( (E+( )=V1( (T*( )
    I12=V1( (i )={[F → i., )+*]}=V1( (E+i )=V1( (T*i )
    I13=V1(E+T)={[E → E+T., $+], [T → T.*F, $+*]}
    I14=V1(T*F)={[T → T*F., $+*]}
    I15=V1( (E) )={[F → (E)., $+*]}
    I16=V1( (E+ )={[E → E+.T, )+], [T → .T*F, )+*], [T → .F, )+*], [F → .(E), )+*], [F → .i, )+*]}=V1( ((E+ )
    I17=V1( (T* )={[T → T*.F, )+*], [F → .(E), )+*], [F → .i, )+*]}=V1( (E+T* )
    I18=V1( ((E )={[F → (E.), )+*], [E → E.+T, )+]}
    I19=V1( (E+T )={[E → E+T., )+], [T → T.*F, )+*]}
    I20=V1(T*F)={[T → T*F., )+*]}
    I21=V1( ((E) )={[F → (E)., )+*]}

    Ennek megfelelően a táblázat a következő:

     ()*+i$ETF
    0s4   s5 123
    1   s6 acc   
    2  s7r2 r2   
    3  r4r4 r4   
    4s11   s12 8910
    5  r6r6 r6   
    6s4   s5  133
    7s4   s5   14
    8 s15 s16     
    9 r2s17r2     
    10 r4r4r4     
    11s11   s12 18910
    12 r6r6r6     
    13  s7r1 r1   
    14  r3r3 r3   
    15  r5r5 r5   
    16s11   s12  1910
    17s11   s12   20
    18 s21       
    19 r1s17r1     
    20 r3r3r3     
    21 r5r5r5     
  6. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → a

    • 2: S → ibtS

    • 3: S → ibtSeS

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .a, $], [S → .ibtS, $], [S → .ibtSeS, $]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(a)={[S → a., $]}=V1(ibta)=V1(ibtSea)
    I3=V1(i)={[S → i.btS, $], [S → i.btSeS, $]}=V1(ibti)=V1(ibtSei)
    I4=V1(ib)={[S → ib.tS, $], [S → ib.tSeS, $]}
    I5=V1(ibt)={[S → ibt.S, $], [S → ibt.SeS, $], [S → .a, $], [S → .ibtS, $], [S → .ibtSeS, $]}
    I6=V1(ibtS)={[S → ibtS., $], [S → ibtS.eS, $]}
    I7=V1(ibtSe)={[S → ibtSe.S, $]}
    I8=V1(ibtSeS)={[S → ibtSeS., $]}

    Ennek megfelelően a táblázat a következő:

     abeit$S
    0s2  s3  1
    1     acc 
    2     r1 
    3 s4     
    4    s5  
    5s2  s3  6
    6  s7  r2 
    7s2  s3  8
    8     r3 
  7. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AA

    • 2: A → b

    • 3: A → aA

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .AA, $], [A → .b, ba], [A → .aA, ba]}
    I1=V1(S)={[I → S., $]}
    I2=V1(A)={[S → A.A, $], [A → .b, $], [A → .aA, $]}
    I3=V1(b)={[A → b., ba]}=V1(ab)
    I4=V1(a)={[A → a.A, ba], [A → .b, ba], [A → .aA, ba]}=V1(aa)
    I5=V1(AA)={[S → AA., $]}
    I6=V1(Ab)={[A → b., $]}=V1(Aab)
    I7=V1(Aa)={[A → a.A, $], [A → .b, $], [A → .aA, $]}=V1(Aaa)
    I8=V1(aA)={[A → aA., ba]}
    I9=V1(AaA)={[A → aA., $]}

    Ennek megfelelően a táblázat a következő:

     ab$SA
    0s4s3 12
    1  acc  
    2s7s6  5
    3r2r2   
    4s4s3  8
    5  r1  
    6  r2  
    7s7s6  9
    8r3r3   
    9  r3  
  8. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → aBa

    • 2: S → cC

    • 3: B → b

    • 4: B → bD

    • 5: C → aD

    • 6: C → b

    • 7: D → ac

    • 8: D → aac

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .aBa, $], [S → .cC, $]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(a)={[S → a.Ba, $], [B → .b, a], [B → .bD, a]}
    I3=V1(c)={[S → c.C, $], [C → .aD, $], [C → .b, $]}
    I4=V1(aB)={[S → aB.a, $]}
    I5=V1(ab)={[B → b., a], [B → b.D, a], [D → .ac, a], [D → .aac, a]}
    I6=V1(cC)={[S → cC., $]}
    I7=V1(ca)={[C → a.D, $], [D → .ac, $], [D → .aac, $]}
    I8=V1(cb)={[C → b., $]}
    I9=V1(aBa)={[S → aBa., $]}
    I10=V1(abD)={[B → bD., a]}
    I11=V1(aba)={[D → a.c, a], [D → a.ac, a]}
    I12=V1(caD)={[C → aD., $]}
    I13=V1(caa)={[D → a.c, $], [D → a.ac, $]}
    I14=V1(abac)={[D → ac., a]}
    I15=V1(abaa)={[D → aa.c, a]}
    I16=V1(caac)={[D → ac., $]}
    I17=V1(caaa)={[D → aa.c, $]}
    I18=V1(abaac)={[D → aac., a]}
    I19=V1(caaac)={[D → aac., $]}

    Ennek megfelelően a táblázat a következő:

     abc$SBCD
    0s2 s3 1   
    1   acc    
    2 s5   4  
    3s7s8    6 
    4s9       
    5r3/s11      10
    6   r2    
    7s13      12
    8   r6    
    9   r1    
    10r4       
    11s15 s14     
    12   r5    
    13s17 s16     
    14r7       
    15  s18     
    16   r7    
    17  19     
    18r8       
    19   r8    
  9. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → A

    • 2: S → AB

    • 3: A → aAb

    • 4: A → ab

    • 5: B → bBc

    • 6: B → bc

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .A, $], [S → .AB, $], [A → .aAb, $b], [A → .ab, $b]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A., $], [S → A.B, $], [B → .bBc, $], [B → .bc, $]}
    I3=V1(a)={[A → a.Ab, $b], [A → a.b, $b], [A → .aAb, b], [A → .ab, b]}
    I4=V1(AB)={[S → AB., $]}
    I5=V1(Ab)={[B → b.Bc, $], [B → b.c, $], [B → .bBc, c], [B → .bc, c]}
    I6=V1(aA)={[A → aA.b, $b]}
    I7=V1(ab)={[A → ab., $b]}
    I8=V1(aa)={[A → a.Ab, b], [A → a.b, b], [A → .aAb, b], [A → .ab, b]}=V1(aaa)
    I9=V1(AbB)={[B → bB.c, $]}
    I10=V1(Abc)={[B → bc., $]}
    I11=V1(Abb)={[B → b.Bc, c], [B → b.c, c], [B → .bBc, c], [B → .bc, c]}=V1(Abbb)
    I12=V1(aAb)={[A → aAb., $b]}
    I13=V1(aaA)={[A → aA.b, b]}
    I14=V1(aab)={[A → ab., b]}
    I15=V1(AbBc)={[B → bBc., $]}
    I16=V1(AbbB)={[B → bB.c, c]}
    I17=V1(Abbc)={[B → bc., c]}
    I18=V1(aaAb)={[A → aAb., b]}
    I19=V1(AbbBc)={[B → bBc., c]}

    Ennek megfelelően a táblázat a következő:

     abc$SAB
    0s3   12 
    1   acc   
    2 s5 r1  4
    3s8s7   6 
    4   r2   
    5 s11s10   9
    6 s12     
    7 r4 r4   
    8s8s14   13 
    9  s15    
    10   r6   
    11 s11s17   16
    12 r3 r3   
    13 s18     
    14 r4     
    15   r5   
    16  s19    
    17  r6    
    18 r3     
    19  r5    
  10. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → Aa

    • 2: S → b

    • 3: A → bdB

    • 4: A → B

    • 5: B → abB

    • 6: B → cB

    • 7: B → ab

    • 8: B → c

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .Aa, $], [S → .b, $], [A → .bdB, a], [A → .B, a], [B → .abB, a], [B → .cB, a], [B → .ab, a], [B → .c, a]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A.a, $]}
    I3=V1(b)={[S → b., $], [A → b.dB, a]}
    I4=V1(B)={[A → B., a]}
    I5=V1(a)={[B → a.bB, a], [B → a.b, a]}=V1(bda)
    I6=V1(c)={[B → c.B, a], [B → c., a], [B → .abB, a], [B → .cB, a], [B → .ab, a], [B → .c, a]}=V1(cc)=V1(bdc)=V1(abc)
    I7=V1(Aa)={[S → Aa., $]}
    I8=V1(bd)={[A → bd.B, a], [B → .abB, a], [B → .cB, a], [B → .ab, a], [B → .c, a]}
    I9=V1(ab)={[B → ab.B, a], [B → ab., a], [B → .abB, a], [B → .cB, a], [B → .ab, a], [B → .c, a]}
    I10=V1(cB)={[B → cB., a]}
    I11=V1(bdB)={[A → bdB., a]}
    I12=V1(abB)={[B → abB., a]}

    Ennek megfelelően a táblázat a következő:

     abcd$SAB
    0s5s3s6  124
    1    acc   
    2s7       
    3   s8r2   
    4r4       
    5 s9      
    6r8/s5 s6    10
    7    r1   
    8s5 s6    11
    9r7/s5 s6    12
    10r6       
    11r3       
    12r5       
  11. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → aAb

    • 2: S → bBc

    • 3: S → aBd

    • 4: S → bAd

    • 5: A → f

    • 6: B → f

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .aAb, $], [S → .bBc, $], [S → .aBd, $], [S → .bAd, $]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(a)={[S → a.Ab, $], [S → a.Bd, $], [A → .f, b], [B → .f, d]}
    I3=V1(b)={[S → b.Bc, $], [S → b.Ad, $], [B → .f, c], [A → .f, d]}
    I4=V1(aA)={[S → aA.b, $]}
    I5=V1(aB)={[S → aB.d, $]}
    I6=V1(af)={[A → f., b], [B → f., d]}
    I7=V1(bB)={[S → bB.c, $]}
    I8=V1(bA)={[S → bA.d, $]}
    I9=V1(bf)={[B → f., c], [A → f., d]}
    I10=V1(aAb)={[S → aAb., $]}
    I11=V1(aBd)={[S → aBd., $]}
    I12=V1(bBc)={[S → bBc., $]}
    I13=V1(bAd)={[S → bAd., $]}

    Ennek megfelelően a táblázat a következő:

     abcdf$SAB
    0s2s3    1  
    1     acc   
    2    s6  45
    3    s9  87
    4 s10       
    5   s11     
    6 r5 r6     
    7  s12      
    8   s13     
    9  r6r5     
    10     r1   
    11     r3   
    12     r2   
    13     r4   
  12. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → aAb

    • 2: S → aBbb

    • 3: A → aAb

    • 4: A → c

    • 5: B → aBbb

    • 6: B → d

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .aAb, $], [S → .aBbb, $]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(a)={[S → a.Ab, $], [S → a.Bbb, $], [A → .aAb, b], [A → .c, b], [B → .aBbb, b], [B → .d, b]}
    I3=V1(aA)={[S → aA.b, $]}
    I4=V1(aB)={[S → aB.bb, $]}
    I5=V1(aa)={[A → a.Ab, b], [B → a.Bbb, b]}=V1(aaa)
    I6=V1(ac)={[A → c., b]}=V1(aac)
    I7=V1(ad)={[B → d., b]}=V1(aad)
    I8=V1(aAb)={[S → aAb., $]}
    I9=V1(aBb)={[S → aBb.b, $]}
    I10=V1(aaA)={[A → aA.b, b]}
    I11=V1(aaB)={[B → aB.bb, b]}
    I12=V1(aBbb)={[S → aBbb., $]}
    I13=V1(aaAb)={[A → aAb., b]}
    I14=V1(aaBb)={[B → aBb.b, b]}
    I15=V1(aaBbb)={[B → aBbb., b]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abcd$SAB
    0s2    1  
    1    acc   
    2s5 s6s7  34
    3 s8      
    4 s9      
    5s5 s6s7  1011
    6 r4      
    7 r6      
    8    r1   
    9 s12      
    10 s13      
    11 s14      
    12    r2   
    13 r3      
    14 s15      
    15 r5      
  13. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AB

    • 2: S → aAb

    • 3: A → aAb

    • 4: A → b

    • 5: B → bBc

    • 6: B → c

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .AB, $], [A → .aAb, bc], [A → .b, bc]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A.B, $], [B → .bBc, $], [B → .c, $]}
    I3=V1(a)={[A → a.Ab, bc], [A → .aAb, b], [A → .b, b]}
    I4=V1(b)={[A → b., bc]}
    I5=V1(AB)={[S → AB., $]}
    I6=V1(Ab)={[B → b.Bc, $], [B → .bBc, c], [B → .c, c]}
    I7=V1(Ac)={[B → c., $]}
    I8=V1(aA)={[A → aA.b, bc]}
    I9=V1(aa)={[A → a.Ab, b], [A → .aAb, b], [A → .b, b]}=V1(aaa)
    I10=V1(ab)={[A → b., b]}=V1(aab)
    I11=V1(AbB)={[B → bB.c, $]}
    I12=V1(AbB)={[B → b.Bc, c], [B → .bBc, c], [B → .c, c]}
    I13=V1(Abc)={[B → c., c]}
    I14=V1(aAb)={[A → aAb., bc]}
    I15=V1(aaA)={[A → aA.b, b]}
    I16=V1(AbBc)={[B → bBc., $]}
    I17=V1(AbBB)={[B → bB.c, c]}
    I18=V1(aaAb)={[A → aAb., b]}
    I19=V1(AbBBc)={[B → bBc., c]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abc$SAB
    0s3s4  12 
    1   acc   
    2 s6s7   5
    3s9s10   8 
    4 r3r3    
    5   r1   
    6 s12s13   11
    7   r5   
    8 s14     
    9s9s10   15 
    10 r3     
    11  s16    
    12 s12s13   17
    13  r5    
    14 r2r2    
    15 s18     
    16   r4   
    17  s19    
    18 r2     
    19  r4    
  14. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → Ba

    • 2: A → aa

    • 3: A → bb

    • 4: B → BB

    • 5: B → bA

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .Ba, $], [B → .BB, ab], [B → .bA, ab]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(B)={[S → B.a, $], [B → B.B, ab], [B → .BB, ab], [B → .bA, ab]}
    I3=V1(b)={[B → b.A, ab], [A → .aa, ab], [A → .bb, ab]}=V1(Bb)
    I4=V1(Ba)={[S → Ba., $]}
    I5=V1(BB)={[B → BB., ab], [B → B.B, ab], [B → .BB, ab], [B → .bA, ab]}=V1(BBB)
    I6=V1(bA)={[B → bA., ab]}
    I7=V1(ba)={[A → a.a, ab]}
    I8=V1(bb)={[A → b.b, ab]}
    I9=V1(baa)={[A → aa., ab]}
    I10=V1(bbb)={[A → bb., ab]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     ab$SAB
    0 s3 1 2
    1  acc   
    2s4s3    
    3s7s8  6 
    4  r1   
    5r4r3/r4   5
    6r5r5    
    7s9     
    8 s10    
    9r2r2    
    10r3r3    
  15. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AB

    • 2: A → a

    • 3: A → cB

    • 4: B → c

    • 5: B → aA

    • 6: B → bB

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .AB, $], [A → .a, cab], [A → .cB, cab]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A.B, $], [B → .c, $], [B → .aA, $], [B → .bB, $]}
    I3=V1(a)={[A → a., cab]}=V1(caa)
    I4=V1(c)={[A → c.B, cab], [B → .c, cab], [B → .aA, cab], [B → .bB, cab]}=V1(cac)
    I5=V1(AB)={[S → AB., $]}
    I6=V1(Ac)={[B → c., $]}=V1(Abc)=V1(Aacc)
    I7=V1(Aa)={[B → a.A, $], [A → .a, $], [A → .cB, $]}=V1(Aba)=V1(Aaca)
    I8=V1(Ab)={[B → b.B, $], [B → .c, $], [B → .aA, $], [B → .bB, $]}=V1(Abb)=V1(Aacb)
    I9=V1(cB)={[A → cB., cab]}
    I10=V1(cc)={[B → c., cab]}=V1(cbc)
    I11=V1(ca)={[B → a.A, cab], [A → .a, cab], [A → .cB, cab]}=V1(cba)
    I12=V1(cb)={[B → b.B, cab], [B → .c, cab], [B → .aA, cab], [B → .bB, cab]}=V1(cbb)
    I13=V1(AaA)={[B → aA., $]}
    I14=V1(Aaa)={[A → a., $]}
    I15=V1(Aac)={[A → c.B, $], [B → .c, $], [B → .aA, $], [B → .bB, $]}
    I16=V1(AbB)={[B → bB., $]}
    I17=V1(caA)={[B → aA., cab]}
    I18=V1(cbB)={[B → bB., cab]}
    I19=V1(AacB)={[A → cB., $]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abc$SAB
    0s3 s4 12 
    1   acc   
    2s7s8s6   5
    3r2r2r2    
    4s11s12s10   9
    5   r1   
    6   r4   
    7s14 s15  13 
    8s7s8s6    
    9r3r3r3    
    10r4r4r4    
    11s3 s4  17 
    12s11s12s10   18
    13   r5   
    14   r2   
    15s7s8s6   19
    16   r6   
    17r5r5r5    
    18r6r6r6    
    19   r3   
  16. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → A

    • 2: S → bB

    • 3: A → a

    • 4: A → ba

    • 5: B → AB

    • 6: B → a

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .A, $], [S → .bB, $], [A → .a, $], [A → .ba, $]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A., $]}
    I3=V1(b)={[S → b.B, $], [A → b.a, $], [B → .AB, $], [B → .a, $], [A → .a, ab], [A → .ba, ab]}
    I4=V1(a)={[A → a., $]}
    I5=V1(bB)={[S → bB., $]}
    I6=V1(ba)={[A → ba., $], [B → a., $], [A → a., ab]}
    I7=V1(bA)={[B → A.B, $], [B → .AB, $], [B → .a, $], [A → .a, ab], [A → .ba, ab]}=V1(bAA)
    I8=V1(bb)={[A → b.a, ab]}=V1(bAb)
    I9=V1(bAB)={[B → AB., $]}
    I10=V1(bAa)={[B → a., $], [A → a., ab]}
    I11=V1(bba)={[A → ba., ab]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     ab$SAB
    0s4s3 12 
    1  acc   
    2  r1   
    3s6s8  75
    4  r3   
    5  r2   
    6r3r3r4/r6   
    7s10s8  79
    8s11     
    9  r5   
    10r3r3r6   
    11r4r4    
  17. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AA

    • 2: S → c

    • 3: A → Bc

    • 4: A → a

    • 5: B → b

    • 6: B → bb

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .AA, $], [S → .c, $], [A → .Bc, ba], [A → .a, ba], [B → .b, c], [B → .bb, c]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A.A, $], [A → .Bc, $], [A → .a, $], [B → .b, c], [B → .bb, c]}
    I3=V1(c)={[S → c., $]}
    I4=V1(B)={[A → B.c, ba]}
    I5=V1(a)={[A → a., ba]}
    I6=V1(b)={[B → b., c], [B → b.b, c]}
    I7=V1(AA)={[S → AA., $]}
    I8=V1(AB)={[A → B.c, $]}
    I9=V1(Aa)={[A → a., $]}
    I10=V1(Bc)={[A → Bc., ba]}
    I11=V1(bb)={[B → bb., c]}
    I12=V1(ABc)={[A → Bc., $]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abc$SAB
    0s5s6s3 124
    1   acc   
    2s9s6   78
    3   r2   
    4  s10    
    5r4r4     
    6 s11r5    
    7   r1   
    8  s12    
    9   r4   
    10r3r3     
    11  r6    
    12   r3   
  18. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → ABc

    • 2: A → bA

    • 3: A → b

    • 4: B → c

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .ABc, $], [A → .bA, c], [A → .b, c]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A.Bc, $], [B → .c, c]}
    I3=V1(b)={[A → b.A, c], [A → b., c], [A → .bA, c], [A → .b, c]}=V1(bb)
    I4=V1(AB)={[S → AB.c, $]}
    I5=V1(Ac)={[B → c., c]}
    I6=V1(bA)={[A → bA., c]}
    I7=V1(ABc)={[S → ABc., $]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     bc$SAB
    0s3  12 
    1  acc   
    2 s5   4
    3s3r3  6 
    4 s7    
    5 r4    
    6 r2    
    7  r1   
  19. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → BaB

    • 2: A → a

    • 3: A → bab

    • 4: B → bB

    • 5: B → a

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .BaB, $], [B → .bB, a], [B → .a, a]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(B)={[S → B.aB, $]}
    I3=V1(b)={ [B → b.B, a], [B → .bB, a], [B → .a, a]}=V1(bb)
    I4=V1(a)={[B → a., a]}=V1(ba)
    I5=V1(Ba)={ [S → Ba.B, $], [B → .bB, $], [B → .a, $]}
    I6=V1(bB)={[B → bB., a]}
    I7=V1(BaB)={[S → BaB., $]}
    I8=V1(Bab)={[B → b.B, $], [B → .bB, $], [B → .a, $]}=V1(Babb)
    I9=V1(Baa)={[B → a., $]}=V1(Baba)
    I10=V1(BabB)={[B → bB., $]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     ab$SAB
    0s4s3 1 2
    1  acc   
    2s5     
    3s4s3   6
    4r5     
    5s9s8   7
    6r4     
    7  r1   
    8s9s8   10
    9  r5   
    10  r4   
  20. Tekintsük a kiegészített nyelvtant!

    • 0: S' → S

    • 1: S → AcB

    • 2: A → aAb

    • 3: A → ba

    • 4: B → aBb

    • 5: B → cba

    Az LR(1) elemek a következőek lesznek:

    I0=V1(λ)={[S' → .S, $], [S → .AcB, $], [A → .aAb, c], [A → .ba, c]}
    I1=V1(S)={[S' → S., $]}
    I2=V1(A)={[S → A.cB, $]}
    I3=V1(a)={[A → a.Ab, c], [A → .aAb, b], [A → .ba, b]}
    I4=V1(b)={[A → b.a, c]}
    I5=V1(Ac)={[S → Ac.B, $], [B → .aBb, $], [B → .cba, $]}
    I6=V1(aA)={[A → aA.b, c]}
    I7=V1(aa)={[A → a.Ab, b], [A → .aAb, b], [A → .ba, b]}=V1(aaa)
    I8=V1(ab)={[A → b.a, b]}=V1(aab)
    I9=V1(ba)={[A → ba., c]}
    I10=V1(AcB)={[S → AcB., $]}
    I11=V1(Aca)={[B → a.Bb, $], [B → .aBb, b], [B → .cba, b]}
    I12=V1(Acc)={[B → c.ba, $]}
    I13=V1(aAb)={[A → aAb., c]}
    I14=V1(aaA)={[A → aA.b, b]}
    I15=V1(aba)={[A → ba., b]}
    I16=V1(AcaB)={[B → aB.b, $]}
    I17=V1(Acaa)={[B → a.Bb, b], [B → .aBb, b], [B → .cba, b]}=V1(Acaaa)
    I18=V1(Acac)={[B → c.ba, b]}=V1(Acaac)
    I19=V1(Accb)={[B → cb.a, $]}
    I20=V1(aaAb)={[A → aAb., b]}
    I21=V1(AcaBb)={[B → aBb., $]}
    I22=V1(AcaaB)={[B → aB.b, b]}
    I23=V1(Acacb)={[B → cb.a, b]}
    I24=V1(Accba)={[B → cba., $]}
    I25=V1(AcaaBb)={[B → aBb., b]}
    I26=V1(Acacba)={[B → cba., b]}

    Ennek megfelelően az elemző táblázat a következő lesz:

     abc$SAB
    0s3s4  12 
    1   acc   
    2  s5    
    3s7s8   6 
    4s9      
    5s11 s12   10
    6 s13     
    7s7s8   14 
    8s15      
    9  r3    
    10   r1   
    11s17 s18   16
    12 s19     
    13  r2    
    14 s20     
    15 r3     
    16 s21     
    17s17 s18   22
    18 s23     
    19s24      
    20 r2     
    21   r4   
    22 s25     
    23s26      
    24   r5   
    25 r4     
    26 r5     

LALR elemzés

[Megjegyzés]Megjegyzés

LALR(1) elemző táblázatok készítésénél két módszert is követhetünk. Első esetben az LR(1) elemző táblázatban vonjuk össze az egymáshoz hasonló (azonos maggal rendelkező) sorokat. A második esetben a táblázot sorról sorra készítjük el, és ha már korábbi sorhoz hasonló sort kapunk, azzal egyből összevonjuk. Mivel ez utóbbi módszert dinamikájában csak hosszan tudnánk bemutatni, megmaradunk az előbbinél. Szerencsére ugyanezen nyelvtanokhoz már elkészítettük az LR(1) elemzőket, így ezeket fel tudjuk használni.

  1. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  2. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  3. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  4. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  5. Az LR(1) elemek közül a következőek hasonlóak: 4-11, 2-9, 3-10, 5-12, 6-16, 7-17, 8-18, 13-19, 14-20 és 15-21.

  6. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  7. Az LR(1) elemek közül a következőek hasonlóak: 3-6, 4-7 és 8-9.

  8. Az LR(1) elemek közül a következőek hasonlóak: 11-13, 14-16, 15-17 és 18-19.

  9. Az LR(1) elemek közül a következőek hasonlóak: 3-8, 5-11, 6-13, 7-14, 9-16, 10-17, 12-18 és 15-19.

  10. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  11. Az LR(1) elemek közül a következőek hasonlóak: I6 és I9. Viszont a táblázat d oszlopához tartozó bejegyzések eltérőek: r6 és r5. Így míg az LR(1) táblázat nem tartalmaz ütközést, az LALR(1) táblázat már fog. Magyarul a feladatban szereplő nyelvtan nem LALR(1) nyelvtan.

  12. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  13. Az LR(1) elemek közül a következőek hasonlóak: 3-9, 4-10, 6-12, 7-13, 8-15, 11-17, 14-18 és 16-19

  14. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  15. Az LR(1) elemek közül a következőek hasonlóak: 3-14, 4-15, 6-10, 7-11, 8-12, 9-19, 13-17 és 16-18.

  16. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  17. Az LR(1) elemek közül a következőek hasonlóak: 4-8, 5-9 és 10-12.

  18. Mivel az LR(1) elemek között nincsenek hasonlóak, az LALR(1) elemző táblázata egybeesik az LR(1) elemző táblázatával.

  19. Az LR(1) elemek közül a következőek hasonlóak: 3-8, 4-9 és 6-10.

  20. Az LR(1) elemek közül a következőek hasonlóak: 3-7, 4-8, 6-14, 9-15, 11-17, 12-18, 13-20, 16-22, 19-23, 21-25 és 24-26.

Bibliográfia

[Csörnyei06] Csörnyei, Zoltán. Fordítóprogramok. Typotex. 2006.

[Fülöp99] Fülöp, Zoltán. Formális nyelvek és szintaktikus elemzésük. Polygon, Szeged. 1999.

[Grune90] , Grune, Dick, és Jacobs, Ceriel J. H.. Parsing techniques: a practical guide. Ellis Horwood, Chichester, England. 1990.

[Thompson68] Thompson, Ken. „Regular expression search algorithm”. 419-422. Comm. Assoc. Comp. Mach.. 11. 6. 1968.