4.14.1 Definite Clause Grammars

Prolog’s grammar rules provide a convenient notation for expressing definite clause grammars, which are useful for the analysis of both artificial and natural languages.

The usual way one attempts to make precise the definition of a language, whether it is a natural language or a programming language, is through a collection of rules called a “grammar”. The rules of a grammar define which strings of words or symbols are valid sentences of the language. In addition, the grammar generally analyzes the sentence into a structure that makes its meaning more explicit.

A fundamental class of grammar is the context-free grammar (CFG), familiar to the computing community in the notation of “BNF” (Backus-Naur form). In CFGs, the words, or basic symbols, of the language are identified by “terminal symbols”, while categories of phrases of the language are identified by non-terminal symbols. Each rule of a CFG expresses a possible form for a non-terminal, as a sequence of terminals and non-terminals. The analysis of a string according to a CFG is a parse tree, showing the constitutent phrases of the string and their hierarchical relationships.

Context-free grammars (CFGs) consist of a series of rules of the form:

nt --> body.

where nt is a non-terminal symbol and body is a sequence of one or more items separated by commas. Each item is either a non-terminal symbol or a sequence of terminal symbols. The meaning of the rule is that body is a possible form for a phrase of type nt. A non-terminal symbol is written as a Prolog atom, while a sequence of terminals is written as a Prolog list, whereas a terminal may be any Prolog term.

Definite clause grammars (DCGs) are a generalization of context-free grammars and rules corresponding to DCGs are referred to as “Grammar Rules”. A grammar rule in Prolog takes the general form

head --> body.

meaning “a possible form for head is body”. Both body and head are sequences of one or more items linked by the standard Prolog conjunction operator ‘,’ (comma).

Definite clause grammars extend context-free grammars in the following ways:

• A non-terminal symbol may be any callable Prolog term.
• A terminal symbol may be any Prolog term. To distinguish terminals from non-terminals, a sequence of one or more terminal symbols is written within a grammar rule as a Prolog list. An empty sequence is written as the empty list ‘[]’. If the terminal symbols are character codes, then such lists can be written (as elsewhere) as strings. An empty sequence is written as the empty list (‘[]’ or ‘""’).
• Extra conditions, in the form of Prolog procedure calls, may be included in the right-hand side of a grammar rule. These extra conditions allow the explicit use of procedure calls in the body of a rule to restrict the constitutents accepted. Such procedure calls are written enclosed in curly brackets (‘{’ and ‘}’).
• The left-hand side of a grammar rule consists of a non-terminal, optionally followed by a sequence of terminals (again written as a Prolog list).
• Alternatives may be stated explicitly in the right-hand side of a grammar rule, using the disjunction operator ‘;’ (semicolon) as in Prolog.
• The cut symbol ‘!’ may be included in the right-hand side of a grammar rule, as in a Prolog clause. The cut symbol does not need to be enclosed in curly brackets. The same is true for the control constructs. However, all other built-in predicates not enclosed in curly brackets will be treated as non-terminal symbols. The precise meaning of this rule is clarified in ref-gru-tra.
• The extra arguments of non-terminals provide the means of building structure (such as parse trees) in grammar rules. As non-terminals are “expanded” by matching against grammar rules, structures are progressively built up in the course of the unification process.
• The extra arguments of non-terminals can also provide a general treatment of context dependency by carrying test and contextual information.