Compilerbau: Grammatik für Anweisungen

Die Grammatik in diesem Beispiel bildet einen Ausschnitt aus dem Anweisungsteil einer Pascal-ähnlichen Sprache.
Sie enthält eine ε-Produktion.
Es wird mit der erweiterten Grammatik gearbeitet, $ steht für das eof-Zeichen.

Die Grammatik

G:      (N, T, P, S)
 
N:      {Expr, SL, SL1, Stmt, Stmt'}
T:      {$, :=, ;, begin, do, done, else, end, fi, id, if, num, then, while}
S:      Stmt'
 
P:      Expr  ::= id
        Expr  ::= num
 
        SL    ::= Stmt SL1
 
        SL1   ::=
        SL1   ::= ; SL
 
        Stmt  ::= begin SL end
        Stmt  ::= id := Expr
        Stmt  ::= if Expr then Stmt else Stmt fi
        Stmt  ::= while Expr do Stmt done
 
        Stmt' ::= Stmt $

Die Iterationen bei der Berechnung der Menge der nullable-Symbole

.0      {}
.1      {SL1}

Die Berechnung der Nullable-Menge ist in diesem Fall trivial.

Die Iterationen bei der Berechnung der FIRST-Mengen

.0      Expr  : {}
        SL    : {}
        SL1   : {}
        Stmt  : {}
        Stmt' : {}
 
.1      Expr  : {id, num}
        SL    : {}
        SL1   : {;}
        Stmt  : {begin, id, if, while}
        Stmt' : {}
 
.2      Expr  : {id, num}
        SL    : {begin, id, if, while}
        SL1   : {;}
        Stmt  : {begin, id, if, while}
        Stmt' : {begin, id, if, while}

Die FIRST-Mengen werden nur für die Nichtterminal-Symbole berechnet.
Für alle Terminal-Symbole t gilt FIRST(t) = {t}.

Ab der 3. Iteration wachsen die Mengen nicht mehr.

Die Iterationen bei der Berechnung der FOLLOW-Mengen

.0      Expr  : {}
        SL    : {}
        SL1   : {}
        Stmt  : {}
        Stmt' : {}
 
.1      Expr  : {do, then}
        SL    : {end}
        SL1   : {}
        Stmt  : {$, ;, done, else, fi}
        Stmt' : {}
 
.2      Expr  : {$, ;, do, done, else, fi, then}
        SL    : {end}
        SL1   : {end}
        Stmt  : {$, ;, done, else, end, fi}
        Stmt' : {}
 
.3      Expr  : {$, ;, do, done, else, end, fi, then}
        SL    : {end}
        SL1   : {end}
        Stmt  : {$, ;, done, else, end, fi}
        Stmt' : {}

Ab der 4. Iteration wachsen die Mengen nicht mehr.
Für die Konstruktion der Parser-Tabelle wird nur FOLLOW(SL1) benötigt.
Für Terminal-Symbole werden die FOLLOW-Mengen nie verwendet, können also auch im Iterationsprozess unberücksichtigt bleiben.

Die LL-Parser-Tabelle

Expr   id     : Expr   ::= id
       num    : Expr   ::= num
 
SL     begin  : SL     ::= Stmt SL1
       id     : SL     ::= Stmt SL1
       if     : SL     ::= Stmt SL1
       while  : SL     ::= Stmt SL1
 
SL1    ;      : SL1    ::= ; SL
       end    : SL1    ::=
 
Stmt   begin  : Stmt   ::= begin SL end
       id     : Stmt   ::= id := Expr
       if     : Stmt   ::= if Expr then Stmt else Stmt fi
       while  : Stmt   ::= while Expr do Stmt done
 
Stmt'  begin  : Stmt'  ::= Stmt $
       id     : Stmt'  ::= Stmt $
       if     : Stmt'  ::= Stmt $
       while  : Stmt'  ::= Stmt $

Zu jedem Nichtterminal und Lookahead gibt es höchstens eine anwendbare Regel.
Also ist die LL(1)-Eigenschaft erfüllt.

Die Tabelleneintrage für Stmt' zeigen, dass alle Programme mit einem der 4 Symbole begin, id, if oder while beginnen.

Die Tabelleneinträge für SL1 zeigen, dass nur ; und end zulässige Lookahead-Zeichen sind.
Ein Syntaxfehler kann also schon in SL1 gemeldet werden,
dieses wurde in dem motivierenden Ad-hoc-Beispiel nicht gemacht.

1. Parser-Lauf

Eingabe: begin id := num ; id := id end $

Die Teile in den beiden Spalten Processed/Stack bilden eine Linksableitung.

Der Stack wird mit dem Startsymbol Stmt' initialisiert.
Es sind noch keine Zeichen von der Eingabe verarbeitet worden.

Liegt oben (in der Tabelle links) auf dem Stack ein Nichtterminal-Symbol, so wird aus der Parser-Tabelle unter diesem Symbol und dem Lookahead (1. Zeichen der Eingabe) die anzuwendende Regel ausgelesen und mit dieser ein Ableitungsschritt gemacht.

Liegt auf dem Stack ein Terminal-Symbol, so wird dieses mit dem Lookahead auf Gleichheit überprüft, aus der Eingabe gelöscht und auf die Processed-Seite geschoben

Dieser Prozess wird wiederholt, bis die gesamte Eingabe eingelesen ist.

Der Prozess wird bei einem Syntaxfehler abgebrochen.

                       Processed | Stack                | Input
---------------------------------+----------------------+---------------------------------
                                 | Stmt'                | begin id := num ; id := id end $
                                 | Stmt $               | begin id := num ; id := id end $
                                 | begin SL end $       | begin id := num ; id := id end $
                           begin | SL end $             |       id := num ; id := id end $
                           begin | Stmt SL1 end $       |       id := num ; id := id end $
                           begin | id := Expr SL1 end $ |       id := num ; id := id end $
                        begin id | := Expr SL1 end $    |          := num ; id := id end $
                     begin id := | Expr SL1 end $       |             num ; id := id end $
                     begin id := | num SL1 end $        |             num ; id := id end $
                 begin id := num | SL1 end $            |                 ; id := id end $
                 begin id := num | ; SL end $           |                 ; id := id end $
               begin id := num ; | SL end $             |                   id := id end $
               begin id := num ; | Stmt SL1 end $       |                   id := id end $
               begin id := num ; | id := Expr SL1 end $ |                   id := id end $
            begin id := num ; id | := Expr SL1 end $    |                      := id end $
         begin id := num ; id := | Expr SL1 end $       |                         id end $
         begin id := num ; id := | id SL1 end $         |                         id end $
      begin id := num ; id := id | SL1 end $            |                            end $
      begin id := num ; id := id | end $                |                            end $
  begin id := num ; id := id end | $                    |                                $
begin id := num ; id := id end $ |                      |

2. Parser-Lauf

Eingabe: begin id := num ; end $

Der Parser-Lauf bleibt vor dem end stecken.

Zu SL und Lookahead end gibt es keinen Eintrag in der Parser-Tabelle,
also liegt ein Syntaxfehler vor.

        Processed | Stack                | Input
------------------+----------------------+------------------------
                  | Stmt'                | begin id := num ; end $
                  | Stmt $               | begin id := num ; end $
                  | begin SL end $       | begin id := num ; end $
            begin | SL end $             |       id := num ; end $
            begin | Stmt SL1 end $       |       id := num ; end $
            begin | id := Expr SL1 end $ |       id := num ; end $
         begin id | := Expr SL1 end $    |          := num ; end $
      begin id := | Expr SL1 end $       |             num ; end $
      begin id := | num SL1 end $        |             num ; end $
  begin id := num | SL1 end $            |                 ; end $
  begin id := num | ; SL end $           |                 ; end $
begin id := num ; | SL end $             |                   end $

Grammatik für Anweisungen