Learn

DCG (Definite Clause Grammars) is Prolog's built-in parsing notation. Grammar rules look like context-free grammar — but compile to ordinary Prolog clauses with two extra arguments (input and remaining).

Basic DCG

%% A digit
digit(D) --> [D], { code_type(D, digit) }.

%% Several digits
digits([D|Rest]) --> digit(D), digits(Rest).
digits([D]) --> digit(D).

%% Number = digits
number(N) --> digits(Cs), { number_codes(N, Cs) }.

The --> is the DCG operator. It's syntactic sugar — the compiler adds two args ("difference list") for the input stream.

Calling a DCG:

?- phrase(number(N), "42").
N = 42.

?- phrase(number(N), [0'4, 0'2]).
N = 42.

phrase/2 runs the grammar against an input list.

Curly braces — call regular Prolog

foo --> [X], { writeln(X) }.

Inside { }, you call ordinary Prolog. Outside, you're matching the input.

Example: Simple expression parser

%% Numbers
num(N) --> digits(Cs), { number_codes(N, Cs) }.
digits([D|Rest]) --> [D], { D >= 0'0, D =< 0'9 }, digits(Rest).
digits([D]) --> [D], { D >= 0'0, D =< 0'9 }.

%% Expression: number + number
expr(X + Y) --> num(X), " + ", num(Y).
expr(N) --> num(N).

?- phrase(expr(E), "3 + 4").
E = 3 + 4.

Why DCGs matter

• Cleaner than manual char-by-char parsing
• Reversible — sometimes you can use the same grammar for parsing AND generation
• Built into ISO Prolog — no library needed

Pushback (input lookahead)

DCGs can use lookahead with \+:

ident([C|Rest]) --> [C], { code_type(C, alpha) }, ident_rest(Rest).
ident_rest([C|Rest]) --> [C], { code_type(C, csym) }, ident_rest(Rest).
ident_rest([]) --> [].

Modern alternatives

• PEG parsers in dedicated libraries
• tokenize for simple lexing in SWI-Prolog
• Marpa for ambiguous grammars

For most parsing tasks in Prolog, DCGs are the right tool. They're particularly natural for natural language and small DSLs.