Definite Clause Grammars

Definite clause grammars are an extension of context free grammars, and may be conveniently expressed in Prolog. A grammar rule in Prolog has the form

Head –> Body.
with the interpretation ``a possible form for Head is Body''. Extra conditions, in the form of explicit Prolog literals or control constructs such as if-then-else (->) or cut (!), may be included in Body.

The syntax of DCGs supported by SB-Prolog is as follows:

  1. A non-terminal symbol may be any Prolog term other than a variable.
  2. A terminal symbol may be any Prolog term. To distinguish terminals from nonterminals, a sequence of terminal symbols
    a, b, c, d,…
    is written as a Prolog list [a, b, c, d,…], with the empty sequence written as the empty list [ ]. If the terminal symbols are ASCII character codes, they can be written (as elsewhere) as strings.
  3. Extra conditions, in the form of Prolog literals, can be included in the right-hand side of a rule by enclosing such conditions in curly braces, { and }. E.g., one can write
    natnum(X) –> {integer(X), X >= 0}.
  4. The left hand side of a rule consists of a single nonterminal. Notice that ``push-back lists'' are thus not supported.
  5. The right hand side of a rule may contain alternatives (written using the disjunction operator `;' or |), and control primitives such as if-then-else (->), not/1 and cut (`!'). The use of not/1 on the right hand side of grammar rules is not recommended, however, because their semantics in this context is murky at best. All other control primitives, e.g. repeat/0, must explicitly be enclosed within curly braces if they are not to be interpreted as nonterminals.

Except for the restriction of lists of terminals in the left hand sides of rules, the translation of DCGs in SB-Prolog is very similar to that in Quintus Prolog.

Library predicates supporting DCGs are the following:

dcg(Rule, Clause)
dcg/2 (L) Succeeds if the DCG rule Rule corresponds to the Prolog clause Clause. At the time of call, Rule must be bound to a term whose principal functor is ->/2.

phrase(Phrase, List)
phrase/2 (L) The usual way to commence execution of grammar rules. The list List is a phrase (i.e., sequence of terminals) generated by Phrase according to the current grammar rules. Phrase is a nonterminal (in general, the right hand side of a grammar rule), and must be instantiated to a nonvariable term in the call. If List is bound to a list of terminals in the call, then the goal corresponds to parsing List; if List is unbound in the call, then the grammar is being used for generation.

expand_term(T1, T2)
expand_term/2 (L) This predicate is used to transform terms that are read in, when a file is consulted or compiled. The usual use is to transform grammar rules into Prolog clauses: if T1 is a grammar rule, then T2 is the corresponding Prolog clause. Users may define their own transformations by defining the predicate term_expansion/2 (U) term_expansion/2. When a term T1 is read in when a file is being compiled or consulted, expand_term/2 first calls term_expansion/2: if the expansion succeeds, the transformed term so obtained is used; otherwise, if T1 is a grammar rule, then it is expanded using dcg/2; otherwise, T1 is used as is.

`C'(S1, Terminal, S2)
`C'/3 (L) Used to handle terminal symbols in the expansion of grammar rules. Not usually of direct use to the user. This is defined as
`C'([X|S], X, S).