Chart-Parser

Ein Chart-Parser, auch Chartparser geschrieben, ist als Computerprogramm ein Parser für kontextfreie Grammatiken, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die Effizienz erheblich und macht das Parsen von kontextfreien Sprachen zu einem in polynomieller Zeit lösbaren Problem.

Chartparsing ist ein Überbegriff für alle Parsverfahren, die eine solche Tabelle benutzen. Nach dem verwendeten Parsalgorithmus unterscheidet man verschiedene Subtypen:

• Top-Down-Chart-Parser (Earley-Parser)
• Left-Corner-Chart-Parser
• Insel-Chart-Parser

Chart

Der Chart ist eine n x n-Matrix, wobei n die Länge des zu analysierenden Satzes ist. Die Zwischenräume zwischen den Wörtern dieses Satzes sind von 0 bis n durchnummeriert. In den einzelnen Chartzellen befinden sich sog. gepunktete Regeln (dotted rules, vgl. LR-Parser).

Formal lässt sich ein Chart als eine Menge von 3-Tupeln < i,j, A → α. β > beschreiben, wobei gilt:

• i (0 ≤ i ≤ n) ist die Position, ab der eine Konstituente der Kategorie A erwartet wird.
• j (>= i) ist Position, bis zu der α erkannt ist.
• A → α . β ist eine gepunktete Regel, von der β noch erkannt werden muss; β heißt daher auch der offene Teil dieser Regel, α ist der geschlossene Teil. α und β bestehen aus einer beliebigen Folge von Terminal- und Nichtterminalsymbolen der kontextfreien Grammatik. α und/oder β können auch leer, d. h. gleich ε, sein.

Beispiel

Ein einzelner Charteintrag kann beispielsweise so aussehen:

< 2, 5, VP → V NP . NP >

Dies bedeutet:

• ab der Satzposition 2 wird eine Verbalphrase (VP) erwartet.
• die Analyse der VP ist bis zur Satzposition 5 vorangeschritten. Zwischen den Positionen 2 und 5 befindet sich der geschlossene Teil V NP der VP-Regel.
• eine weitere NP wird ab der Position 5 erwartet, falls die betreffende VP-Regel überhaupt angewendet werden kann.

Parseroperationen

Chart-Parser verwenden während der Analyse im Normalfall drei verschiedene Operationen:

1. Hüllenbildung (predict)
2. Integration eines Terminalsymbols (scan)
3. Kombination zweier Teilkonstituenten (complete)

Hüllenbildung

Ist < i, j, A → α . B β > ∈ Chart und

ist B → γ eine Regel der Grammatik,

dann füge

< j, j, B → . γ >

in den Chart ein, falls dieses Tupel noch nicht vorhanden ist.

Ab der Satzposition j wird also eine Konstituente der Kategorie B erwartet. Zur Expansion von B existiert eine Regel mit rechter Seite γ. Man generiert also eine neue Erwartung, γ beginnend ab der Position j zu finden.

Integration eines Terminalsymbols

Ist < i, j, A → α . w β > ∈ Chart (w ist ein Terminalsymbol bzw. Präterminal) und

ist w das j-te Wort des zu analysierenden Satzes s = w₀w₁ ... w_n,

dann füge

< i, j+1, A → α w . β >

in den Chart ein, falls dieses Tupel noch nicht vorhanden ist.

Die Analyse ist somit soweit vorangeschritten, dass nach der Position j ein Terminalsymbol bzw. eine Wortkategorie (wie Verb) erwartet wird. Ist das j-te Wort tatsächlich gleich w (bzw. von der Wortart w), dann kann dieses Wort in die Analyse integriert werden. Der Punkt wird dann über das erkannte Wort verschoben.

Kombination zweier Teilkonstituenten

Hinweis: die hier beschriebene Kombinationsoperation ist diejenige des Top-Down-Chart-Parsers. Andere Methoden des Chart-Parsings gehen hier etwas anders vor.

Ist < i, j, A → α . B β > ∈ Chart (B ist ein Nichtterminalsymbol) und

ist auch < j, k, B → γ . > ∈ Chart

dann füge

< i, k, A → α B . β >

in den Chart ein, falls dieses Tupel noch nicht vorhanden ist.

Während der Analyse wurde eine vollständige Konstituente B zwischen den Positionen j und k gefunden. Im Chart existiert ein weiteres Tupel, das die Erwartung einer Konstituente B ab Position j reflektiert. Also können beide zu einem neuen Tupel kombiniert werden, welches die Positionen i bis k überdeckt. Der Punkt wurde dabei über die erkannte Konstituente B weitergesetzt.

Parsalgorithmus

Eingabe: Ein Satz s = w₀w₁ ... w_n.

1. Füge <0,0, S' → . S > in den Chart ein (S ist das Startsymbol der Grammatik, S' ein bisher nicht vorhandenes Nichtterminalsymbol).
2. Wende die oben beschriebenen Schritte Predict, Scan und Complete solange an, bis keine weiteren Charteinträge mehr erzeugt werden können.

Ausgabe: yes, falls <0, n, S' → S . > ∈ Chart, andernfalls no.

Hinweis: Eigentlich ist das lediglich ein Erkennungsverfahren. Die tatsächlichen Satzstrukturen können aber mit etwas zusätzlicher Verwaltungsinformation aus dem Chart rekonstruiert werden (sog. shared packed parse forest).

Die Schritte unter 2. sind in ihrer Reihenfolge nicht geordnet. Ihre Reihenfolge kann mit Hilfe verschiedener Suchverfahren (Tiefensuche, Breitensuche, Bestensuche) systematisiert werden.

Beispiel

Gegeben sei eine kontextfreie Grammatik mit folgenden Produktionsregeln:

1. S → NP VP
2. S → S PP
3. VP → V NP
4. NP → NP PP
5. NP → Art N
6. PP → P NP

Lexikonregeln

1. NP → Donald
2. NP → Daisy
3. V → beobachtet
4. N → Fernglas
5. P → mit
6. Art → dem

Der zu parsende Satz sei "Donald beobachtet Daisy mit dem Fernglas"

Nr	Eingefügter Charteintrag	Begründung
1	< 0, 0, S' → . S >	Initialisierung
2	< 0, 0, S → . NP VP >	P 1, 1
3	< 0, 0, S → . S PP >	P 1, 2
4	< 0, 0, NP → . NP PP >	P 2, 4
5	< 0, 0, NP → . Art N >	P 2, 5
6	< 0, 1, NP → Donald . >	S 2, L1
7	< 0, 1, S → NP . VP >	C 2, 6
8	< 0, 1, NP → NP . PP >	C 4,6
9	< 1, 1, VP → . V NP >	P 7, 3
10	< 1, 1, PP → . P NP >	P 8, 6
11	< 1, 2, V → beobachtet . >	S 9, L3
12	< 1, 2, VP → V . NP >	C, 9, 11
13	< 2, 2, NP → . NP PP >	P 12, 4
14	< 2, 2, NP → . Art N >	P 12, 5
15	< 2, 3, NP → Daisy . >	S 12, L2
16	< 1, 3, VP → V NP . >	C 12, 15
17	< 2, 3, NP → NP . PP >	C 13, 15
18	< 0, 3, S → NP VP . >	C 7, 16
19	< 3, 3, PP → . P NP >	P 17, 6
20	< 3, 4, PP → mit . NP >	S 19, L5
21	< 4, 4, NP → . NP PP >	P 20, 4
22	< 4, 4, NP → . Art N >	P 20, 5
23	< 4, 5, Art → dem . >	S 22, L6
24	< 0, 3, S → S . PP >	C 3, 18
25	< 4, 5, NP → Art . N >	C 22, 23
26	< 5, 6, N → Fernglas . >	S 25, L4
27	< 4, 6, NP → Art N . >	C, 25, 26
28	< 3, 6, PP → mit NP . >	C 20, 27
29	< 2, 6, NP → NP PP . >	C 17, 28
30	< 1, 6, VP → V NP . >	C, 12, 29
31	< 0, 6, S → NP VP . >	C 7, 30
32	< 0, 6, S → S PP . >	C 24, 28
33	< 0, 0, S' → S . >	C 1,31

Erläuterung:

• Pn,m=Hüllenbildung (predict) von Eintrag n mit Produktionsregel m,
• Sn,Lm=Integration (scan) von der Hüllenbildung von Eintrag n mit Lexikonregel m,
• Cn,m=Kombination (complete) der beiden Einträge n und m

Die Tatsache, dass Eintrag 33 auch durch Kombination von Eintrag 1 mit Eintrag 32 hätte gebildet werden können, zeigt, dass der Satz auf zwei Arten geparst werden kann (also zweideutig ist).

Erweiterungen

Tilgungsregeln

Tilgungsregeln sind u. a. Produktionsregeln der Form A → ε. Solche Regeln werden meist durch spezielle Vorarbeitungsstrategien in der Chartparser integriert.

Vorausschau (Lookahead)

Das Erzeugen von überflüssigen Charteinträgen kann durch Integration von k Lookahead-Symbolen in die Charttupel verhindert werden. Diese Technik wird auch bei LR(k)-Parsern verwendet.

Separierte Grammatik

Zur Parsen von natürlichen Sprachen werden in der Regel sog. separierte Grammatiken verwendet, bei denen Lexikon und Phrasenstrukturregeln voneinander getrennt sind. Die rechten Regelseiten der kontextfreien Grammatik enthalten somit entweder nur Terminalsymbole (Alphabetsymbole) oder Nichtterminalsymbole. Dies macht den Predict- und Scan-Vorgang effizienter, da sie nur bis zur Ebene der Präterminale (Wortarten) voranschreiten.

Robustheit

Da die Eingaben des Parsers nicht immer im Sinne der Grammatik wohlgeformt sind (vgl. die Anwendung der Grammatikprüfung), ist es nützlich, den Parser robust, d. h. unanfällig für Grammatikfehler zu machen. Dies betrifft beispielsweise unbekannte Wörter, für die dann im Scan-Schritt alle wahrscheinlichen Wortarten eingetragen werden, oder fehlende oder überzählige Wörter, die mit speziellen Fehlerproduktionen erkannt werden.

Komplexität

O(n³) für beliebige kontextfreie Grammatiken, O(n²) für nicht-ambige kontextfreie Grammatiken.

Anwendungen

Chart-Parser werden meist im Zusammenhang mit der syntaktischen Analyse natürlicher Sprachen eingesetzt, da sie – neben dem Tomita-Parser – die beste Zeitkomplexität für beliebige (d. h. auch ambige) kontextfreie Grammatiken aufweisen. Beispielsweise verwendet die Grammatikprüfung von Microsoft Word einen Chartparser. Für Programmiersprachen, deren Syntax spezielle Eigenschaften aufweist, werden meist effizientere Parser wie LR(k)- bzw. LL(k)-Parser eingesetzt.

Siehe auch

• Syntaxanalyse
• natürliche Sprache

Literatur

• Jay Earley: An Efficient Context-Free Parsing Algorithm. In: Communications of the ACM 13, 1970, , S. 94–102.
• Gerald Gazdar, Chris Mellish: Natural Language Processing in Prolog. An Introduction to computational Linguistics. Addison-Wesley, Wokingham u. a. 1989, ISBN 0-201-18053-7.