ParsingProlog Aufbaukurs SS 2000

Heinrich-Heine-Universität Düsseldorf

Christof Rumpf

17.04.2000 Parsing 2

Parsing

• engl. to parse: „grammatisch zerlegen“

• Ein Parser ist ein Automat, der einer Zeichenkette aufgrund einer Grammatik einen Syntaxbaum zuordnet.

Grammatik Parser SyntaxbaumZeichenkette

In Out

17.04.2000 Parsing 3

Parsingstrategien

• top-down• bottom-up• left-corner

Parsingstrategien unterscheiden sich durch die Reihenfolge, in der bei der Konstruktion des Syntaxbaums die Knoten im Baum besucht werden.

• depth-first• breadth-first

• left-to-right• right-to-left

17.04.2000 Parsing 4

Beispielgrammatik (CFPSG)

rule(s,[np,vp]).rule(np,[d,n]).rule(np,[np,conj,np]).1

rule(vp,[v,np]).rule(vp,[v,np,pp]).rule(pp,[p,np]).rule(d,[]).2

word(d,the).word(conj,and).word(p,near).word(n,dog).word(n,dogs).word(n,cat). word(n,cats).word(n,elephant). word(n,elephants).word(v,chase). word(v,chases).word(v,see). word(v,sees).word(v,amuse). word(v,amuses).

1 nicht für top-down-Parser2 nicht für bottom-up-Parser

17.04.2000 Parsing 5

Top-Down-Traversierung

S1

NP2 VP7

D3 N5 V8 NP10

D11 N13

the4 dog6 chased9 the12 cat14

top-down depth-first left-to-right

17.04.2000 Parsing 6

Top-Down-Parser

parse(C,[Word|S],S) :- word(C,Word).

parse(C,S1,S) :- rule(C,Cs), daughters(Cs,S1,S).

daughters([C|Cs],S1,S) :- parse(C,S1,S2), daughters(Cs,S2,S).

daughters([],S,S).

% Wort der Kategorie C% Lexikon-Zugriff

% Phrase der Kategorie C% Regel mit Mutter C% Töchter Cs parsen

% Tochter der Kategorie C% ist Mutter eines Teilbaums% Schwestern parsen

% Alle Töchter verarbeitet

17.04.2000 Parsing 7

Problem: Linksrekursion

• Top-Down-Strategie loopt bei linksrekursiven Regeln:

NP NP Conj NP

• Auswege: – Linksrekursion vermeiden– Bottom-Up- oder Left-Corner-Strategie

17.04.2000 Parsing 8

Bottom-Up-Traversierung

S14

NP5 VP13

D2 N4 V7 NP12

D9 N11

the1 dog3 chased6 the8 cat10

17.04.2000 Parsing 9

Shift-Reduce-Algorithmus

• Shift: lege ein Wort aus der Eingabekette auf einen Stapel.

• Reduce: reduziere den Stapel mit Hilfe der Grammatik soweit wie möglich.

• Falls die Eingabekette noch Wörter enthält, gehe zu Shift, sonst halte.

17.04.2000 Parsing 10

Shift-Reduce-Beispiel

Schritt Aktion Stack Input StringStart the dog barked

1 Shift the dog barked2 Reduce D dog barked3 Shift D dog barked4 Reduce D N barked5 Reduce NP barked6 Shift NP barked7 Reduce NP V8 Reduce NP VP9 Reduce S

17.04.2000 Parsing 11

Shift-Reduce-Parserparse(S,Result) :- shift_reduce(S,[],Result).

shift_reduce(S,Stack,Result) :- shift(Stack,S,NewStack,S1), reduce(NewStack,ReducedStack), shift_reduce(S1,ReducedStack,Result).shift_reduce([],Result,Result).

shift(X,[H|Y],[H|X],Y).

reduce(Stack,ReducedStack) :- brule(Stack,Stack2), reduce(Stack2,ReducedStack).reduce(Stack,Stack).

brule([vp,np|X],[s|X]).brule([np,conj,np|X],[np|X]).% ...brule([Word|X],[Cat|X]) :- word(Cat,Word).

% S = String, Result = Stapel.% Initialisierung: leerer Stapel.

% Nichtleere Eingabekette S.% Lege ein Wort auf den Stapel.% Reduziere den Stapel.% Verarbeite Rest S1.% Leere Eingabekette.

% Lege ein Wort auf den Stapel.

% Reduziere Stack durch Anwendung% einer Backward-Regel.% Reduziere weiter.% Keine Reduktion mehr möglich.

% Backward-Regel.% Linksrekursive Backward-Regel.% ...weitere Backward-Regeln.% Lexikon-Zugriff.

17.04.2000 Parsing 12

Problem: Leere Kategorien

• Bottom-Up-Strategie loopt bei leeren Kategorien.

Det .

• Auswege– Leere Kategorien vermeiden.– Left-Corner-Strategie mit Linking.

17.04.2000 Parsing 13

Left-Corner-Algorithmus

Um eine Konstituente von Typ C zu Parsen1. Nimm das erste Wort der Kette mit Kategorie W.

2. Vervollständige Ca) falls C=W: fertig

b) sonst:i. Finde eine Regel mit W als linker Ecke (erstes Element der

rechten Seite) und Mutter M.

ii. Parse die Schwestern von W.

iii. Ersetze W durch M und gehe zu Schritt 2.

17.04.2000 Parsing 14

Left-Corner-Traversierung

S1

NP4 VP7/10

D3 N5 V9 NP11/14

D13 N15

the2 dog6 chased8 the12 cat16

nach Covington 1994

17.04.2000 Parsing 15

Left-Corner-Traversierung

S1

NP6 VP7

D3 N4 V9 NP10

D12 N13

the2 dog5 chased8 the11 cat14

nach Rumpf

17.04.2000 Parsing 16

Left-Corner-Parserlcp(C,[Word|S2],S):- word(W,Word), complete(W,C,S2,S).

complete(C,C,S,S).complete(W,C,S1,S):- rule(P,[W|Rest]), lc_sisters(Rest,S1,S2), complete(P,C,S2,S).

lc_sisters([C|Cs],S1,S):- lcp(C,S1,S2), lc_sisters(Cs,S2,S).lc_sisters([],S,S).

% Nimm erstes Wort der Kette.% Bestimme Kategorie.% Vervollständige Kette.

% Akt. Kat = erwartet.% Akt. Kat \= erwartet.% Akt. Kat ist linke Ecke.% Parse LC-Schwestern.% Vervollständige Kette.

% Aktuelle Schwester ist% Mutter eines Teilbaums.% Parse übrige Schwestern.% Alle Töchter geparst.

17.04.2000 Parsing 17

Problem: Leere Kategorien

• Erweiterung für leere Kategorien:lcp(C,S2,S):- rule(W,[]), complete(W,C,S2,S).

• Problem: Left-Corner-Strategie loopt beim Backtracking, da beliebig viele leere Kategorien eingebaut werden können.

• Ausweg: Linking

17.04.2000 Parsing 18

Linking

• Die Linke-Ecke-Relation bestimmt die erste Konstituente in der Expansion einer Phrase.

• Die Linking-Relation ist die reflexive, transitive Hülle der Linke-Ecke-Relation.

S NP VPNP D NVP V NP

le(np, s)le(d, np)le(v, vp)

link(np, s).link(d, np).link(d, s).link(v, vp).link(X, X).

17.04.2000 Parsing 19

LC-Parser mit Linking

lcp(C,[Word|S2],S):- word(W,Word), link(W,C), complete(W,C,S2,S).

lcp(C,S2,S):- rule(W,[]), link(W,C), complete(W,C,S2,S).

17.04.2000 Parsing 20

Literatur

• Covington, Michael A. (1994): Natural Language Processing for Prolog Programmers. Chap. 6: Parsing Algorithms. Prentice-Hall.

• Gazdar, Gerald & Chris Mellish (1989): Natural Language Processing in Prolog. Addison Wesley.