Earley-Algorithmus

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Earley-Algorithmus 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 dynamische Programmierung.

[Bearbeiten] Verwendung

Eine Aufgabe eines Compilers ist es, zu überprüfen, ob der eingegebene Quelltext 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 erreicht. Beide sind optimal, um das Problem für eine allgemeine Sprache zu lösen. Der Earley Algorithmus hat jedoch den Vorteil, dass keine Umwandlung der Grammatik in Chomsky-Normalform nötig ist.

In der Praxis versucht man meist, den relativ hohen Rechenaufwand der beiden Algorithmen zu vermeiden oder zu reduzieren. Man optimiert dabei den Compiler 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.

[Bearbeiten] Algorithmus

Der Algorithmus benötigt als Eingabe eine kontextfreie Grammatik und ein Wort über dem selben 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 $a_1 \dots a_n$ verwendet der Algorithmus die Zustandsmengen $Q_0, \dots, Q_n$ . Ein Zustand des Algorithmus ist dabei eine Produktion, deren rechte Seite durch einen Punkt $\cdot$ zerlegt ist. Alle Zeichen vor diesem Punkt gelten als schon überprüft. Eine solche Produktion $(A \rightarrow a \cdot b, i)$ ist in einer Zustandsmenge $Q j$ enthalten und durch einen zusätzlichen Zähler $i$ gekennzeichnet. Dieser bestimmt, aus welcher Menge die Produktion ursprünglich stammt, damit der Algorithmus mit Rekonstruktionschritten schnell einen Ableitungsbaum erzeugen kann.

Am Anfang wird $(\overline{S}\rightarrow\cdot 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:

Voraussage: falls $(X\rightarrow u \cdot Av, j)$ in $Q i$ enthalten ist, wird für jede Produktion $A\rightarrow w$ aus der Grammatik $(X\rightarrow u\cdot wv, i)$ zu $Q i$ hinzugefügt.

Eingabeüberprüfung: falls $(X\rightarrow u\cdot cv, j) \in Q_{i-1}$ und $c = a i$ , wird $(X\rightarrow uc\cdot v, j)$ zu $Q i$ hinzugefügt.

Rekonstruktion: falls $(B\rightarrow w\cdot ,j)\in Q_i$ existiert werden alle $(X\rightarrow uB\cdot v, k) \in Q_i$ für die ein $(X\rightarrow u\cdot Bv, k) \in Q_j$ existiert zu $Q i$ hinzugefügt.

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

[Bearbeiten] Beispiel

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$ :

- $(\overline{S}\rightarrow \cdot S,0)$
- Die Voraussagen für $S$ :
- $(S \rightarrow \cdot () ,0)$ (V)
- $(S \rightarrow \cdot ()(),0)$ (V)
- $(S \rightarrow \cdot (A),0)$ (V)
- $(S \rightarrow \cdot (A)(A),0)$ (V)

In Q₁:
- Zuerst alle Eingabeüberprüfungen
- $(S \rightarrow (\cdot ) ,0)$ (E)
- $(S \rightarrow (\cdot)() ,0)$ (E)
- $(S \rightarrow (\cdot A) ,0)$ (E)
- $(S \rightarrow (\cdot A)(A) ,0)$ (E)
- Jetzt ist es möglich $A$ vorauszusagen. Dieses A ist 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 \cdot \varepsilon ,1)$ (V)
- $(A \rightarrow \cdot (A) ,1)$ (V)
- $(A \rightarrow \cdot (A)(A) ,1)$ (V)
- Wegen der Epsilonproduktion ist das Nichtterminal $A$ hier fertig produziert. Es ist also schon ein Rekonstruktionsschritt möglich:
- $(S \rightarrow (\cdot ) ,0)$ (R)
- $(S \rightarrow (\cdot )(A) ,0)$ (R)

Weitere Schritte sind nicht möglich,

Also geht es weiter in Q₂:
- wieder zuerst die Vorhersagen, das aktuelle Zeichen ist ')':
- $(S \rightarrow ()\cdot ,0)$ (E)
- $(S \rightarrow ()\cdot () ,0)$ (E)
- $(S \rightarrow () \cdot ,0)$ (E)
- $(S \rightarrow ()\cdot (A) ,0)$ (E)
- alle anderen Regeln lassen sich hier nicht anwenden.
In Q₃:
- Nur bei einer Produktion lässt sich das richtige Zeichen einlesen:
- $(S \rightarrow ()(\cdot A) ,0)$ (E)
- Jetzt können neue Vorhersagen für $A$ gemacht werden:
- $(A \rightarrow \cdot \varepsilon ,3)$ (V)
- $(A \rightarrow \cdot (A) ,3)$ (V)
- $(A \rightarrow \cdot (A)(A) ,3)$ (V)
- $(S \rightarrow ()(\cdot) ,0)$ (R)
In Q₄:
- $(A \rightarrow (\cdot A) ,3)$ (E)
- $(A \rightarrow (\cdot A)(A) ,3)$ (E)
- $A$ wird wieder vorhergesagt:
- $(A \rightarrow \cdot \varepsilon ,4)$ (V)
- $(A \rightarrow \cdot (A) ,4)$ (V)
- $(A \rightarrow \cdot (A)(A) ,4)$ (V)
- $(A \rightarrow (\cdot ) ,3)$ (R)
- $(A \rightarrow (\cdot )(A) ,3)$ (R)
In Q₅:
- $(A \rightarrow ()\cdot ,3)$ (E)
- $(A \rightarrow ()\cdot (A) ,3)$ (E)
- Da das obere $A$ fertig eingelesen ist, dann jetzt aus $Q 3$ rekonstruiert werden
- $(S \rightarrow ()(\cdot) ,0)$ (R)
In Q₆:
- $(S \rightarrow ()()\cdot ,0)$ (E)
- Das Startsymbol wurde also komplett gelesen. $\overline{S}$ kann also rekonstruiert werden.
- $(\overline{S}\rightarrow S\cdot,0)$ (R)