Folge 31 - Parserkonstruktion

1. Regel 1

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.

Betrachten wir einmal die Produktion 2 der Grammatik

  1. Expr --> Term
  2. Expr --> Expr + Term [ print "add"]
  3. Expr --> Expr - Term [ print "sub"]
  4. Term --> Fact
  5. Term --> Term * Fact [ print "mul"]
  6. Term --> Term / Fact [ print "div"]
  7. Fact --> num [ print "push "+ token.zahlenAttribut]
  8. Fact --> id [ print "push "+ token.stringAttribut]
  9. Fact --> (Expr)

Eine entsprechende Java-Umsetzung könnte so aussehen:

public void expr()
{
   expr();
   match();
   term();
   print("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();
   print("mul");
}

Kommen wir nun zur Regel 2.

2. 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:

  1. Expr --> Term Moreterms
  2. Moreterms --> + Term [ print "add"] Moreterms
  3. Moreterms --> - Term [ print "sub"] Moreterms
  4. Moreterms --> nothing

  5. Term --> Factor Morefactors
  6. Morefactors --> * Factor [ print "mul"] Morefactors
  7. Morefactors --> / Factor [ print "div"] Morefactors
  8. Morefactors --> nothing

  9. Factor --> id [ print "push "+ token.stringAttribut]
  10. Factor --> num [ print "push "+ token.zahlenAttribut]
  11. Factor --> ( Expr )

Erstmal wenden wir die Produktion 4 an und verwandeln Term in Fact. Fact ist aber noch kein Terminal, also machen wir weiter und verwandeln Fact mit Produktion 7 in num. Ein aus Term hergeleiteter Ausdruck kann also mit einer Zahl anfangen, num gehört somit zur Menge First(Term). Mit Produktion 8 können wir aus Fact auch einen Bezeichner herleiten. Somit gehört auch id zur Menge First(Term). Schließlich können wir mit Produktion 9 Fact in (Expr) umwandeln. Dieser Ausdruck fängt mit einer geöffneten Klammer an. Somit gehört auch die geöffnete Klammer zur Menge First(Term). Fassen wir zusammen:

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

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

Regel 2

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 aufgerufen. Ist das lookahead in der Menge First(P2), so wird die für P2 zuständige Methode aufgerufen etc.

Anwendung der Regel 2

Zur Anwendung kommt die Regel 2 z.B. bei den Produktionen 1 bis 3 der obigen Grammatik, alle drei Produktionen haben Expr auf der linken Seite stehen. Da man Term direkt aus Expr herleiten kann (Produktion 1), gilt: First(Expr) = First(Term). Die beiden Mengen sind also gleich. Auch wenn man die Produktion 2 mit der Produktion 3 vergleicht, kommt man zu dem Schluss, dass die Mengen First(P1), First(P2) und First(P3) identisch sind. Die Regel 2 zur Parserkonstruktion kann also gar nicht auf diese Grammatik angewandt werden. So eindeutig, wie die Grammatik am Anfang auch aussah, ist sie nicht geeignet zur Konstruktion eines Parsers. Wenn der Parser nämlich das lookahead num sieht, so könnte er sowohl die Produktion 1 wie auch die Produktion 2 oder 3 zur Rückwärtsableitung anwenden.

Unerwünschte Rekursion

Schaut man sich den Java-Quelltext der nach der Regel 1 erzeugten Methode für 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 überhauptnicht für die Konstruktion eines Parsers geeignet, obwohl es sich um eine eindeutige Grammatik handelt.

An dieser Stelle Herzlichen Dank an die folgenden Herren:

Christian Schebek
Felix Sterzelmaier und
Sven Neubauer

die mir sehr bei der Beseitigung eines lästigen Fehlers in der Grammatik geholfen haben.

Vielen Dank!

3. Beseitigung der Rekursion

Eine neue Grammatik

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:

  1. Expr --> Term Moreterms
  2. Moreterms --> + Term [ print "add"] Moreterms
  3. Moreterms --> - Term [ print "sub"] Moreterms
  4. Moreterms --> nothing

  5. Term --> Factor Morefactors
  6. Morefactors --> * Factor [ print "mul"] Morefactors
  7. Morefactors --> / Factor [ print "div"] Morefactors
  8. Morefactors --> nothing

  9. Factor --> id [ print "push "+ token.stringAttribut]
  10. Factor --> num [ print "push "+ token.zahlenAttribut]
  11. 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.

Ein Parser in Pascal

Den Compilerbaukurs führe ich seit über 10 Jahren erfolgreich im Informatikunterricht der Stufe 12/2 durch. Wegen der neuen Informatikrichtlinien des Landes NRW sowie des gleichzeitigen Umstiegs von der Programmiersprache Pascal/Delphi auf Java/BlueJ hat sich die Behandlung des Themas Compilerbau auf die Jahrgangsstufe 13/1 verlagert. Ich möchte Ihnen jetzt den kompletten Quelltext der Pascal-Unit uParser zeigen und diesen Quelltext mit Ihnen besprechen. Eine Umsetzung in Java ist in diesem neuen Kurs nicht geplant. Begabte Schüler und Schülerinnen können sich ja trotzdem an einer solchen Umsetzung versuchen; erwarten Sie aber nicht übermäßig viele Punkte dafür. Damit diese Webseite nicht übermäßig lang wird, habe ich die Besprechung des Quelltextes auf eine Extraseite ausgelagert.

Quelltext der Pascal-Unit uParser als Textdatei

Ausführliche Besprechung der Unit uParser

Übung 31.1 (3 Punkte, auch als Hausaufgabe geeignet)

Beweisen Sie, dass der Ausruck (id + num) * (num + id) zur Sprache L(G) der neuen Grammatik (siehe weiter oben) gehört!

Übung 31.2 (8 Punkte)

Besorgen Sie sich die Unit uParser sowie die Unit uLexer aus dem alten Compilerbau-Kurs und versuchen Sie das Ganze unter Java zum Laufen zu bringen.

Wichtig:

Bitte nicht während der Informatikstunden diese Übung bearbeiten, so viel Zeit haben wir nicht. Wer will, kann sich in den Freistunden oder zu Hause an den Rechner setzen. Ebenfalls wichtig: Erwarten Sie bei dieser Umsetzung keine Hilfe von dem betreuenden Lehrer; dafür ist das Vorhaben etwas zu komplex.

Übung 31.2 - Alternativaufgabe (6 Punkte)

Studieren Sie die ausführliche Besprechung der Unit uParser und erstellen Sie eine Präsentation zum Thema, in der das rekursive Arbeiten des Parsers an einem selbstgewählten Beispiel deutlich gemacht wird.

Ende des Kurses

Haben Sie es bereits gemerkt? Wir sind am Ende des Compilerbau-Kurses angekommen. Eine letzte Zusatzaufgabe für alle Leute, die noch Punkte brauchen:

Übung 31.3 (8 Punkte)

Erstellen Sie eine schöne Präsentationen, in der alles, was Sie in den Folgen 21 bis 31 gelernt haben, anschaulich dargestellt wird.

Vorschlag für Ihre Präsentation: Vom Quelltext zum Maschinencode

Zuerst schildern Sie, wie man aus einem Java- oder Pascal-Quelltext (möglichst kurz) mit Hilfe eines Lexers und eines rekursiven Parsers einen Stackmaschinencode erzeugt, und dann erläutern Sie Schritt für Schritt, wie dieser smc.Stackmaschinencode von einem Stackinterpreter abgearbeitet wird.

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 1. August 2006.






IMPRESSUM