Definite Clause Grammars in Prolog: From Natural Language to Fast Arithmetic Parsers

Concrete Problem: Parsing Arithmetic Expressions in Prolog

Suppose you need to evaluate expressions like 3 + 4 * (2 - 1) inside a Prolog program. You want a parser that is both readable and fast, and you’d like to avoid writing manual list‑handling code. Definite Clause Grammars (DCGs) are a natural fit, but they come with quirks that can trip up even seasoned Prolog developers.

Thesis: Use DCGs with Careful Design and Tabling for Robust, Performant Parsing

DCGs transform natural‑language‑style rules into ordinary Prolog clauses, automatically threading a list of tokens. When you combine this with tabling (memoisation) and a disciplined grammar design, you can create parsers that are both expressive and efficient. The key is to avoid left‑recursion, structure semantic actions cleanly, and leverage built‑in predicates like phrase/2 and listing/1 for integration and debugging.

1. DCG Basics: From Syntax to Clauses

A DCG rule looks like a Prolog clause but uses the // operator to separate the grammar head from the body. The compiler rewrites it as a predicate that takes two extra arguments: the input token list and the remaining token list.

% A simple rule that matches the token 'plus'
plus // [] --> [plus].

When you write a DCG, you don’t need to manage the token list manually. The phrase/2 predicate stitches everything together:

% Parse the token list [3, plus, 4] into a term
?- phrase(expr(T), [3, plus, 4]).
T = 3 + 4.

Behind the scenes, phrase/2 calls expr/3, the compiled version of the expr rule.

2. Avoiding Left‑Recursion: The Infinite Loop Trap

Left‑recursive rules, where a nonterminal calls itself as the first element of its own body, cause standard DCG implementations to loop forever. For arithmetic expressions, a naïve grammar might look like:

expr --> expr, plus, term.
expr --> term.

Running phrase(expr(_), [3, plus, 4]) would never terminate. The fix is to rewrite the grammar using right‑recursion or to introduce an auxiliary rule that accumulates the result.

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

This pattern is common: split the left‑recursive part into a tail‑recursive helper that collects the remaining terms.

3. Tabling for Performance and Left‑Recursion

Modern Prolog systems such as SWI‑Prolog support tabling, which memoises the results of predicates. By declaring a DCG rule with :- table, you can safely use left‑recursive grammars without infinite loops, and you often gain a performance boost for repeated sub‑parses.

:- table expr/1.

expr --> expr, plus, term.
expr --> term.

After adding :- table expr/1, the parser can handle left‑recursive input and will reuse previously computed sub‑expressions, reducing redundant work.

4. Integrating with Modern Prolog Tools

• phrase/2 and phrase/3: The former takes a token list; the latter can accept an input stream or a string, converting it to tokens automatically.
• listing/1: Inspect the compiled DCG clauses to verify that the transformation matches your expectations.
• debugging utilities: Use trace or debug to step through the generated clauses, which can be invaluable when semantic actions become complex.

Worked Example: Parsing and Evaluating Arithmetic Expressions

Below is a compact DCG that parses integer literals, addition, and multiplication, builds an abstract syntax tree (AST), and evaluates it. The grammar is written to avoid left‑recursion, and tabling is used to speed up repeated sub‑expressions.

% Enable tabling for expr/1
:- table expr/1.

% Entry point
expr(Term) --> term(Term), expr_rest(Term, Result), {Result = Term}.

expr_rest(Acc, Result) --> plus, term(T), {Acc1 is Acc + T}, expr_rest(Acc1, Result).
expr_rest(Acc, Result) --> [] , {Result = Acc}.

term(Term) --> factor(Term), term_rest(Term, Result), {Result = Term}.
term_rest(Acc, Result) --> times, factor(F), {Acc1 is Acc * F}, term_rest(Acc1, Result).
term_rest(Acc, Result) --> [] , {Result = Acc}.

factor(Term) --> [Number], {integer(Number), Term = Number}.
factor(Term) --> lparen, expr(Term), rparen.

% Token definitions
plus --> [plus].
times --> [times].
lparen --> [lparen].
rparen --> [rparen].

To parse and evaluate an expression:

% Convert a string to a token list
?- string_to_atom("3 + 4 * (2 - 1)", Atom),
   atom_chars(Atom, Chars),
   phrase(tokens(Tokens), Chars),
   phrase(expr(Result), Tokens).
Result = 7.

In this example, tokens/1 is a helper DCG that turns characters into the token list [3, plus, 4, times, lparen, 2, minus, 1, rparen]. The parser then builds and evaluates the AST.

Trade‑off: Complexity of Semantic Actions

Embedding Prolog code inside DCG bodies (the curly‑brace {} construct) is powerful, but it can also make the grammar harder to read and debug. If you need to perform many side effects or build large data structures, consider separating the parsing phase from the semantic phase: parse to a simple AST first, then traverse it with ordinary Prolog predicates.

Actionable Closing: Build, Test, and Profile Your DCG

1. Write a minimal grammar that covers your language’s core constructs.
2. Run listing/1 to confirm the generated clauses match your expectations.
3. Profile with time/1 or statistics/2 to spot performance bottlenecks.
4. When left‑recursion is unavoidable, enable tabling with :- table and re‑profile.
5. Use phrase/2 or phrase/3 for integration with I/O, and rely on debug or trace to step through complex semantic actions.

By following these guidelines, you’ll harness the full expressive power of Prolog’s DCGs while keeping your parsers efficient, maintainable, and well‑integrated with modern Prolog tooling.