Previous Up Next

7.17  Term expansion

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 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: 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-2007 Daniel Diaz

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

More about the copyright
Previous Up Next