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 lanaguage, 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, 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 disjunction operator can also be written as `|' (vertical-bar).)
• 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.