1.6. Á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