Earley-Algorithmus

Der Earley-Algorithmus oder Earley-Parser ist in der Informatik ein Algorithmus, der entscheidet, ob ein Wort von einer kontextfreien Grammatik erzeugt werden kann. Er wurde 1970 von Jay Earley entwickelt. Er ähnelt dem Cocke-Younger-Kasami-Algorithmus und löst wie dieser das Wortproblem der kontextfreien Sprachen. Er verwendet die Methode der dynamischen Programmierung.

Verwendung

Eine Aufgabe eines Compilers oder Parsers ist es, zu überprüfen, ob der eingegebene Quelltext den Regeln der entsprechenden Grammatik folgt, also der Syntax der Programmiersprache entspricht. Dies entspricht dem Lösen des Wortproblems. Da die meisten Programmiersprachen kontextsensitiv sind, werden dabei bestimmte Bedingungen zunächst ignoriert. Dadurch kann man erreichen, dass nur das wesentlich einfachere (nicht NP-vollständige) Wortproblem der kontextfreien Sprachen gelöst werden muss. Die kontextsensitiven Nebenbedingungen, wie etwa die Vollständigkeit der Variablendeklarationen müssen dann mit einem anderen Algorithmus geprüft werden. So wird der erste Schritt der Syntaxprüfung auf das Wortproblem der kontextfreien Sprachen zurück geführt. Diese wird vom Earley-Algorithmus und auch vom CYK-Algorithmus mit $O(n^{3})$-Zeitaufwand erreicht, bei eindeutigen Grammatiken mit $O(n^{2})$ und in manchen speziellen Grammatiken mit $O(n)$. Beide sind optimal, um das Problem für eine allgemeine kontextfreie Sprache zu lösen. Der Earley Algorithmus hat jedoch den Vorteil, dass keine Umwandlung der Grammatik in Chomsky-Normalform nötig ist. Nachteil ist die Einschränkung auf Epsilon-freie Grammatiken. Epsilon-Regeln können jedoch immer durch Umformung der Grammatik eliminiert werden.

In der Praxis versucht man meist, den relativ hohen Rechenaufwand der beiden Algorithmen zu vermeiden oder zu reduzieren. Man optimiert dabei den Compiler oder Parser speziell an die verwendete Programmiersprache und kann so oft einen geringeren Berechnungsaufwand erreichen. Besonders große Verbesserungen können dabei erreicht werden, wenn man die Syntax der Programmiersprache so weit einschränkt, dass sie LR1- oder sogar LL1-Eigenschaften hat. Dies wird bei der Entwicklung neuerer Programmiersprachen berücksichtigt. Für solche Programmiersprachen exisiteren Algorithmen, die in der Praxis schneller sind und weniger Speicher benötigen als der Earley-Parser. Für generelle kontextfreie Grammatiken ist der Earley-Parser und verwandte Algorithmen dagegen anderen überlegen.

Algorithmus

Der Algorithmus benötigt als Eingabe eine kontextfreie Grammatik und ein Wort über demselben Alphabet. Er entscheidet dann, ob die Grammatik das Wort erzeugen kann. Dabei geht er nicht wie der CYK-Algorithmus rückwärts wieder zum Startsymbol der Grammatik, sondern versucht das Wort zeichenweise zu erzeugen. In jedem Berechnungsschritt versucht er also, ein Zeichen des Wortes weiter zu kommen, bis das ganze Wort erzeugt ist. In einem solchen Fall ist das Wort von der Grammatik erzeugbar. Falls das Wort nicht erzeugbar (also nicht in der Sprache enthalten) ist, bricht der Algorithmus ab, da er an einem Zeichen ankommt, das er nicht vorhersagen kann. Bei der Eingabe eines Wortes $x_{1}x_{2}\dots x_{\mathrm {n} }$ verwendet der Algorithmus die Zustandsmengen $Q_{0},\dots ,Q_{n}$. Ein Zustand (oder Earley-Zustand, engl. Earley item, auch dottet rule) des Algorithmus ist dabei eine Produktion, deren rechte Seite durch einen Teilungspunkt $\bullet$ zerlegt ist. Alle Zeichen vor diesem Punkt gelten als schon überprüft. Eine solcher Zustand $(A\rightarrow \ldots \bullet \ldots ,i)$ ist in einer Zustandsmenge $Q_{\mathrm {j} }$ enthalten und durch einen zusätzlichen Zähler $i$ gekennzeichnet. Dieser bestimmt, aus welcher Menge der Zustand ursprünglich stammt, damit der Algorithmus später mit Rekonstruktionschritten schnell einen Syntaxbaum erzeugen kann.

Am Anfang wird $(S'\rightarrow \bullet S,0)\in Q_{0}$ gesetzt. Dabei ist $S$ das Startsymbol der Grammatik. Der Algorithmus läuft nun Zeichen für Zeichen und wendet im $i$ ten Schritt immer die drei folgenden Regeln an, solange bis jeweils keine weiteren Zustände mehr angefügt werden können:

Voraussage (P) (engl. predictor)

Falls $(A\rightarrow \ldots \bullet B\ldots ,j)$ in $Q_{i}$ enthalten ist, füge für jede Regel $B\rightarrow \alpha$ der Grammatik den Zustand $(B\rightarrow \bullet \alpha ,i)$ zu $Q_{i}$ hinzu.

Überprüfung (S) (engl. scanner)

Falls $(A\rightarrow \ldots \bullet a\ldots ,j)\in Q_{i}$ und $a=x_{i+1}$, füge $(A\rightarrow \ldots a\bullet \ldots ,j)$ zu $Q_{i+1}$ hinzu.

Vervollständigung (C) (engl. completer)

Falls ein komplettierter Zustand $(A\rightarrow ...\bullet ,j)\in Q_{i}$ existiert, füge für alle Zustände $(B\rightarrow \ldots \bullet A\ldots ,k)\in Q_{j}$ einen Zustand $(B\rightarrow \ldots A\bullet \ldots ,k)$ zu $Q_{i}$ hinzu.

Man nennt die drei Schritte auch prädiktive Erweiterung, lexikalische Konsumption und Konstituentenvervollständigung. In der Definition bedeuten Kleinbuchstaben terminierte Symbole (auch lexikalische Kategoriensymbole, engl. terminals), Großbuchstaben nichtterminierte Symbole (auch komplexe syntaktische Kategoriensymbole, engl. non-terminals) und lateinische Buchstaben die gesamte rechte Seite einer Regel, bestehend aus verschiedenen Symbolen.

Genau dann, wenn am Ende $(S'\rightarrow S\bullet ,0)$ in der Zustandsmenge $Q_{\mathrm {n} }$ enthalten ist, kann die Grammatik das Wort erzeugen.

Im Anschluss müssen die einzelnen Zustände durch einen geeigneten rekursiven Suchalgorithmus (engl. walker) wieder miteinander verknüpft werden, um den Syntaxbaum zu erzeugen.

Beispiele

Beispiel 1: einfacher mathematischer Ausdruck

Die folgende die Grammatik (Anwendungsbeispiel aus )

$S'\rightarrow E$ $E\rightarrow E+T$ $E\rightarrow E-T$ $E\rightarrow T$

$T\rightarrow T*F$ $T\rightarrow T/F$ $T\rightarrow F$

$F\rightarrow n$ $F\rightarrow -F$ $F\rightarrow +F$ $F\rightarrow (S')$

beschreibt einfache mathematische Ausdrücke (mit $n$ als Platzhalter für Zahlen). Als Eingabe soll der Ausdruck n+n erkannt werden. Die nach Ablauf des Earley-Algorithmus im Speicher befindlichen Zustände sind in den Tabellen $Q_{0}$ bis $Q_{3}$

$Q_{0}$
$S'\rightarrow \bullet E$ $,\,0$ $E\rightarrow \bullet E+T$ $,\,0$ $E\rightarrow \bullet E-T$ $,\,0$ $E\rightarrow \bullet T$ $,\,0$ $T\rightarrow \bullet T*F$ $,\,0$ $T\rightarrow \bullet T/F$ $,\,0$ $T\rightarrow \bullet F$ $,\,0$ $F\rightarrow \bullet n$ $,\,0$ $F\rightarrow \bullet -F$ $,\,0$ $F\rightarrow \bullet +F$ $,\,0$ $F\rightarrow \bullet (S)$ $,\,0$

n

$Q_{1}$
$\color {Red}F\rightarrow n\bullet$ $\color {Red},\,0$ $\color {Red}T\rightarrow F\bullet$ $\color {Red},\,0$ $\color {Red}E\rightarrow T\bullet$ $\color {Red},\,0$ $T\rightarrow T\bullet *F$ $,\,0$ $T\rightarrow T\bullet /F$ $,\,0$ $S'\rightarrow E\bullet$ $,\,0$ $E\rightarrow E\bullet +T$ $,\,0$ $E\rightarrow E\bullet -T$ $,\,0$

+

$Q_{2}$
$E\rightarrow E+\bullet T$ $,\,0$ $T\rightarrow \bullet T*F$ $,\,2$ $T\rightarrow \bullet T/F$ $,\,2$ $T\rightarrow \bullet F$ $,\,2$ $T\rightarrow \bullet n$ $,\,2$ $T\rightarrow \bullet -F$ $,\,2$ $T\rightarrow \bullet +F$ $,\,2$ $T\rightarrow \bullet (S')$ $,\,2$

n

$Q_{3}$
$\color {Red}F\rightarrow n\bullet$ $\color {Red},\,2$ $\color {Red}T\rightarrow F\bullet$ $\color {Red},\,2$ $\color {Red}E\rightarrow E+T\bullet$ $\color {Red},\,0$ $T\rightarrow T\bullet *F$ $,\,2$ $T\rightarrow T\bullet /F$ $,\,2$ $\color {Red}0,S'\rightarrow E\bullet$ $\color {Red},\,0$

gezeigt. Sie wurden durch mehrfache Anwendung der drei Schritte Voraussage, Überprüfung und Vervollständigung erzeugt. Rot markiert sind die komplettierten Zustände, deren Punkt das Ende der Regel erreicht hat. Bis zu dieser Stelle entspricht also der Ausdruck einer gegebenen Regel. Jedoch nur wenn, wie in diesem Beispiel, in der letzten Zustandsmenge $Q_{3}$ der komplettierte Zustand der Startregel enthalten ist, wurde der Ausdruck erfolgreich erkannt und wird folglich durch die Grammatik beschrieben. Durch eine rekursive Suche kann nun, ausgehend von diesem letzten Zustand, der Pfad zurück zum Anfang zurückverfolgt und ein Syntaxbaum erzeugt werden.

Beispiel 2: Dyck-Sprache

Die Dyck-Sprache $D_{1}$ der korrekt geklammerten Ausdrücke mit nur einer Art Klammern wird von dieser kontextfreien Grammatik erzeugt:

$S\rightarrow ()\mid ()()\mid (A)\mid (A)(A)$

$A\rightarrow \varepsilon \mid (A)\mid (A)(A)$

Bei Eingabe des Wortes ()(()) läuft der Algorithmus folgendermaßen ab:

• In $Q_{0}$:

• • $(S'\rightarrow \bullet S,0)$
  • Die Voraussagen für $S$:
  • $(S\rightarrow \bullet (),0)$(P)
  • $(S\rightarrow \bullet ()(),0)$(P)
  • $(S\rightarrow \bullet (A),0)$(P)
  • $(S\rightarrow \bullet (A)(A),0)$(P)

• In $Q_{1}$:
  • Zuerst alle Überprüfungen
  • $(S\rightarrow (\bullet ),0)$(S)
  • $(S\rightarrow (\bullet )(),0)$(S)
  • $(S\rightarrow (\bullet A),0)$(S)
  • $(S\rightarrow (\bullet A)(A),0)$(S)
  • Jetzt ist es möglich $A$ vorauszusagen. Dieses A kann dann ab dem zweiten Zeichen eingesetzt werden. Es kommt also sozusagen aus $Q_{1}$, daher wird der Zähler auf 1 gesetzt.
  • $(A\rightarrow \bullet \varepsilon ,1)$(P)
  • $(A\rightarrow \bullet (A),1)$(P)
  • $(A\rightarrow \bullet (A)(A),1)$(P)
  • Wegen der Epsilonproduktion ist das Nichtterminal $A$ hier fertig produziert. Es ist also schon ein Vervollständigungsschritt möglich:
  • $(S\rightarrow (\bullet ),0)$(C)
  • $(S\rightarrow (\bullet )(A),0)$(C)

Weitere Schritte sind nicht möglich,

• Also geht es weiter in $Q_{2}$:
  • wieder zuerst die Vorhersagen, das aktuelle Zeichen ist ')':
  • $(S\rightarrow ()\bullet ,0)$(S)
  • $(S\rightarrow ()\bullet (),0)$(S)
  • $(S\rightarrow ()\bullet ,0)$(S)
  • $(S\rightarrow ()\bullet (A),0)$(S)
  • alle anderen Regeln lassen sich hier nicht anwenden.
• In $Q_{3}$:
  • Nur bei einem Zustand lässt sich das richtige Zeichen einlesen:
  • $(S\rightarrow ()(\bullet A),0)$(S)
  • Jetzt können neue Vorhersagen für $A$ gemacht werden:
  • $(A\rightarrow \bullet \varepsilon ,3)$(P)
  • $(A\rightarrow \bullet (A),3)$(P)
  • $(A\rightarrow \bullet (A)(A),3)$(P)
  • $(S\rightarrow ()(\bullet ),0)$(C)
• In $Q_{4}$:
  • $(A\rightarrow (\bullet A),3)$(S)
  • $(A\rightarrow (\bullet A)(A),3)$(S)
  • $A$ wird wieder vorhergesagt:
  • $(A\rightarrow \bullet \varepsilon ,4)$(P)
  • $(A\rightarrow \bullet (A),4)$(P)
  • $(A\rightarrow \bullet (A)(A),4)$(P)
  • $(A\rightarrow (\bullet ),3)$(C)
  • $(A\rightarrow (\bullet )(A),3)$(C)
• In $Q_{5}$:
  • $(A\rightarrow ()\bullet ,3)$(S)
  • $(A\rightarrow ()\bullet (A),3)$(S)
  • Da das obere $A$ fertig eingelesen ist, dann jetzt aus $Q_{3}$ vervollständigt werden
  • $(S\rightarrow ()(\bullet ),0)$(C)
• In $Q_{6}$:
  • $(S\rightarrow ()()\bullet ,0)$(S)
  • Das Startsymbol wurde also komplett gelesen. $S'$ kann also vervollständigt werden.
  • $(S'\rightarrow S\bullet ,0)$(C)

Damit ist das Wort in der Dyck-Sprache enthalten.

Literatur

• Jay Earley: An efficient context-free parsing algorithm. In: Communications of the Association for Computing Machinery. Band 13, Nr. 2, 1970, S. 94–102 (PDF, 902 KB). 
• J. Aycock, R. N. Horspool: Practical Earley Parsing. In: The Computer Journal. Band 45, Nr. 6, 2002, S. 620–630 (PDF, 162 kB). 
• Grune, Dick; Jacobs, Ceriel J. H.: Parsing Techniques: A Practical Guide. 1. Auflage. Ellis Horwood, New York 1990, ISBN 0-13-651431-6, S. 149–163 (PDF, 1,9 MB). 

Weblinks

• Vorlesungsskript der Universität Tübingen mit Beispielen und Korrektheitsbeweis (pdf) (845 kB)
• Earley-Algorithmus (WikiLingua, freie Wissensdatenbank für Computerlinguistik)

Einzelnachweise