Definite Clause Grammars

DCGs are Prolog's built-in notation for parsing and generating sequences — one of its most elegant features.

DCGs are Prolog's built-in notation for parsing and generating sequences — one of its most elegant features.

19.1 Basic grammar

DCG rules translate into ordinary predicates with two extra arguments (a difference list):

greeting --> [hello], name.
name --> [world].
name --> [prolog].

?- phrase(greeting, [hello, world]).    % true
?- phrase(greeting, X).                 % X = [hello, world] ; X = [hello, prolog]

greeting(S0, S) :- S0 = [hello|S1], name(S1, S).

19.2 Arguments, pushback, and Prolog goals

% Parse a number into its value
digits([D|T]) --> digit(D), digits(T).
digits([D]) --> digit(D).
digit(D) --> [D], { code_type(D, digit) }.     % { } embeds plain Prolog

integer(N) --> digits(Ds), { number_codes(N, Ds) }.

?- phrase(integer(N), `123`).                  % N = 123

19.3 Building parse trees

sentence(s(NP, VP)) --> noun_phrase(NP), verb_phrase(VP).
noun_phrase(np(D, N)) --> det(D), noun(N).
verb_phrase(vp(V, NP)) --> verb(V), noun_phrase(NP).
det(d(the)) --> [the].
det(d(a)) --> [a].
noun(n(cat)) --> [cat].
noun(n(dog)) --> [dog].
verb(v(chases)) --> [chases].

?- phrase(sentence(T), [the, cat, chases, a, dog]).
T = s(np(d(the), n(cat)), vp(v(chases), np(d(a), n(dog)))).

19.4 Arithmetic expression parser & evaluator

(Left recursion is avoided with the "rest" pattern.)

:- set_prolog_flag(double_quotes, codes).

expr(V) --> term(T), expr_rest(T, V).
expr_rest(Acc, V) --> "+", !, term(T), { A1 is Acc + T }, expr_rest(A1, V).
expr_rest(Acc, V) --> "-", !, term(T), { A1 is Acc - T }, expr_rest(A1, V).
expr_rest(V, V) --> [].

term(V) --> factor(F), term_rest(F, V).
term_rest(Acc, V) --> "*", !, factor(F), { A1 is Acc * F }, term_rest(A1, V).
term_rest(Acc, V) --> "/", !, factor(F), { A1 is Acc / F }, term_rest(A1, V).
term_rest(V, V) --> [].

factor(V) --> "(", !, expr(V), ")".
factor(V) --> integer(V).

?- phrase(expr(V), "2*(3+4)-5").     % V = 9

19.5 Useful DCG tools (SWI library(dcg/basics))

library(dcg/high_order): sequence//3, sequence//5 (e.g. comma-separated lists).

:- use_module(library(dcg/basics)).
% blanks//0, blank//0, white//0, digits//1, integer//1, number//1, float//1,
% string//1, string_without//2, remainder//1, eos//0, nonblanks//1, csym//1
line(Key-Value) --> string_without(`=`, K), "=", remainder(V),
                    { atom_codes(Key, K), atom_codes(Value, V) }.

19.6 Pushback & call//N

look_ahead(X), [X] --> [X].       % pushback: peek without consuming
any(N) --> call(take(N)).         % call//N invokes a DCG non-terminal as a closure

19.7 Parsing files

:- use_module(library(pio)).
?- phrase_from_file(lines(Ls), 'data.txt').   % lazy parsing of a file with a DCG

19.8 Generating with DCGs

Because DCGs are relations, the same grammar can generate sentences, enumerate languages, and produce output strings (e.g., pretty-printers, code generators).