imported>Jule Glühwurm: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-03-30T11:19:42Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

Ein '''Chart-Parser''', auch '''Chartparser''' geschrieben, ist als [[Computerprogramm]] ein [[Parser]] für [[kontextfreie Grammatik]]en, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die Effizienz erheblich und macht das Parsen von [[Kontextfreie Sprache|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 [[Terminalsymbol|Terminal-]] und [[Nichtterminalsymbol]]en 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 [[Verb|V]] [[Nominalphrase|NP]] der VP-Regel.
* eine weitere [[Nominalphrase|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:

# '''Hüllenbildung''' ('''predict''')
# '''Integration eines Terminalsymbols''' ('''scan''')
# '''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 = w0w1 ... wn,

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 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 = w0w1 ... wn.

# Füge <0,0, S' → . S > in den Chart ein (S ist das [[Startsymbol]] der Grammatik, S' ein bisher nicht vorhandenes [[Nichtterminalsymbol]]).
# 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 [[Produktionsregel]]n:
# [[Satz (Grammatik)|S]] → [[Nominalphrase|NP]] [[Verbalphrase|VP]]
# [[Satz (Grammatik)|S]] → [[Satz (Grammatik)|S]] [[Präpositionalphrase|PP]]
# [[Verbalphrase|VP]] → [[Verb|V]] [[Nominalphrase|NP]]
# [[Nominalphrase|NP]] → [[Nominalphrase|NP]] [[Präpositionalphrase|PP]]
# [[Nominalphrase|NP]] → [[Artikel (Wortart)|Art]] [[Nomen|N]]
# [[Präpositionalphrase|PP]] → [[Präposition|P]] [[Nominalphrase|NP]]

Lexikonregeln
# [[Nominalphrase|NP]] → Donald
# [[Nominalphrase|NP]] → Daisy
# [[Verb|V]] → beobachtet
# [[Nomen|N]] → Fernglas
# [[Präposition|P]] → mit
# [[Artikel (Wortart)|Art]] → dem

Der zu parsende Satz sei „Donald beobachtet Daisy mit dem Fernglas“

{| class="wikitable"
!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. [[Produktionsregel]]n der Form A → ε. Solche Regeln werden meist durch spezielle Verarbeitungsstrategien in den 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-Parser|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(n3) für beliebige kontextfreie Grammatiken, O(n2) 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-Parser|LR(k)]]- bzw. [[LL-Parser|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, {{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.

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Computerlinguistik]]

Chart-Parser - Versionsgeschichte

imported>Jule Glühwurm: /* growthexperiments-addlink-summary-summary:2|0|0 */