LbP Definite Clause Grammars

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Einführung 2 Konventionelle Repräsentation kfG in Prolog 3 DCG für obige Grammatik 4 DCGs mit Argumenten

Einführung

Die Verarbeitung kontextfreier Grammatiken (kfG) war eine der ersten Anwendungen, für die Colmerauer Prolog benutzt hat. Es ist daher nicht verwunderlich, dass ein Interpreter für kfG - als syntaktischer Zucker - in Prolog integriert wurde. Es handelt sich in Wirklichkeit um einen Übersetzer, der eine Grammatik in Gestalt einer definite clause grammar (DCG) nimmt und (automatisch, d.h. direkt beim Einlesen der Datei) in Prolog-Regeln umwandelt. Die Idee der DCGs geht auf Fernando Peiera und David H.D. Warren (1980) zurück.

Wir betrachten zunächst ein Beispiel, das ohne DCG auskommt. Gegeben sei eine kfG in BNF-Syntax.

G = ({sentence, noun_phrase, verb_phrase},               // Nichtterminale
     {evelyn, chris, sings, jogs, loves},                // Terminale
     {sentence    -> noun_phrase verb_phrase             // Produktionen
      noun_phrase -> evelyn | chris
      verb_phrase -> sings | jogs | loves noun_phrase}
     sentence)                                           // Spitzensymbol

Der Satz evelyn loves chris gehört natürlich zu .

Konventionelle Repräsentation kfG in Prolog

Die Regeln des folgenden Prolog-Programms sind so aufgebaut, dass für das jeweils erste Listenelement geprüft wird, ob es der entsprechenden Kategorie angehört. Die Restliste wird weitergereicht. Am Ende muss die Analyse für den gesamten Satz stattgefunden haben, deshalb erfolgt der Aufruf mit der leeren Liste als zweites Argument.

sentence(List, Rest) :- noun_phrase(List, Rest1), verb_phrase(Rest1, Rest). noun_phrase([evelyn|Rest], Rest). noun_phrase([chris|Rest], Rest). verb_phrase([sings|Rest], Rest). verb_phrase([jogs|Rest], Rest). verb_phrase([loves|Rest1], Rest) :- noun_phrase(Rest1, Rest).

Die Prolog-Anfrage lautet

sentence([evelyn, loves, chris], []).

ausführen

DCG für obige Grammatik

Offensichtlich ist die Weiterreichung der jeweiligen Restliste in obigem Programm eher technisch bedingt, um eine elementweise Analyse zu gewährleisten. Insbesondere in sentence sieht man sehr genau, wo das erste Argument List und das zweite Argument Rest im Regelkörper auftauchen müssen.

Diese Zwangsläufigkeit kann für eine allgemeine Transformation der Grammatik in einer davon abstrahierenden Syntax, der DCG, in Prolog ausgenützt werden. Man braucht diesen Übersetzer nicht selbst zu schreiben, er existiert für die gängigen Prolog-Systeme. Es ist aber nicht sicher, dass die Implementation dieses Übersetzers in allen Prologsystemen identisch ist.

Eine zugehörige DCG-Version für G ist

sentence --> noun_phrase, verb_phrase. noun_phrase --> [evelyn]. noun_phrase --> [chris]. verb_phrase --> [sings]. verb_phrase --> [jogs]. verb_phrase --> [loves], noun_phrase.

Dies kommt der BNF doch recht nahe. Da sich DCG und obiges konventionelles Prolog-Programm lediglich durch die Transformation unterscheiden, überrascht es nicht, dass der Aufruf ebenso lautet.

sentence([evelyn, loves, chris], []).

ausführen

Die obige DCG-Satz wurde in folgendes Prolog-Programm umgewandelt:

sentence(A, B) :- noun_phrase(A, C), verb_phrase(C, B). noun_phrase([evelyn|A], A). noun_phrase([chris|A], A). verb_phrase([sings|A], A). verb_phrase([jogs|A], A). verb_phrase(A, B) :- 'C'(A, loves, C), noun_phrase(C, B).

Das darin enthaltene Prädikat 'C' ist append/3 ganz ähnlich.

Beispiel

URL's parsing: Das folgende Beispiel demonstriert, dass (neben Listen) auch Zeichenketten zur Repräsentation von Sätzen verwendet werden können. Diese werden bei der weiteren Verarbeitung in Listen umgewandelt. Die Elemente dieser Listen sind die zugehörigen ASCII-Zahlencodes der auftretenden Zeichen.

url --> transport, "://", machine, "/", path.
url --> "file:/", path.

transport --> "http".
transport --> "ftp".

machine --> ident, dot_idents.

dot_idents --> [].
dot_idents --> ".", ident, dot_idents.

path --> [].
path --> ident.
path --> ident, "/", path.

ident --> char.
ident --> char, ident.

char --> [X], {97 =< X, X =< 122}.

Dies wird umgewandelt zu:

url(A, B) :- transport(A, C), append([58, 47, 47], D, C), machine(D, E), 'C'(E, 47, F), path(F, B). url(A, B) :- append([102, 105, 108, 101, 58, 47], C, A), path(C, B). transport([104, 116, 116, 112|A], A). transport([102, 116, 112|A], A). machine(A, B) :- ident(A, C), dot_idents(C, B). dot_idents(A, A). dot_idents(A, B) :- 'C'(A, 46, C), ident(C, D), dot_idents(D, B). path(A, A). path(A, B) :- ident(A, B). path(A, B) :- ident(A, C), 'C'(C, 47, D), path(D, B). ident(A, B) :- char(A, B). ident(A, B) :- char(A, C), ident(C, B). char(A, B) :- 'C'(A, C, D), 97 =< C, C =< 122, B = D.

Nun wollen wir feststellen, ob die folgende Zeichenkette eine nach der oben definierten kfG korrekte URL ist.

url("http://www.cs.indiana.edu/pub/scheme", []).

ausführen

(Fehler: Die URL sollte eigentlich korrekt sein!)

Bei komplexeren Beispielen ist die Verwendung eines zweistufigen Verfahrens angezeigt: Auf lexikalischer Ebenso sorgt ein Scanner für das Tokenizing. Die entstehende Token-Liste wird mit einer Token-Grammatik geparst. Dies ist das bei Compilern übliche Verfahren. Dies würde sich im Beispiel für ident anbieten, so dass dafür ein evtl. gleichnamiges Token verwendet werden könnte.

DCGs mit Argumenten

Argumente in DCG können beispielsweise benutzt werden, um die zu einem erfolgreichen Parsing gehörende abstrakte Syntax (Stichwort: AST) explizit zu machen. Dafür ist eine geeignete Repräsentation erforderlich, die man durch die Positionierung der Argumente beeinflussen kann.

sentence(Meaning) --> noun_phrase(Subject), verb_phrase(Subject, Meaning). noun_phrase(evelyn) --> [evelyn]. noun_phrase(chris) --> [chris]. verb_phrase(Subject, sings(Subject)) --> [sings]. verb_phrase(Subject, jogs(Subject)) --> [jogs]. verb_phrase(Subject, loves(Subject, Object)) --> [loves], noun_phrase(Object).

Aufrufbeispiel:

sentence(X, [evelyn, loves, chris], []).

ausführen