Compilerbau: Grammatik für Anweisungen |
Die Grammatik in diesem Beispiel bildet einen Ausschnitt aus dem Anweisungsteil
einer Pascal-ähnlichen Sprache. Die GrammatikG: (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.
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.
Die LL-Parser-TabelleExpr 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. 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. 1. Parser-Lauf
Eingabe: Die Teile in den beiden Spalten Processed/Stack bilden eine Linksableitung.
Der Stack wird mit dem Startsymbol Stmt' initialisiert. 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: Der Parser-Lauf bleibt vor dem end stecken.
Zu SL und Lookahead end gibt es keinen Eintrag in der Parser-Tabelle, 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 $
|
Letzte Änderung: 19.12.2018 | © Prof. Dr. Uwe Schmidt |