Prolog DCGs: Use --> for readable parsers but keep the difference-list contract visible

Writing a parser in Prolog with manual difference lists is easy to get wrong. The useful takeaway is that Definite Clause Grammars give you a clean --> notation for context-free rules, but the compiler still implements them as ordinary Prolog predicates with two extra arguments that thread a difference list through the parse. If you forget that contract you get silent mis-parses or non-termination.

Start with the contract, not the syntax

A difference list is a pair of list variables In and Out where the elements between them represent the unconsumed input. A DCG rule like

sentence --> noun_phrase, verb_phrase.

is not a special form at runtime. The Prolog compiler rewrites it into a predicate that takes the extra difference-list arguments. Conceptually sentence/3 is called with an input list head and an output tail, and it succeeds only when the rule consumes exactly the intended tokens.

The standard entry point is phrase/2, which hides the two arguments for you. In a SWI-Prolog top-level you can write:

?- phrase(sentence, [the,cat,chases,the,mouse]).

No special permissions are required; this runs in the interactive toplevel. A successful query means the list is fully consumed by the grammar. If the list is left over, the query fails. The risk here is assuming phrase/2 will tell you where parsing stopped; it will not, it only reports success or failure.

Mechanism with one worked configuration

Consider a minimal English fragment:

% grammar
sentence --> noun_phrase, verb_phrase.

noun_phrase --> [the], noun.
noun_phrase --> noun.

verb_phrase --> verb, noun_phrase.

noun --> [cat].
noun --> [mouse].

verb --> [chases].
verb --> [sees].

With that source loaded, the three-argument form of phrase exposes the difference list directly:

?- phrase(noun_phrase, Input, Rest).

Input is the list head, Rest is the remaining tail after the rule succeeds. The compiler adds those two arguments automatically; you do not write them.

To see the generated arity, you can inspect the predicate table in the toplevel:

?- current_predicate(sentence/3).

The check confirms the extra arguments exist. The same holds for noun_phrase/3, verb_phrase/3, etc. Tracing a call with trace/0 lets you observe the threading of the second argument through recursive calls, which is the practical way to verify that the difference list is being passed correctly.

Semantic actions are allowed inside a DCG rule by using { ... }:

sentence --> noun_phrase(N), verb_phrase(V), { build_tree(N,V,Tree) }.

The braces delimit ordinary Prolog code that runs after the surrounding grammar parts have matched and before the difference list is passed on. Mixing actions with grammar makes readability drop quickly, so keep actions small and pure.

Limits and common mistakes

DCGs are best suited for context-free languages. Ambiguous grammars will generate multiple parse trees by backtracking, which can be expensive and surprising if you expect a single result.

Left recursion is a common pitfall. A rule like

expr --> expr, [plus], term.

will loop because Prolog tries the recursive call before consuming input. This is a Prolog evaluation order issue, not a DCG bug, but it is often blamed on DCGs.

Forgetting to thread the difference list through recursive calls is the classic manual error when people try to write the expanded predicates by hand. With --> the compiler does the threading, but if you call an expanded predicate directly you must supply both In and Out arguments in the correct order. Swapping them silently produces wrong parses.

Performance overhead of DCGs is minimal; the cost is the extra argument passing. Deep recursion can still grow the Prolog stack. Over-reliance on built-ins like phrase/2 can obscure the underlying mechanics, making debugging harder when a rule unexpectedly succeeds with leftover input.

Check results practically by using the three-argument form of phrase to inspect Rest, and by querying current_predicate/1 to confirm the /3 arity was generated. If Rest is not [] for a complete parse, the grammar did not consume the intended input.