8.17  Term expansion

• Definite clause grammars
• expand_term/2, term_expansion/2
• phrase/3, phrase/2

8.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 8.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 (End). 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).

8.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 8.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 4.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.

8.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

Portability

GNU Prolog predicates.