Parsing Small DSLs with Prolog Definite Clause Grammars

When you need to parse a small domain-specific language (DSL) or structured configuration format, spinning up a separate parser-generator toolchain can feel like overkill. Prolog offers a built-in alternative: Definite Clause Grammars, or DCGs. Instead of writing a lexer and parser in a different language, you express the grammar directly as Prolog rules and let the engine's unification (Prolog's pattern matching) and backtracking (its automatic search over rule alternatives) do the work. The practical payoff is that parsing, tokenizing, and semantic checks live in one place, and the same grammar can produce an abstract syntax tree (AST) or evaluate input on the fly.

What a DCG compiles to

DCG rules use the --> operator. To Prolog, they are syntactic sugar for ordinary predicates that operate on difference lists—pairs of lists where the first list is the unconsumed input and the second is the remaining input after parsing. When you write a terminal like ['*'], the compiler inserts code that consumes that token from the input list. When you write a nonterminal like factor(X), it calls the translated predicate. The driver predicate phrase/2 (or phrase/3 for remainder capture) invokes the grammar against a list of codes.

Because the compiled form is just Prolog, you can embed arbitrary goals inside a rule using {Goal}. That means you can evaluate arithmetic, push tokens onto a stack, or even call constraint solvers without leaving the grammar.

A worked arithmetic example

Suppose you want to parse and evaluate 2*(3+4). In a Prolog top level, a compact DCG can do both. First, convert the input to a code list; in SWI-Prolog you can use atom_codes/2 or set the double_quotes flag so that double-quoted strings become code lists. In GNU Prolog and SICStus, explicit conversion is safer because string handling differs.

expr(E)    --> term(T), expr_tail(T, E).
expr_tail(E0, E) --> ['+'], term(T), {E1 is E0 + T}, expr_tail(E1, E).
expr_tail(E, E)  --> [].
term(T)    --> factor(F), term_tail(F, T).
term_tail(F0, F) --> ['*'], factor(F), {F1 is F0 * F}, term_tail(F1, F).
term_tail(F, F)  --> [].
factor(N)  --> number(N).
number(N) --> [D], {code_type(D, digit), N is D - 0'0}.

Running phrase(expr(T), Codes) against the code list for 2*(3+4) should bind T to 14 if the arithmetic succeeds. If you prefer an AST instead of evaluation, replace the {E1 is ...} calls with terms such as bin(op(*), num(2), bin(op(+), num(3), num(4))). Because nonterminals accept arguments, the same grammar skeleton serves both purposes.

The left-recursion limit

The most common DCG pitfall is left recursion. A rule like expr --> expr, ['+'], term. looks natural, but it compiles to a predicate that calls itself before consuming any input. The result is an infinite loop, not a crash. You will notice the query hangs rather than returning false.

The fix is the same one hand-written recursive-descent parsers use: rewrite the rule as right-recursive or iterative. The expr_tail//2 helper above consumes operators left-to-right and accumulates the result, so it terminates. Before scaling up a grammar, test it with a one-token input; if the query loops, you have left recursion.

Error reporting and dialect differences

DCG failure is blunt: phrase/2 simply fails, giving you no line or column number. Production grammars often add a position argument to every nonterminal so that failure can report where parsing stopped. For file input, phrase_from_file/2 (available in some systems) wraps reading and parsing, though custom reporting still requires extra plumbing.

Dialect differences matter. ISO Prolog defines the core DCG syntax, but phrase/3, string handling, and library predicates vary across SWI-Prolog, GNU Prolog, and SICStus. Double-quoted strings are implementation-defined; prefer [...] terminals or explicitly convert input to code lists. Check whether your system ships library(dcg/basics) or an equivalent before hand-writing whitespace, number, and identifier terminals.

How to check your result

To verify a grammar, convert a known input to a code list and run phrase/2. Confirm that the expected value or AST binds. Then test edge cases: empty input, a single token, and a deliberately malformed string. If a query loops on a tiny input, suspect left recursion. If it fails where you expect success, check terminal lists and embedded goals for typos.

DCGs are not a replacement for industrial-strength parser generators on large grammars, and their error messages are weak. But for small DSLs, configuration snippets, and structured input where you want parsing and semantics in one language, they keep the toolchain small and the logic transparent.