Parsing with Prolog DCGs: From Text to Structure Without the Boilerplate

The problem: parsing without a parser generator

You need to turn a text format — maybe a config file, a tiny DSL, or a network protocol — into structured data. The usual options are writing a recursive-descent parser by hand, reaching for a generator like ANTLR or PEG.js, or abusing regular expressions until they break. Each adds a build step, a new syntax to learn, or a runtime dependency.

Prolog's Definite Clause Grammars (DCGs) offer a different trade-off: a parser written as declarative rules that compiles to ordinary Horn clauses, runs in the same process, and can also generate valid inputs from the same grammar. No separate toolchain, no code generation, and the same logic works for parsing, validation, and test-case generation.

How DCGs work under the hood

A DCG rule looks like nonterm --> body. At compile time the Prolog system rewrites it to nonterm(S0, S) :- body_expanded(S0, S). The two extra arguments thread an implicit difference list through the parse: S0 is the input list before the rule consumes anything, S is what remains after. Terminals are written as lists [token] (or single atoms/chars); non-terminals appear as bare identifiers. The expansion handles the list plumbing automatically, so you describe what the language looks like, not how to shuffle list pointers.

The entry point is phrase/2 (or phrase/3 for a custom remainder). For a grammar digit_sum//1 you call phrase(digit_sum(Sum), "12 + 7 + 3") and get Sum = 22.

A worked example: summing integers separated by plus signs

Create a file sum_dcg.pl:

:- use_module(library(dcg/basics)).

digit_sum(Sum) -->
    integer(I),
    blanks,
    digit_sum_rest(I).

digit_sum_rest(Acc) -->
    [+],
    blanks,
    integer(I),
    blanks,
    digit_sum_rest(Acc + I).
digit_sum_rest(Sum) -->
    eos,
    {Sum = Total}.

Load it in SWI-Prolog or Scryer and query:

?- phrase(digit_sum(S), "12 + 7 + 3").
S = 22.

The same grammar runs backward. Ask phrase(digit_sum(19), L). and Prolog yields L = "12 + 7" (among other solutions). This bidirectionality means one grammar serves as parser, validator, and generator — handy for property-based testing where you generate inputs, parse them, and assert round-trip equality.

Where DCGs shine and where they bite

Composition and libraries

DCGs compose cleanly: sentence --> noun_phrase, verb_phrase. builds a parser from smaller pieces. library(dcg/basics) (available in SWI, Scryer, Trealla) supplies string//1, blanks//0, integer//1, digit//1, eos//0 so you rarely write low-level token matching.

Left-recursion is a hard stop

A rule like expr --> expr, [+], term. causes infinite recursion in top-down execution. Rewrite to right-recursion or use library(dcg/basics) expression//1 with operator-precedence declarations. This is the most common pitfall for newcomers.

Ambiguity and tabling

Ambiguous grammars explore exponential paths. If your target system supports tabling (SWI, XSB, Trealla), add :- table nonterm/2. (the two implicit args plus any explicit ones) to memoize sub-parses. Benchmark with statistics/2 to confirm the win.

Error reporting is manual

DCGs don't carry line/column info automatically. Wrap rules with a location//2 helper or use library(dcg/high_order) combinators like sequence//2 and optional//1 that preserve position data.

Interoperability with streams and files

phrase/3 works with any sequence type implementing next/3 — lists, streams, arrays. phrase_from_file/2 (de facto standard in SWI, Scryer, Trealla) lets you parse a UTF-8 file directly: phrase_from_file(digit_sum(S), 'data.txt'). where data.txt contains 42 + 8.

Practical checklist before you adopt

• Verify library(dcg/basics) exists in your target Prolog (GNU Prolog lacks some combinators).
• Rewrite left-recursive rules to right-recursion or use expression//1.
• Add tabling directives for ambiguous grammars on supported systems.
• Instrument error positions if you need user-friendly messages.
• Test bidirectional use: phrase(Grammar, Input) for parsing, phrase(Grammar, Output) for generation.

Next step: try it on a real format

Pick a small text format you currently parse with ad-hoc code — a CSV variant, a simple config syntax, a log line pattern. Write a DCG for it in 20–30 lines, load it, and run phrase/2 on sample data. If it works, you've replaced a fragile parser with a maintainable, testable, and reversible grammar without leaving your Prolog environment.