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.
|
| |
Invariante
|
für alle Recursive Descent Parser
|
|
für alle X ∈ N gilt:
{input = w}
X(); // die zu X gehörige Prozedur
{input = w2, w = w1 ⋅ w2, X ⊢* w1}
|
|---|
| |
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 |
deterministische Grammatik für arithmetische Ausdrücke
mit den vier Grundrechenarten und mit Klammerschachtelung.
|
|
E ::= E + T
E ::= E - T
E ::= T
T ::= T * F
T ::= T / F
T ::= F
F ::= id
F ::= num
F ::= ( E )
|
|---|
| |
Routine für E |
void E() {
switch (sy) {
case ??? :
E();checkSymbol(PLUSSY);T();
break;
case ??? :
E();checkSymbol(MINUSSY);T();
break;
case ??? :
T();
break;
default :
error("??? expected");
}
}
|
|
Wie werden die case-Marken berechnet?
|
|
Ist die Berechnung in diesem Fall überhaupt möglich?
|
| |
Formalisierung
|
FIRST- und FOLLOW-Mengen für die Berechnung der Regelauswahl
und zum Testen, ob der rekursive Abstieg überhaupt möglich ist.
|
| |
Compilerbau: Rekursiver Abstieg
