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.
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.
Practice what you learned
1. What do the two extra arguments added to a DCG-translated predicate represent?
2. What does {Goal} do inside a DCG rule body?
3. What is the difference between phrase(sentence, Tokens) and phrase(sentence, Tokens, Rest)?
4. Why might a DCG rule fail to generate useful output even though it parses correctly?
5. What happens if a DCG rule is written left-recursively, such as expr --> expr, [+], term?
Was this page helpful?
You May Also Like
Higher-Order Predicates in Prolog
How Prolog treats goals as ordinary data, enabling call/N, maplist, foldl, include, exclude, and partition to parameterize control flow.
Constraint Logic Programming
How CLP(FD) extends Prolog with propagating constraints over finite domains, replacing brute-force generate-and-test with early pruning.
findall, bagof, and setof
The three built-in all-solutions predicates that collect every proof of a goal into a list, each with different rules for failure, grouping, and duplicates.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics