Does a DCG automatically produce a parse tree?

No. The rules can include arguments that build one, but a recognizer may only report success or failure.

Can it generate sentences?

Often yes for suitable relational grammars, although termination and completeness depend on the rules and query.

Is a DCG a language model?

It is an explicit logic-based grammar mechanism. It does not inherently learn token probabilities or generate text through statistical prediction.

AI Glossary / Graphs and symbolic AI / Intermediate

Definite clause grammar

Definition

A definite clause grammar, or DCG, is a notation for describing grammars and related sequence-processing relations in logic programming. In Prolog, DCG rules are translated into ordinary predicates that pass information about the unconsumed part of a sequence.

What it means

A grammar describes how smaller pieces combine into larger structures. A DCG lets those descriptions look like grammar rules while using Prolog's logical variables, unification and search.

A simple rule might say that a command consists of an action followed by a target. Other rules specify which tokens count as actions or targets. The grammar can recognize an input, build a structured representation or, when its rules support the intended use, generate possible sequences.

DCGs are not limited to ordinary context-free grammars: additional arguments and logical conditions can express relationships such as agreement or carry semantic information. This expressiveness also means their execution behavior depends on more than the visible grammar shape.

How it works

In Prolog notation, the operator --> separates a DCG rule's head from its body. Literal token sequences appear in lists, and nonterminal calls refer to other grammar rules. Extra arguments can carry values such as a parse tree or extracted identifier.

The usual translation adds two hidden arguments: the input sequence before a rule runs and the remaining sequence afterward. Neighboring grammar components connect these arguments so that one begins where the previous one finished. This is commonly explained using difference lists.

The phrase/2 interface asks whether a grammar consumes a complete input. The phrase/3 interface also exposes the remainder. Prolog goals can appear inside braces, but their behavior can restrict how the grammar can be run. Left recursion, rule order and other search choices can affect termination.

Three practical examples

Command parsing: A small application translates a restricted command language into structured actions and targets.
Text processing: A tool recognizes record fields and returns extracted values together with the unused input.
Language teaching: A grammar demonstrates how agreement and parse structure can be represented through shared logical arguments.

Think of it this way

Think of passing a bookmark through a line of instructions. Each reader consumes the part it recognizes and hands the bookmark to the next reader at the right place. The analogy explains sequence position; a DCG can also explore alternatives and bind logical variables, which an ordinary bookmark does not do.

Worked example

Consider this small grammar:

command --> action, target.
action --> [open].
action --> [close].
target --> [door].
target --> [window].

The query phrase(command, [open,door]) succeeds. The action consumes open, leaving [door]. The target consumes door, leaving the empty list. Complete consumption is required by this query.

There are exactly four complete token sequences in this grammar: [open,door], [open,window], [close,door] and [close,window]. This follows from two action choices combined with two target choices.

The query phrase(command, [open,door,now]) fails because now remains after the command has been recognized. In contrast, phrase(command, [open,door,now], Rest) can succeed with Rest = [now]. That second query recognizes a prefix rather than requiring the entire input to match.

The underlying connection can be pictured as command(Input,Rest) calling action(Input,Middle) and target(Middle,Rest). For [open,door,now], Middle becomes [door,now] and Rest becomes [now]. No step should restart at the original input.

This grammar accepts token lists, not arbitrary raw text. Converting a user's text into tokens and handling capitalization or punctuation would require additional rules or preprocessing.

Illustrative case study

Fictional case: Linden Controls uses a DCG to interpret a restricted set of workshop demonstration commands. Initial tests show that valid commands are recognized, but a review discovers that the application uses a prefix-recognition query and ignores the remaining tokens.

As a result, an input containing a valid command followed by unrelated text is treated as fully understood. The team changes the acceptance check to require complete consumption and presents a clear failure when extra text remains.

It also separates parsing from execution. Recognizing a command produces a structured value; a later component checks whether the requested action is allowed in the current demonstration state. The case illustrates why syntactic recognition and action authorization are different responsibilities.

Common misconceptions and mistakes

A successful prefix parse proves the whole input is valid. Remaining tokens must be checked when full recognition is required.
DCGs only describe context-free languages. Extra arguments and goals allow richer relations.
Any DCG runs equally well for parsing and generation. Some rules or embedded goals only work properly in particular modes.
Grammar notation guarantees termination. Recursive structure and the underlying search strategy still matter.

Business use

DCGs are useful for small structured languages, predictable text formats and applications already using Prolog. Their compact notation can keep grammar structure close to the logic that builds a useful interpretation.

Before deployment, decide whether the input is characters, character codes or tokens. Define whether the parser accepts prefixes or complete records, and test empty, malformed and ambiguous inputs. Evaluate termination for the queries the application actually performs. Keep semantic validation and action checks explicit even when the grammar successfully produces a parse.

Check your understanding

A grammar consumes [close,window] from [close,window,please] and leaves [please]. Has it recognized the entire input?

Answer: No. It has recognized a prefix. Full-input acceptance requires the remainder to be empty.

Related terms

Learn next

Extend the worked grammar with an optional please token and list the accepted complete sequences. Then add an argument that returns the action and target as a structured term. Compare full-input recognition with a query that deliberately keeps the remainder.

Sources

SWI-Prolog documents DCG expansion and the phrase/2 and phrase/3 interfaces: https://www.swi-prolog.org/pldoc/man?section=DCG

Learn Prolog Now! explains the relationship between grammar notation, difference lists and search behavior: https://lpn.swi-prolog.org/lpnpage.php?pageid=lpn-htmlse29&pagetype=html

The command grammar and Linden Controls case are original illustrations. Query outcomes follow from the displayed rules; no claim of a separately executed Prolog test is made.

Previous: Definite clause Next: Definite reference