Chart-Parser

Chart-Parser

Ein Chart-Parser, auch Chartparser geschrieben, ist 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

Inhaltsverzeichnis

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

  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. SNP VP
  2. SS PP
  3. VPV NP
  4. NPNP PP
  5. NPArt N
  6. PPP 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(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(k)- bzw. LL(k)-Parser eingesetzt.

Siehe auch

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.

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Chart parser — A chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages). It uses the dynamic programming approach partial hypothesized results are stored in a structure called a chart and can be re used. This… …   Wikipedia

  • Chart parser — Un chart parser es un analizador sintáctico dedicado a las gramáticas libres de contexto, que utiliza un chart (una tabla) como ayuda para ir guardando las constituyentes sintácticas según va procesando la oración correspondiente. Este método de… …   Wikipedia Español

  • Chart Parsing — Ein Chartparser ist 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… …   Deutsch Wikipedia

  • Parser — Ein Parser [ˈpɑːʁzɐ] (engl. to parse, „analysieren“, bzw. lateinisch pars, „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Computertechnik für die Zerlegung und Umwandlung einer beliebigen Eingabe in ein für …   Deutsch Wikipedia

  • Chart (disambiguation) — For information about charts in Wikipedia, see Wikipedia:Charts. A chart is a graphical representation of data. Chart may also refer to: A specific type of map, for example: Aeronautical chart, a representation of airspace and ground features… …   Wikipedia

  • Text-Parser — Ein Parser [ˈpɑːɹsɚ] (engl. to parse „analysieren“ bzw. von lateinisch pars „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Computertechnik für die Zerlegung und Umwandlung einer beliebigen Eingabe in ein… …   Deutsch Wikipedia

  • Tomita-Parser — Ein Tomita Parser (nach Masaru Tomita) ist ein Parsverfahren für kontextfreie Grammatiken, das eine Verallgemeinerung des LR(k) Verfahrens ist. Das Verfahren wird deshalb auch GLR(k) Verfahren (für Generalized LR(k)) genannt. Ausgangspunkt des… …   Deutsch Wikipedia

  • Earley parser — The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named after its inventor, Jay Earley. The algorithm uses dynamic programming.Earley parsers are appealing because they can parse all context free… …   Wikipedia

  • Sequential Function Chart — язык программирования стандарта IEC61131 3. Предназначен для программирования промышленных контроллеров. Широко используется в SCADA/HMI пакетах. SFC графический язык, предназначенный для написания программ последовательного управления… …   Википедия

  • Parsing — Ein Parser [ˈpɑːɹsɚ] (engl. to parse „analysieren“ bzw. von lateinisch pars „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Computertechnik für die Zerlegung und Umwandlung einer beliebigen Eingabe in ein… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”