2.7. 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