Rekursiver Abstieg
|
|
|
|
Idee
|
|
.1
|
Zu jedem Nichtterminal-Symbol wird eine Prozedur
für die Analyse von Zeichenreichen entwickelt, die aus dem NT-Symbol abgeleitet
werden können.
|
|
|
.2
|
In jeder Prozedur wird durch Testen des nächsten Eingabe-Symbols
eine Regel (eine rechte Seite einer Produktion) für das NT-Symbol
ausgewählt.
|
|
|
Rahmen
|
class Parser {
static final int
IFSY = 1,
ID = 2,
...
EOFSY = n;
int sy;
int nextSymbol () {
return ...;
}
void inSymbol() {
sy = nextSymbol();
}
void checkSymbol(int sy) {
if ( this.sy == sy ) {
inSymbol();
} else {
error(...);
}
}
void error(...) {
}
void parse() {
inSymbol();
S1();
}
void S1() {
S();
checkSymbol(EOFSY);
}
}
|
|
|
Beispiel |
Grammatik für den Anweisungsteil einer einfachen Pascal-ähnlichen Sprache.
Die Terminalsymbole und Nichtterminalsymbole können aus den Regeln extrahiert werden.
Stmt sei das Startsymbol.
|
|
Stmt ::= if Expr then Stmt else Stmt fi
Stmt ::= while Expr do Stmt done
Stmt ::= begin SL end
Stmt ::= id := Expr
SL ::= Stmt SL1
SL1 ::=
SL1 ::= ; SL
Expr ::= id
Expr ::= num
|
|---|
|
|
Parser |
Die aus den Regeln erzeugten Routinen für den recursive descent parser
|
|
void Stmt() {
switch (sy) {
case IFSY :
checkSymbol(IFSY);
Expr();
checkSymbol(THENSY);
Stmt();
checkSymbol(ELSESY);
Stmt();
checkSymbol(FISY);
break;
case WHILESY :
checkSymbol(WHILESY);
Expr();
checkSymbol(DOSY);
Stmt();
checkSymbol(DONESY);
break;
case BEGINSY :
checkSymbol(BEGINSY);
SL();
checkSymbol(ENDSY);
break;
case ID :
checkSymbol(ID);
checkSymbol(ASSIGNSY);
Expr();
break;
default :
error("if, while, begin or id expected");
}
}
void SL() {
Stmt();
SL1();
}
void SL1() {
switch (sy) {
case SEMICOLON :
checkSymbol(SEMICOLON);
SL();
break;
default :
break;
}
}
|
|---|
|
|
Strategie
|
- über das nächste Eingabezeichen die passende Regel auswählen
- Terminalsymbole mit checkSymbol oder inSymbol überlesen
- für die NT-Symbole die zugehörige Prozedur aufrufen
|
|
|
|
Fehlererkennung und Fehlerbehandlung noch ungenau und nur rudimentär realisiert
|
|
|
|
Nur eine Regel für ein NT-Symbol: keine Auswahl-Problematik.
|
|
|
|
Problem: Die Auswahl der Regeln nur durch Testen des einen nächsten Zeichens.
|
|
|
|
Problem: Mit welchen Symbolen kann eine rechte Seite beginnen?
|
|
|
|
Problem: Wie behandelt man Epsilon-Produktionen?
|
|
|
2. Beispiel |
Grammatik für arithmetische Ausdrücke mit Klammerschachtelung.
|
|
Expr ::= Expr + Term
Expr ::= Expr - Term
Expr ::= Term
Term ::= Term * Factor
Term ::= Term / Factor
Term ::= Factor
Factor ::= id
Factor ::= num
Factor ::= ( Expr )
|
|---|
|
|
Formalisierung
|
FIRST- und FOLLOW-Mengen für die Berechnung der Regelauswahl
und zum Testen, ob der rekursive Abstieg überhaupt möglich ist.
|
|
|
Compilerbau & Formale Sprachen: Rekursiver Abstieg
