7: DCGs

Zu den Aufgaben Folien ansehen Musterlösungen herunterladen

Eine formale Grammatik besteht aus

einem Alphabet von Terminalsymbolen Σ (den Symbolen der beschriebenen Sprache)
einer Menge von Nichtterminalsymbolen N (unseren Hilfssymbolen)
einem Startsymbol S ∈ N
einer Menge von Regeln der Form α → β, wobei α und β Ketten von Symbolen aus Σ ∪ N sind.

Grammatiken sind endliche Regelsysteme.
Die Menge aller Ketten, die von einer Grammatik generiert werden, bilden die von der Grammatik beschriebene formale Sprache (das sind alle Ketten von Terminalsymbolen, die man aus dem Startsymbol durch sukzessive Regelanwendung gewinnen kann).

kontextfreie Grammatiken

Eine formale Grammatik in der jede linke Regelseite aus genau einem
Nichtterminalsymbol besteht heißt kontextfrei.
Beispiel:
G = ({S,NP,VP,N,V,Det}, {eine, die, keine, katze, maus, jagt klaut}, S, P)

Chomskyhierarchie & Automaten (grober Überblick)

Grammatik 1 ohne Listen

% Grammatikregel:
s(W1,W2,W3,W4,W5):-
    det(W1),
    n(W2),
    v(W3),
    det(W4),
    n(W5).
% Lexikon:
det(eine).
det(die).
det(keine).
n(maus).
n(katze).
v(jagt).
v(klaut).

Vorteile

• effiziente Implementierung

Nachteile

Es werden keinerlei Generalisierungen erfasst.
Pro Satzlänge wird eine eigenes Satzprädikat s(W1,…,Wn) benötigt.
Rekursive Strukturen können nicht erfasst werden (z.B. „Die alte, schöne, hungrige, …,verrückte, gemeine katze klaut die maus’“).

Grammatik 2 mit Listen und append/3 am Ende

% Grammatikregeln,
% append/3 am Ende:
s(L3):-
    np(L1),
    vp(L2),
    append(L1,L2,L3).
np(L3):-
    det(L1),
    n(L2),
    append(L1,L2,L3).
vp(L3):-
    v(L1),
    np(L2),
    append(L1,L2,L3).
% Lexikon:
det([eine]).
det([die]).
det([keine]).
n([maus]).
n([katze]).
v([jagt]).
v([klaut]).

Vorteile

Grammatische Generalisierungen werden erfasst
Direkte Übertragung einer kontextfreien Grammatik in dieses Format ist möglich

Nachteile

Sehr ineffizient:
- es werden zunächst beliebige NPs und VPs generiert,
- anschließend werden sie konkateniert, dann wird geprüft, ob sie gleich der zu überprüfenden Kette sind.

Grammatik 3 mit Listen und append/3 am Anfang

% Grammatikregeln,
% append/3 am Anfang:
s(L3):-
    append(L1,L2,L3),
    np(L1),
    vp(L2).
np(L3):-
    append(L1,L2,L3),
    det(L1),
    n(L2).
vp(L3):-
    append(L1,L2,L3),
    v(L1),
    np(L2).
% Lexikon:
det([eine]).
det([die]).
det([keine]).
n([maus]).
n([katze]).
v([jagt]).
v([klaut]).

Vorteile

Grammatische Generalisierungen werden erfasst
Direkte Übertragung einer kontextfreien Grammatik in dieses Format ist möglich

Nachteile

Nicht zur Generierung geeignet. Loopt sobald beim backtracking auf append/3 in der np-Klausel, die die NP innerhalb der VP generiert, das erste Mal eine Präfixliste generiert wird, die länger ist als 1.
Immer noch sehr ineffizient:
- es werden zunächst beliebige Zerlegungen des Satzes generiert,
- anschließend wird geprüft, ob die erste Teilkette eine NP und die zweite eine VP bildet

Grammatik 4 mit Differenzlisten

% Grammatikregeln:
s(A,C):-
    np(A,B),
    vp(B,C).
np(A,C):-
    det(A,B),
    n(B,C).
vp(A,C):-
    v(A,B),
    np(B,C).
% Lexikon:
det([eine|A],A).
det([die|A],A).
det([keine|A],A).
n([maus|A],A).
n([katze|A],A).
v([jagt|A],A).
v([klaut|A],A).

Vorteile

Grammatische Generalisierungen werden erfasst
Direkte Übertragung einer kontextfreien Grammatik in dieses Format ist möglich
Sehr effizient

Nachteile

Differenzlisten sind schwierig zu lesen.
Die Verwendung der vielen Variablen ist unübersichtlich und führt leicht zu Fehlern.

Definite Clause Grammar (DCG)

% Grammatikregeln:
s --> np, vp.
np --> det, n.
vp --> v, np.
% Lexikon:
det --> [eine].
det --> [die].
det --> [keine].
n --> [maus].
n --> [katze].
v --> [jagt].
v --> [klaut].

Vergleiche DCGs mit append_dl/3

Prolog ermöglicht die kompakte Darstellung von Phrasenstrukturgrammatiken als Definite Clause Grammars.
DCG-Klauseln werden intern umgewandelt in Klauseln mit Differenzlisten (siehe vorherige Grammatik 4).
Bei der DCG-Darstellung handelt es sich nur um “notational sugar”. ?- listing(s/2).
Definite Clause Grammars in Prolog entsprechen in ihrer Form den kontextfreien Phrasenstrukturregeln.
DCGs werden beim Laden (consult) eines Prolog- Programms mit Differenzlisten annotiert.

Prologs Parsingstrategie

Linksableitung:

S
NP VP
Det N VP
die N VP
die katze VP
die katze V NP
die katze klaut NP
die katze klaut Det N
die katze klaut die N
die katze klaut die maus

Beispiel:

s –> np, vp.
s([die,katze,klaut,die,maus],[]):-
    np([die,katze,klaut,die,maus],[klaut,die,maus]),
    vp([klaut,die,maus],[]).
np –> det, n.
np([die,katze,klaut,die,maus],[klaut,die,maus]):-
    det([die,katze,klaut,die,maus],[katze,klaut,die,maus]),
    n([katze,klaut,die,maus],[klaut,die,maus]).
det –> [die].
det([die,katze,klaut,die,maus],[katze,klaut,die,maus]).
n –> [katze].
n([katze,klaut,die,maus],[klaut,die,maus]).
vp –> v, np.
vp([klaut,die,maus],[]):-
    v([klaut,die,maus],[die,maus]),
    np([die,maus],[]).
v –> [klaut].
v([klaut,die,maus],[die,maus]).
np –> det,n.
np([die,maus],[]):-
    det([die,maus],[maus]),
    n([maus],[]).
det –> [die].
det([die,maus],[maus]).
n –> [maus].
n([maus],[]).

Ableitungsbaum:

Rechtslineare Grammatiken:

Eine Grammatik ist rechtslinear, wenn jede ihrer Regeln die Form A → a B oder die Form A → a hat (a steht für ein Terminal und A und B für Nichtterminale).
Zu jeder Sprache, die von einer rechtslinearen Grammatik generiert wird, gibt es einen endlichen Automaten, der die Sprache akzeptiert und umgekehrt.
Eine Sprache ist regulär, wenn sie von einer rechtslinearen Grammatik generiert bzw. von einem endlichen Automaten akzeptiert wird.

Beispiel:

Die Sprache a+ b∗ wird von folgender rechtslinearer Grammatik generiert:
S → aS, S → bB, B → , B → bB (Vorsicht: nicht im strengen Sinne rechtslinear
wg. B → e).

% Modellierung als DCG:
s --> [a], s.
s --> [a], bblock.
bblock --> [].
bblock --> [b], bblock.
% externe Repräsentation:
bblock --> [].
bblock --> [b], bblock.
% interne Repräsentation:
bblock(A, A).
bblock([b|A], B) :-
    bblock(A, B).

Beispiel: Sprache a+ b∗

Rekursion: Erweiterung um Adjektive

„eine kleine, kleine, … Maus“

np --> det, adjs, n.
adjs --> [].
adjs --> adj, adjs.
adj --> [kleine].
det --> [eine].
n --> [maus].

?- np(X,[]).
X = [eine,maus] ? ;
X = [eine,kleine,maus] ? ;
X = [eine,kleine,kleine,maus] ? ;
X = [eine,kleine,kleine,kleine,maus] ? ;
X = [eine,kleine,kleine,kleine,kleine,maus] ? ;
X = [eine,kleine,kleine,kleine,kleine,kleine,maus] ? ;
X = [eine,kleine,kleine,kleine,kleine,kleine,kleine,maus] ? ;
X = [eine,kleine,kleine,kleine,kleine,kleine,kleine,kleine,maus] ? ;
...

Linksrekursion

Erweiterung um Konjunktionen:
„Die Maus jagt die Katze und die Katze klaut die Maus.“

s --> s, conj, s.
s --> np, vp.
conj --> [und].

Loopt bei jedem Satz. ⇒ Verbesserung:

s --> np, vp.
s --> s, conj, s.
conj --> [und].

Loopt bei jedem ungrammatischen Satz. ⇒ Verbesserung:

s --> simple_s.
s --> simple_s, conj, s.
simple_s --> np, vp.
conj --> [und].

Diese Technik zur Vermeidung von Linksrekursion nennt man left-corner transform.

Zusammenfassung DCGs

DCGs bieten eine sehr einfache, direkte Methode zur Formulierung
von kontextfreien Grammatiken in Prolog.

Allerdings:

haben wir bisher keine einfache Möglichkeit, Grammatiken um häufige, generelle Phänomene wie Kongruenz zwischen
Konstituenten zu erweitern (z.B. KNG-Kongruenz zwischen Adjektiv und Nomen), haben wir keine Möglichkeit mächtigere Grammatiken als kontextfreie zu formulieren.

⇒ parametrisierte DCGs ermöglichen diese Erweiterungen.

Zusammenfassung

Wir haben gesehen, dass Grammatiken, die append/3 einsetzen
sehr ineffizient sind.
Differenzlisten ermöglichen die Implementierung effizienter Grammatiken.
DCGs bieten eine sehr einfache, direkte Methode zur Formulierung von kontextfreien Grammatiken in Prolog.
DCGs werden intern in Grammatiken mit Differenzlisten übersetzt.