Rekonstruktion von Parsebäumen in Earley Parsern

Rekonstruktion von Parsebäumen in Earley Parsern

Matthias Braun matthias.braun@kit.edu

Anmerkung: Da die Probleme im folgenden nicht in der Vorlesung vorgestellt wurden sind Sie selbstverständlich nicht Prüfungsrelevant.

1. Einleitung

Bei der Vorstellung des Earley Parsing Algorithmus wird üblicherweise ausführlich über die Schritte zur Berechnung der Earleymengen geredet (Completion, Scanning, Prediction). Hat man die Earleymengen berechnet so hat man das Akzeptanzproblem, also die Frage ob eine Eingabe zu einer gegebenen Sprache gehört, gelöst.

Die natürliche nächste Frage, wie man einen Syntaxbaum erzeugt wird meist nicht mehr im Detail behandelt. Dieser Text nimmt deshalb an, dass die Berechnung der Earleymengen bekannt und verstanden ist und beschäftigt sich genau mit der Rekonstruktion der Syntaxbäumen aus Earleymengen.

2. Ursprünglicher Ansatz

In seinen Arbeiten schreibt Earley, dass man sich zur Rekonstruktion des Syntaxbaums bei einem erfolgten Completion Schritt einen Zeiger zum Item merkt dass die Completion erlaubt hat. Es ergibt sich also für jedes Nicht-Terminal auf der rechten Seite eines Items eine Liste von Itemreferenzen die für dieses eingesetzt werden können.

Eine Rekonstruktion beginnt dann also von Items in der Menge zum EOF-Zeichen die mit dem Startsymbol beginnen. Die rechte Seite der Produktion ergibt Kinder im Syntaxbaum. Nichtterminale auf der Rechten Seite enthalten Referenzen zu Regeln die man dann als weitere Kinder im Baum darstellt. Falls die Eingabe+Grammatik Mehrdeutig war, findet man bei manchen Nichtterminalen mehrere Referenzen.

3. Probleme

Die Earleymengen enthalten mit den zusätzlichen Zeigern also alle möglichen Syntaxbäume in einer faktorisierten Form. Was in der ursprünglichen und in den meisten Nachfolgenden Arbeiten leider oft übersehen wird, ist dass diese faktorisierte Form auch unmögliche Parsebäume enthält. Nimmt man das Beispiel von den Vorlesungsfolien:

Grammatik:
S' -> S
S  -> S 'und' S | S 'oder' S
S  -> 'blau' | 'gestreift' | 'glatt' | 'teuer'
Eingabe:
blau und gestreift oder glatt und teuer

ergibt folgenden faktorisierten Syntaxbaum (Varianten sind gestrichelt gezeichnet):

(Die dazugehörigen Earleysets)

Beim Aufzählen von konkreten Syntaxbäumen muss man also noch einmal überprüfen ob der erzeugte Baum tatsächlich der Eingabe entspricht. Dies ergibt dann 5 echte Syntaxbäume (die weiteren 5 Varianten entsprechen nicht der Eingabe):

Eine etwas performantere dafür aber aufwändigere Variante des Tests findet sich im Buch Parsing Techniques. A Practical Guide; ISBN 0-13-651431-6, Kapitel 7.2.1.2, S. 153–154 beschrieben.

4. Implementierung

Eine Implementierung der beschriebenen Verfahren ist auf den Webseiten der Übungs verfügbar: http://pp.info.uni-karlsruhe.de/lehre/SS2012/compiler/uebung/earley.zip