imported>Invisigoth67: typo

2024-09-20T14:37:12Z

typo

Neue Seite

Der '''Earley-Algorithmus''' oder '''Earley-Parser''' ist in der [[Informatik]] ein [[Algorithmus]], der [[Entscheidbar|entscheidet]], ob ein Wort von einer [[Kontextfreie Grammatik|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 (Berechenbarkeitstheorie)|Wortproblem]] der [[Kontextfreie Sprache|kontextfreien Sprachen]]. Er verwendet die Methode der [[Dynamische Programmierung|dynamischen Programmierung]].

== Verwendung ==
Eine Aufgabe eines [[Compiler]]s oder [[Parser]]s 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 [[Kontextsensitive Sprache|kontextsensitiv]] sind, werden dabei bestimmte Bedingungen zunächst ignoriert. Dadurch kann man erreichen, dass nur das wesentlich einfachere (nicht [[NP-Vollständigkeit|NP-vollständige]]) Wortproblem der kontextfreien Sprachen gelöst werden muss. Die [[Kontextsensitive Nebenbedingung|kontextsensitiven Nebenbedingungen]], wie etwa die Vollständigkeit der [[Variablendeklaration]]en, 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 [[Landau-Symbole|<math>O(n^3)</math>]]-[[Komplexitätstheorie|Zeitaufwand]] erreicht, bei eindeutigen Grammatiken mit <math>O(n^2)</math> und in manchen speziellen Grammatiken mit <math>O(n)</math>. 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 [[Leeres Wort|Epsilon]]-freie Grammatiken. Epsilon-Regeln können jedoch immer durch Umformung der Grammatik eliminiert werden.

In der [[Praktische Informatik|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 [[LR(k)-Grammatik|LR1]]- oder sogar [[LL(k)-Grammatik|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 sind der Earley-Parser und verwandte Algorithmen dagegen anderen überlegen.

== Algorithmus ==
Der Algorithmus benötigt als [[Eingabe (Computer)|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 <math>x_1 x_2 \dots x_n</math> verwendet der Algorithmus die Zustandsmengen <math>Q_0, \dots, Q_n</math>. Ein Zustand (oder ''Earley-Zustand'', engl. {{lang|en|Earley item}}, auch {{lang|en|dottet rule}}) des Algorithmus ist dabei eine [[Produktionsregel|Produktion]], deren rechte Seite durch einen Teilungspunkt <math>\bullet</math> zerlegt ist. Alle Zeichen vor diesem Punkt gelten als schon überprüft. Ein solcher Zustand <math>(A \rightarrow \ldots \bullet \ldots , i)</math> ist in einer Zustandsmenge <math>Q_j</math> enthalten und durch einen zusätzlichen Zähler <math>i</math> 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 <math>(S'\rightarrow\bullet S,0) \in Q_0</math> gesetzt. Dabei ist <math>S</math> das Startsymbol der Grammatik. Der Algorithmus läuft nun Zeichen für Zeichen und wendet im <math>i</math> ten Schritt immer die drei folgenden Regeln an, solange bis keine weiteren Zustände mehr angefügt werden können. Dabei ist zu beachten, dass Änderungen der Zustandsmenge auch vorherige Regeln erneut zur Anwendung bringen können. Zum Beispiel muss auf Zustände, die durch den completer hinzukommen, wieder der predictor aufgerufen werden.

{| class="wikitable"
|style="background:#CAE1FF; width:10em"| Voraussage (P) (engl. {{lang|en|predictor}})
|style="width:50em"| Falls <math>(A\rightarrow \ldots \bullet B \ldots , j)</math> in <math>Q_i</math> enthalten ist, füge für jede Regel <math>B\rightarrow \alpha</math> der Grammatik den Zustand <math>(B\rightarrow \bullet\alpha, i)</math> zu <math>Q_i</math> hinzu.
|}

{| class="wikitable"
|style="background:#CAE1FF; width:10em" | Überprüfung (S) (engl. {{lang|en|scanner}})
|style="width:50em"| Falls <math>(A\rightarrow \ldots \bullet a \ldots , j) \in Q_i</math> und <math>a=x_{i+1}</math>, füge <math>(A\rightarrow \ldots a\bullet \ldots , j)</math> zu <math>Q_{i+1}</math> hinzu.
|}

{| class="wikitable"
|style="background:#CAE1FF; width:10em"| Vervollständigung (C) (engl. {{lang|en|completer}})
|style="width:50em"| Falls ein finaler Zustand <math>(A\rightarrow ...\bullet ,j) \in Q_i</math> existiert, füge für alle Zustände <math>(B\rightarrow \ldots \bullet A \ldots , k) \in Q_j</math> einen Zustand <math>(B\rightarrow \ldots A\bullet \ldots , k)</math> zu <math>Q_i</math> 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. {{lang|en|terminals}}), Großbuchstaben ''nichtterminierte Symbole'' (auch ''komplexe syntaktische Kategoriensymbole'', engl. {{lang|en|non-terminals}}) und griechische Buchstaben die gesamte rechte Seite einer Regel, bestehend aus verschiedenen Symbolen.

Genau dann, wenn am Ende <math>(S'\rightarrow S\bullet , 0)</math> in der Zustandsmenge <math>Q_n</math> enthalten ist, kann die Grammatik das Wort erzeugen.

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

=== Beispiel: einfacher mathematischer Ausdruck ===
Die folgende Grammatik (Anwendungsbeispiel aus <ref>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]] ([http://www.rsdn.ru/File/73/deep-2.pdf rsdn.ru] PDF).</ref>)
{|
|width="150"|
{|
|<math>S' \rightarrow E</math>
|-
|<math>E \rightarrow E+T</math>
|-
|<math>E \rightarrow E-T</math>
|-
|<math>E \rightarrow T</math>
|}
|width="150"|
{|
|<math>T \rightarrow T*F</math>
|-
|<math>T \rightarrow T/F</math>
|-
|<math>T \rightarrow F</math>
|}
|width="150"|
{|
|<math>F \rightarrow n</math>
|-
|<math>F \rightarrow -F</math>
|-
|<math>F \rightarrow +F</math>
|-
|<math>F \rightarrow (E)</math>
|}
|}
beschreibt einfache mathematische Ausdrücke. Die Symbole stehen hier für ''start'' (<math>S</math>), ''expression'' (<math>E</math>), ''term'' (<math>T</math>), ''factor'' (<math>F</math>) und ''number'' (<math>n</math>, Platzhalter für Zahlen. Hier könnten weitere Regeln für den genauen Aufbau von Zahlen eingefügt werden). Als Beispiel soll der Ausdruck <math>n+n</math> erkannt werden. Die nach Ablauf des Earley-Algorithmus im Speicher befindlichen Zustände sind in den Tabellen <math>Q_0</math> bis <math>Q_3</math>

<div style="float:left; margin-right:1em;">
{| class="hintergrundfarbe1 rahmenfarbe1" cellpadding="4" rules="all" style="border:1px solid #999999; border-collapse:collapse; margin:1em 0;"
|+ n
! colspan="2" style="background:#EEEEEE"| <math>Q_0</math>
|-
|
{|
|style="background:#CAE1FF"|
|
|<math>S' \rightarrow \bullet E </math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>E \rightarrow \bullet E+T</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>E \rightarrow \bullet E-T</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>E \rightarrow \bullet T</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>T \rightarrow \bullet T*F</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>T \rightarrow \bullet T/F</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>T \rightarrow \bullet F</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>F \rightarrow \bullet n</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>F \rightarrow \bullet -F</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>F \rightarrow \bullet +F</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>F \rightarrow \bullet (E)</math>
|<math>,\,0</math>
|}
|}
</div>
<div style="float:left; margin-right:1em;">
{| class="hintergrundfarbe1 rahmenfarbe1" cellpadding="4" rules="all" style="border:1px solid #999999; border-collapse:collapse; margin:1em 0;"
|+ +
! colspan="2" style="background:#EEEEEE"| <math>Q_1</math>
|-
|
{|
|style="background:#CAE1FF"|S:
|
|<math>\color{Red}F \rightarrow n\bullet</math>
|<math>\color{Red},\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>\color{Red}T \rightarrow F\bullet</math>
|<math>\color{Red},\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>\color{Red}E \rightarrow T\bullet</math>
|<math>\color{Red},\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>T \rightarrow T\bullet *F</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>T \rightarrow T\bullet /F</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>\color{Red}S' \rightarrow E\bullet</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>E \rightarrow E\bullet +T</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>E \rightarrow E\bullet -T</math>
|<math>,\,0</math>
|}
|}
</div>
<div style="float:left; margin-right:1em;">
{| class="hintergrundfarbe1 rahmenfarbe1" cellpadding="4" rules="all" style="border:1px solid #999999; border-collapse:collapse; margin:1em 0;"
|+ n
! colspan="2" style="background:#EEEEEE"| <math>Q_2</math>
|-
|
{|
|style="background:#CAE1FF"|S:
|
|<math>E \rightarrow E+\bullet T</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>T \rightarrow \bullet T*F</math>
|<math>,\,2</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>T \rightarrow \bullet T/F</math>
|<math>,\,2</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>T \rightarrow \bullet F</math>
|<math>,\,2</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>F \rightarrow \bullet n</math>
|<math>,\,2</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>F \rightarrow \bullet -F</math>
|<math>,\,2</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>F \rightarrow \bullet +F</math>
|<math>,\,2</math>
|-
|style="background:#CAE1FF"|P:
|
|<math>F \rightarrow \bullet (E)</math>
|<math>,\,2</math>
|}
|}
</div>
<div style="float:left; margin-right:1em;">
{| class="hintergrundfarbe1 rahmenfarbe1" cellpadding="4" rules="all" style="border:1px solid #999999; border-collapse:collapse; margin:1em 0;"
|+  
! colspan="2" style="background:#EEEEEE"| <math>Q_3</math>
|-
|
{|
|style="background:#CAE1FF"|S:
|
|<math>\color{Red}F \rightarrow n\bullet</math>
|<math>\color{Red},\,2</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>\color{Red}T \rightarrow F\bullet</math>
|<math>\color{Red},\,2</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>\color{Red}E \rightarrow E+T\bullet</math>
|<math>\color{Red},\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>T \rightarrow T\bullet *F</math>
|<math>,\,2</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>T \rightarrow T\bullet /F</math>
|<math>,\,2</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>\color{Red}S' \rightarrow E\bullet</math>
|<math>\color{Red},\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>E \rightarrow E\bullet+T</math>
|<math>,\,0</math>
|-
|style="background:#CAE1FF"|C:
|
|<math>E \rightarrow E\bullet-T</math>
|<math>,\,0</math>
|}
|}
</div>

<div style="clear:both;"></div>

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 <math>Q_3</math> 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 <math>n+n</math> ergibt sich:

{|
|-
|<math>S'</math> →
|<math>E</math>
|-
|
|<math>E</math> →
|<math>E</math> +
|<math>T</math>
|-
|
|
|↓
|<math>T</math> →
|<math>F</math>
|-
|
|
|↓
|
|<math>F</math> → <math>n</math>
|-
|
|
|
<math>E</math> →
|<math>T</math>
|-
|
|
|
|<math>T</math> →
|<math>F</math>
|-
|
|
|
|
|<math>F</math> → <math>n</math>
|}

== Konstruktion des Syntaxbaums ==

Für die Berechnung des Syntax-Baumes schlug J. Earley in seiner Originalarbeit 1970 eine Rückverfolgung der Zustände vor, indem jeder Zustand einen Zeiger auf den Zustand speichert, der diesen erzeugt hat. Tomita<ref>Masaru Tomita, ''Efficient parsing for natural language'', Kluwer Academic Publishers, Boston, p. 201, 1986.</ref> zeigte 1986, dass dieser Ansatz bei manchen mehrdeutigen Grammatiken zu falschen Syntaxbäumen führt. Um Syntaxbäume für generelle kontextfreie Grammatiken zu berechnen, muss eine rekursive Suche durchgeführt werden.

Dazu wird bei der finalen Startregel begonnen, die sich in der letzten Zustandsmenge befindet. Mit einer rekursiven Suche werden die Zustandsmengen und der Eingabe-String rückwärts durchlaufen. Dies kann wiederum mit einer Art Rückwärts-Scanner, Rückwärts-Predictor und Rückwärts-Completer realisiert werden, solange bis die anfängliche Startregel reproduziert wurde. Der Pfad zurück zum Anfang gibt den gesuchten Syntaxbaum wieder. Bei mehrdeutigen Situationen müssen rekursiv alle Möglichkeiten durchlaufen werden. Wenn bei einer mehrdeutigen Grammatik mehrere korrekte Syntaxbäume berechnet werden sollen, wird der gefundene Zustand gespeichert und die Rekursion solange fortgesetzt, bis in allen Rekursionsebenen alle Mehrdeutigkeiten abgearbeitet wurden.

Im Folgenden wird ein Algorithmus beschrieben, der nur die finalen Zustände und den Eingabe-String für die Rekursion benötigt. Nichtterminierte Zustände können vorher gelöscht werden. Es handelt sich um eine Modifikation des im Lehrbuch von D. Grune<ref>{{Literatur |Autor=Dick Grune, Ceriel J. H. Jacobs |Titel=Parsing Techniques. A Practical Guide |Auflage=1. |Verlag=Ellis Horwood |Ort=New York |Datum=1990 |ISBN=0-13-651431-6 |Kapitel=Kapitel 7.2.1.2 |Seiten=153–154 |Online=[ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf ftp.cs.vu.nl] |Format=PDF |KBytes=1900}}</ref> beschriebenen Algorithmus, der den Eingabe-String bei der Rekursion nicht benötigt, stattdessen auch alle nichtterminierten Zustände. Beide Algorithmen sollten prinzipiell äquivalent sein.

[[Datei:earleytree.svg]]

In der Abbildung entspricht die rekursive Suche einer Wanderung von rechts nach links über den Stapel aus verschachtelten Regeln. Die oberste Rekursionsebene der Suche entspricht in der Abbildung dem rechten Ende der unteren Startregel und die unterste Rekursionsebene dem linken Ende. Die Rekursionsebenen der Suche stehen also senkrecht im Bild. Der Punkt steht zunächst in allen Zuständen ganz rechts am Ende und wird während der Baumkonstruktion wieder an den Anfang zurück geschoben. Wenn der Punkt bei allen Zuständen, die Teil des Baumes sind, am Anfang steht, ist ein vollständiger Baum gefunden worden. Jeder Schritt über den Stapel hat drei Fälle:

; Rückwärts-Predictor (Stufe nach oben): Dieser Fall tritt ein, wenn ein nichtterminiertes Symbol vor dem Punkt steht. Die noch leere Vertiefung wird mit einem passenden Zustand befüllt, der dem Symbol vor dem Punkt entspricht. Ein Zustand darf nur dann eingefügt werden, wenn zwischen den Startpositionen entweder keine Lücke verbleibt oder bei dazwischenliegenden Symbolen mindestens so viele Stellen frei bleiben, wie Symbole vorhanden sind. Andernfalls können inkorrekte Bäume entstehen. Stehen mehrere Zustände zur Auswahl, muss später zu dieser Stelle zurückgegangen und die nächste Alternative durchlaufen werden. Wurde erfolgreich ein neuer Zustand platziert, kann eine Stufe weiter nach oben gegangen werden.
; Rückwärts-Scanner (Schritt nach links): Dieser Fall tritt ein, wenn ein terminiertes Symbol vor dem Punkt steht. Die Übereinstimmung mit der Eingabe muss erneut geprüft werden. Bei Übereinstimmung wird der Punkt des Zustandes wieder um eins nach links geschoben und in der Abbildung wird ein Schritt nach links gegangen.
; Rückwärts-Completer (Stufe nach unten): Dieser Fall tritt ein, wenn der Punkt am Anfang einer Regel angekommen ist. In diesem Fall geht es nach links eine Stufe hinab. In dem Zustand, in dem man ankommt, wird der Punkt um eins zurück nach links geschoben.

Der Algorithmus kann unterwegs hängen bleiben, wenn der Rückwärts-Scanner einen Unterschied feststellt, oder der Rückwärts-Predictor keine Alternative mehr hat. Dann muss der Weg zum vorherigen Rückwärts-Predictor zurückgegangen und dort die nächste Alternative versucht werden. Gelangt man schließlich nach links an den Anfang des Stapels, wurde ein möglicher Syntaxbaum gefunden. Um die weiteren Bäume einer mehrdeutigen Grammatik zu finden, wird beim letzten Rückwärts-Predictor weitergemacht und dort die Suche bis zur nächsten vollständigen Alternative fortgesetzt.

=== Pseudocode ===
Der folgende Pseudocode beschreibt den gesamten Ablauf des Algorithmus:

Gegeben seien die zu parsenden Symbole s1...sN
(''Q''0,...,''Q''''N'') = '''ParseText'''(''s''1...''s''''N'')
Falls die finale Startregel „S ->...*“ in ''Q''''N'' enthalten ist:
''i'' = ''N''
''j'' = ''0''
''b'' = Liste von Earley-Zuständen mit als einzigem Element der finalen Startregel
'''BaumRekursion'''(''i'',''j'',''b'',(''Q''0,...,''Q''''N''))
Sonst:
gebe Syntaxfehler aus

'''Funktion''' '''ParseText'''(s1...sN):
Lege leere Zustandsmengen ''Q''''i'' mit ''i''=0..''N'' an
Füge die Startregel „S ->*...“ zu ''Q''0 dazu
Für ''i''=0..''N'':
Füge Early-Zustände gemäß den drei Regeln predictor, scanner und completer
zu ''Q''''i'' hinzu, solange bis keine mehr hinzugefügt werden können
gebe Zustandsmengen (''Q''0,...,''Q''''N'') zurück

'''Funktion''' '''BaumRekursion'''(''i'',''j'',''b'',(''Q''0,...,''Q''''N'')):
''//i: Index der aktuellen Zustandsmenge Qi''
''//j: Index des aktuellen Zustandes bj im Baum b''
Solange ''i'' > 0:
''//Rückwärts-Predictor''
Falls im Zustand ''b''''j'' vor dem Punkt ein Nonterminal steht:
''W''''j'' = Wert des Nonterminals vor dem Punkt des Zustandes ''b''''j''
''k''''j'' = Startindex des Zustandes ''b''''j''
''p''''j'' = Punktposition des Zustandes ''b''''j'' (0 entspricht dem Anfang)
Für alle finalen Zustände ''z'' in ''Q''''i'' mit Wertigkeit ''W'', Startindex ''k'' und Punktposition ''p'',
für die gilt ''W'' = ''W''''j'' und ((''p''''j''-1 = 0 und ''k'' = ''k''''j'') oder (''p''''j''-1 > 0 und ''k''-''k''''j'' >= ''p''''j''-1)):
Hänge Kopie von ''z'' hinten an ''b'' an (alternativ: füge z nach ''b''''j'' ein)
BaumRekursion(''i'',''j+1'',''b'',(''Q''0,...,''Q''''N''))
Lösche das hinterste Element von ''b'' (alternativ: lösche Element ''b''''j+1'')
Beende den Funktionsaufruf ('''return''')
''//Rückwärts-Scanner''
Falls im Zustand ''b''''j'' vor dem Punkt ein Terminal steht:
Falls das Terminal vor dem Punkt gleich s''i'' ist:
Setze Punkt von ''b''''j'' um eins zurück
''i'' = ''i''-1
''//Rückwärts-Completer''
Falls der Punkt von ''b''''j'' am Anfang steht:
''j'' = ''j''-1
Setze Punkt von ''b''''j'' um eins zurück
Falls ''b''''j'' die Startregel ist:
Gebe gefundenen Syntax-Baum ''b'' aus

''//Ausgabe bei der oben gezeigten Grammatik und dem Beispiel n+n''
b =
S -> *E , 0
E -> *E+T , 0
E -> *T , 0
T -> *F , 0
F -> *n , 0
T -> *F , 2
F -> *n , 2

== Auswertung des Syntaxbaumes ==
Um den mathematischen Ausdruck der gezeigten Beispiel-Grammatik auszuwerten, kann mithilfe eines Stacks direkt eine Handlungsvorschrift für die Berechnung erzeugt werden. Dazu wird die Reihenfolge der ermittelten Liste von Zuständen umgekehrt (oder rückwärts durchlaufen) und alle nicht für die Berechnung relevanten Regeln gelöscht oder ignoriert. Für jeden Schritt wird die entsprechende Zahl von Eingangswerten der Operation aus dem [[Stapelspeicher|Stack]] geholt bzw. das Ergebnis der Operation in den Stack zurückgeschoben. Für das obige Beispiel ergibt sich:

F -> *n , 2: Schiebe n in den Stack
T -> *F , 2
F -> *n , 0: Schiebe n in den Stack
T -> *F , 0
E -> *T , 0
E -> *E+T , 0: Hole zwei Werte aus dem Stack, addiere
sie und schiebe das Ergebnis in den Stack
S -> *E , 0: Hole Wert aus dem Stack und gebe ihn aus

Auf diese Weise kann ein beliebig komplexer und verschachtelter mathematischer Ausdruck geparst und ausgewertet werden.

== Literatur ==
* {{Literatur
|Autor=Jay Earley
|Titel=An efficient context-free parsing algorithm
|Sammelwerk=Communications of the [[Association for Computing Machinery]]
|Band=13
|Nummer=2
|Datum=1970
|Seiten=94–102
|Online=[http://ccl.pku.edu.cn/alcourse/nlp/LectureNotes/An_Efficient_Context_Free_Parsing_Algorithm%20%28Earley%20Algorithm%29.pdf ccl.pku.edu.cn]
|Format=PDF
|KBytes=902}}
* {{Literatur
|Autor=John Aycock, R. Nigel Horspool
|Titel=Practical Earley Parsing
|Sammelwerk=The Computer Journal
|Band=45
|Nummer=6
|Datum=2002
|Seiten=620–630
|Online=[http://www.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf cs.uvic.ca]
|Format=PDF
|KBytes=162}}
* {{Literatur
|Autor=Dick Grune, Ceriel J. H. Jacobs
|Titel=Parsing Techniques. A Practical Guide
|Auflage=1.
|Verlag=Ellis Horwood
|Ort=New York
|Datum=1990
|ISBN=0-13-651431-6
|Seiten=149–163
|Online=[ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf ftp.cs.vu.nl]
|Format=PDF
|KBytes=1900}}

== Einzelnachweise ==
<references />

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Dynamische Programmierung]]

Earley-Algorithmus - Versionsgeschichte

imported>Invisigoth67: typo