27.3 Parserkonstruktion

Ein Parser in Java

Wir wollen nun zum Abschluss des Kurses kommen und überlegen, wie man jetzt einen funktionierenden Parser konstruieren kann, wenn eine eindeutige und kontextfreie Grammatik G vorgegeben ist. Es gibt eigentlich nur zwei Regeln zur Parserkonstruktion, die beachtet werden müssen.

Regel 1

Wir erweitern unsere eindeutige Grammatik um Ausgaben. Ein Compiler analysiert ja nicht nur den Quelltext und meldet Fehler, sondern er gibt ja auch die Übersetzung des Quelltextes aus. Um solche Ausgabebefehle müssen wir nun die Grammatik erweitern:

P1: Expr --> Term 
P2: Expr --> Expr + Term [ print "add"]
P3: Expr --> Expr - Term [ print "sub"]

P4: Term --> Fact 
P5: Term --> Term * Fact [ print "mul"]
P6: Term --> Term / Fact [ print "div"]

P7: Fact --> num [ print "push "+ token.zahlenAttribut]
P8: Fact --> id  [ print "push "+ token.stringAttribut]
P9: Fact --> (Expr)

Das ist die gleiche Grammatik wie im letzten Abschnitt, allerdings wurden die Produktionsregeln um eine Codeerzeugung erweitert. Wenn der Parser die Produktionen 2, 3, 5, 6, 7, oder 8 anwendet (Rückwärtsableitung; Reduktion), dann wird gleichzeitig der in den eckigen Klammern stehende Code ausgedruckt, zum Beispiel in die Konsole oder in eine Textdatei.

Eine entsprechende Java-Umsetzung der Produktion 2 könnte zum Beispiel so aussehen:

public void expr()
{
   expr();
   match('+');
   term();
   System.out.println("add");
}

Jedes Nichtterminal auf der rechten Seite der Produktion wird durch den Aufruf einer Methode realisiert. Die Methode heißt genau so wie das Nichtterminal, allerdings ist in Java auf die Schreibweise zu achten: Methoden sollten stets mit einem Kleinbuchstaben beginnen. Im vorliegenden Fall ruft sich die Methode expr selbst auf; dies ist ein Beispiel für eine direkte Rekursion.

Jedes Terminal auf der rechten Seite, z.B. das Plus-Zeichen, wird durch den Aufruf einer Methode match realisiert. Die Aufgabe dieser Methode ist es, das nächste Token aus dem Tokenstrom zu holen, der dem Parser vom Lexer übergeben wurde.

Die Umsetzung der Produktion 5 sähe nach dieser Regel so aus:

public void term()
{
   term();
   match('*');
   fact();
   System.out.println("mul");
}

Regel 2

Lookahead

Um diese Regel zu verstehen, muss man erst mal klären, was ein lookahead ist. Wenn der Parser einen Ausdruck wie z.B.

(num + num) * num

untersucht, so beginnt er mit der geöffneten Klammer, das nächste Token ist dann die Zahl num, dann kommt der add-Operator und so weiter. Das jeweils gerade untersuchte Token wird als lookahead bezeichnet.

First

Als nächstes müssen wir den Begriff First(X) klären. First(X) ist eine Menge, und zwar die Menge aller Terminalsymbole, mit denen ein aus X hergeleiteter Ausdruck beginnen kann.

Untersuchen wir einmal, was man aus dem Nichtterminal Term alles herleiten kann. Hier noch einmal die Grammatik:

P1: Expr --> Term 
P2: Expr --> Expr + Term [ print "add"]
P3: Expr --> Expr - Term [ print "sub"]

P4: Term --> Fact 
P5: Term --> Term * Fact [ print "mul"]
P6: Term --> Term / Fact [ print "div"]

P7: Fact --> num [ print "push "+ token.zahlenAttribut]
P8: Fact --> id  [ print "push "+ token.stringAttribut]
P9: Fact --> (Expr)

Mit P4 erhalten wir Fact aus Term, das ist aber noch kein Terminalsymbol, also müssen wir weiter machen.

Mit P7 erhalten wir num aus Fact und mit P8 erzeugen wir id aus Fact. Diese beiden Terminale gehören also auf jeden Fall schon einmal zu First(Term).

Mit P9 erhalten wir (Expr) aus Fact, das am weitesten links stehende Symbol ist das Terminal (, also gehört auch dieses zu First(Term).

First(Term) = { num, id, ( }

Jetzt endlich können wir die zweite Regel zur Parserkonstruktion verstehen:

Existieren mehrere Produktionen P1, P2, … Pk mit der gleichen linken Seite, so wird folgendermaßen verfahren: Wenn das lookahead in der Menge First(P1) ist, wird P1 für die Rückwärtsableitung aufgerufen. Ist das lookahead in der Menge First(P2), so wird die für P2 zuständige Methode aufgerufen etc.

Unerwünschte Rekursion

Schaut man sich den Java-Quelltext der nach der Regel 1 erzeugten Methode expr einmal näher an:

public void expr()
{
   expr();
   match('+');
   term();
   print("add");
}

so sieht man, dass diese Methode eine direkte Rekursion enthält: expr ruft expr auf. Da weit und breit kein "if" vor diesem rekursiven Aufruf zu sehen ist, handelt es sich um eine unbedingte Rekursion: Die Rekursion wird auf jeden Fall ausgeführt.

Dies führt aber zu einer Endlosschleife: Wenn expr aufgerufen wird, wird innerhalb von expr als erstes expr aufgerufen. Innerhalb dieses expr-Aufrufs wird wieder als erstes expr aufgerufen und so weiter. Irgendwann ist der Arbeitsspeicher des Rechners erschöpft, und das Programm bricht mit einem Laufzeitfehler ab.

Wir sehen also, die obige Grammatik ist aus zweierlei Gründen überhaup tnicht für die Konstruktion eines Parsers geeignet, obwohl es sich um eine eindeutige Grammatik handelt.

Beseitigung der Rekursion

Kommen wir nun zur Beseitigung der unerwünschten Rekursion. Gut, dass es schlaue Leute auf der Welt gibt, die dicke Bücher über Compilerbau schreiben und denen man etwas über die Schultern schauen darf. In dem berühmten "Drachenbuch" (AHO, SETI, ULLMANN, Compilerbau Teil 1, Bonn 1988) habe ich folgende schöne Grammatik gefunden:

P1  Expr        ---> Term Moreterms
P2  Moreterms   ---> + Term [print "add"] Moreterms
P3  Moreterms   ---> - Term [print "sub"] Moreterms
P4  Moreterms   ---> nothing

P5  Term        ---> Factor Morefactors
P6  Morefactors ---> * Factor [print "mul"] Morefactors
P7  Morefactors ---> * Factor [print "div"] Morefactors
P8  Morefactors ---> nothing

P9  Factor      ---> id  [print "push" + token.stringAttribut]
P10 Factor      ---> num [print "push" + token.zahlenAttribut]
P11 Factor      ---> ( Expr )

Die Produktionen mit dem Symbol "nothing" auf der rechten Seite sind ganz praktisch; mit ihnen kann man nämlich überflüssige Grammatiksymbole verschwinden lassen.