Compilerbau: Grammatik für Arithmetische Ausdrücke

Die "natürliche" Grammatik für arithmetische Ausdrücke mit +, -, * und / und Klammerschachtelung
Prioritäten und Assoziativitäten sind fest gelegt.
Es gibt also keine Mehrdeutigkeiten.

Die Grammatik

G:      (N, T, P, S)
 
N:      {E, F, S, T}
T:      {$, (, ), *, +, -, /, id, num}
S:      S
 
P:      S ::= E $
 
        E ::= E + T
        E ::= E - T
        E ::= T
 
        T ::= F
        T ::= T * F
        T ::= T / F
 
        F ::= ( E )
        F ::= id
        F ::= num

Die Iterationen bei der Berechnung der Menge der Nullable-Symbole

.0 {}

Es gibt keine ε-Produktionen.

Die Iterationen bei der Berechnung der FIRST-Mengen

.0      E : {}
        F : {}
        S : {}
        T : {}
 
.1      E : {}
        F : {(, id, num}
        S : {}
        T : {}
 
.2      E : {}
        F : {(, id, num}
        S : {}
        T : {(, id, num}
 
.3      E : {(, id, num}
        F : {(, id, num}
        S : {}
        T : {(, id, num}
 
.4      E : {(, id, num}
        F : {(, id, num}
        S : {(, id, num}
        T : {(, id, num}

Nach 4 Iterationen wachsen die Mengen nicht mehr

Die Iterationen bei der Berechnung der FOLLOW-Mengen

.0      E : {}
        F : {}
        S : {}
        T : {}
 
.1      E : {$, ), +, -}
        F : {}
        S : {}
        T : {*, /}
 
.2      E : {$, ), +, -}
        F : {*, /}
        S : {}
        T : {$, ), *, +, -, /}
 
.3      E : {$, ), +, -}
        F : {$, ), *, +, -, /}
        S : {}
        T : {$, ), *, +, -, /}

Die Berechnung der FOLLOW-Mengen ist eigentlich redundant, da es keine ε-Produktionen gibt.

Die LL-Parser-Tabelle

E      (    : E  ::= T
              E  ::= E - T
              E  ::= E + T
              ^^^^^^^^^^^^^^
       id   : E  ::= T
              E  ::= E - T
              E  ::= E + T
              ^^^^^^^^^^^^^^
       num  : E  ::= T
              E  ::= E - T
              E  ::= E + T
              ^^^^^^^^^^^^^^
 
F      (    : F  ::= ( E )
       id   : F  ::= id
       num  : F  ::= num
 
S      (    : S  ::= E $
       id   : S  ::= E $
       num  : S  ::= E $
 
T      (    : T  ::= T / F
              T  ::= T * F
              T  ::= F
              ^^^^^^^^^^^^^^
       id   : T  ::= T / F
              T  ::= T * F
              T  ::= F
              ^^^^^^^^^^^^^^
       num  : T  ::= T / F
              T  ::= T * F
              T  ::= F
              ^^^^^^^^^^^^^^

Die Tabelle zeigt, dass sowohl für E als auch für T für alle 3 Lookahead-Zeichen (, id und num jeweils alle 3 Regeln angewendet werden können.

Also ist diese Grammatik für das LL(1)-Parsen völlig unbrachbar.

Die Ursache liegt in den Linksrekursionen in den Regeln für E und T

Für diese Grammatik muss also eine gleichwertige Grammatig G' entwickelt werden, die keine Linksrekursionen mehr enthält.

Grammatik für Arithmetische Ausdrücke

3. Beispiel für FIRST- und FOLLOW-Mengen

Die Grammatik

Die Iterationen bei der Berechnung der Menge der Nullable-Symbole

Die Iterationen bei der Berechnung der FIRST-Mengen

Die Iterationen bei der Berechnung der FOLLOW-Mengen

Die LL-Parser-Tabelle