7.17 | Term expansion

- Definite clause grammars
- `expand_term/2`, `term_expansion/2`
- `phrase/3`, `phrase/2`

7.17.1 | Definite clause grammars

Definite clause grammars are a useful notation to express grammar rules. However the ISO reference does not include them, so they should be considered as a system dependent feature. Definite clause grammars are an extension of context-free grammars. A grammar rule is of the form:

  head`-->` body`.`

`-->` is a predefined infix operator (section 7.14.10).
Here are some features of definite clause grammars:

- a non-terminal symbol may be any callable term.
- a terminal symbol may be any Prolog term and is written as a list. The empty list represents an empty sequence of terminals.
- a sequence is expressed using the Prolog conjunction operator `(`(',')/2).
- the head of a grammar rule consists of a non-terminal optionally followed by a sequence of terminals (i.e. a Prolog list).
- the body of a grammar rule consists of a sequence of non-terminals, terminals, predicate call, disjunction (using `;/2`), if-then (using `(->)/2`) or cut (using `!`).
- a predicate call must be enclosed in curly brackets (using `{}/1`). This makes it possible to express an extra condition.

A grammar rule is nothing but a ``syntactic sugar'' for a Prolog clause. Each grammar rule accepts as input a list of terminals (tokens), parses a prefix of this list and gives as output the rest of this list (possibly enlarged). This rest is generally parsed later. So, each a grammar rule is translated into a Prolog clause that explicitly the manages the list. Two arguments are then added: the input list (`Start`) and the output list (`Stop`). For instance:

  `p --> q.`

is translated into:

  `p(Start, End) :- q(Start, End).`

Extra arguments can be provided and the body of the rule can contain several non-terminals. Example:

      p(X, Y) -->
              q(X),
              r(X, Y),
              s(Y).

is translated into:

      p(X, Y, Start, End) :-
              q(X, Start, A),
              r(X, Y, A, B),
              s(Y, B, End).

Terminals are translated using unification:

  `assign(X,Y) --> left(X), [:=], right(Y), [;].`

is translated into:

      assign(X,Y,Start,End) :-
              left(X, Start, A),
              A=[:=|B],
              right(Y, B, C),
              C=[;|End].

Terminals appearing on the left-hand side of a rule are connected to the output argument of the head.
It is possible to include a call to a prolog predicate enclosing it in curly brackets (to distinguish them from non-terminals):

  `assign(X,Y) --> left(X), [:=], right(Y0), {Y is Y0 }, [;].`

is translated into:

      assign(X,Y,Start,End) :-
              left(X, Start, A),
              A=[:=|B],
              right(Y0, B, C),
              Y is Y0,
              C=[;|End].

Cut, disjunction and if-then(-else) are translated literally (and do not need to be enclosed in curly brackets).

7.17.2 | `expand_term/2`, `term_expansion/2`

Templates

  `expand_term(?term, ?term)
  term_expansion(?term, ?term)`

Description
`expand_term(Term1, Term2)` succeeds if `Term2` is a transformation of `Term1`. The transformation steps are as follows:

- if `Term1` is a variable, it is unified with `Term2`
- if `term_expansion(Term1, Term2)` succeeds `Term2` is assumed to be the transformation of `Term1`.
- if `Term1` is a DCG then `Term2` is its translation (section 7.17.1).
- otherwise `Term2` is unified with `Term1`.

`term_expansion(Term1, Term2)` is a hook predicate allowing the user to define a specific transformation.
The GNU Prolog compiler (section 3.4) automatically calls `expand_term/2` on each `Term1` read in. However, in the current release, only DCG transformation are done by the compiler (i.e. `term_expansion/2` cannot be used). To use `term_expansion/2`, it is necessary to call `expand_term/2` explicitly.
Errors
None.
Portability
GNU Prolog predicate.

7.17.3 | `phrase/3`, `phrase/2`

Templates

  `phrase(?term, ?list, ?list)
  phrase(?term, ?list)`

Description
`phrase(Phrase, List, Remainder)` succeeds if the list `List` is in the language defined by the grammar rule body `Phrase`. `Remainder` is what remains of the list after a phrase has been found.
`phrase(Phrase, List)` is equivalent to `phrase(Phrase, List, [])`.
Errors

`List` is neither a list nor a partial list |  | `type_error(list, List)`

`Remainder` is neither a list nor a partial list |  | `type_error(list, Remainder)`

Portability
GNU Prolog predicates.

Copyright (C) 1999-2002 Daniel Diaz
Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
More about the copyright