DCGs — Definite Clause Grammars

prolog2-4 ended with a promise: the difference-list threading built by hand there reappears, hidden, inside Prolog's own --> notation. This chapter delivers on that — DCGs are Prolog's built-in grammar-writing sugar, and no other language covered on this site has anything comparable baked directly into the language itself, not layered on as a separate parser-combinator library.

The --> Notation

A DCG rule looks like an ordinary Prolog clause, but with --> instead of :-, and its body written as a sequence of terminals — literal list elements in square brackets — to be matched against the input, left to right. phrase/2 is how you actually run one: phrase(NonTerminal, List) checks whether List can be fully consumed by the grammar rule NonTerminal.

What --> Is Actually Sugar Over

Every DCG rule is translated, automatically, into an ordinary Prolog clause with two extra hidden arguments — an input-so-far list and a remaining-list, threaded through exactly like prolog2-4's own List-Hole pair. Conceptually, greeting --> [hello], [world]. becomes:

Each terminal peels one element off the front of the "remaining input so far" list, threading the leftover tail into the next goal — S0 to S1 to S, the exact same open-list-with-a-hole pattern the previous chapter built by hand. phrase(greeting, [hello, world]) is really just calling greeting([hello, world], []) — the whole list in, nothing left over.

Nonterminals — Rules Calling Rules

A DCG rule body can reference other DCG rules, not just literal terminals — each nonterminal call receives whatever input is left after the rules before it, and passes along whatever remains after it consumes its own piece. This is exactly how a real grammar is meant to compose: small rules for individual pieces (noun, verb), combined into larger ones (noun_phrase, sentence) without any of them needing to know how the input-threading actually works underneath.

Embedding Ordinary Prolog Code — Curly Braces

Anything inside { } inside a DCG body is treated as an ordinary Prolog goal, run as-is rather than being interpreted as a grammar symbol to match against the input list — the escape hatch that lets a grammar rule check arithmetic, call another predicate, or do anything else Prolog can normally do, mid-parse.

A Practical Use — Summing an Expression List

A genuinely useful grammar, not just a toy: expr parses a term, then repeatedly looks for plus followed by another term, accumulating the running total with prolog1-7's own is/2 inside a curly-brace escape at each step, until expr_rest's empty-list base case is reached and the accumulated sum is unified with the final result.

Coding Challenges