. Die
sind Symbole der Grammatik, die 
Zustände des
Parsers. 
ist das oberste Kellersymbol (TOS).
Ein Nachteil des Topdown-Verfahrens aus dem letzten Abschnitt ist, daß dieses
Verfahren nicht immer angewendet werden kann.
Wir wenden uns jetzt einem
Parserprinzip zu, daß eine noch größere Klassen von kontextfreien
Grammatiken abdeckt.
Bei diesem Vorgehen wird eine Reduktionsfolge
gesucht, die eine Zeichenreihe, die von links nach rechts verarbeitet
wird, auf das Startsymbol reduziert. Hierbei wird immer das rechteste
Nichtterminal ersetzt - daher auch die Bezeichnung
LR-Parsing .
Da hier von den Blättern des Ableitungsbaums her in
Richtung Wurzel gearbeitet wird, spricht man auch von einem Bottom-up-Verfahren .
LR-Parser sind aus verschiedenen Gründen interessant:
Für reale Programmiersprachen kann man diese Parser jedoch nicht mehr
manuell konstruieren. Man benötigt ein Werkzeug, nämlich einen
Parsergenerator.
yacc bzw. bison ist
der wohl prominenteste Vertreter dieser Gattung.
Selbst wenn die Grammatik Mehrdeutigkeiten enthält, können - mit
notfalls manuellen Eingriffen - effiziente Parser erzeugt werden.
Ein solcher Parser besteht aus zwei Teilen: einem Treiber, der immer gleich ist, und einer Tabelle, die aus der Grammatik generiert wird.
Wir werden drei Methoden kennenlernen, Parsertabellen zu erzeugen:
Wir betrachten die prinzipielle Arbeitsweise eines LR-Parsers [3]
.
Der Parser verarbeitet eine Eingabe von links nach rechts. Der Keller
enthält eine Zeichenreihe der Form . Die
sind Symbole der Grammatik, die Zustände des
Parsers. ist das oberste Kellersymbol (TOS).
Die Parser-Tabelle besteht aus einer ACTION- und einer
GOTO-Komponente.
Wenn TOS = ist und 
das aktuelle Eingabesymbol,
so legt ACTION 
eine von vier möglichen Aktionen fest:
Die Funktion GOTO berechnet aus einem Zustand und einem Symbol einen Folgezustand des Parsers.
Eine Konfiguration eines LR-Parsers ist ein Paar aus Kellerinhalt und unverbrauchter Eingabe:
Die Folgekonfiguration nach jeder der vier möglichen Aktionen ist dann:
.
und 
.
accept error
Wir betrachten wieder einmal die Grammatik für arithmetische Ausdrücke:
Die Codes für die Aktionen sind:
Die Parsertabelle
| Zustand | ACTION | GOTO | |||||||
| id | + | * | ( | ) | $ | E | T | F | |
| 0 | s5 | s4 | 1 | 2 | 3 | ||||
| 1 | s6 | acc | |||||||
| 2 | r2 | s7 | r2 | r2 | |||||
| 3 | r4 | r4 | r4 | r4 | |||||
| 4 | s5 | s4 | 8 | 2 | 3 | ||||
| 5 | r6 | r6 | r6 | r6 | |||||
| 6 | s5 | s4 | 9 | 3 | |||||
| 7 | s5 | s4 | 10 | ||||||
| 8 | s6 | s11 | |||||||
| 9 | r1 | s7 | r1 | r1 | |||||
| 10 | r3 | r3 | r3 | r3 | |||||
| 11 | r5 | r5 | r5 | r5 | |||||
Der Kellerinhalt
1. 0 id * id + id $ 2. 0 id 5 * id + id $ 3. 0 F 3 * id + id $ 4. 0 T 2 * id + id $ 5. 0 T 2 * 7 id + id $ 6. 0 T 2 * 7 id 5 + id $ 7. 0 T 2 * 7 F 10 + id $ 8. 0 T 2 + id $ 9. 0 E 1 + id $ 10. 0 E 1 + 6 id $ 11. 0 E 1 + 6 id 5 $ 12. 0 E 1 + 6 F 3 $ 13. 0 E 1 + 6 T 9 $ 14 0 E 1 $
Wenn die Parsertabelle keine doppelten Einträge enthält, kann man eine
Zeichenreihe ohne Backtracking analysieren.
Um zu entscheiden, welche Aktion ausgeführt werden soll, muß man nur
den obersten Eintrag auf dem Keller aus Zustand und Symbol sowie
(möglicherweise) die k nächsten Eingabesymbole betrachten.
In der Praxis kommt man mit k <= 1 aus.
Ein Grammatik, die von einem LR-Parser mit einem Lookahead von
k Symbolen geparst werden kann, bezeichnen wir als
LR(k)-Grammatik.
Man kann zeigen, daß man für jede LR(k)-Grammatik eine äquivalente
LR(1)-Grammatik erzeugen kann. Allerdings existieren Grammatiken, die
nicht LR(k) für alle k >= 0 sind.
Beispiel: (dangling else)
Hier kann man nicht erkennen, ob geshiftet oder reduziert werden muß, wenn in der Eingabe ein ELSE erscheint.
Ein Handle einer Rechtsableitung 
ist eine
Produktion 
und eine Position in , an
der die Zeichenreihe 
gefunden und durch A ersetzt wird, um
die vorhergehende Satzform in der Rechtsableitung von zu
erhalten.
Wenn S 
eine Rechtsableitung
ist, so ist in der Position, die auf
folgt, ein Handle.
Wenn die Grammatik eindeutig ist, so hat jede Satzform in einer
Rechtsableitung genau ein Handle.
Wenn der Zusammenhang klar ist, sagen wir auch ist ein
Handle von .
Beispiel:
Diese Grammatik ist bekanntlich mehrdeutig. Man betrachte die
Rechtsableitung
Hier ist z.B. 
Handle von 
da man durch
Ersetzung von durch E die vorhergehende Satzform erhalten
kann.
Da die Grammatik mehrdeutig ist, gibt es eine weitere Rechtsableitung
für die gleiche Zeichenreihe:
Im ersten Fall war 
ein Handle für
, jetzt ist
Handle für die gleiche Satzform.
In diesem Abschnitt beschreiben wir ein Verfahren, mit dem ein
''einfacher'' LR-Parser (Simple LR-Parser )
konstruiert werden kann.
Die grundlegende Idee ist die Konstruktion eines DEA aus
der Grammatik, den wir dann in eine Parsertabelle
umwandeln.
Dieser DEA erkennt die brauchbaren Präfixe (viable
prefixes )
der Grammatik, das sind
diejenigen Anfangsworte von Satzformen in Rechtsableitungen, die keine
Symbole rechts vom Handle enthalten.
Definition:
Ein LR(0)-Item (kurz Item) einer Grammatik G ist
eine Produktion aus G, die an einer Stelle der rechten Seite einen
Punkt enthält.
Beispiel:
erzeugt die Items:
erzeugt nur
Ein Item zeigt also an, wieviel wir von einer Produktion während des
Parsens schon gesehen haben.
heißt, wir haben eine Zeichenkette, die
aus X ableitbar ist, erkannt und erwarten nun eine Zeichenkette, die
man aus YZ ableiten kann.
Die Items werden nun in Mengen zusammengefaßt, die die Zustände eines
LR-Parsers darstellen.
Die kanonische LR(0)-Kollektion ist die Basis für die
Konstruktion von SLR-Parsern.
Für die Berechnung benötigen wir eine erweiterte Grammatik G'
und zwei Funktionen CLOSURE und GOTO .
Die erweiterte Grammatik:
Sei G = (V,T,P,S) eine kfG . Dann ist die erweiterte
Grammatik 
. Es wird also lediglich ein neues Startsymbol eingeführt.
Sei I eine Menge von Items für eine Grammatik G = (V,T,P,S). Dann berechnen wir CLOSURE(I) wie folgt:
CLOSURE(I) und
CLOSURE(I)
Der Grund für diese Berechnung ist, daß wir, wenn
im Parsingprozeß auftritt,
erwarten, als Nächstes eine Zeichenkette, die aus 
und damit
aus 
abgeleitet
werden kann, in der Eingabe zu finden.
, CLOSURE(I) ist dann:
Algorithmus:
ItemSet Closure(ItemSet I)
{
do
{
für alle A -> a.Bb aus I und alle B -> g aus G':
falls B -> .g nicht aus I
setze I = I + {B -> .g}
} while ``noch neue Items zu I hinzugekommen'';
return I;
}
Ein Item 
ist gültig für ein brauchbares Präfix 
,
wenn es eine Rechtsableitung S'
gibt.
Normalerweise kann ein Item für mehrere Präfixe gültig sein.
Wenn
gültig für
ist, und 
, so heißt dies, das wir noch nicht
das ganze Handle auf dem Keller haben und daher eine shift-Aktion
ausführen müssen.
Ist 
, so haben wir
als Handle erkannt
und müssen reduzieren .
Nun kann es mehrere gültige Items für ein brauchbares Präfix geben, die unterschiedliche Aktionen erfordern. Einige dieser Konflikte lassen sich durch die Verwendung des Lookahead auflösen.
Wenn I eine Menge von Items ist und X ein Symbol der Grammatik,
dann ist GOTO(I,X) als
CLOSURE 
definiert.
Beispiel:
GOTO(I,+) ist dann
Wenn I eine Menge gültiger Items für ein brauchbares Präfix
ist, so ist GOTO(I,X) die Menge der gültigen Items
für das brauchbare Präfix 
.
Algorithmus:
Collection Items(Grammar G')
{
Collection C;
C = {Closure({[S' -> .S]})};
do
{
für alle Itemmengen I aus C und jedes Symbol X aus G':
M = GOTO(I,X);
if ((M != {}) && (M nicht aus C))
C = C + {M};
} while ``C hat sich noch verändert'';
return C;
}
Beispiel:
I0: I5 = GOTO(I0,id)
E'-> .E F -> id.
E -> .E+T
E -> .T I6 = GOTO(I1,+)
T -> .T*F E -> E+.T
T -> .F T -> .T*F
F -> .(E) T -> .F
F -> .id F -> .(E)
F -> .id
I1 = GOTO(I0,E)
E'-> E. I7 = GOTO(I2,*)
E -> E.+T T -> T*.F
F -> .(E)
I2 = GOTO(I0,T) F -> .id
E -> T.
T -> T.*F I8 = GOTO(I4,E) GOTO(I4, T) = I2
F -> (E.) GOTO(I4, F) = I3
I3 = GOTO(I0,F) E -> E.+T
T -> F.
I9 = GOTO(I6,T)
I4 = GOTO(I0,() E -> E+T.
F -> (.E) T -> T.*F
E -> .E+T
E -> .T I10 = GOTO(I7,F)
T -> .T*F T -> T*F.
T -> .F
F -> .(E) I11 = GOTO(I8,))
F -> .id F -> (E).
Wenn wir die Itemmengen als Zustände eines DEA D ansehen,
als Anfangszustand und alle Zustände als Endzustände, so
können wir GOTO(I,X) als Zustandsübergangsfunktion
interpretieren. Dann ist D ein endlicher Automat, der alle
brauchbaren Präfixe der Grammatik G' akzeptiert.
Zu einer kontextfreien Grammatik G konstruieren wir die erweiterte Grammatik G' und die kanonische Kollektion von LR(0)-Items C.
Hieraus leiten wir jetzt die Funktionen ACTION und GOTO her:
Sei 
Die Zustände 
des Parsers werden aus den 
konstruiert.
Konstruktion von ACTION
,
GOTO 
dann ist ACTION(i, a) = reduce 
für 
dann ist ACTION 
accept
Falls bei dieser Konstruktion Mehrfacheinträge auftreten, schlägt die
Konstruktion fehl. Die Grammatik ist dann nicht SLR.
Konstruktion von GOTO
:
Anfangszustand ist der Zustand der zur Itemmenge gehört,
die 
enthält.
Die SLR-Methode erfordert im Zustand i eine Reduktion
für das Eingabesymbol a, wenn 
ein
Item in und ist.
Nun kann sich aber im Zustand i ein brauchbares Präfix 
auf dem Stack befinden, für das keine Rechtsableitung
existiert. Dann wäre die Reduktion
nicht zulässig. Wir betrachten ein
Beispiel:
Die LR(0)-Item-Mengen
I0: I5 = GOTO(I0, id)
S' -> .S L -> id.
S -> .L = R
S -> .R I6 = GOTO(I2, =)
L -> .*R S -> L=.R
L -> .id R -> .L
R -> .L L -> .*R
L -> .id
I1 = GOTO(I0, S)
S' -> S. I7 = GOTO(I4, R)
L -> *R.
I2 = GOTO(I0, L)
S -> L.=R I8 = GOTO(I4, L)
R -> L. R -> L.
I3 = GOTO(I0, R) I9 = GOTO(I6, R)
S -> R. S -> L=R.
I4 = GOTO(I0, *)
L -> *.R
R -> .L
L -> .*R
L -> .id
Die Parsertabelle:
| Zustand | ACTION | GOTO | |||||
| * | id | = | $ | S | L | R | |
| 0 | s4 | s5 | 1 | 2 | 3 | ||
| 1 | acc | ||||||
| 2 | s6/r5 | r5 | |||||
| 3 | r2 | ||||||
| 4 | s4 | s5 | 8 | 7 | |||
| 5 | r4 | r4 | |||||
| 6 | s4 | s5 | 8 | 9 | |||
| 7 | r3 | r3 | |||||
| 8 | r5 | r5 | |||||
| 9 | r1 | ||||||
Da 
und 
müßte eine
Reduktion erfolgen. Es gibt aber keine Satzform, die mit 'R='
beginnt. Andererseits wird gefordert, daß das '=' geshiftet und in
Zustand 6 gewechselt wird.
Um diesen Konflikt zu lösen, erweitern wir die Items um eine
zusätzliche Komponente, den Lookahead , und sprechen von
LR(1)-Items :
Wenn 
, ist der Lookahead ohne Wirkung.
Eine Reduktion wird aber nur noch dann durchgeführt, wenn das Item die
Form 
hat und a das aktuelle Eingabesymbol
ist.
Definition:
Ein LR(1)-Item heißt gültig für ein
brauchbares Präfix , wenn es eine Ableitung
S 
mit 
gibt,
und a das erste Symbol von w oder 
und 
ist.
Wenn 
ein gültiges Item für ein brauchbares
Präfix ist, so existiert nach unserer Definition eine
Rechtsableitung S 
mit .
Angenommen aus 
kann man die terminale Zeichenkette by
ableiten. Dann existiert für jede Produktion 
eine
Ableitung
S 
.
Dann ist 
gültig für .
b kann das erste aus abgeleitete Terminal sein, oder aber
auch a, wenn zu 
abgeleitet werden kann:
by
Zusammenfassend kann also b ein beliebiges Terminal aus
sein.
Wir benötigen wieder die Funktionen CLOSURE und GOTO.
ItemSet Closure(ItemSet I)
{
do
{
für alle [A -> alpha.B beta, a] aus I
und alle B -> gamma aus G'
und alle b aus FIRST(beta a):
falls B -> .gamma nicht aus I
setze I = I + {[B -> .gamma, b]}
} while ``noch neue Items zu I hinzugekommen'';
return I;
}
Collection GOTO(ItemSet I, Symbol X)
{
Collection C;
C = {[A -> alpha X. beta, a] |
[A -> alpha .X beta, a] aus I};
return Closure(C);
}
int main()
{
Collection C;
C = {Closure({[S' -> .S, $]})};
do
{
für ''alle Items I aus C
und alle Symbole X aus G',
für die GOTO(I,X) nicht leer
und nicht in C''
C = C + GOTO(I, X);
} while ''C hat sich verändert''
return 0;
}
I0: I4 = GOTO(I0, id) GOTO(I5, *) = I5
S' -> .S, $ L -> id., =
S -> .L=R, $ L -> id., $ GOTO(I5, id) = I4
S -> .R, $
L -> .*R, = I5 = GOTO(I0, *)
L -> .id, = L -> *.R, =
R -> .L, $ L -> *.R, $ I8 = GOTO(I5, L)
L -> .*R, $ R -> .L, = R -> L., =/$
L -> .id, $ R -> .L, $
L -> .*R, =/$ I9 = GOTO(I6, L)
I1 = GOTO(I0, S) L -> .id, =/$ R -> L., $
S' -> S., $
I6 = GOTO(I2, =) I10 = GOTO(I6, *)
I2 = GOTO(I0, L) S -> L=.R, $ L -> *.R, $
S -> L.=R, $ R -> .L, $ R -> .L, $
R -> L., $ L -> .*R, $ L -> .*R, $
L -> .id, $ L -> .id, $
I3 = GOTO(I0, R)
S -> R., $ I7 = GOTO(I5, R) I11 = GOTO(I6, id)
L -> *R., = L -> id., $
L -> *R., $
I12 = GOTO(I6, R) I13 = GOTO(I10, R)
S -> L=R., $ L -> *R., $
GOTO(I10, L) = I9 GOTO(I10, *) = I10 GOTO(I10, id) = I11
Zu einer kontextfreien Grammatik G konstruieren wir die erweiterte Grammatik G' und die Mengen von LR(1)-Items C.
Hieraus leiten wir jetzt die Funktionen ACTION und GOTO her:
Sei die Kollektion der Mengen von LR(1)-Items.
Die Zustände des Parsers werden aus den
konstruiert.
Konstruktion von ACTION
,
GOTO 
dann ist ACTION(i, a) = reduce . reduziert wurde.
dann ist ACTION accept
Falls bei dieser Konstruktion Mehrfacheinträge auftreten, schlägt die
Konstruktion fehl. Die Grammatik ist dann nicht LR(1).
Konstruktion von GOTO
:
Anfangszustand ist der Zustand der zur Itemmenge gehört,
die 
enthält.
Die Parser-Tabelle zum Beipiel:
| Zustand | ACTION | GOTO | |||||
| * | id | = | $ | S | L | R | |
| 0 | s5 | s4 | 1 | 2 | 3 | ||
| 1 | acc | ||||||
| 2 | s6 | r6 | |||||
| 3 | r3 | ||||||
| 4 | r5 | r5 | |||||
| 5 | s5 | s4 | 8 | 7 | |||
| 6 | s10 | s11 | 9 | 12 | |||
| 7 | r4 | r4 | |||||
| 8 | r6 | r6 | |||||
| 9 | r6 | ||||||
| 10 | s10 | s11 | 9 | 13 | |||
| 11 | r5 | ||||||
| 12 | r2 | ||||||
| 13 | r4 | ||||||
Abschließend konstruieren wir die LALR-Parser-Tabellen .
Die kanonische LR-Tabelle eines Parsers für eine Programmiersprache
wie Pascal oder C ist mit mehreren tausend Zuständen etwa um das
Zehnfache größer als die entsprechende SLR-Tabelle. Die LALR-Tabelle
hat immer genauso viele Zustände wie die SLR-Tabelle und daher der
LR-Tabelle vorzuziehen.
Die Idee beim LALR-Verfahren, das in der Praxis von Parsergeneratoren wie yacc verwendet wird, ist die folgende:
Bei den LR(1)-Itemmengen treten häufig Mengen auf, deren Elemente sich
nur in der zweiten Komponente unterscheiden. Im Beispiel des letzten Abschnitts
sind das z.B. die Mengen 
und 
oder auch 
und 
.
Man sagt, diese Zustände haben den gleichen Kern oder
core .
Im Zustand 12 wird nur dann eine Reduktion durchgeführt, wenn das
Endsymbol in der Eingabe erscheint, sonst liegt ein Fehler vor. Im
Zustand 4 wird auch beim Symbol = reduziert. Wenn wir nun die beiden
Mengen vereinigen, reduzieren wir immer, unabhängig vom aktuellen
Eingabesymbol.
Bei einer fehlerhaften Zeichenkette wie id = id = id wird beim LR(1)-Parser das fehlerhafte zweite = im Zustand 11 bemerkt. Vereinigt man nun die Zustände 4 und 11, so wird noch einmal reduziert, aber dann wird der Fehler ebenfalls erkannt, und zwar bevor das nächste Symbol geshifted wird.
Da die GOTO-Funktion nur vom Kern des Zustandes abhängt, kann man auch
die GOTO-Mengen von zusammengelegten Zuständen vereinigen.
Durch dieses Zusammenlegen können möglicherweise
reduce/reduce-Konflikte entstehen, nämlich wenn die Grammatik in
zwei Mengen Items der Art 
und 
enthält.
shift/reduce-Konflikte kann es nicht geben, da dann diese
Konflikte bereits in der ursprünglichen Kollektion auftreten müßten.
Enthält die Vereinigung von zwei Mengen mit gleichem Kern die Items
und 
, so müssen diese
beiden Elemente schon vor der Vereinigung in einer Menge
aufgetreten und daher die Grammatik nicht - wie vorausgesetzt - LR(1)
gewesen sein.
Konstruktion von ACTION
die Kollektion der Mengen von
LR(1)-Items.
die resultierende Menge von
LR(1)-Items.
Berechne ACTION wie beim LR(1)-Verfahren.
: 
. Dann haben 
den gleichen Kern. Sei K die Vereinigung aller
Itemmengen, die den gleichen Kern wie 
haben. Setze
GOTO(J, X) = K
Beispiel:
Wir betrachten wieder die Tabelle aus dem Beispiel von Seite
.
Es lassen sich die Mengen
identifizieren. Damit ergibt sich die Tabelle:
| Zustand | ACTION | GOTO | |||||
| * | id | = | $ | S | L | R | |
| 0 | s5.10 | s4.11 | 1 | 2 | 3 | ||
| 1 | acc | ||||||
| 2 | s6 | r6 | |||||
| 3 | r3 | ||||||
| 4.11 | r5 | r5 | |||||
| 5.10 | s5.10 | s4.11 | 8.9 | 7.13 | |||
| 6 | s5.10 | s4.11 | 9 | 12 | |||
| 7.13 | r4 | r4 | |||||
| 8.9 | r6 | r6 | |||||
| 12 | r2 | ||||||
Nachdem wir im letzten Abschnitt die theoretischen Grundlagen der
LR-Analyse kennengelernt haben, wollen wir nun die Praxis am Beispiel
des
Parsergenerators yacc betrachten.
Die Abkürzung yacc steht für yet another
compiler compiler. Die GNU-Werkzeuge enthalten
einen kompatiblen Generator mit dem Namen bison .
Wir betrachten zunächst ein Beispiel. Danach sehen wir uns das Zusammenspiel von lex und yacc an und betrachten die Syntax für yacc-Spezifikationen.
Als Eingabe erwartet der Generator eine kontextfreie Grammatik, aus der dann ein LALR-Parser erzeugt wird. Wir geben zunächst die lex-Spezifikation für die übliche Grammatik für arithmetische Ausdrücke an:
expr.l:
%{
#include "expr.h"
#include "expr.tab.h"
%}
idf [A-Za-z][A-Za-z0-9_]*
nl \n
blank [ \t]+
%%
{blank} ;
nl {linecnt++;}
\* {return mult;}
\( {return lpar;}
\) {return rpar;}
\+ {return plus;}
{idf} {return id;}
Die zugehörige yacc-Spezifikation ist
expr.y:
%{
#include "expr.h"
%}
%token plus mult lpar rpar id
%start E
%%
E : E plus T | T
T : T mult F | F
F : id | lpar E rpar
%%
Außerdem benötigen wir einige Deklarationen und ein Hauptprogramm:
expr.h: #include <fstream.h> #include <string.h> #include <iomanip.h> void yyerror(char *err); int yylex(); extern int error; extern int linecnt;
exprmain.cc:
#include "expr.h"
#include <FlexLexer.h>
int linecnt = 1;
extern void yyparse();
void yyerror(char *err)
{ error = 1;
cerr << "Line: " << linecnt << ": " << err;
}
FlexLexer* lexer = new yyFlexLexer;
int yylex(){return lexer->yylex();}
int error = 0;
int main()
{
cout << "Auf gehts" << endl;
yyparse();
return 0;
}
Der Aufruf bison -v expr.y liefert die Datei expr.output, die sehr nützliche Informationen über den generierten Parser enthält:
Grammar
rule 1 E -> E plus T
rule 2 E -> T
rule 3 T -> T mult F
rule 4 T -> F
rule 5 F -> id
rule 6 F -> lpar E rpar
state 0
lpar shift, and go to state 1
id shift, and go to state 2
E go to state 3
T go to state 4
F go to state 5
state 1
F -> lpar . E rpar (rule 6)
lpar shift, and go to state 1
id shift, and go to state 2
E go to state 6
T go to state 4
F go to state 5
state 2
F -> id . (rule 5)
$default reduce using rule 5 (F)
state 3
E -> E . plus T (rule 1)
$ go to state 12
plus shift, and go to state 7
state 4
E -> T . (rule 2)
T -> T . mult F (rule 3)
mult shift, and go to state 8
$default reduce using rule 2 (E)
state 5
T -> F . (rule 4)
$default reduce using rule 4 (T)
state 6
E -> E . plus T (rule 1)
F -> lpar E . rpar (rule 6)
plus shift, and go to state 7
rpar shift, and go to state 9
state 7
E -> E plus . T (rule 1)
lpar shift, and go to state 1
id shift, and go to state 2
T go to state 10
F go to state 5
state 8
T -> T mult . F (rule 3)
lpar shift, and go to state 1
id shift, and go to state 2
F go to state 11
state 9
F -> lpar E rpar . (rule 6)
$default reduce using rule 6 (F)
state 10
E -> E plus T . (rule 1)
T -> T . mult F (rule 3)
mult shift, and go to state 8
$default reduce using rule 1 (E)
state 11
T -> T mult F . (rule 3)
$default reduce using rule 3 (T)
state 12
$ go to state 13
state 13
$default accept
Die Eingabe a + b * (c + d) liefert den folgenden Trace:
Auf gehts
yydebug = 1
Starting parse
Entering state 0
Reading a token: Next token is 262 (id)
Shifting token 262 (id), Entering state 2
Reducing via rule 5 (line 14), id -> F
state stack now 0
Entering state 5
Reducing via rule 4 (line 12), F -> T
state stack now 0
Entering state 4
Reading a token: Next token is 258 (plus)
Reducing via rule 2 (line 10), T -> E
state stack now 0
Entering state 3
Next token is 258 (plus)
Shifting token 258 (plus), Entering state 7
Reading a token: Next token is 262 (id)
Shifting token 262 (id), Entering state 2
Reducing via rule 5 (line 14), id -> F
state stack now 0 3 7
Entering state 5
Reducing via rule 4 (line 12), F -> T
state stack now 0 3 7
Entering state 10
Reading a token: Next token is 259 (mult)
Shifting token 259 (mult), Entering state 8
Reading a token: Next token is 260 (lpar)
Shifting token 260 (lpar), Entering state 1
Reading a token: Next token is 262 (id)
Shifting token 262 (id), Entering state 2
Reducing via rule 5 (line 14), id -> F
state stack now 0 3 7 10 8 1
Entering state 5
Reducing via rule 4 (line 12), F -> T
state stack now 0 3 7 10 8 1
Entering state 4
Reading a token: Next token is 258 (plus)
Reducing via rule 2 (line 10), T -> E
state stack now 0 3 7 10 8 1
Entering state 6
Next token is 258 (plus)
Shifting token 258 (plus), Entering state 7
Reading a token: Next token is 262 (id)
Shifting token 262 (id), Entering state 2
Reducing via rule 5 (line 14), id -> F
state stack now 0 3 7 10 8 1 6 7
Entering state 5
Reducing via rule 4 (line 12), F -> T
state stack now 0 3 7 10 8 1 6 7
Entering state 10
Reading a token: Next token is 261 (rpar)
Reducing via rule 1 (line 10), E plus T -> E
state stack now 0 3 7 10 8 1
Entering state 6
Next token is 261 (rpar)
Shifting token 261 (rpar), Entering state 9
Reducing via rule 6 (line 14), lpar E rpar -> F
state stack now 0 3 7 10 8
Entering state 11
Reducing via rule 3 (line 12), T mult F -> T
state stack now 0 3 7
Entering state 10
Reading a token:
Now at end of input.
Reducing via rule 1 (line 10), E plus T -> E
state stack now 0
Entering state 3
Now at end of input.
Shifting token 0 ($), Entering state 12
Now at end of input.
Das folgende Makefile erzeugt einen Parser für arithmetische Ausdrücke:
FLAGS = -g -DUNIX -DYYDEBUG
BISONFLAGS = --debug
GCC = g++
LEXY = lex.yy
TABB = expr.tab
CLEAN = rm -f *.o *.tab.* lex.yy.cc exprmain
exprmain : $(LEXY).o exprmain.o $(TABB).o \
; $(GCC) $(FLAGS) -o exprmain *.o -lfl
$(LEXY).o : $(LEXY).cc \
; $(GCC) $(FLAGS) -c $(LEXY).cc
$(TABB).o : $(TABB).cc \
; $(GCC) $(FLAGS) -c $(TABB).cc
$(TABB).cc : $(TABB).c \
; cp $(TABB).c $(TABB).cc
$(TABB).c : expr.y \
; bison $(BISONFLAGS) expr.y
$(TABB).h : expr.y \
; bison -d $(BISONFLAGS) expr.y
$(LEXY).cc : expr.l $(TABB).h expr.h \
; flex -+ expr.l
exprmain.o : exprmain.cc expr.h \
; $(GCC) $(FLAGS) -c exprmain.cc
clean : \
; $(CLEAN)
Eine yacc-Spezifikation setzt sich aus drei Abschnitten zusammen:
Deklarationen
%%
Grammatik-Regeln
%%
C-Routinen
%{
C-Deklarationen
%}
Die C-Deklarationen können enthalten:
#include
#define
Deklarationen von C-Variablen und C-Typen
Alles, was zwischen %{...%} steht, wird in das erzeugte C-Programm kopiert.
%token ID NUMBER /* Token-Deklarationen */%start prog /* Definition des Startsymbols */
%union {typ typename; ...} /* Typdefinition für yylval */
%type<typename> nonterminal /* Typdefinition für Variable */
%token<typename> token /* Typdefinition für token */
Symbol : ĒDefinition {
Semantische Aktion
}
;
Mit den einzelnen Produktionen der Grammatik kann man semantische Aktionen verknüpfen, z.B. das Berechnen von Werten, wenn der Parser Teil eines Interpretierers ist, oder die Ausgabe von Codesequenzen in einem Compiler:
%union {float real;
int integer;}
%token PLUS
%token <integer> INTEGER
%token <real> REAL
%type <real> rexpr
%type <integer> iexpr
%start expr1
%%
expr1: |
expr1 expr
expr : rexpr
{printf("real sum = %f\n", $1);}
| iexpr
{printf("int sum = %d\n", $1);}
iexpr : INTEGER PLUS INTEGER
{ $$ = $1 + $3;}
rexpr : REAL PLUS REAL
{ $$ = $1 + $3;}
%%
#include "lex.yy.c"
Mit jedem Element (Terminal oder Nonterminal) der rechten Seite kann ein semantischer Wert
verbunden werden, auf
den über die Positionsnummer zugegriffen werden kann. Dazu ist es
nötig, den Typ des zugeordneten Wertes im Deklarationsabschnitt zu
vereinbaren. Das geschieht durch die Angabe des Typs im
der Token- bzw. Nonterminaldeklaration und
durch Anlegen einer Kompentente in der
Struktur yylval :
%union {Node *nodeptr;
char strval[256]; /* Identifikatoren */
long intval; /* Integerkonstanten */
struct {BinNode *l,
*up;} sel;
}
%token <intval> multop divop modop andop addop subop orop
...
%token <intval> integer
%token <strval> ident
...
%type <intval> Sign Op1 Op2 Relop
%type <nodeptr> Factor Term SimpleExpression Expression
%type <sel> Selector
...
Das folgende Beispiel zeigt eine mehrdeutige Grammatik für primitive
arithmetische Ausdrücke. Der vorhandene
shift/reduce-Konflikt wird dadurch aufgelöst, daß yacc im
Zweifelsfall immer shiftet.
State 4 contains 1 shift/reduce conflict.
Grammar
rule 1 expr -> 'a'
rule 2 expr -> expr '+' expr
state 0
'a' shift, and go to state 1
expr go to state 2
state 1
expr -> 'a' . (rule 1)
$default reduce using rule 1 (expr)
state 2
expr -> expr . '+' expr (rule 2)
$ go to state 5
'+' shift, and go to state 3
state 3
expr -> expr '+' . expr (rule 2)
'a' shift, and go to state 1
expr go to state 4
state 4
expr -> expr . '+' expr (rule 2)
expr -> expr '+' expr . (rule 2)
'+' shift, and go to state 3
'+' [reduce using rule 2 (expr)]
$default reduce using rule 2 (expr)
state 5
$ go to state 6
state 6
$default accept
Ein weiteres bekanntes Problem ist die Zuordnung des else in geschachtelten bedingten Anweisungen, das von yacc aber wie erwartet gelöst wird:
State 5 contains 1 shift/reduce conflict.
Grammar
rule 1 S -> 'i' '5' 't' S
rule 2 S -> 'i' '5' 't' S 'e' S
rule 3 S -> 'a'
state 0
'i' shift, and go to state 1
'a' shift, and go to state 2
S go to state 8
state 1
S -> 'i' . '5' 't' S (rule 1)
S -> 'i' . '5' 't' S 'e' S (rule 2)
'5' shift, and go to state 3
state 2
S -> 'a' . (rule 3)
$default reduce using rule 3 (S)
state 3
S -> 'i' '5' . 't' S (rule 1)
S -> 'i' '5' . 't' S 'e' S (rule 2)
't' shift, and go to state 4
state 4
S -> 'i' '5' 't' . S (rule 1)
S -> 'i' '5' 't' . S 'e' S (rule 2)
'i' shift, and go to state 1
'a' shift, and go to state 2
S go to state 5
state 5
S -> 'i' '5' 't' S . (rule 1)
S -> 'i' '5' 't' S . 'e' S (rule 2)
'e' shift, and go to state 6
'e' [reduce using rule 1 (S)]
$default reduce using rule 1 (S)
state 6
S -> 'i' '5' 't' S 'e' . S (rule 2)
'i' shift, and go to state 1
'a' shift, and go to state 2
S go to state 7
state 7
S -> 'i' '5' 't' S 'e' S . (rule 2)
$default reduce using rule 2 (S)
state 8
$ go to state 9
state 9
$ go to state 10
state 10
$default accept
Das spezielle Token error ist ein vordefiniertes terminales
Symbol, das für die Fehlerbehandlung reserviert ist. Wenn ein
Fehler auftritt, generiert der Parser dieses Token. Wenn eine Regel
existiert, die dieses Token im aktuellen Kontext erkennt, kann der
Parser weitermachen:
Beispiel:
stmnt: /* empty string */
| stmnt '\n'
| stmnt exp '\n'
| stmnt error '\n'
Die vierte Regel besagt, daß das error-Token gefolgt von einem Zeilenende ein gültiges Statement ist. Wenn nun ein Fehler z.B. in exp auftritt, wird yacc Zustände und Objekte vom Keller entfernen, bis ein Zustand erreicht wird, in dem error ein gültiges Eingabesymbol ist. Wenn dann der Lookahead ein Zeilenende ist, kann error auf den Keller geshiftet werden, ansonsten werden die Eingabesymbole überlesen, bis ein Zeilenende auftritt.
Es kann auch nützlich sein, im Fehlerfall zur schließenden Klammer eines geklammerten Ausdrucks vorzuspulen:
Factor: lpar Expression rpar
|integer
|ident Selector
|notsy Factor
|lpar error {yyerror(" error in factor ");}
rpar { $$ = NULL;}
Eingabe: 1 MODULE main; 2 BEGIN 3 WHILE (a + ) DO 4 IF a < b 5 THEN a := b; c := d 6 ELSIF c < a THEN a := c 7 ELSIF b = (a+*b) 8 THEN b = c 9 ELSE a := 2 * 10 END; 11 END 12END main. Ausgabe: Syntaxfehler in Zeile 3: parse error Syntaxfehler in Zeile 3: error in factor Syntaxfehler in Zeile 7: parse error Syntaxfehler in Zeile 7: error in factor Syntaxfehler in Zeile 7: error in factor Syntaxfehler in Zeile 7: error in factor Syntaxfehler in Zeile 8: parse error
Trace:
Reducing via rule 44 (line 233), Term -> SimpleExpression
state stack now 0 1 2 3 5 10 19 45 78 45 78 45 17 35
Entering state 40
Next token is 262 (addop)
Shifting token 262 (addop), Entering state 60
Reducing via rule 48 (line 248), addop -> Op1
state stack now 0 1 2 3 5 10 19 45 78 45 78 45 17 35 40
Entering state 70
Reading a token: Next token is 274 (rpar)
Syntaxfehler in Zeile 9: parse error
Error: state stack now 0 1 2 3 5 10 19 45 78 45 78 45 17 35 40
Error: state stack now 0 1 2 3 5 10 19 45 78 45 78 45 17 35
Shifting error token, Entering state 55
Reducing via rule 61 (line 290), -> @1
Syntaxfehler in Zeile 9: error in factor
state stack now 0 1 2 3 5 10 19 45 78 45 78 45 17 35 55
Entering state 87
Next token is 274 (rpar)
Shifting token 274 (rpar), Entering state 97
Reducing via rule 62 (line 290), lpar error @1 rpar -> Factor
Prof. Dr. Reinhard Völler