2.9. 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:

  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>><<==<<