DCGs (Definite Clause Grammars)

Analogy categoryAnalogies

DCGs as Sugar Over Difference Lists

A DCG rule written with --> is translated by the Prolog reader into an ordinary clause with two extra arguments threading a difference list — a pair of lists representing 'what's left to consume' before and after the rule matches — so sentence --> noun_phrase, verb_phrase compiles roughly to sentence(S0, S) :- noun_phrase(S0, S1), verb_phrase(S1, S). This translation is exactly what a hand-written difference-list parser does manually, which is why DCGs are often introduced as 'syntactic sugar,' but in practice they read far more like a grammar specification than like plumbing code.

🏏

Cricket analogy: It's like a scoring shorthand where 'four' on the sheet secretly expands into 'runs before + 4 = runs after' bookkeeping the scorer does automatically — a DCG rule similarly expands into difference-list bookkeeping the programmer never has to write by hand, even though it's happening underneath.

Terminals, Nonterminals, and Embedded Goals with {}/1

Within a DCG body, a list like [the] matches a single terminal token literally, consuming it from the input, a bare atom like noun_phrase invokes another DCG rule (a nonterminal), and curly braces {Goal} escape out to ordinary Prolog, calling Goal without touching the difference-list arguments at all — so digit(D) --> [D], { code_type(D, digit) } consumes one token and separately checks, via plain Prolog, that it satisfies a type test, combining grammar matching and arbitrary computation in a single rule.

🏏

Cricket analogy: It's like a scoring rule that consumes exactly one delivery from the over ([D]) and then separately checks, via a side calculation, whether it was a legal ball ({code_type(D, legal)}) — the terminal-matching and the extra check are two distinct steps combined in one rule, just as DCGs separate token consumption from embedded Prolog checks.

Invoking DCGs with phrase/2 and phrase/3

Because DCG rules actually compile to predicates with two extra arguments, you rarely call them directly; instead phrase(NonTerminal, List) calls the translated predicate with List as the starting difference-list position and [] as the ending position, checking that NonTerminal consumes the entire list, while phrase(NonTerminal, List, Rest) is the more general form that leaves Rest bound to whatever wasn't consumed, useful for parsing a prefix of a longer stream or for chaining grammars where one rule's leftover feeds into the next.

🏏

Cricket analogy: It's like phrase/2 checking that an entire over's six balls are accounted for by an 'over' pattern with nothing left dangling, while phrase/3 is the version used mid-analysis where you deliberately want to know how many balls are left unaccounted for — full consumption versus partial, leftover-returning consumption.

prolog

sentence --> noun_phrase, verb_phrase.
noun_phrase --> [the], noun.
verb_phrase --> verb, noun_phrase.
noun --> [cat] ; [dog].
verb --> [chased] ; [saw].

?- phrase(sentence, [the, cat, chased, the, dog]).
true.

digits([D|Ds]) --> [D], { code_type(D, digit) }, digits(Ds).
digits([D]) --> [D], { code_type(D, digit) }.

?- phrase(digits(Ds), `123`).
Ds = "123".

Bidirectionality: One Grammar, Parsing and Generating

Because DCG-translated predicates are ordinary Prolog clauses with logic-variable arguments, the same grammar can often run in either direction: phrase(sentence, [the,cat,sat], []) parses a token list to check it's a valid sentence, while phrase(sentence, Tokens, []) with Tokens left unbound can generate valid token lists by backtracking through the grammar's own rules — but this only works cleanly if the grammar's embedded {}/1 goals and any recursive nonterminals are written to behave sensibly with unbound variables, since a goal like {Number > 5} used for parsing will simply fail to generate anything useful if Number is not yet bound when it runs.

🏏

Cricket analogy: It's like a well-designed net session that works both for a batter reviewing recorded deliveries (parsing) and for a bowling machine generating new practice deliveries from the same rule set (generating) — but only if the drill's side conditions, like 'speed > 140kph', don't assume a ball has already been bowled when they run.

Left-recursive DCG rules, like phrase_a --> phrase_a, [x], recurse before consuming any input and will loop forever under Prolog's depth-first, left-to-right execution strategy — exactly like left-recursive rules in a plain recursive-descent parser. DCGs inherit this limitation because they compile straight down to ordinary Prolog clauses.

A DCG rule (-->) compiles into an ordinary predicate with two extra arguments threading a difference list through the grammar.
A terminal like [the] consumes a literal token; a bare atom invokes another DCG rule (a nonterminal).
Curly braces {Goal} embed ordinary Prolog inside a DCG body without touching the difference-list arguments.
phrase(NonTerminal, List) checks that NonTerminal consumes List entirely, using [] as the ending position.
phrase(NonTerminal, List, Rest) is the more general form, leaving Rest bound to whatever wasn't consumed.
Because DCG predicates use ordinary logic variables, the same grammar can often parse and generate token lists via the same rules.
Left-recursive DCG rules loop forever under Prolog's depth-first execution, just like left-recursive recursive-descent parsers.