EinChart-Parser, auchChartparser geschrieben, ist als Computerprogramm einParser fürkontextfreie Grammatiken, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die Effizienz erheblich und macht das Parsen vonkontextfreien 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

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 eineKonstituente 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 deroffene Teil dieser Regel, α ist dergeschlossene Teil. α und β bestehen aus einer beliebigen Folge vonTerminal- undNichtterminalsymbolen der kontextfreien Grammatik. α und/oder β können auch leer, d. h. gleich ε, sein.

Ein einzelner Charteintrag kann beispielsweise so aussehen:

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

Dies bedeutet:

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

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)

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 Satzpositionj 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 Positionj zu finden.

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

istw dasj-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 so weit vorangeschritten, dass nach der Positionj einTerminalsymbol bzw. eine Wortkategorie (wieVerb) erwartet wird. Ist dasj-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.

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 einNichtterminalsymbol) 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 Positionenj undk gefunden. Im Chart existiert ein weiteres Tupel, das die Erwartung einer Konstituente B ab Positionj reflektiert. Also können beide zu einem neuen Tupel kombiniert werden, welches die Positioneni bisk überdeckt. Der Punkt wurde dabei über die erkannte Konstituente B weitergesetzt.

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

1. Füge <0,0, S' → . S > in den Chart ein (S ist dasStartsymbol der Grammatik, S' ein bisher nicht vorhandenesNichtterminalsymbol).
2. Wende die oben beschriebenen SchrittePredict,Scan undComplete solange an, bis keine weiteren Charteinträge mehr erzeugt werden können.

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

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.

Gegeben sei einekontextfreie Grammatik mit folgendenProduktionsregeln:

1. S →NPVP
2. S →SPP
3. VP →VNP
4. NP →NPPP
5. NP →ArtN
6. PP →PNP

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“

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).

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

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

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.

Da die Eingaben des Parsers nicht immer im Sinne der Grammatik wohlgeformt sind (vgl. die Anwendung derGrammatikprü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.

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

Chart-Parser werden meist im Zusammenhang mit der syntaktischen Analyse natürlicher Sprachen eingesetzt, da sie – neben demTomita-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 wieLR(k)- bzw.LL(k)-Parser eingesetzt.

• Syntaxanalyse
• natürliche Sprache

• Jay Earley:An Efficient Context-Free Parsing Algorithm. In:Communications of the ACM 13, 1970,ISSN 0001-0782, 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.

• Theorie formaler Sprachen
• Computerlinguistik