1

Parsing

Hauke TraulsenMethoden der

Sprachverarbeitung

Heute

• Parser - Arten• Parsing - Arten grob klassifiziert• Interessante Parser – Arten detailierter

Einführung

• Bedeutung „Parsing“

– Zuweisung einer Strukturbeschreibung zu einer Texteingabe

– engl. to parse: „grammatikalisch bestimmen“

Grammatik – Parser I

• Interpretierender Parser• „deklarative“ Grammatik• Grammatik losgelöst von der Analyse• Interpretiert vom Parser

Grammatik - Parser II

• Prozeduraler Parser• Grammatik in Algorithmus integriert• Grammatik ist prozedural als eine Menge von

Instruktionen formuliert.• Neue Prozedur für jede neue Grammatik

Grammatik – Parser III

• Kompilierter Parser• (Deklarative) Grammatik• Erzeugung eines prozeduralen Parsers durch

Generator (JavaCC)

2

Grammatik Spezifikation

• Produktionsregeln

– Möglichkeit, mit diesen alle wohlgeformten Sprachkonstrukte zu generieren

– Start bei einer Root – Kategorie (meistens S oder sentence genannt

– „kontextfreie Grammatik“

Grammatik Spezifikation II

• Übergangsnetzwerke– (transition networks)– Knoten: Zustände in einem Prozess– Kanten: Übergänge, beschriftet mit den

Wortkategorien

– RTN, ATN

Grammatik Spezifikation III

• complement slots– syntaktische Einheit (z.B. Verb)– Fordert andere Konstrukte (Subjekt,...)– Suche nach diesen Konstrukten– Im Lexikon für jedes Item festgehalten

Komplement: Vervollständigung (zu einem Satz)

Strukturelle Beschreibung I

• constituency structure (Teilbildung)• typischer Parsebaum

Strukturelle Beschreibung II

• dependency structures• Alle Knoten sind elementare Segmente der

Eingabe• Aber: Komplexe Strukturen wiederum als

Dependency Trees (Subjekt, Objekt,...)

Konstruktion Parsebaum I

• Top – Down –Analyse• Beginn an der Wurzel• Produktionsregeln: von links nach rechts• Expansion • „expectation driven“, da Hypothesen

3

Konstruktion Parsebaum II

• Bottom – Up – Analyse• Beginn an der Eingabe• data driven • Nutzt Produktionsregeln von rechts nach links• Reduktion• „SR-Parser“

Konstruktion Parsebaum III

• Depth First• Sowohl TD als auch BU einsetzbar(TD sinnvoll)• Linkeste / rechteste Symbol zuerst• Überwindet schnellstmöglich die gesamte Höhe

des Baumes• (im Falle TD) schnellstmögliche Überprüfung

der bisher getroffenen Entscheidungen anhand der Daten

Konstruktion Parsebaum IV

• Breadth First• bottom up sinnvoll• Abarbeitung aller Symbole in der Reihenfolge

ihrer Entstehung• Dadurch: Bearbeitung in der Breite• Selten

Alternativen

Grund:– ungenügende Informationen– mehrdeutige Informationen

Lösungsansätze– Backtracking– Parallele (nebenläufige) Ausführung– Lookahead (z.B. LL(k) – Grammatiken)

Charts

• Abspeicherung bereits erkannter Substrukturen in einer Tabelle

• Effizienz• Bekanntester Algorithmus:

Earley (Jay Earley 1970)

Vorgestellte Parser

• Top – Down mit Backtracking• Top – Down mit Parallel Processing• Top – Down mit Divided Productions• Bottom – Up mit Charts• Tabellengesteuerter SR – Parser• Parser mit RTN • Erweiterte Übergangsnetzwerke (ATN)• Chart Parsing nach Slot – Filler – Prinzip

4

Top – Down – Parser mit Backtracking

– Erkennungexpectation driven

– Resultatconstituency tree

– Grammatikspezifikationkontextfreie Produktionsregeln

Zur Übersicht

Top – Down mit Backtracking II

• Man nehme:– Eine Menge von Produktionsregeln– Ein Lexikon für die Wortkategorien– Eine Eingabetabelle (Wort,Kat.,Pos.)– Eine Positionsvariable P i.d. Eingabe– Ein Arbeitsraum (organisiert als Stack)– Ein Backtrackingstack (hält alternative

Produktionen)

Zur Übersicht

Top – Down mit Backtracking III

• Das Vorgehen:1. Start bei Root (Produktion S)

2. Innerhalb einer Produktion entwickelt man von links nach rechts (S NP VP : NP wird zuerst weiterentwickelt)

3. Alternativen der Reihe nach (Backtracking)

4. Depth-First

5. Vergleichen, ob die erwartete Kategorie mit der des nächsten Wortes der Eingabe übereinstimmt.

Zur Übersicht

Top – Down mit Backtracking IV

– Kategorie passt (sonst BT):– betrachte Rest der aktuellen Produktion:

• Rest leer und Eingabe enthält noch Elemente Backtracking

• Rest nicht leer Weiterentwickeln des linkesten NT-Symbols

• Rest leer und Eingabe leer: Matching Ausgabe– Backtrackingstack nicht leer Backtracking– Sonst Ende

Zur Übersicht

Top – Down mit Backtracking V

• Bewertung– Durch das Backtracking gehen bereits

gefundende Teile wieder verloren+ Durch Left-Right und Depth-First erhält man

schnell ein erstes Ergebnis• Überdeckung

– Kontextfreie Grammatiken ohne Linksrekursion

Zur Übersicht

Top – Down mit Parallel Processing

• Kaum Unterschied zu Backtracking• Einzigster Unterschied:

– Statt Backtracking parallele Auswertung der Produktionsalternativen

Zur Übersicht

5

Top-Down mit geteilten Produktionen

– Erkennungexpectation driven

– Resultatconstituency tree

– Grammatikspezifikationkontextfreie Produktionsregeln

Zur Übersicht

Top-Down mit geteilten Produktionen II

• Anders ist:– Generell zwar TD, jedoch mit zwischenzeitlichen BU-Phasen– Kein Backtracking, stattdessen substring-table– Linksrekursion in Grammatik erlaubt

– Earley‘s Algorithmus: „Active Chart Parser“

Zur Übersicht

Top – Down mit geteilten Produktionen III

• Man nehme:– Eine Menge von Produktionsregeln einer kfG– Ein Lexikon für die Wortkategorien– Eine Eingabetabelle (Wort, Kat., Berandungen)– Eine Arbeitstabelle (Substring-Tabelle, auch

Chart)– Zwei Variablen CUR und NEW

Zur Übersicht

Top-Down mit geteilten Produktionen IV

• Eingabetabelle (Beispiel)

Berandungen!

Zur Übersicht

Top-Down mit geteilten Produktionen V

• Arbeitstabelle

• CUR und NEW initial auf dieser Zeile 1 (sonst Tabelle leer)

• Punkt teilt linken und rechten Teil einer ganzen Grammatikproduktion

• Links wird hier verarbeitet, rechts noch ungeprüft.

Zur Übersicht

Top-Down mit geteilten Produktionen VI

• Vorgehensweise• 1. Predictor

Wenn in Zeile CUR ein NT-Symbol hinter dem Punkt zu finden ist neue Zeile einfügen, mit Produktion, die dieses NT-Symbol entwickelt.

Zur Übersicht

6

Top-Down mit geteilten Produktionen VI

• Immer: NEW auf die neue Zeile• Predictor: rechten Rand von CUR erben• Undo, falls Dublikat

Zur Übersicht

Top-Down mit geteilen Produktionen VII

• Wenn kein NT-Symbol in der CUR-Zeile hinter dem Punkt steht Scanner

• Mögliche Bedeutung:a. Der Punkt wurde durch alle Bestandteile

der Eingabe bewegtb. Ein Lex-Symbol steht hinter dem Punkt

der CUR-Zeile

Zur Übersicht

Top-Down mit geteilten Produktionen VIII

Scanner: • Wenn Lex-Symbol erwartet: Von der Eingabe

lesen.

• Wenn Wort der Eingabe passtKopiere CUR-Produktion in neue ZeileBewege den Punkt hinter den erkannten TeilSetze NEW auf diese neue ZeileERHÖHE RECHTEN RAND + 1

Zur Übersicht

Top-Down mit geteilten Produktionen IX

• Wenn ein NT- oder Lex-Symbol in der CUR-Produktion stand:

CUR = CUR +1 und von vorne

• Versetzen des Punktes führt dazu, dassirgendwann die Phase Completer auf eine Zeile angewendet werden kann.

Zur Übersicht

Top-Down mit geteilten Produktionen X

3. Completer• Wenn die Produktion X Y in Zeile CUR komplett ist

(Punkt ist ganz rechts)• Betrachte linke Margin• Suche in entsprechender Sektion, ob X in einer

Teilproduktion S genau rechts vom Punkt benutzt wird

• Bemerke: Lrand == Rrand (keine Überlappung durch Randnumerierung)

• Wenn neue ProduktionNEW auf neue Produktionneue Produktion wie S, aber X nun links vom Punkt

Zur Übersicht

Top-Down mit geteilten Produktionen XI

Ende des AlgorithmusWenn eine Aktion des Completers dazu führt,

dass

• # S. • Linke Margin = 0• Rechte Margin = Wortanzahl der Eingabe

Dann hat man die Eingabe komplett parsen können.

Zur Übersicht

7

Top-Down mit geteilten Produktionen XII

Betreff: Margins• Beginnend mit (0,0) für # .S• Predictor: Vererbung der rechten Margin für daraus

ableitbare Teilproduktionen (links und rechts: (1,2) - - > (2,2) )

• Scanner: Erhöht rechte Margin um 1

• Completer:Linke Margin der kleineren, Rechte Margin der größeren

• Bedeutung ?

Zur Übersicht

Top-Down mit geteilten Produktionen XIII

Warum vererbt man von Produktion X aus im Predictor den rechten Rand ?Weiterentwicklung im Predictor nur des jeweils ersten Symbols rechts vom PunktAus der Sicht der Produktion X betrachtet X alle Eingabesymbole zwischen seinen Begrenzungen:Diese sind auch bereits gelesen worden (Erhöhung nur durch Scannereinsatz)Für das Symbol rechts vom Punkt in X sind noch keine Eingaben gelesen worden, folglich Vererbung des rechten Randes von X

Zur Übersicht

Top-Down mit geteilten Produktionen XIV

• Warum wird beim Scanner der rechte Rand um 1 erhöht ?

• Trivial: ein Eingabewort mehr gelesen und somit von der neuen Produktion bearbeitet.

Zur Übersicht

Top-Down mit geteilten Produktionen XV

Warum bekommt die im Completer entstehende neue Produktion den linken Rand von X und den rechten Rand der Teilproduktion Y, die man in X einpflanzen kann ?X hatte bereits alle Eingabezeichen von xl

bis xr behandelt, Y hat nun alle Eingabezeichen von xr+1 bis yr behandeltResultat: gesamte neue Produktion

behandelt alle Eingabezeichen von xl bis yr

Zur Übersicht

Top-Down mit geteilten Produktionen XVI

Bewertung• Eine Menge von unbenötigten Produktionen

werden generiert.• Nicht wird zweimal getan, da alle

Zwischenergebnisse wiederverwendet werden.

• Kein Backtracking• TD kombiniert mit BU (BU im Completer)• kFG ohne Beschränkungen

Zur Übersicht

Bottom-Up mit Chart

– Erkennungdata driven

– Resultatconstituency tree UND dependency tree

– Grammatikspezifikationkontextfreie Produktionsregeln

Zur Übersicht

8

Bottom-Up mit Chart II

Man nehme:• Eine kontextfreie Grammatik in

Chomsky Normalform• Ein Lexikon (wie bekannt)• Eine Variable P, die durch die Eingabe

läuft• Eine Arbeitstabelle (Chart)• Drei Variablen CUR,NEW, NEIGHBOR

Zur Übersicht

Bottom-Up mit Chart III

Aufbau der Arbeitstabelle• Wie gehabt: Unteilung in Sektionen gemäß

des rechten Randes• Jede Zeile

– Kategorie eines Segmentes der Eingabe– linker und rechter Rand– Segment durch Reduktion Angabe des linken

und des rechten Bestandteils (durch Zeilennummer)

Zur Übersicht

Bottom-Up mit Chart IV

Beispiel Tabelle (Auszug)

Zur Übersicht

Bottom-Up mit Chart V

Variablen• CUR: aktuell bearbeitete Zeile

• NEW: Zeile neu erstelltes Segment am Ende der Tabelle

• NEIGHBOR: ein linker Nachbar von CUR (?...kommt)

Kategorie in Zeile CUR ist momentan zu verarbeitendes Symbol

Zur Übersicht

Bottom-Up mit Chart VI

Vorgehen1. Shift-Phase

– Holen einer Terminal-Kategorie (von Position P) auf die Tabelle = Lesen von Eingabe

– Rechter Rand = P– Linker Rand = P-1– Setze Bestandteile auf Null („-“)– Falls mehrere Kategorien für gelesenes (Mehrdeutigkeit):

ebenfalls neue Zeile für diese

Zur Übersicht

Bottom-Up mit Chart VII

2. Reduce– Symbol in CUR ist Kandidat für Reduktion

– Suche nach der nächsten Produktion X, die Symbol in CUR als rechten Teil besitzt.

– Suche linken Nachbarn (Produktion) im Chart (NEIGHBOR)

– Falls existent, Reduktion mit neuer Zeile, NEW erhöhen, Nachbarn eintragen

– Wiederhole Reduce, bis keine Produktion X mehr zu finden

Zur Übersicht

9

Bottom-Up mit Chart VIII

3. Endbedingung überprüfen– Erhöhe CUR um 1– Wenn CUR ungleich NEW Reduce– Andernfalls erhöhe P um 1:

• P hinter dem letzten Eingabewort komplettes Resultat ?• Sonst Shift

4. Komplettes Resultat– Min. eine Zeile mit:

• Linker Rand = 0• Rechter Rand = Anzahl Eingabewörter

Zur Übersicht

Bottom-Up mit Chart IX

• Arbeitstabelle ist Chart (Beispiel)

Zur Übersicht

6 und 10 sind überflüssige Reduktionen

(keine weiteren Reduktionen von diesen aus möglich)

Bottom-Up mit Chart X

• Ausgabe– Als contituency trees leicht aus Chart ableitbar:

Zur Übersicht

Bottom-Up mit Chart XI

Ausgabe 2Auch möglich als dependency trees:• Beginn: Zeile mit komplettem Resultat wird Root• Unterscheidung: dominant ist fettgedruckt (vgl.

Produktionsregeln; auch Working table)• Ersetzung eines Knotens durch seinen dominanten

Teil (untergeordneter Teil wird Subknoten)• Runter bis zu den lexikalischen Kategorien

Zur Übersicht

Bottom-Up mit Chart XII

Beispiel Bildung eines dependency trees(14:S)(12:Vi (1:Nu) )( 5:Vi (1:Nu) (9:PP) )( 2:Vt (1:Nu) (4:Nu) (9:PP) )( 2:Vt (1:Nu) (4:Nu) (7:Prep (8:Nu) ) )( 2:study (1:they) (4:fish) (7:in (8:cans) ) )

Zur Übersicht

Bottom-Up mit Chart XIII

Bewertung• Erzeugt nichts zweimal (Wiederverwendung)• Aber alle möglichen Kombinationen (Overhead)• Gegenüber geteilten Produktionen : eingängiger

Algorithmus• Zwei mögliche Darstellungsarten (nettes Feature)

Zur Übersicht

10

Rekursive Übergangsnetzwerke (RTN)

• Interpretierender Parser• Erstellt Consituency Trees• Erstellung von RTNs aus einer Menge

von kf Produktionsregeln spezifiziert die Grammatik

Zur Übersicht

RTN II

• Man nehme:– Menge von kf Produktionsregeln (keine Links-

Rekursion)– Lexikon– Eingabetabelle (wie in TD mit Backtracking)– Menge von RTNs (erstellt aus kfG)– Arbeitstabelle– Backtrackingmechanismus

Zur Übersicht

RTN III

• Beispiel: RTNs für G1

S 1 2/eNP VP

VP 3 5/evt NP 4

vi

PP

ε

NP 6 8/edet adj 7 n

εε

PP 9 10/eprep NP

Zur Übersicht

RTN IV

Vorgehen• Beginnend mit S• ….intuitiv ….intuitiv• Wenn am Pfeil eine lexikalische Kategorie steht

Scanner…bei nicht passen Backtracking• Wenn am Pfeil der initiale Zustand eines anderen Netzwerkes

steht Abarbeitung dieses Netzwerkes einfügen • Erfolgreiches Ende, wenn Arbeitstabelle (Stackartig!) wieder

leer ist + komplette Eingabe gelesen…intuitiv…intuitiv

Zur Übersicht

RTN V

• Bewertung– Nutzt dieselben Prinzipien wie TD mit BT– …und ist deshalb auch nicht besser !

Zur Übersicht

Erweiterte Übergangsnetzwerke (Augmented Transition Networks)

• ATN

–ErkennungGewöhnlich TD, Pattern orientiert

–Verhältnis Grammatik-ParserProzeduraler P., keine Trennung

Zur Übersicht

11

ATN II

Wie in RTN:- Knoten, Übergänge („Arcs“), rekursive Subnetzaufrufe- Erweiterung der Übergänge durch

- Vorbedingungen- Aktionen vor / nach einem Übergang

- Erweiterungen in Prog.-sprache (LISP)- Möglichkeit, Register zu erschaffen (sogar globale

Variablen möglich) Mächtigkeit einer Turing-Maschine (Generierung jeder aufzählbaren Sprache)

- Turing-Mächtigkeit ist Overkill, darum Selbstrestriktion für natürliche Sprachen

Zur Übersicht

ATN III

Sprachverarbeitung• Verschiedene Pfeilarten

CAT-Arc: Übergang weist lexikalische Kategorie auf 1. Übereinstimmung mit Kategorie aktuelles Wort, andernfalls

BT2. Spezifizierte Vorbedingungen bestehen, andernfalls BT3. Spezifizierte Aktionen ausführen4. Neuen Knoten betreten

Zur Übersicht

ATN IV

WRD-arcErwartet lexikalisches Element1. Identität zwischen erwartetem Element und

Eingabewort, andernfalls BT2. Tests3. Aktionen4. Nächsten Knoten betreten

Zur Übersicht

ATN V

• Einige weitere Übergangsarten– Push-Arc: Rekursiv Subnetz aufrufen– Pop-Arc: Aus Rekursion zurückkehren– Jump-Arc: Übergang ohne Erhöhung der

aktuellen Eingabeposition

Zur Übersicht

ATN VI

Erfolg des Algorithmus

Durch Erreichen des Eingabeendes garantiert !

Zur Übersicht

ATN VII

Beispiel eines ATN-Formalismus für NL-Parsing

Zur Übersicht

12

ATN VIII

Ausschnitt von gleichem Auschnitt in prozeduraler Schreibweise

Zur Übersicht

ATN IX

Beispielgrammatik (Ausschnitt) ATN graphisch

Zur Übersicht

ATN X

• Bewertung– Da ATN für eine spezielle Grammatik erschaffen

sehr effizient– Backtracking vermeidbar: (geschickte

Registernutzung)– Sehr sorgfältige Programmierer benötigt

(sideeffects in Registern)

Aufgrund ihrer Mächtigkeit einziger Parser, der allesprachlichen Möglichkeiten verarbeiten könnte ! (z.B. Ellipsen)

Zur Übersicht

ENDE