<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
"http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>
<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.06-7 of 2001-11-14">
<TITLE>
Term expansion
</TITLE>
</HEAD>
<BODY TEXT=black BGCOLOR=white>
<A HREF="manual039.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="manual023.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="manual041.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>
<TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66dbff"><DIV ALIGN=center><TABLE>
<TR><TD><FONT SIZE=4><B><A NAME="htoc178">7.17</A></B></FONT></TD>
<TD WIDTH="100%" ALIGN=center><FONT SIZE=4><B>Term expansion</B></FONT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><UL>
<LI><A HREF="manual040.html#toc140"> Definite clause grammars</A>
<LI><A HREF="manual040.html#toc141"> <TT>expand_term/2</TT>,
<TT>term_expansion/2</TT></A>
<LI><A HREF="manual040.html#toc142"> <TT>phrase/3</TT>,
<TT>phrase/2</TT></A>
</UL>
<A NAME="Term-expansion"></A><BR>
<A NAME="toc140"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc179">7.17.1</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B>Definite clause grammars</B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<A NAME="DCG"></A>
<BR>
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:
<DL COMPACT=compact><DT><DD>head<TT> --> </TT>body<TT>.</TT></DL>
<TT>--></TT> is a predefined infix operator (section <A HREF="manual037.html#op/3:(Term-input/output)">7.14.10</A>).<BR>
<BR>
Here are some features of definite clause grammars:
<UL><LI>a non-terminal symbol may be any callable term.<BR>
<BR>
<LI>a terminal symbol may be any Prolog term and is written as a list. The
empty list represents an empty sequence of terminals.<BR>
<BR>
<LI>a sequence is expressed using the Prolog conjunction operator
<TT>(</TT>(',')/2).<BR>
<BR>
<LI>the head of a grammar rule consists of a non-terminal optionally
followed by a sequence of terminals (i.e. a Prolog list).<BR>
<BR>
<LI>the body of a grammar rule consists of a sequence of non-terminals,
terminals, predicate call, disjunction (using <TT>;/2</TT>), if-then (using
<TT>(->)/2</TT>) or cut (using <TT>!</TT>).<BR>
<BR>
<LI>a predicate call must be enclosed in curly brackets (using
<TT>{}/1</TT>). This makes it possible to express an extra
condition.</UL>
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 (<TT>Start</TT>) and the output list
(<TT>Stop</TT>). For instance:
<DL COMPACT=compact><DT><DD><TT>p --> q.</TT></DL>
is translated into:
<DL COMPACT=compact><DT><DD><TT>p(Start, End) :- q(Start, End).</TT></DL>
Extra arguments can be provided and the body of the rule can contain several
non-terminals. Example:
<DL COMPACT=compact><DT><DD>
<PRE>
p(X, Y) -->
q(X),
r(X, Y),
s(Y).
</PRE></DL>
is translated into:
<DL COMPACT=compact><DT><DD>
<PRE>
p(X, Y, Start, End) :-
q(X, Start, A),
r(X, Y, A, B),
s(Y, B, End).
</PRE></DL>
Terminals are translated using unification:
<DL COMPACT=compact><DT><DD><TT>assign(X,Y) --> left(X), [:=], right(Y), [;].</TT></DL>
is translated into:
<DL COMPACT=compact><DT><DD>
<PRE>
assign(X,Y,Start,End) :-
left(X, Start, A),
A=[:=|B],
right(Y, B, C),
C=[;|End].
</PRE></DL>
Terminals appearing on the left-hand side of a rule are connected to the
output argument of the head.<BR>
<BR>
It is possible to include a call to a prolog predicate enclosing it in curly
brackets (to distinguish them from non-terminals):
<DL COMPACT=compact><DT><DD><TT>assign(X,Y) --> left(X), [:=], right(Y0), {Y is Y0 },
[;].</TT></DL>
is translated into:
<DL COMPACT=compact><DT><DD>
<PRE>
assign(X,Y,Start,End) :-
left(X, Start, A),
A=[:=|B],
right(Y0, B, C),
Y is Y0,
C=[;|End].
</PRE></DL>
Cut, disjunction and if-then(-else) are translated literally (and do not need
to be enclosed in curly brackets).<BR>
<BR>
<A NAME="toc141"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc180">7.17.2</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B><TT>expand_term/2</TT>,
<TT>term_expansion/2</TT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
expand_term(?term, ?term)<BR>
term_expansion(?term, ?term)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>expand_term(Term1, Term2)</TT> succeeds if
<TT>Term2</TT> is a transformation of <TT>Term1</TT>. The transformation
steps are as follows:
<UL><LI>if <TT>Term1</TT> is a variable, it is unified with <TT>Term2</TT><BR>
<BR>
<LI>if <TT>term_expansion(Term1, Term2)</TT> succeeds <TT>Term2</TT> is
assumed to be the transformation of <TT>Term1</TT>.<BR>
<BR>
<LI>if <TT>Term1</TT> is a DCG then <TT>Term2</TT> is its translation
(section <A HREF="#DCG">7.17.1</A>).<BR>
<BR>
<LI>otherwise <TT>Term2</TT> is unified with <TT>Term1</TT>.</UL>
<TT>term_expansion(Term1, Term2)</TT> is a hook predicate allowing the user
to define a specific transformation. <BR>
<BR>
The GNU Prolog compiler (section <A HREF="manual008.html#The-GNU-Prolog-compiler">3.4</A>) automatically calls
<TT>expand_term/2</TT> on each <TT>Term1</TT> read in. However, in the
current release, only DCG transformation are done by the compiler (i.e.
<TT>term_expansion/2</TT> cannot be used). To use
<TT>term_expansion/2</TT>, it is necessary to call <TT>expand_term/2</TT>
explicitly.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc142"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc181">7.17.3</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B><TT>phrase/3</TT>,
<TT>phrase/2</TT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
phrase(?term, ?list, ?list)<BR>
phrase(?term, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>phrase(Phrase, List, Remainder)</TT> succeeds if the list
<TT>List</TT> is in the language defined by the grammar rule body
<TT>Phrase</TT>. <TT>Remainder</TT> is what remains of the list after a
phrase has been found. <BR>
<BR>
<TT>phrase(Phrase, List)</TT> is equivalent to
<TT>phrase(Phrase, List, [])</TT>.<BR>
<BR>
<B>Errors</B><BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>List</TT> is neither a list nor a partial list</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>type_error(list, List)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>Remainder</TT> is neither a list nor a partial list</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>type_error(list, Remainder)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR></TABLE><BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicates.<BR>
<BR>
<HR SIZE=2>
Copyright (C) 1999-2002 Daniel Diaz
<BR>
<BR>
Verbatim copying and distribution of this entire article is permitted in any
medium, provided this notice is preserved. <BR>
<BR>
<A HREF="index.html#copyright">More about the copyright</A>
<HR>
<A HREF="manual039.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="manual023.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="manual041.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
