Using Definite Clause Grammars in Prolog for Simple Parsers

Problem: writing a parser without boilerplate

When you need to recognize a small language in Prolog, writing explicit difference‑list predicates quickly becomes noisy. You end up threading two list arguments through every rule, which obscures the grammar intent and makes maintenance harder.

Thesis: DCGs hide the plumbing while keeping the power of Prolog

Definite Clause Grammars (DCGs) let you describe a grammar with a clean >> syntax. The Prolog system automatically expands each rule into ordinary clauses that carry the hidden input and output lists, so you can focus on the structure of the language. The same DCG works for both parsing and generation, and you can embed arbitrary Prolog goals with curly braces to build syntax trees or compute values.

How a DCG is translated

Consider the rule:

sentence --> noun_phrase, verb_phrase.

The compiler adds two hidden arguments (the difference list) and produces roughly:

sentence(In, Out) :- noun_phrase(In, Mid), verb_phrase(Mid, Out).

Each non‑terminal becomes a predicate with those extra arguments; terminals like ["the"] consume one element from the input list.

Worked example: parsing a tiny English fragment

We will parse sentences of the form "determiner noun verb" (e.g., "the cat sits"). First, define the lexicon:

% lexicon
det --> [the].
det --> [a].
noun --> [cat].
noun --> [dog].
verb --> [sits].
verb --> [runs].

Now the grammar:

sentence --> noun_phrase, verb_phrase.
noun_phrase --> det, noun.
verb_phrase --> verb.

To test parsing, load the clauses into a Prolog REPL (e.g., swipl) and query:

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

If the definition is correct, the goal succeeds. To see a parse tree, add a semantic action that builds a term:

sentence --> noun_phrase(NP), verb_phrase(VP), {Sentence = sentence(NP, VP)}.
noun_phrase --> det(D), noun(N), {NP = noun_phrase(D, N)}.
verb_phrase --> verb(V), {VP = verb(V)}.
det --> [the], {D = the}.
det --> [a],   {D = a}.
noun --> [cat], {N = cat}.
noun --> [dog], {N = dog}.
verb --> [sits], {V = sits}.
verb --> [runs], {V = runs}.

Now the query:

?- phrase(sentence, [the, cat, sits], Sentence).

binds Sentence to sentence(noun_phrase(the, cat), verb(sits)). The same DCG can generate sentences:

?- phrase(sentence, Words).

enumerates all word lists that satisfy the grammar (subject to any depth limits you set).

Trade‑off and limitation

DCGs rely on Prolog’s depth‑first search. A left‑recursive rule such as:

expr --> expr, '+', term.
expr --> term.

will cause an infinite loop unless the system offers tabling or you rewrite the grammar to be right‑recursive:

expr --> term, expr_tail.
expr_tail --> [].
expr_tail --> ['+', term, expr_tail].

This transformation preserves the language but changes the shape of the parse tree, which may affect downstream semantic actions. Another practical concern is list copying: each hidden difference list creates new lists on every recursive step. For very long inputs you can mitigate this by using the library(dcg/high_order) predicates or by manually threading difference lists in performance‑critical sections.

Actionable closing

Start by extracting the tokens of your language into a list of atoms or strings. Write a DCG that mirrors the BNF you already have, using >> for rules and curly braces for any semantic processing you need. Test with phrase/2 for both parsing and generation. If you encounter left recursion, apply the right‑recursive rewrite shown above, and verify that the generated parse trees still contain the information you require. Finally, profile with a realistic input size; if list copying becomes a bottleneck, consider the high‑order library or hand‑crafted difference‑list optimizations.