Prolog DCGs: Declarative Parsing That Also Generates

The problem: parsing and generation are usually separate

Most parser generators (Yacc, ANTLR, PEG libraries) produce a recognizer that consumes input and builds a tree. If you also need to generate valid strings from the same grammar—say, for testing or pretty-printing—you typically write a second, hand-coded serializer. Prolog’s Definite Clause Grammars (DCGs) avoid that duplication: one declarative grammar both parses and generates, and the compiler turns it into efficient difference-list code.

How DCGs work under the hood

A DCG rule uses the --> operator instead of :-. The rule sentence --> noun, verb. is syntactic sugar for a predicate that threads two implicit list arguments: an input list and an output list. This difference-list technique lets the parser consume tokens from the front of the input while leaving the remainder in the output, all without manual accumulator passing.

The built-in phrase/2 and phrase/3 predicates drive the grammar. phrase(Grammar, Input) succeeds only when Grammar consumes all of Input. phrase(Grammar, Input, Rest) succeeds when Grammar consumes a prefix, leaving Rest as the unconsumed suffix. The same call can be used with variables in Input to generate sentences.

Worked example: arithmetic expressions with an AST

The following grammar parses a tiny arithmetic language and builds an abstract syntax tree (AST) in the same pass. Save it as expr.pl and load it in SWI-Prolog, GNU Prolog, or any ISO-compliant system.

% expr.pl
expr(Val) --> term(T), expr_tail(T, Val).
expr_tail(In, Out) --> [+], term(T), expr_tail(In+T, Out).
expr_tail(In, Out) --> [-], term(T), expr_tail(In-T, Out).
expr_tail(Val, Val) --> [].

term(Val) --> factor(F), term_tail(F, Val).
term_tail(In, Out) --> [*], factor(F), term_tail(In*F, Out).
term_tail(In, Out) --> [/], factor(F), term_tail(In/F, Out).
term_tail(Val, Val) --> [].

factor(N) --> [N], { number(N) }.
factor(Val) --> ['('], expr(Val), [')'].

Each rule returns a value through its explicit argument (Val, In, Out). The curly-brace goals { number(N) } are semantic actions—ordinary Prolog goals that run during parsing without consuming tokens. They let us constrain tokens, build structures, or call arbitrary code.

To parse a token list:

?- phrase(expr(AST), [1, '+', 2, '*', 3]).
AST = 1+(2*3).

To generate all expressions that evaluate to 5 (with a small search bound):

?- length(Tokens, _), phrase(expr(5), Tokens).
Tokens = [5] ;
Tokens = [1, '+', 4] ;
Tokens = [2, '+', 3] ;
... % more solutions on backtracking

The same grammar drives both directions because DCGs are pure relations.

Trade-offs you will hit

• Left recursion loops. A rule like expr --> expr, [+], term causes infinite recursion in standard SLD resolution. Either rewrite to right recursion (as above) or enable tabling: :- table expr//1. in SWI-Prolog or XSB.
• Cut (!) breaks threading. The implicit difference-list arguments are not visible, so a cut inside a DCG can prune alternatives that the caller expects. Use \+/1 or (Condition -> Then ; Else) for deterministic choices.
• Error locations require extra work. DCGs only report success or failure. To report line/column numbers, thread a position counter as an extra argument (or use library(dcg/basics) which provides prolog_var_name//1 and similar helpers).
• Portability of libraries. The --> syntax and basic expansion are ISO standard. phrase/3, library(dcg/basics), and library(dcg/high_order) are de-facto extensions present in SWI, SICStus, Scryer, and Trealla but not guaranteed everywhere.

What to try next

1. Create expr.pl above and run swipl -q -f expr.pl -g "phrase(expr(A), [1,+,2]), writeln(A), halt" to see the AST printed.
2. Add :- table expr//1. and test a left-recursive version to confirm termination.
3. Inspect the compiled clauses with listing(expr//1). to see the generated difference-list code.
4. Explore library(dcg/high_order) for combinators like sequence//2 and foldl//4 that let you compose grammars without leaving DCG notation.

DCGs give you a single source of truth for syntax, parsing, and generation. For small-to-medium languages they are often faster to develop and easier to maintain than a separate parser generator plus serializer.