EMZETT.
Login

Emzett Wiki

Prolog: DCG, Grammatiken und Sprachverarbeitung

Properties1
tagsprogrammiersprachen, prolog

3 Min. Lesezeit

Kurz: Mit DCG (—>) beschreibt man Grammatiken. Prolog übersetzt sie in Prädikate über Listen:

Teil des Kurses Prolog

Kapitel 6 von 8 im Kurs Prolog. Mit Fortschritt, Quiz und Zertifikat auf der Lernseite.

Definite Clause Grammars

Mit DCG (-->) beschreibt man Grammatiken. Prolog übersetzt sie in Prädikate über Listen:

satz --> nominalphrase, verbalphrase.
nominalphrase --> artikel, nomen.
verbalphrase --> verb, nominalphrase.
verbalphrase --> verb.
artikel --> [der].
artikel --> [die].
nomen --> [hund].
nomen --> [katze].
verb --> [sieht].
verb --> [schlaeft].
 
main :-
    ( phrase(satz, [der, hund, sieht, die, katze]) -> writeln(gueltig) ; writeln(ungueltig) ),
    ( phrase(satz, [hund, der, sieht]) -> writeln(gueltig) ; writeln(ungueltig) ),
    findall(S, (phrase(satz, S), length(S, L), L =< 3), Saetze), writeln(Saetze).

Ausgabe:

gueltig
ungueltig
[[der,hund,sieht],[der,hund,schlaeft],[der,katze,sieht],[der,katze,schlaeft],[die,hund,sieht],[die,hund,schlaeft],[die,katze,sieht],[die,katze,schlaeft]]

Zahlen parsen

DCGs eignen sich gut zum Zerlegen von Text:

:- use_module(library(dcg/basics)).
 
zahlenliste([Z|Rest]) --> integer(Z), ( "," -> zahlenliste(Rest) ; { Rest = [] } ).
 
ausdruck(W) --> term(T), ausdruck_rest(T, W).
ausdruck_rest(Acc, W) --> "+", term(T), { A1 is Acc + T }, ausdruck_rest(A1, W).
ausdruck_rest(Acc, W) --> "-", term(T), { A1 is Acc - T }, ausdruck_rest(A1, W).
ausdruck_rest(W, W) --> [].
term(W) --> faktor(F), term_rest(F, W).
term_rest(Acc, W) --> "*", faktor(F), { A1 is Acc * F }, term_rest(A1, W).
term_rest(W, W) --> [].
faktor(W) --> integer(W).
faktor(W) --> "(", ausdruck(W), ")".
 
main :-
    phrase(zahlenliste(L), `1,22,333`), writeln(L),
    phrase(ausdruck(W), `2+3*(4-1)`), writeln(W),
    ( phrase(ausdruck(_), `2+*3`) -> writeln(ok) ; writeln('Syntaxfehler') ).

Ausgabe:

[1,22,333]
11
Syntaxfehler

Mit Argumenten und Parsebäumen

satz(s(NP, VP)) --> np(NP), vp(VP).
np(np(Art, N)) --> art(Art), n(N).
vp(vp(V, NP)) --> v(V), np(NP).
art(art(der)) --> [der].
art(art(die)) --> [die].
n(n(hund)) --> [hund].
n(n(katze)) --> [katze].
v(v(jagt)) --> [jagt].
 
main :-
    phrase(satz(Baum), [der, hund, jagt, die, katze]),
    print(Baum), nl,
    findall(S, phrase(satz(_), S), Alle),
    length(Alle, N), format("~d mögliche Sätze~n", [N]).

Ausgabe:

s(np(art(der),n(hund)),vp(v(jagt),np(art(die),n(katze))))
16 mögliche Sätze

Operatoren und eigene Syntax

Prolog erlaubt eigene Operatoren, mit denen Programme wie Fachsprachen lesen:

:- op(700, xfx, ist_groesser_als).
:- op(200, xfy, und).
 
mia ist_groesser_als tom.
tom ist_groesser_als ben.
 
transitiv(A, B) :- A ist_groesser_als B.
transitiv(A, C) :- A ist_groesser_als B, transitiv(B, C).
 
main :-
    ( transitiv(mia, ben) -> writeln('mia ist größer als ben') ; true ),
    X = (a und b und c), writeln(X),
    X =.. Liste, writeln(Liste),
    functor(f(a, b), Name, Stelligkeit), writeln(Name/Stelligkeit),
    T =.. [punkt, 1, 2], writeln(T),
    arg(2, T, Zweites), writeln(Zweites).

Ausgabe:

mia ist größer als ben
a und b und c
[und,a,b und c]
f/2
punkt(1,2)
2

Merke

  • DCG-Regeln (-->) beschreiben Grammatiken; phrase/2 startet das Parsen
  • Argumente in DCGs bauen Parsebäume oder berechnen Werte
  • library(dcg/basics) bietet integer//1, blanks//0, string//1 und mehr
  • Eigene Operatoren (op/3) und =.. erlauben meta-programmierung

Übungsaufgabe

Erweitere den Ausdrucksparser um Division und Leerzeichen.

Quiz zur Selbstkontrolle

Weiter im Kurs

Zurück: Klassische Probleme lösen

Weiter: Module, Ein-/Ausgabe und Ökosystem

Alle Kapitel: Prolog im Überblick

Graphansicht

Backlinks