DCGs in Prolog: Declarative Grammar Parsing with Difference Lists

DCGs: declarative grammars that compile to difference‑list predicates

DCGs let you write context‑free grammars in a declarative style; the Prolog system translates each rule into ordinary predicates that receive an extra difference‑list argument, so parsing and generation share the same code.

Minimal worked configuration

Below is a self‑contained example that can be entered in any ISO‑compatible Prolog REPL (for instance SWI‑Prolog 8.x).

% Define a simple sentence grammar
s(N, R) --> noun_phrase(N, C), verb_phrase(C, R).
noun_phrase(N, C) --> [the], noun(N), [C].
noun(N) --> [cat].
verb_phrase(C, R) --> [sleeps], [R].

The three rules describe a sentence (s) as a noun phrase followed by a verb phrase. The extra arguments N, C and R are the input list, the point where the nonterminal ends, and the remaining tail, respectively. This extra argument is the difference list that the DCG compiler injects automatically.

Running the query:

?- phrase(s, [the, cat, sleeps]).

Succeeds with R = [], indicating that the whole list was consumed. The predicate phrase/2 is the entry point that the DCG library provides; it expands to the compiled clause s/2 with the two list arguments.

Practical verification

• Load the code in a Prolog REPL (SWI‑Prolog 8.x or another ISO‑compatible system).
• Call phrase(s, [the, cat, sleeps]). Expect true.
• Execute listing(s/2). The output shows a clause with two list arguments, confirming the extra difference‑list parameter.
• Define a left‑recursive rule such as a --> a, [x] and query phrase(a, [x]). The interpreter will not terminate, demonstrating the depth‑first limitation.

When to prefer DCGs

DCGs are advantageous when you need a compact, declarative description of a grammar that is naturally recursive and context‑free. They eliminate the boilerplate of manually threading difference lists, reduce the chance of mismatched list boundaries, and let the Prolog system reuse existing unification algorithms. However, for highly ambiguous grammars or when performance is critical, a hand‑written parser that controls backtracking explicitly may be preferable.

Quick comparison

Aspect	DCG	Manual parsing
Syntax	Declarative, rule‑based	Imperative, procedural
List handling	Automatic via difference list	Manual list passing
Backtracking control	Depends on Prolog’s depth‑first order	Explicit via cut or separate clauses
Performance	Can be fast with good indexing, but vulnerable to exponential blow‑up	Often more predictable, can be tuned
Maintenance	Concise, easier to read for simple grammars	More code, but clearer control flow

Engineering limits and common pitfalls

Because DCGs compile to ordinary predicates, they inherit the host Prolog’s evaluation strategy. The primary constraints are:

• Context‑free only: DCGs cannot express features that require context‑sensitive checks, such as variable binding or arithmetic on terms.
• Depth‑first search: Left‑recursive rules cause non‑termination, and ambiguous grammars may generate exponential numbers of solutions due to backtracking.
• No built‑in lookahead: The engine tries alternatives in the order they appear; without explicit ordering, performance can degrade.
• Performance sensitivity: Indexing the input list and strategic placement of cuts affect speed; poorly placed cuts can prune valid parses.

Cut placement inside a DCG rule is especially hazardous. The cut (!) commits the current choice both during parsing and during generation. If a valid alternative exists later in the grammar, the cut will silently eliminate it, leading to subtle bugs.

Typical mistakes include:

• Calling the expanded predicate with a single list argument instead of two, e.g., s([the,cat,sleeps]) rather than phrase(s, [the,cat,sleeps]). This bypasses the difference‑list mechanism and yields instantiation errors.
• Mixing phrase/2 with manual list arguments inside a DCG rule, which defeats the purpose of automatic list threading.
• Embedding a cut inside a DCG definition. The cut affects both the parse and the generate phases, potentially removing legitimate alternatives.

Version assumptions: the ISO standard specifies that DCG rules are expanded into a conjunction of ordinary predicates with an additional difference‑list argument. Library names differ – SWI‑Prolog provides phrase/2, while older systems may expose dcg/2. Assuming the standard expansion semantics avoids compatibility surprises.

When these constraints are respected, DCGs remain a powerful tool for concise grammar definitions that support both parsing and generation without manual list handling.