Parametrisierte DCGs
Prolog Grundkurs WS 99/00
Christof Rumpf
[email protected]
Kontextfreie Sprachen
DCGs ohne Parameter entsprechen den
kontextfreien Grammtiken der ChomskyHierarchie.
Die folgende DCG erkennt die kontextfreie
Sprache anbn , n  0 :
s --> [].
s --> [a], s, [b].
20.12.99
GK Prolog - Parametrisierte DCGs
2
Reguläre Sprachen
Durch Beschränkung der Regeln auf die Form
VN × VT VN  VN × VT
kann man mit DCGs reguläre Grammatiken
schreiben. Die folgende DCG erkennt die reguläre
Sprache a*b*: s --> [].
s --> [a], s.
s --> [b], b.
b --> [].
b --> [b], b.
20.12.99
GK Prolog - Parametrisierte DCGs
3
Kontextsensitive Sprachen
Parametrisierte DCGs sind in der Lage, kontextsensitive Sprachen zu erkennen. Die folgende DCG
erkennt die kontextsensitive Sprache anbncn, n  0:
s --> a(I), b(I), c(I).
a(i) --> [].
a(i(I)) --> [a], a(I).
b(i) --> [].
b(i(I)) --> [b], b(I).
c(i) --> [].
c(i(I)) --> [c], c(I).
20.12.99
GK Prolog - Parametrisierte DCGs
4
Rekursiv aufzählbare Sprachen
Mit parametrisierten DCGs können selbst rekursiv
aufzählbare Sprachen erkannt werden. Zum
Beweis implementiere man eine allgemeine
Turing-Maschine mit einer DCG.
Repräsentiere
– Zustände als Konstituenten
– Band als Listen-Parameter
20.12.99
GK Prolog - Parametrisierte DCGs
5
Schweitzerdeutsch
Das Schweizerdeutsche zeigt sogenannte
kreuzserielle Abhängigkeiten zwischen Verben und
NPs, die den kontextfreien Rahmen sprengen.
Claudia Helmut Eva Hans Ulrike watched let help make work.
NP1
NP2
NP3 NP4 NP5 V1
V2 V3 V4 V5
Claudia beobachtete, wie Helmut Eva Hans helfen ließ, Ulrike
zum arbeiten zu bringen.
n
m
n
m
Sortiert nach akk/dat-Zuweisung: NPakk
NPdat
Vakk
Vdat
20.12.99
GK Prolog - Parametrisierte DCGs
6
Generierung von Syntaxbäumen
Zusätzliche Argumente von DCGs können
verwendet werden, um beim Parsen einer Kette den
entsprechenden Ableitungsbaum zu erzeugen.
?- s(T,[paul,klaut,bananen],[]).
T = s(np(paul),vp(v(klaut),np(bananen)))
yes
20.12.99
GK Prolog - Parametrisierte DCGs
7
Baum als Struktur
s(s(NP,VP)) -->
np(NP,Num), vp(VP,Num).
vp(vp(V,NP),Num) -->
v(V,Num), np(NP,_).
v(v(klaut),
sg)
v(v(klauen),
pl)
np(np(paul),
sg)
np(np(bananen),pl)
20.12.99
-->
-->
-->
-->
[klaut].
[klauen].
[paul].
[bananen].
GK Prolog - Parametrisierte DCGs
8
Baum als Liste
s([s,NP,VP]) -->
np(NP,Num), vp(VP,Num).
vp([vp,V,NP],Num) -->
v(V,Num), np(NP,_).
v([v,[klaut]],
sg)
v([v,[klauen]],
pl)
np([np,[paul]],
sg)
np([np,[bananen]],pl)
20.12.99
-->
-->
-->
-->
GK Prolog - Parametrisierte DCGs
[klaut].
[klauen].
[paul].
[bananen].
9
Parsen mit Baum-Ausgabe
Eine DCG mit Syntaxbaumgenerierung kann mit
einem Pretty-Printer gekoppelt werden, um einen
Parser mit Ausgabe zu erhalten.
parse(Sentence):s(Tree,Sentence,[]),
pp(Tree).
20.12.99
GK Prolog - Parametrisierte DCGs
10
Verarbeitung von Testsätzen
Zum Testen einer Grammatik wird oft eine Menge
von Testsätzen benötigt, die man am besten als
Fakten in der Datenbasis ablegt.
ex(1,[maria,sieht,den,mann]).
ex(2,[maria,sieht,dem,mann]).
ex(3,...
test(N):ex(N,S), write(S), nl,
parse(S).
20.12.99
GK Prolog - Parametrisierte DCGs
11
Testen von Teilphrasen
Eine Grammatik besteht neben dem Lexikon aus
einer Menge von Phrasenstrukturregeln. Bei der
Grammtikentwicklung ist es oft sinnvoll, die
Regeln für Teilphrasen gezielt zu testen, bevor
man ganze Sätze parst. Dadurch werden Fehler
i.d.R. viel schneller gefunden.
?- pp([mit,dem,teleskop],[]).
20.12.99
GK Prolog - Parametrisierte DCGs
12
Metavariablen
Weder unser parse/1 noch test/1 sind
geeignet, um Teilphrasen zu verarbeiten. Lösung:
Aufruf der DCG über Metavariablen mit dem
eingebauten Prädikat call/1.
ex(1,s([maria,sieht,den,mann],[])).
ex(2,pp([im,park],[])).
ex(3,...
test(N):ex(N,G), write(G), nl, call(G).
20.12.99
GK Prolog - Parametrisierte DCGs
13
Analyse vs. Generierung
Der Aufruf eines Parsers mit einer gegebenen
Kette setzt einen Analyseprozeß in Gang. Das
Ergebnis der Analyse ist ein Grammatikalitätsurteil über die Kette bezüglich der Grammatik.
Der Aufruf eines Parsers mit einer Variablen
bewirkt die Generierung von grammatischen
Ketten (bezüglich der Grammatik!).
20.12.99
GK Prolog - Parametrisierte DCGs
14
Korrektheit und Vollständigkeit
Korrektheit und Vollständigkeit von Grammatiken
versucht man durch Testen zu ermitteln. Dazu
analysiert man eine Menge geeigneter Testsätze, die
auch ungrammatische Sätze enthalten sollte, bzw.
generiert Sätze und beurteilt deren Grammatikalität.
– Korrektheit: Es werden nur grammatische Ketten
analysiert/generiert.
– Vollständigkeit: Es werden alle grammatischen
Ketten analysiert/generiert.
20.12.99
GK Prolog - Parametrisierte DCGs
15
Generierung rekursiver Phrasen
Rekursive Regeln können beliebig lange Ketten
generieren. Beim Testen von Grammatiken auf
generative Kapazität bereitet das top-down depthfirst-Verfahren des Interpreters Probleme, da die
erste Ableitung beliebig oft iteriert wird und
Alternativen unberücksichtigt bleiben.
Maria sieht den Mann im Park im Park im Park
im Park im Park im Park ...
20.12.99
GK Prolog - Parametrisierte DCGs
16
Beschränkung der Kettenlänge
Durch die Bindung einer Kette an eine Liste definiter
Länge kann die Generierung redundanter Iterationen
vermieden werden.
?- S = [_,_,_,_,_,_,_,_,_], s(S,[]).
S=[maria,sieht,den,mann,im,park,mit,dem,teleskop]->;
S=[maria,sieht,den,mann,mit,dem,teleskop,im,park]->;
S=[maria,mit,dem,teleskop,sieht,den,mann,im,park]->;
...
20.12.99
GK Prolog - Parametrisierte DCGs
17
Generierung von Listen
Die Generierung von Listen definiter Länge kann
automatisiert und für einen „Phrasengenerator“
verwendet werden.
genlist(0,[]).
genlist(N,[_|T]):N > 0, M is N-1, genlist(M,T).
generate(N):- genlist(N,S), parse(S).
20.12.99
GK Prolog - Parametrisierte DCGs
18
Fail-Loop
Mit Hilfe eines Fail-Loops kann ein Generator
definiert werden, der alle Phrasen einer festen
Länge ohne Benutzerinteraktion generiert und
ausgibt.
generateall(N):genlist(N,S), s(S,[]), write(S), nl,
fail.
generateall(_).
20.12.99
GK Prolog - Parametrisierte DCGs
19
Zählschleife
Mit einer Zählschleife definieren wir einen
Generator, der alle Phrasen ausgibt, deren Länge in
einem gegebenen Intervall liegt.
generateall(Max,Max):- generateall(Max).
generateall(N,Max):N < Max, M is N+1,
generateall(N),
generateall(M,Max).
20.12.99
GK Prolog - Parametrisierte DCGs
20
Pretty-Printer für Ketten
Unser Generator kann noch etwas attraktiver
gestalten werden, indem eine Ausgabe der Ketten
ohne Listenklammern und Kommata eingebaut wird.
print_phrase([]):- nl.
print_phrase([Word|Words]):tab(1),write(Word),
print_phrase(Words).
?- print_phrase([maria,sieht,den,mann]).
maria sieht den mann
20.12.99
GK Prolog - Parametrisierte DCGs
21
Dateiausgabe
Die Ausgabe komplexer Syntaxbäume oder
größerer Mengen von generierten Sätzen läßt den
Bildschirm des Arity\Prolog-Interpreters als
ungeignetes Ausgabemedium erscheinen, da man
nicht zurückblättern kann. Auch möchte man
manchmal Programm-Ausgaben dauerhaft
dokumentieren. Dazu benötigen wir Mittel, um
eine Ausgabe in eine Datei umzuleiten.
20.12.99
GK Prolog - Parametrisierte DCGs
22
tell/1 und told/0
Das eingebaute Prädikat tell/1 öffnet eine
Datei und setzt einen Zeiger auf den Dateianfang.
Der Dateiname muß als atomares Argument
spezifiziert sein.
Das eingebaute Prädikat told/0 schließt die
Datei, die als letztes geöffnet wurde. Wird
told/0 nach einem Aufruf von tell/1 nicht
ausgeführt, stürzt Prolog ab.
20.12.99
GK Prolog - Parametrisierte DCGs
23
file_output/2
Das Prädikat file_output/2 leitet alle
Ausgaben in eine Datei File um, die während
der Ableitung eines Aufrufs Goal erfolgen.
file_output(File,Goal):tell(File),
(call(Goal) ; true),
told.
20.12.99
GK Prolog - Parametrisierte DCGs
24

Document