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ückgeführt. Diese wird vom Earley-Algorithmus und auch vom CYK-Algorithmus mit O(n³)-Zeitaufwand erreicht, bei eindeutigen Grammatiken mit O(n²) 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 existieren 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_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_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 keine weiteren Zustände mehr angefügt werden können:

Voraussage (P) (engl. predictor)

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

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

Falls $(A\rightarrow \ldots \bullet a \ldots , j) \in Q_i$ und a = xi + 1, füge $(A\rightarrow \ldots a\bullet \ldots , j)$ zu Qi + 1 hinzu.

Vervollständigung (C) (engl. completer)

Falls ein finaler 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 Qi 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 griechische 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_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.

Beispiel: einfacher mathematischer Ausdruck

Die folgende Grammatik (Anwendungsbeispiel aus ^[1])

$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. Die Symbole stehen hier für start (S), expression (E), term (T), factor (F) und number (n, Platzhalter für Zahlen). Als Beispiel soll der Ausdruck n + n erkannt werden. Die nach Ablauf des Earley-Algorithmus im Speicher befindlichen Zustände sind in den Tabellen Q₀ bis Q₃

Q0

$S' \rightarrow \bullet E$ $,\,0$ P: $E \rightarrow \bullet E+T$ $,\,0$ P: $E \rightarrow \bullet E-T$ $,\,0$ P: $E \rightarrow \bullet T$ $,\,0$ P: $T \rightarrow \bullet T*F$ $,\,0$ P: $T \rightarrow \bullet T/F$ $,\,0$ P: $T \rightarrow \bullet F$ $,\,0$ P: $F \rightarrow \bullet n$ $,\,0$ P: $F \rightarrow \bullet -F$ $,\,0$ P: $F \rightarrow \bullet +F$ $,\,0$ P: $F \rightarrow \bullet (E)$ $,\,0$

n

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

+

Q2
S: $E \rightarrow E+\bullet T$ $,\,0$ P: $T \rightarrow \bullet T*F$ $,\,2$ P: $T \rightarrow \bullet T/F$ $,\,2$ P: $T \rightarrow \bullet F$ $,\,2$ P: $F \rightarrow \bullet n$ $,\,2$ P: $F \rightarrow \bullet -F$ $,\,2$ P: $F \rightarrow \bullet +F$ $,\,2$ P: $F \rightarrow \bullet (E)$ $,\,2$

n

Q3
S: $\color{Red}F \rightarrow n\bullet$ $\color{Red},\,2$ C: $\color{Red}T \rightarrow F\bullet$ $\color{Red},\,2$ C: $\color{Red}E \rightarrow E+T\bullet$ $\color{Red},\,0$ C: $T \rightarrow T\bullet *F$ $,\,2$ C: $T \rightarrow T\bullet /F$ $,\,2$ C: $\color{Red}S' \rightarrow E\bullet$ $\color{Red},\,0$ C: $E \rightarrow E\bullet+T$ $,\,0$ C: $E \rightarrow E\bullet-T$ $,\,0$

gezeigt. Sie wurden durch mehrfache Anwendung der drei Schritte Voraussage (P), Überprüfung (S) und Vervollständigung (C) erzeugt, wie gekennzeichnet. Rot markiert sind die finalen 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₃ der finale Zustand der Startregel enthalten ist, wurde der gesamte Ausdruck erfolgreich erkannt und wird folglich durch die Grammatik erzeugt. Durch eine rekursive Suche kann nun, ausgehend von diesem letzten Zustand, der Pfad zurück zum Anfang zurückverfolgt und ein Syntaxbaum erzeugt werden.

Als gesuchter Syntaxbaum zu n + n ergibt sich:

S' →	E
	E →	E +	T
		↓	T →	F
		↓		F → n
		E →	T
			T →	F
				F → n

Die Konstruktion des Syntaxbaumes ergibt sich allein aus den rot markierten finalen Zuständen. Die nicht-finalen Zustände sind nur während der Erzeugung der finalen Zustände notwendig und können vor der rekursiven Konstruktion des Baumes gelöscht werden.

Literatur

• Jay Earley: An efficient context-free parsing algorithm. In: Communications of the Association for Computing Machinery. 13, Nr. 2, 1970, S. 94–102 (PDF, 902 KB).
• John Aycock, R. Nigel Horspool: Practical Earley Parsing. In: The Computer Journal. 45, Nr. 6, 2002, S. 620–630 (PDF, 162 kB).
• Dick Grune, Ceriel J. H. Jacobs: 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

1. ↑ J. Aycock, N. Horspool: Directly-Executable Earley Parsing. In: Lecture Notes in Computer Science. 2027, 2001, S. 229–243, doi:10.1007/3-540-45306-7 (PDF).