\chapter{Definite Clause Grammars} \label{DCGs}
\index{definite clause grammars}\index{grammars!definite clause}
%===============================================================

\section{General Description}
%============================

Definite clause grammars (DCGs) are an extension of context free
grammars that have proven useful for describing natural and formal
languages, and that may be conveniently expressed and executed in
Prolog.  A Definite Clause Grammar rule is executable because it is
just a notational variant of a logic rule that has the following
general form:
\begin{center}
                {\em Head} {\tt -->} {\em Body.}
\end{center}
with the declarative interpretation that ``a possible form for {\em
Head} is {\em Body}''. The procedural interpretation of a grammar rule
is that it takes an input sequence of symbols or character codes,
analyses some initial portion of that list, and produces the remaining
portion (possibly enlarged) as output for further analysis.  In XSB,
the exact form of this sequence is determined by whether XSB's {\em
DCG mode} is set to use tabling or not, as will be discussed below.
In either case, the arguments required for the input and output lists
are not written explicitly in the DCG rule, but are added when the
rule is translated (expanded) into an ordinary normal rule during
parsing.  Extra conditions, in the form of explicit Prolog literals or
control constructs such as {\em if-then-elses} ({\tt '->'/2}) or {\em
cuts}\index{cut} (\cut)\index{\texttt{"!/0}}, may be included in the {\em
Body} of the DCG rule and they work exactly as one would expect.

The syntax of DCGs is orthogonal to whether tabling is used for DCGs
or not.  An overview of DCG syntax
 supported by XSB is as follows:
\begin{enumerate}
\item A non-terminal symbol may be any HiLog term other than a variable
      or a number. A variable which appears in the body of a rule is
      equivalent to the appearance of a call to the standard predicate
      {\tt phrase/3} as it is described below.
\item A terminal symbol may be any HiLog term. In order to distinguish 
      terminals from nonterminals, a sequence of one or more terminal
      symbols   $\alpha, \beta, \gamma, \delta, \ldots$
      is written within a grammar rule as a Prolog list 
         {\tt [} $\alpha, \beta, \gamma, \delta, \ldots$ {\tt ]},
      with the empty sequence written as the empty list {\tt [\,]}.
      The list of terminals may contain variables but it has to be a 
      proper list, or else an error message is sent to the standard 
      error stream and the expansion of the grammar rule that contains 
      this list will fail. If the terminal symbols are ASCII character
      codes, they can be written (as elsewhere) as strings.
\item Extra conditions, expressed in the form of Prolog predicate calls, 
      can be included in the body (right-hand side) of a grammar rule by 
      enclosing such conditions in curly brackets, {\tt '$\{$'} and
      {\tt '$\}$'}.
      For example, one can write:
      \begin{center}
                {\tt positive\_integer(N) --> [N], $\{$integer(N), N > 0$\}$.}
                \footnote{A term like {\tt $\{$foo$\}$} is just a
			  syntactic-sugar for the term {\tt '$\{\}$'(foo)}.}
      \end{center}
\item The left hand side of a DCG rule must consist of a single non-terminal,
      possibly followed by a sequence of terminals (which must be written as
      a {\em unique} Prolog list). Thus in XSB, unlike SB-Prolog 
      version 3.1, ``push-back lists'' are supported.
\item The right hand side of a DCG rule may contain alternatives (written 
      using the usual Prolog's disjunction operator {\tt ';'} or 
      using the usual BNF disjunction operator {\tt '|'}. 
\item The Prolog control primitives {\em if-then-else} ({\tt '->'/2}),
      {\em nots} ({\tt not/1, fail\_if/1}, \not\ or {\tt tnot/1}) and 
      {\em cut}\index{cut} (\cut)\index{\texttt{"!/0}} may also be included in the 
      right hand side of a DCG rule. These symbols need not be enclosed in 
      curly brackets. 
      \footnote{Readers familiar with Quintus Prolog may notice the difference
                in the treatment of the various kinds of not. For example, in 
                Quintus Prolog a {\tt not/1} that is not enclosed within curly 
                brackets is interpreted as a non-terminal grammar symbol.}
      All other Prolog's control primitives, such as {\tt repeat/0}, must
      be enclosed explicitly within curly brackets if they are not meant
      to be interpreted as non-terminal grammar symbols.
\end{enumerate}
 

\section{Translation of Definite Clause Grammar rules}
%=====================================================

In this section we informally describe the translation of DCG rules
into normal rules in XSB.  Each grammar rule is translated into a
Prolog clause as it is consulted or compiled.  This is accomplished
through a general mechanism of defining the hook predicate {\tt
term\_expansion/2}, \index{\texttt{term\_expansion/2}} by means of which
a user can specify any desired transformation to be done as clauses
are read by the reader of XSB's parser.  This DCG term expansion is as
follows:

A DCG rule such as:

\stuff{
\> \> p(X) --> q(X).
}

\noindent
will be translated (expanded) into:

\stuff{
\> \> p(X, Li, Lo) :- \\ 
\> \> \>  q(X, Li, Lo).
}

If there is more than one non-terminal on the right-hand side, as in

\stuff{\> \> p(X, Y) --> q(X), r(X, Y), s(Y).}

\noindent
the corresponding input and output arguments are identified, 
translating into:

\stuff{
\> \> p(X, Y, Li, Lo) :- \\ 
\> \> \> q(X, Li, L1), \\
\> \> \> r(X, Y, L1, L2), \\
\> \> \> s(Y, L2, Lo).
}

Terminals are translated using the predicate {\tt 'C'/3} (See 
section~\ref{DCG_builtins} for its description).  For instance:

\stuff{\> \> p(X) --> [go, to], q(X), [stop].}

\noindent
is translated into:

\stuff{  
\> \> p(X, S0, S) :- \\
\> \> \> 'C'(S0, go, S1), \\
\> \> \> 'C'(S1, to, S2), \\
\> \> \> q(X, S2, S3), \\
\> \> \> 'C'(S3, stop, S).
}

Extra conditions expressed as explicit procedure calls naturally translate
into themselves. For example,

\stuff{
\> \> positive\_number(X) --> \\
\> \> \> [N], $\{$integer(N), N > 0$\}$, \\
\> \> \> fraction(F), $\{$form\_number(N, F, X)$\}$.}

\noindent
translates to:

\stuff{
\> \> positive\_number(X, Li, Lo) :- \\
\> \> \> 'C'(Li, N, L1), \\
\> \> \> integer(N), \\
\> \> \> N > 0, \\
\> \> \> L1 = L2, \\
\> \> \> fraction(F, L2, L3), \\
\> \> \> form\_number(N, F, N), \\
\> \> \> L3 = Lo. \\
}

Similarly, a cut is translated literally.

{\em Push-back lists} (a proper list of terminals on the left-hand side of 
a DCG rule) translate into a sequence of {\tt 'C'/3} goals with the first 
and third arguments reversed.
For example,

\stuff{\> \> it\_is(X), [is, not] --> [aint].}

\noindent
becomes

\stuff{
\> \> it\_is(X, Li, Lo) :- \\
\> \> \> 'C'(Li, aint, L1), \\
\> \> \> 'C'(Lo, is, L2), \\
\> \> \> 'C'(L2, not, L1).
}

Disjunction has a fairly obvious translation.  For example, the DCG clause:

\stuff{
\> \> expr(E) --> \\
\> \> \> \ \ expr(X), "+", term(Y), $\{$E is X+Y$\}$ \\
\> \> \>   | term(E).
}

\noindent
translates to the Prolog rule:

\stuff{
\> \>expr(E, Li, Lo) :- \\
\> \> \>   ( expr(X, Li, L1), \\
\> \> \> \ \ 'C'(L1, 43, L2), \> \% 0'+ = 43 \\
\> \> \> \ \ term(Y, L2, L3) \\
\> \> \> \ \ E is X+Y, \\
\> \> \> \ \ L3 = Lo \\
\> \> \>   ; term(E, Li, Lo) \\
\> \> \>   ).
}

\subsection{Definite Clause Grammars and Tabling}
%============================================================
\label{sec:dcg_tabling}

Tabling can be used in conjunction with Definite Clause Grammars to get the
effect of a more complete parsing strategy.  When Prolog is used to evaluate
DCG's, the resulting parsing algorithm is {\em ``recursive descent''}.
Recursive descent parsing, while efficiently implementable, is known to
suffer from several deficiencies:  1) its time can be exponential in the size
of the input, and 2) it may not terminate for certain context-free grammars (in
particular, those that are left or doubly recursive).  By appropriate use of
tabling, both of these limitations can be overcome.  With appropriate tabling,
the resulting parsing algorithm is a variant of {\em Earley's algorithm\/} and
of {\em chart parsing algorithms}.

In the simplest cases, one needs only to add the directive {\tt :-
auto\_table} (see Section~\ref{tabling_directives}) to the source file
containing a DCG specification.  This should generate any necessary
table declarations so that infinite loops are avoided (for
context-free grammars).  That is, with a {\tt :- auto\_table}
declaration, left-recursive grammars can be correctly processed.  Of
course, individual {\tt table} directives may also be used, but note
that the arity must be specified as two more than that shown in the
DCG source, to account for the extra arguments added by the expansion.
However, the efficiency of tabling for DCGs depends on the
representation of the input and output sequences used, a topic to
which we now turn.

\index{definite clause grammars!list mode}

Consider the expanded DCG rule from the previous section:

\stuff{ \>
\> p(X, S0, S) :- \\ 
\> \> \> 'C'(S0, go, S1), \\ 
\> \> \> 'C'(S1, to,S2), \\ 
\> \> \> q(X, S2, S3), \\ 
\> \> \> 'C'(S3, stop, S).  } 

In a Prolog system, each input and output variable, such as {\tt S0}
or {\tt S} is bound to a variable or a difference list.  In XSB, this
is called {\em list mode}.  Thus, to parse {\em go to lunch stop} the
phrase would be presented to the DCG rule as a list of tokens {\tt
[go,to,lunch,stop]} via a call to {\tt phrase/3} such as:

\stuff{\> \> phrase(p(X),[go,to,lunch,stop]).}

\noindent
or an explicit call to {\tt p/3}, such as:

\stuff{\> \> p(X,[go,to,lunch,stop|X],X).}

\noindent
Terminal elements of the sequence are consumed (or generated) via the
predicate {\tt 'C'/3} which is defined for Prolog systems as:

\stuff{\> \> 'C'([Token|Rest],Token,Rest).}

While such a definition would also work correctly if a DCG rule were
tabled, the need to copy sequences into or out of a table can lead to
behavior quadratic in the length of the input sequence (See Section
\ref{sec:TablingPitfalls}).  As an alternative, XSB allows a mode of
DCGs that defines {\tt 'C'/3} as a call to a Datalog predicte {\tt
word/3} \index{\texttt{word/3}}:

\stuff{\> \> 'C'(Pos,Token,Next\_pos):- word(Pos,Token,Next\_pos).}

\noindent
assuming that each token of the sequence has been asserted as a {\tt
word/3} fact, e.g:

\stuff{
\> \> word(0,go,1). \\
\> \> word(1,to,2). \\
\> \> word(2,lunch,3). \\
\> \> word(3,stop,4).
}

\noindent
The above mode of executing DCGs is called {\em datalog mode}.  
\index{definite clause grammars!datalog mode}

{\tt word/3} facts are asserted via a call to the predicate {\tt
tphrase\_set\_string/1}.  Afterwards, a grammar rule can be called
either directly, or via a call to {\tt tphrase/1}.  To parse the list
{\tt [go,to,lunch,stop]} in datalog mode using the predicate {\tt p/3}
from above, the call

\stuff{\> \> tphrase\_set\_string([go,to,lunch,stop])}

\noindent
would be made, afterwards the sequence could be parsed via the goal:

\stuff{tphrase(p(X)).}

\noindent
or

\stuff{p(X,0,F).}

To summarize, DCGs in list mode have the same syntax as they do in
datalog mode: they just use a different definition of {\tt 'C'/3}.  Of
course tabled and non-tabled DCGs can use either definition of {\tt
'C'/3}.  Indeed, this property is necessary for tabled DCG predicates
to be able to call non-tabled DCG predicates and vice-versa.  At the
same time,tabled DCG rules may execute faster in datalog mode, while
non-tabled DCG rules may execute faster in list mode.

Finally, we note that the mode of DCG parsing is part of XSB's state.
XSB's default mode is to use list mode: the mode is set to datalog
mode via a call to {\tt tphrase\_set\_string/3} and back to list mode
by a call to {\tt phrase/2} or by a call to {\tt reset\_dcg\_mode/0}.

\section{Definite Clause Grammar predicates} \label{DCG_builtins}
%================================================================
The library predicates of XSB that support DCGs are the following:

\begin{description}

\ouritem{phrase(+Phrase, ?List)}\index{\texttt{phrase/2}}
    This predicate is true iff the list {\tt List} can be parsed as a phrase 
    (i.e. sequence of terminals) of type {\tt Phrase}.  {\tt Phrase} can be 
    any term which would
    be accepted as a nonterminal of the grammar (or in general, it can 
    be any  grammar rule body), and must be instantiated to a
    nonvariable term  at the time of the call; otherwise an error
    message is sent to the standard error stream and the predicate fails. 
    This predicate is the usual way to commence execution of grammar rules.

    If {\tt List} is bound to a list of terminals by the time of the call,
    then the goal corresponds to parsing {\tt List} as a phrase of type
    {\tt Phrase}; otherwise if {\tt List} is unbound, then the grammar
    is being used for generation.

\ouritem{tphrase(+Phrase)}\index{\texttt{tphrase/1}} This predicate is
    succeeds if the current database of {\tt word/3} facts can be
    parsed via a call to the term expansion of {\tt +Phrase} whose
    input argument is set to {\tt 0} and whose output argument is set
    to the largest {\tt N} such that {\tt word(\_,\_,N)} is currently
    true.  

    The database of {\tt word/3} facts is assumed to have been
    previously set up via a call to {\tt tphrase\_set\_string/1} (or variant).  If
    the databse of {\tt word/3} facts is empty, {\tt tphrase/1} will
    abort.

% TLS: handle error condition better in predicate.

\ouritem{phrase(+Phrase, ?List, ?Rest)}\index{\texttt{phrase/3}}
    This predicate is true iff the segment between the start of list 
    {\tt List} and the start of list {\tt Rest} can be parsed as a phrase 
    (i.e. sequence of terminals) of type {\tt Phrase} . In other words, if 
    the search for phrase 
    {\tt Phrase} is started at the beginning of list {\tt List}, then 
    {\tt Rest} is what remains unparsed after {\tt Phrase} has been
    found. Again, {\tt Phrase} can be any term which
    would be accepted as a nonterminal of the grammar (or in general, any
    grammar rule body), and must be instantiated to a nonvariable term
    at the time of the call; otherwise an error message is sent to the
    standard error stream and the predicate fails.

    Predicate {\tt phrase/3} is the analogue of {\tt call/1} for grammar
    rule bodies, and provides a semantics for variables in the bodies of
    grammar rules.  A variable {\tt X} in a grammar rule body is treated
    as though {\tt phrase(X)} appeared instead, {\tt X} would expand into 
    a call to {\tt phrase(X, L, R)} for some lists {\tt L} and {\tt R}.  

\ouritem{expand\_term(+Term1, ?Term2)}\index{\texttt{expand\_term/2}}
    This predicate is used to transform terms that appear in a Prolog program
    before the program is compiled or consulted.
    The standard transformation performed by {\tt expand\_term/2} is that 
    when {\tt Term1} is a grammar rule, then {\tt Term2} is the corresponding
    Prolog clause; otherwise {\tt Term2} is simply {\tt Term1} unchanged. If
    {\tt Term1} is not of the proper form, or {\tt Term2} does not unify with
    its clausal form, predicate {\tt expand\_term/2} simply fails.

    Users may override the standard transformations performed by predicate
    {\tt expand\_term/2} by defining their own compile-time transformations.
    This can be done by defining clauses for the predicate
    {\tt term\_expansion/2}\index{\texttt{term\_expansion/2}}.
    When a term {\tt Term1} is read in when a file is being compiled or 
    consulted, {\tt expand\_term/2} calls {\tt term\_expansion/2} first;
    if the expansion succeeds, the transformed term so obtained is used and 
    the standard grammar rule expansion is not tried; otherwise, if 
    {\tt Term1} is a grammar rule, then it is expanded using {\tt dcg/2}; 
    otherwise, {\tt Term1} is used as is.  Note that predicate {\tt
    term\_expansion/2} must be defined in the XSB's default read-in
    module ({\tt usermod}) and should be loaded there before the compilation
    begins.

\ouritem{'C'(?L1, ?Terminal, ?L2)}\index{\texttt{`C'/3}}
This predicate generally is of no concern to the user.  Rather it is used 
    in the transformation of terminal symbols in 
    grammar rules and expresses the fact that {\tt L1} is connected 
    to {\tt L2} by the terminal {\tt Terminal}. This predicate is
    needed to avoid problems due to source-level
    transformations in the presence of control primitives such as
    {\em cuts}\index{cut} (\cut)\index{\texttt{"!/0}}, or {\em if-then-elses} 
    ({\tt '->'/2}) and is defined by the single clause:
    \begin{center}
                {\tt 'C'([Token|Tokens], Token, Tokens).}
    \end{center}
    The name 'C' was chosen for this predicate so that another useful
    name might not be preempted.

\ouritem{tphrase\_set\_string(+List)}\index{\texttt{tphrase\_set\_string/1}}
This predicate 

\begin{enumerate}
\item abolishes all tables;
\item retracts all {\tt word/3} facts from XSB's store; and
\item asserts new {\tt word/3} facts corresponding to {\tt List} as
described in Section \ref{sec:dcg_tabling}.
\end{enumerate}

\noindent
implicitly changing the DCG mode from list to datalog.

\ouritem{tphrase\_set\_string\_keeping\_tables(+List)}\index{\texttt{tphrase\_set\_string\_keeping\_tables/1}}
This predicate is the same as {\tt tphrase\_set\_string}, except
it does not abolish any tables.  When using this predicate, the
user is responsible for explicitly abolishing the necessary tables.

\ouritem{tphrase\_set\_string\_auto\_abolish(+List)}\index{\texttt{tphrase\_set\_string\_auto\_abolish/1}}
This predicate is the same as {\tt tphrase\_set\_string}, except
it abolishes tables that have been indicated as dcg-supported tables
by a previous call to {\tt set\_dcg\_supported\_table/1}.

\ouritem{set\_dcg\_supported\_table(+TabSkel)}\index{\texttt{set\_dcg\_supported\_table/1}}
This predicate is used to indicate to the DCG subsystem that a
particular tabled predicate is part of a DCG grammar, and thus the
contents of its table depends on the string being parsed.  {\tt
TabSkel} must be the skeleton of a tabled predicate.  When {\tt
tphrase\_set\_string\_auto\_abolish/1} is called, all tables that have
been indicated as DCG-supported by a call to this predicate will be
abolished.

\ournewitem{dcg(+DCG\_Rule, ?Prolog\_Clause)}{dcg}
\index{\texttt{dcg/2}}
    Succeeds iff the DCG rule {\tt DCG\_Rule} translates to the Prolog
    clause {\tt Prolog\_Clause}.  At the time of call, {\tt DCG\_Rule}
    must be bound to a term whose principal functor is {\tt '-->'/2}
    or else the predicate fails.  {\tt dcg/2} must be explicitly
    imported from the module {\sf dcg}.

\end{description}


\section{Two differences with other Prologs}\label{sec-dcg-differences}
%===========================================
The DCG expansion provided by XSB is in certain cases different 
from the ones provided by some other Prolog systems (e.g.  Quintus Prolog, 
SICStus Prolog and C-Prolog). The most important of these differences are:
\begin{enumerate}
\item XSB expands a DCG clause in such a way that when a \cut\ is 
      the last goal of the DCG clause, the expanded DCG clause is always 
      {\em steadfast}.

      That is, the DCG clause:

      \stuff{
      \> \> a --> b, ! ; c.
      }

      \noindent
      gets expanded to the clause:

      \stuff{
      \> \> a(A, B) :- b(A, C), !, C = B ;  c(A, B).
      }

      \noindent
      and {\em not\/} to the clause:

      \stuff{
      \> \> a(A, B) :- b(A, B), ! ; c(A, B).
      }

      \noindent
      as in Quintus, SICStus and C Prolog.

      The latter expansion is not just optimized, but it can have a
      {\em different (unintended) meaning} if {\tt a/2} is called with
      its second argument bound.

      However, to obtain the standard expansion provided by the other Prolog
      systems, the user can simply execute:
      
      \index{\texttt{set\_dcg\_style/1}}
      \stuff{
        \>\> set\_dcg\_style(standard).
      }
    
      To switch back to the XSB-style DCG's, call
      
      \stuff{
        \>\> set\_dcg\_style(xsb).
      }

\index{definite clause grammars!style}
      This can be done anywhere in the program, or interactively.
      By default, XSB starts with the XSB-style DCG's. To change that,
      start XSB as follows:

      \stuff{
        \> \> xsb -e "set\_dcg\_style(standard)."
        }

      Problems of DCG expansion in the presence of {\em cuts} have been known
      for a long time and almost all Prolog implementations expand a DCG
      clause with a \cut\ in its body in such a way that its expansion is
      steadfast, and has the intended meaning when called with its second
      argument bound.  For that reason almost all Prologs translate the DCG
      clause:

      \stuff{
      \> \> a --> ! ; c.
      }

      \noindent
      to the clause:

      \stuff{
      \> \> a(A, B) :- !, B = A ;  c(A, B).
      }

      \noindent 
      But in our opinion this is just a special case of a \cut\ being
      the last goal in the body of a DCG clause.


      Finally, we note that the choice of DCG style is orthogonal to
      whether the DCG mode is list or datalog.

\item Most of the control predicates of XSB need not be enclosed in
      curly brackets.  A difference with, say Quintus, is that predicates
      {\tt not/1}, {\not}, or {\tt fail\_if/1} do not get expanded when
      encountered in a DCG clause.  That is, the DCG clause:

      \stuff{
      \> \> a --> (true -> X = f(a) ; not(p)).
      }

      \noindent
      gets expanded to the clause:

      \stuff{
      \> \> a(A,B) :- (true(A,C) -> =(X,f(a),C,B) ; not p(A,B))
      }

      and {\em not\/} to the clause:

      \stuff{
      \> \> a(A,B) :- (true(A,C) -> =(X,f(a),C,B) ; not(p,A,B))
      }

      \noindent
      that Quintus Prolog expands to.

      However, note that all non-control but standard predicates (for example 
      {\tt true/0} and {\tt '='/2}) get expanded if they are not enclosed in 
      curly brackets.
\end{enumerate}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "manual1"
%%% End: 
