Compilerbau: LL(1)-Gramatik für Arithmetische Ausdrücke

Die nicht mehr "natürliche" Grammatik für arithmetische Ausdrücke mit +, -, * und / und Klammerschachtelung.
Linksrekursionen sind durch rechtsrekursive Regeln ersetzt worden.

Es werden neue Nichtterminale nötig und es sind ε-Produktionen dazu gekommen.

Die Grammatik

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

Die Iterationen bei der Berechnung der Menge der Nullable-Symbole

.0      {}
.1      {E', T'}

Die Berechnung ist wieder trivial

Die Iterationen bei der Berechnung der FIRST-Mengen

.0      E  : {}
        E' : {}
        F  : {}
        S  : {}
        T  : {}
        T' : {}
 
.1      E  : {}
        E' : {+, -}
        F  : {(, id, num}
        S  : {}
        T  : {}
        T' : {*, /}
 
.2      E  : {}
        E' : {+, -}
        F  : {(, id, num}
        S  : {}
        T  : {(, id, num}
        T' : {*, /}
 
.3      E  : {(, id, num}
        E' : {+, -}
        F  : {(, id, num}
        S  : {}
        T  : {(, id, num}
        T' : {*, /}
 
.4      E  : {(, id, num}
        E' : {+, -}
        F  : {(, id, num}
        S  : {(, id, num}
        T  : {(, id, num}
        T' : {*, /}

Wieder nach 4 Iterationen wachsen die Mengen nicht mehr.

Die Iterationen bei der Berechnung der FOLLOW-Mengen

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

Die Berechnung der FOLLOW-Mengen wird für E' und T' benötigt.

Die LL-Parser-Tabelle

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

Die Tabelle zeigt, dass die Regel alle eindeutig bestimmt sind.

Die ε-Produktionen müssen bei E' und T' für die Lookaheads $ und ) verwendet werden,
bei T' zusätzlich noch für + und -.

Parser-Lauf

Eingabe: id + id * ( id + num ) $

               Processed | Stack               | Input
-------------------------+---------------------+-------------------------
                         | S                   | id + id * ( id + num ) $
                         | E $                 | id + id * ( id + num ) $
                         | T E' $              | id + id * ( id + num ) $
                         | F T' E' $           | id + id * ( id + num ) $
                         | id T' E' $          | id + id * ( id + num ) $
                      id | T' E' $             |    + id * ( id + num ) $
                      id | E' $                |    + id * ( id + num ) $
                      id | + T E' $            |    + id * ( id + num ) $
                    id + | T E' $              |      id * ( id + num ) $
                    id + | F T' E' $           |      id * ( id + num ) $
                    id + | id T' E' $          |      id * ( id + num ) $
                 id + id | T' E' $             |         * ( id + num ) $
                 id + id | * F T' E' $         |         * ( id + num ) $
               id + id * | F T' E' $           |           ( id + num ) $
               id + id * | ( E ) T' E' $       |           ( id + num ) $
             id + id * ( | E ) T' E' $         |             id + num ) $
             id + id * ( | T E' ) T' E' $      |             id + num ) $
             id + id * ( | F T' E' ) T' E' $   |             id + num ) $
             id + id * ( | id T' E' ) T' E' $  |             id + num ) $
          id + id * ( id | T' E' ) T' E' $     |                + num ) $
          id + id * ( id | E' ) T' E' $        |                + num ) $
          id + id * ( id | + T E' ) T' E' $    |                + num ) $
        id + id * ( id + | T E' ) T' E' $      |                  num ) $
        id + id * ( id + | F T' E' ) T' E' $   |                  num ) $
        id + id * ( id + | num T' E' ) T' E' $ |                  num ) $
    id + id * ( id + num | T' E' ) T' E' $     |                      ) $
    id + id * ( id + num | E' ) T' E' $        |                      ) $
    id + id * ( id + num | ) T' E' $           |                      ) $
  id + id * ( id + num ) | T' E' $             |                        $
  id + id * ( id + num ) | E' $                |                        $
  id + id * ( id + num ) | $                   |                        $
id + id * ( id + num ) $ |                     |