\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{fontenc}
\usepackage{hyperref}
\usepackage{verbatim}
\hyphenation{Pro-log}

\newcommand{\tab}{\hspace*{2em}}
\newcommand{\code}[1]{\texttt{#1}}
\newcommand{\codenl}[1]{\texttt{#1}\\}
%\newcommand{\code}[1]{\small \texttt{#1}\normalsize}
%\newcommand{\codenl}[1]{\small \texttt{#1}\normalsize\\}
\newcommand{\bypassop}{\{\}}
\newcommand{\superop}{{\large \textasciicircum \textasciicircum}}
\newcommand{\notop}{$\backslash$+}

\newenvironment{squote}{\begin{quote}\small}{\normalsize\end{quote}}

\renewenvironment{quote}{\begin{list}{}
	{\setlength{\leftmargin}{\parindent}}{\setlength{\rightmargin}{\leftmargin}}
	\item[]}{\end{list}}


\begin{document}


\pagestyle{headings}


\title{
	ISO/IEC DTR 13211--3:2006\\
	Definite clause grammar rules}

\author{
	Editor: Klaus.Daessler\\
	klaus.daessler@mathint.com\\}
\date{\today}

\maketitle

\setcounter{secnumdepth}{-1}
\section{Introduction} 
This technical report (TR) is an optional part of the International Standard for Prolog, ISO/IEC 13211. Prolog manufacturers wishing to implement Definite Clause Grammar rules in a portable way should do so in compliance with this technical report.

Grammar rules provide convenient functionality for parsing and processing text in a variety of languages. They have been implemented in many Prolog processors.  
%Klaus: find "variety of languages" OK
This TR is an extension to the ISO/IEC 13211--1 Prolog standard, adopting a similar structure. In particular, this TR adds new subclauses to, or modifies existing subclauses of ISO/IEC 13211--1.

\medskip

\subsection{Previous editors and draft documents} 
\begin{itemize}
	\item Paulo Moura: \textsl{ISO/IEC DTR 13211--	3:2006 Grammar rules in Prolog}, ISO, 2006-10
	\item Roger Scowen: \textsl{N171 --- ISO/IEC DTR 13211--3:2004 Grammar rules in Prolog}, ISO, 2004-05
	\item Tony Dodd: \textsl{DCGs in ISO Prolog --- A Proposal}, BSI, 1992
\end{itemize}


%\subsection{Draft document comments}

%\begin{itemize}
%	\item Paulo Moura: \textsl{Portuguese comments on ISO/IEC DTR 13211--3: 2004:  Grammar Rules in Prolog}, IPQ CT 167 WG17, 2005
%	\item Klaus Daessler: \textsl{German comments on ISO/IEC DTR 13211--3: 2004:  Grammar Rules in Prolog}, DIN NI22 WG17, 2005
%\end{itemize}

\newpage

\subsection{Contributors}

\textsl{This list needs to be completed; so far we have only included people present at the ISO meetings collocated with the ICLP (2005, 2006, and 2007), Richard O'Keefe, and the authors of the two drafts cited.} 
\begin{itemize}
	\item Bart Demoen (Belgium)
	\item David Warren (USA)
	\item Jan Wielemaker, (Netherlands)
	\item Joachim Schimpf (UK)
	\item Jonathan Hodgson (USA)
	\item Jose Morales (Spain)
	\item Katsuhiko Nakamura (Japan)
	\item Klaus Daessler (Germany)
	\item Manuel Carro (Spain)
	\item Manuel Hermenegildo (Spain)
	\item Mats Carlsson (Sweden)
	\item Mike Covington (USA)
	\item Paulo Moura (Portugal)
	\item Per Mildner (Sweden)
	\item Peter Szabo (Hungary)
	\item Peter Szeredi (Hungary)
	\item Pierre Deransart (France)
	\item Richard O'Keefe (NZ)
	\item Roger Scowen (UK)
	\item Tony Dodd (UK)
	\item Ulrich Neumerkel (Austria)
	\item Victor Santos Costa (Portugal)
\end{itemize}


\setcounter{secnumdepth}{+4}
\section{Scope}

This TR is designed to promote the applicability and portability of Prolog grammar rules in data processing systems that support standard Prolog as defined in ISO/IEC 13211--1:1995 and, if supported by the processor, in ISO/IEC 13211--2:2000, and the two Corrigenda of 13211-1: ISO/IEC 13211-1 Technical Corrigendum 1:2007-11, and ISO/IEC 13211-1 Technical Corrigendum 2:2012-02. This TR specifies: 
\newcounter{Lcount}
\begin{list}{\alph{Lcount})}{\usecounter{Lcount}}
	\item The representation, syntax, and constraints of Prolog grammar rules
	\item A logical expansion of grammar rules into Prolog clauses
	\item A set of built-in predicates for parsing with grammar rules
	\item  A reference implementation.
%	\item Reference implementations and tests for the specified built-in predicates and for a grammar rule translator 
\end{list}

%Klaus: In my opinion NOTE 2 should remain, because the requirements of pt 1 are fundamental to DTR DCGs,
% but what pt 1 excludes to define has to be explicit in DCGs

\noindent
NOTE --- The scope, expressed in clause 1, Scope, of ISO/IEC 13211--1:1995 does apply to this TR.


\section{Normative references}

The following TR contains provisions which, through reference in this text, constitute provisions
of this TR as Part of ISO/IEC 13211. 

\begin{itemize}

	\item ISO/IEC 13211-1:1995
	\item ISO/IEC 13211-2:2000
	\item Corrigendum 1 of 13211-1:2006
	\item Corrigendum 2 of 13211-1:2012

\end{itemize}	

\section{Definitions}

\textsl{For the purposes of this TR, the following Definitions are added to the ones specified in ISO/IEC 13211--1:}

\def\theparagraph{\arabic{section}.\arabic{paragraph}}

\paragraph{alternative:} A compound term with principal functor \code{(;)/2} or with principal functor \code{('|')/2} with each argument being a body (of a grammar-rule). 

\paragraph{body (of a grammar-rule):} See \code{grammar-rule-body}

\paragraph{clause-term:} A read-term \code{T.} in Prolog text where \code{T} does not have principal functor \code{(:-)/1} nor principal functor \code{(-->)/2.} (This definition replaces subclause 3.33 of ISO/IEC 13211--1).

\paragraph{comprehensive terminal-sequence:} see terminal-sequence, comprehensive.

\paragraph{cover, a terminal-sequence by a non-terminal (resp. a body):}  A
terminal sequence is covered by a non-terminal (resp. a body)  if the non-terminal
(resp. the body) generates the terminal sequence. Alternatively if the non-terminal (resp. body)
parses the terminal sequence.

\paragraph{definite clause grammar:} A definite clause grammar is a set of definite clause non-terminal definitions, and a definite clause non-terminal definition is a sequence of grammar-rules.

\paragraph{expansion (of a grammar-rule):} The preparation for execution (cf. ISO/IEC 13211--1, subclause 7.5.1) of a grammar rule.
% JPEH Is this right?
% KD I think so!

\paragraph{generating (wrt a non-terminal and a definite clause grammar):} Producing a terminal-sequence of that definite clause grammar, obeying semicontexts, if any.

% \paragraph{grammar-body-choice:} A compound term with principal functor \code{(->)/2}. The first argument is a body (of a grammar-rule), and the second argument is a body. 

\paragraph{grammar-body-element:} A grammar-body-cut (the atom \code{!}), or a grammar-goal, or a non-terminal, or a terminal-sequence.

\paragraph{grammar-body-not:} A compound term with principal functor \code{($\backslash$+)/1} whose argument is a body (of a grammar rule). 

\paragraph{grammar-body-sequence:} A compound term with principal functor \code{(',')/2} and each argument being a body (of a grammar-rule). 

\paragraph{grammar-goal:} A compound term with principal functor \code{\{\}/1} whose argument is a goal. 

\paragraph{grammar-rule:} A compound term with principal functor \code{(-->)/2}.

\paragraph{grammar-rule-body:} A compound term which forms, or is in the form of, the second argument of a grammar-rule. A grammar-body-sequence, or an alternative, or a grammar-body-not,  or a grammar-body-element. 

% the next definition is changed JPEH. 
\paragraph{grammar-rule-head:}\label{defGrammarRuleHead} The first argument of a grammar-rule. 
Either a non-terminal (of a grammar), or a compound term whose principal functor is \code{(',')/2}, 
where the first argument is a non-terminal (of a grammar), and the
second argument is a semicontext (cf Definition \ref{defSemiContext}). 

\paragraph{new variable with respect to a term T:} A variable that is not a member of the variable set of \code{T}. 

\paragraph{non-terminal (of a grammar-rule):} A callable term (cf. ISO/IEC 13211--1, Definitions 3.25), i.e., an atom or a compound term, that denotes a non terminal symbol of a grammar rule. 

\paragraph{non-terminal indicator:}\label{defNonTerminalInd} A compound term \code{A//N} where \code{A} is an atom and \code{N} is a non-negative integer, denoting one particular non-terminal (cf \ref{ssection:nonterminalIndicator}). 

\paragraph{parsing (wrt. a definite clause grammar):} Successively accepting or consuming terminal-sequences, assigning them to corresponding non-terminals and obeying  semicontexts, if any.

\paragraph{remaining terminal-sequence:} See terminal-sequence, remaining.

\paragraph{semicontext:}\label{defSemiContext} A terminal-sequence occurring optioally after the non-terminal of a grammar-rule-head, constraining parsing (respectively generation) by this grammar rule. 

\paragraph{steadfastness of a goal wrt. an argument} Goal \code{G} is steadfast in argument \code{n} of its sequence of arguments, if for any term \code{T} that is the \code{n}th argument in the goal, and the goal \code{Gnw} 
that results by replacing \code{T} by a new variable \code{Vnw} the execution (cf. ISO/IEC 13211--1, subclause 7.7.1) of \code{G} and \code{(Gnw, Vnw=T)} is the same. 

\paragraph{terminal (of a grammar):} Any Prolog term that denotes a terminal symbol of the grammar. 

\paragraph{terminal-sequence:}\label{defTerminalSequence} A list (cf. ISO/IEC 13211--1, subclauses 3.99, 6.3.5 and 6.3.1.3) whose first argument, if any, is a terminal (of a grammar), and the second argument, if any, is a terminal-sequence.

\paragraph{terminal-sequence, comprehensive:} Terminal sequence containing a  prefix, and the prefix covered (cf. Definition 3.5) by a grammar-rule-body, i.e. accepted resp. generated by \code{phrase/3} (cf \ref{sssection:phraseSpecification}) .

\paragraph{terminal-sequence, remaining:} Rest of comprehensive terminal-sequence without the leading terminal-sequence covered (cf. Definition 3.5) by a grammar-rule-body.

\paragraph{variable, new with respect to a term T:} See \textsl{new variable with respect to a term \code{T}}.

\newpage

\section{Symbols and abbreviations}

NOTE --- No changes from the ISO/IEC 13211--1 Prolog standard.


\section{Compliance}


\subsection{Prolog processor}
\label{strictMode}

\noindent
A conforming Prolog processor shall:
\begin{list}{\alph{Lcount})}{\usecounter{Lcount}}
	\item Correctly prepare for execution Prolog text which conforms to: 
\renewcommand{\labelenumi}{\theenumi.}
\begin{enumerate}
	\item the requirements of this TR, and 
	\item the requirements of ISO/IEC 13211--1, and 
	\item the implementation defined and implementation specific features of the Prolog processor, 
\end{enumerate}
	\item Correctly execute Prolog goals which have been prepared for execution and which conform to: 
\begin{enumerate}
	\item the requirements of this TR, and 
	\item the requirements of ISO/IEC 13211--1, and 
	\item the implementation defined and implementation specific features of the Prolog processor, 
\end{enumerate}
	\item Reject any Prolog text or read-term whose syntax fails to conform to: 
\begin{enumerate}
	\item the requirements of this TR, and 
	\item the requirements of ISO/IEC 13211--1, and 
	\item the implementation defined and implementation specific features of the Prolog processor, 
\end{enumerate}
	\item Specify all permitted variations from this TR in the manner prescribed by this TR and by the ISO/IEC 13211--1, and 
	\item Offer a strictly conforming mode which shall reject the use of an implementation specific feature in Prolog text or while executing a goal. 
\end{list}

\noindent
NOTE --- This extends the corresponding subclause of ISO/IEC 13211--1.

\subsection{Prolog text}

\noindent
NOTE --- No changes from the ISO/IEC 13211--1 Prolog standard.


\subsection{Prolog goal}

NOTE --- No changes from the ISO/IEC 13211--1 Prolog standard.


\subsection{Documentation}

\noindent
\textsl{The corresponding subclause in the ISO/IEC 13211--1 Prolog standard is modified as follows:}\\

\noindent
A conforming Prolog processor shall be accompanied by documentation that completes the definition of every implementation defined and implementation specific feature specified in this TR and in ISO/IEC 13211--1 Prolog. 

\subsection{Extensions}

\noindent
\textsl{The corresponding subclause in the ISO/IEC 13211--1 Prolog standard is modified as follows:}\\

\noindent
A processor may support, as an implementation specific feature, any construct that is implicitly or explicitly undefined in this TR or in the ISO/IEC 13211--1 Prolog standard.\\
 
\noindent 
A Prolog processor may support additional grammar control constructs, beyond the required ones by this standard (cf. \ref{ssection:controlConstructs}).
These additional control constructs must be treated as non-terminals by a Prolog processor working in a strictly conforming mode (see \ref{strictMode}e).

\medskip
\noindent
NOTE ---  Examples for additional grammar control constructs include \textsl{soft-cuts} and control constructs that enable the use of grammar rules stored on encapsulation units other than modules, such as objects.

\setcounter{subsubsection}{1}
\subsubsection{Predefined operators}

\textsl{Please see subclause \ref{ssection:grammarRuleOperator} for the new predefined operators that this TR adds to the ISO/IEC 13211--1 Prolog standard.}


\section{Syntax}


\subsection{Notation}


\subsubsection{Backus Naur Form}

\noindent
\textsl{No changes from the ISO/IEC 13211--1 Prolog standard.}


\subsubsection{Abstract term syntax}

\textsl{The text near the end of this subclause in the ISO/IEC 13211--1 Prolog standard is modified as follows:}\\

\noindent
Prolog text (6.2) is represented abstractly by an abstract list \code{x} where \code{x} is: 

\begin{list}{\alph{Lcount})}{\usecounter{Lcount}}
	\item  \code{d.t} where \code{d} is the abstract syntax for a directive, 
and \code{t} is Prolog text, or 
	\item  \code{g.t} where \code{g} is the abstract syntax for a grammar 
rule, and \code{t} is Prolog text, or 
	\item  \code{c.t} where \code{c} is the abstract syntax for a clause, 
and \code{t} is Prolog text, or 
	\item  \code{nil}, the empty list.
\end{list}

\noindent
\textsl{The following subclause extends, with the specified number, the corresponding ISO/IEC 13211--1 subclause.}


\setcounter{subsubsection}{2}
\subsubsection{Variable names convention for terminal-sequences}
\label{sssection:variableNameConvention}

This TR uses variables named \code{S0}, \code{S1}, ..., \code{S} to represent the terminal-sequences used as arguments when processing grammar rules or when expanding grammar rules into clauses. In this notation, the variables \code{S0}, \code{S1}, ..., \code{S} can be regarded as a sequence of states, with \code{S0} representing the initial state and the variable \code{S} representing the final state. Thus, if the variable \code{Si} represents the terminal-sequence in a given state, the variable \code{Si+1} will represent the remaining terminal-sequence after parsing \code{Si} with a grammar rule.\\
 
\subsection{Prolog text and data}

\noindent
\textsl{The first paragraph of this subclause on ISO/IEC 13211--1 is modified as follows:}\\

\noindent
Prolog text is a sequence of read-terms which denote (1) directives, (2) grammar rules, and (3) clauses of user-defined procedures.


\subsubsection{Prolog text} 
\noindent
\textsl{The corresponding subclause in the ISO/IEC 13211--1 is modified as follows:}\\

\noindent
Prolog text is a sequence of directive-terms, grammar-rule terms, and clause-terms.

\begin{tabular}{l l l l}
~ & \code{prolog text =} &  \code{p text} & ~\\
Abstract: & \textsl{pt} & \textsl{pt} & ~\\
~ & \code{p text =} & \code{directive term ,} & \code{p text}\\
Abstract: & \textsl{d.t} & \textsl{d} & \textsl{t}\\
~ & \code{p text =} & \code{grammar rule term ,} & \code{p text}\\
Abstract: & \textsl{g.t} & \textsl{g} & \textsl{t}\\
~ & \code{p text =} & \code{clause term ,} & \code{p text}\\
Abstract: & \textsl{c.t} & \textsl{c} & \textsl{t}\\
~ & \code{p text =} & \code{;}\\
Abstract: & \textsl{nil}
\end{tabular}

\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}
\paragraph{Directives} ~\\

\noindent
\textsl{Syntactically, there are no changes w.r.t. ISO/IEC 13211--1 Prolog standard, with the exception
of the operator syntax (cf \ref{ssection:grammarRuleOperator}); for
the semantic changes see \ref{sssection:prologDirectives} of this TR. Whenever directives are applicable
to non-terminals, the non-terminal indicators (cf \ref{ssection:nonterminalIndicator}),
as arguments of these directives, shall be used like predicate indicators for the predicates, resulting
from expanding these non-terminals.}

\medskip
\noindent
NOTE --- The directives \code{dynamic/1, multifile/1 and discontiguous/1} are applicable to
non-terminal indicators.


\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}
\paragraph{Clauses} ~\\

\noindent
\textsl{The corresponding subclause in the ISO/IEC 13211--1 is modified as follows:}\\

\begin{tabular}{l l l}
~ & \code{clause term =} & \code{term, end}\\
Abstract: & \textsl{c} & \textsl{c}\\
Priority: & 1201\\
Condition: & The principal functor of \code{c} is not \code{(:-)/1}\\
Condition: & The principal functor of \code{c} is not \code{(-->)/2}\\
\end{tabular}

\medskip
\noindent
NOTE --- Subclauses 7.5 and 7.6 define how clauses become part of the database.\\

\noindent
\textsl{The following subclause modifies, with the specified number, the corresponding ISO/IEC 13211--1 subclause:}

\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}
\paragraph{Grammar rules} ~\\

\begin{tabular}{l l l}
~ & \code{grammar rule term =} & \code{term, end}\\
Abstract: & \textsl{gt} & \textsl{gt}\\
Priority: & 1201\\
Condition: & The principal functor of \code{gt} is \code{(-->)/2}\\
\\
~ & \code{grammar rule =} & \code{grammar rule term}\\
Abstract: & \textsl{g} & \textsl{g}\\
\end{tabular}
\\

\medskip
\noindent
NOTE --- Subclause \ref{section:logicalExpansion} of this TR defines how a grammar rule in Prolog text is expanded into an equivalent clause when Prolog text is prepared for execution.

\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}
\paragraph{Semicontexts} ~\\

\begin{tabular}{l l l}
~ & \code{semicontext term =} & \code{term}\\
Abstract: & \textsl{sc} & \textsl{sc}\\
Priority: & 1201\\
Condition: & semicontext term is a list\\
\\
~ & \code{semicontext =} & \code{semicontext term}\\
Abstract: & \textsl{s} & \textsl{s}\\
\end{tabular}

\medskip
\noindent
NOTE --- Subclause \ref{section:logicalExpansion} of this TR, \code{dcg\_rule/4}, first clause, defines how a semicontext in a grammar rule is expanded when Prolog text is prepared for execution.
% Modified JPEH.
% Accepted and corrected KD

\subsection{Terms}
\label{ssection:grammarRuleOperator}

\noindent
Extend the operator table of subclause 6.3.4.4 of ISO/IEC 13211--1 as follows: \\


\begin{tabular}{l l l}

\code{Priority} & \code{Specifier} & \code{Operator(s)} \\

1105 & \code{xfy} & \code{'|'} \\

\end{tabular}

\medskip
\noindent
NOTE --- The operator \code{(-->)/2}, specified in subclause 6.3.4.4 of the ISO/IEC 13211--1 Prolog standard, is used as the principal functor of grammar rules.



\section{Language concepts and semantics}

\noindent
\textsl{The following subclause extends, with the specified number, the corresponding ISO/IEC 13211--1 subclause:}

\setcounter{subsection}{3}
\subsection{Prolog text}
\label{ssection:prologText}


\setcounter{subsubsection}{1}
\subsubsection{Directives}
\label{sssection:prologDirectives}

A non-terminal indicator may appear anywhere that a predicate indicator can appear in the following directives:
\code{multifile/1}, and \code{discontiguous/1}  as specified in subclause 7.4.2 of the ISO/IEC 13211--1 Prolog standard.


\setcounter{subsubsection}{3}
\subsubsection{Grammar rules}

A grammar rule term in Prolog text (6.2.1.3) enables suitable clauses to be added to the database.\\ 
\noindent
The non-terminal indicator NT//N of the non-terminal of the grammar-rule-head shall not be the non-terminal-indicator of a grammar control construct, and the predicate indicator NT/M where M is N + 2 shall not be the predicate indicator of a built-in predicate or a control construct.\\

% no mixing remark! multifile, discontiguous geeignet verweisen oder wiederverwenden.
\noindent
During preparation for execution the Prolog processor converts grammar rule terms to Prolog procedures of the database. Section 10 of this DTR defines a correspondence between  grammar rule terms and suitable clauses of a procedure in the database.


\begin{comment}
% MODULES STUFF
\medskip
\noindent
If the Prolog processor supports Prolog Modules as defined in ISO/IEC 13211-2:2000, a non-terminal indicator may appear anywhere that a predicate indicator can in the Module interface directives
\code{export/1, reexport/1, reexport/2} and the Module directives \code{import/1, import/2}
of subclause 6.24 of ISO/IEC 13211-2:2000. Higher order interferences between Prolog Modules and Definite Clause Grammars
(e.g. meta non-terminals) shall be implementation specific.
\end{comment}

\subsection{Database}


\subsubsection{Preparing a Prolog text for execution}
If a Prolog grammar rule with non-terminal indicator NT//N is prepared for execution, and a Prolog clause with predicate-indicator NT/M, where M is N + 2, is already part of the extended database, or vice versa, then the effect of this preparation for execution shall be implementation dependent.\\

\begin{comment}
%MODULES STUFF
\setcounter{subsection}{12}
\subsection{Predicate properties}
\label{ssection:predicateProperties}

\textsl{The following subclause extends subclauses 6.8 and 7.2.2 of ISO/IEC 13211--2 Prolog Modules:}

\noindent
The following property is added to the list of predicate properties of subclause 6.8
of ISO/IEC 13211--2:

\begin{itemize}
	\item \code{expanded\_from(A//N)} --- The predicate resp. callable with predicate indicator \code{A/(N+2)} results from the expansion of a grammar rule with non-terminal indicator \code{A//N}, (cf. Definition 3.18 and subclause \ref{ssection:nonterminalIndicator}). 
\end{itemize}

\medskip

\noindent
NOTE  --- a predicate property is the second argument of the built-in predicate \code{predicate\_property(Callable, Property)}, cf. subclause 6.8 of ISO/IEC 13211--2.\\
\noindent
NOTE 2  --- the \code{expanded\_from/2} property name was chosen in order to account for other possible, implementation-specific expansions.
\end{comment}

%Klaus: was some wisdom from Paulo, don't remember why. Omitted.

\setcounter{subsection}{12}
\subsection{Grammar rules}

\subsubsection{terminals and non-terminals}

\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}
 
In grammar rule bodies, one or more terminals are represented by terms directly contained in lists in order to distinguish them from non-terminals.
The empty terminal sequence (empty list) is possible.
Non-terminals are represented by callable terms.\\

\medskip
\noindent
NOTE --- In the context of a grammar rule, \textsl{terminals} represent tokens of some language, and \textsl{non-terminals} represent sequences of tokens (see, respectively, Definitions 3.23 and 3.17).

\begin{comment}
String notation may be used as an alternative to lists when the terminals are characters and the 
flag "double\_quotes" has value "chars"; see subclauses 6.3.7 and 6.4.6 of ISO/IEC 13211--1. 

\noindent
Using the values \code{"codes"} and \code{"atoms"} for String notation of terminals shall be implementation specific.
\end{comment} 

\paragraph{Example} 

\ \vspace{1em}

\noindent
A simple grammar consisting of 11 grammar rules, parsing or generating 
terminal sequences of the form

\begin{quote}
\begin{verbatim}
	[the, dog, runs]
	[the, dog, barks]
	[the, dog, bites]
	[the, nice, cat, barks]
\end{verbatim}
\end{quote}		

\noindent
is given:

\begin{quote}
\begin{verbatim}
	sentence		--> noun_phrase, verb_phrase.
	verb_phrase		--> verb.
	noun_phrase		--> article, noun.
	noun_phrase		--> article, adjective, noun.
	article		--> [the].
	adjective		--> [nice].
	noun			--> [dog].
	noun			--> [cat].
	verb			--> [runs].
	verb			--> [barks].
	verb			--> [bites].
\end{verbatim}
\end{quote}	

\noindent
Here the symbols \code{sentence, verb\_phrase, verb} etc. denote non-terminals, whereas
\code{runs, nice, cat} etc. denote terminals.	
	

\subsubsection{Format of grammar rules}

A grammar rule has the format:
\begin{quote}
\begin{verbatim}
GRHead --> GRBody.
\end{verbatim}
\end{quote}
where \code{GRHead}, the grammar-rule-head (cf. Definition 3.15), can be rewritten by \code{GRBody}, its grammar-rule-body (cf. Definition 3.14). The head and the body of grammar rules are constructed from \textsl{terminals} and \textsl{non-terminals}, including special non-terminals, the \textsl{grammar control constructs}. The grammar-rule-head is a non-terminal, or a non-terminal, followed by a terminal-sequence (a \textsl{semicontext}, see \ref{sssection:rightHandcontext}):
\begin{quote}
\begin{verbatim}
NonTerminal --> GRBody.

NonTerminal, Semicontext --> GRBody. 
\end{verbatim}
\end{quote}

\noindent
If \code{NonTerminal} is a grammar control construct its effect shall be implementation dependent.\\
\noindent
The effect of a \code{Semicontext} which is not a terminal-sequence shall be implementation dependent.\\


\noindent
The control constructs that may be used in a body are described in subclause \ref{ssection:controlConstructs}. An empty body is represented by an empty terminal sequence:
\begin{quote}
\begin{verbatim}
GRHead --> [].
\end{verbatim}
\end{quote}

\medskip

\noindent
NOTE  --- There is no \code{(-->)/1} form for grammar rules.


\subsubsection{Semicontext}
\label{sssection:rightHandcontext}

\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}

\paragraph{Description}

\ \vspace{1em}

\noindent
A \textsl{semicontext} is a terminal-sequence (see \ref{defTerminalSequence}), which follows, separated by a comma,  the non-terminal of the head of a grammar rule (see \ref{defGrammarRuleHead}).  The terminals of the semicontext make up a prefix of
the remaining terminal-sequence.

% \paragraph{Syntax}

% \begin{quote}
% \begin{verbatim}

% RightHandContext   =  TerminalSequence

% \end{verbatim}
% \end{quote}

\paragraph{Examples}

\ \vspace{1em}

\noindent
Assume we need rules to \textsl{look-ahead} one or two tokens that would be consumed next. This could be accomplished by the following grammar rules:
\begin{quote}
\begin{verbatim}
look_ahead(X), [X]      --> [X]. 
look_ahead(X, Y), [X,Y] --> [X,Y].
\end{verbatim}
\end{quote}
When used for parsing, procedurally, these grammar rules can be interpreted as, respectively, consuming, and then restoring, one or two terminals. \\
\noindent
Another example may be a small grammar rule with semicontext:
\begin{quote}
\begin{verbatim}
phrase1, [word] --> phrase2, phrase3.
\end{verbatim}
\end{quote}
\noindent
After preparation for execution this may occur in the database as follows.
\noindent
\begin{quote}
\begin{verbatim}
phrase1(S0, S):-
    phrase2(S0, S1),
    phrase3(S1, S2),
    S = [word | S2].
\end{verbatim}
\end{quote}

\medskip
\noindent
NOTES\\

\noindent
1\hspace{1.5em} In case of parsing, as soon as \code{phrase2} and \code{phrase3} have successfully parsed the comprehensive terminal-sequence (input list), the terminal \code{word} is prefixed to the remaining terminal-sequence. \code{word} is then the first terminal to be consumed in further parsing after \code{phrase1}. Thus further parsing is constrained by the semicontext.\\  

% process from path JPEH  March 28th Simplified second sentence. JPEH
% KD fixed

\noindent
2\hspace{1.5em} The concepts \textsl{comprehensive terminal-sequence} resp. \textsl{remaining terminal-sequence} are often called \textsl{input list} resp. \textsl{output list}. This is misleading, because it only considers  the case of parsing using  a grammar. There a terminal list shall be parsed wrt. non-terminals, and there will be a  remainder after the parsing step. The inverse case, generating sentences by expanding grammars, where the comprehensive terminal-sequence is the output list, is ignored by such wording.\\
% Above par modified JPEH  also March 2014 
% KD In former versions of the Draft (by Paulo) only the concepts of input list and output list were used.
% The meaning was that during parsing a non-terminal consumes some terminals from the (larger) input list,
% and there remains a (smaller) output list, subject to following parsing. But for generating it is the opposite,
% there the output is larger (i.e. contains more terminals) than the input list. The wording input list and
% output list is very colloquial, therefore shall be a clarification here.

\noindent
3\hspace{1.5em}  There are cases, where the remaining terminal-sequence is the comprehensive terminal-sequence. See, e.g. the following grammar rule. There maybe a trailing terminal-sequence, however, as the following example shows.
% Above par modified JPEH
% KD OK

\noindent
\begin{quote}
\begin{verbatim}

nt,[word] --> [].
\end{verbatim}
\end{quote}

\noindent
which may be expanded by preparation for execution to:

\noindent
\begin{quote}
\begin{verbatim}

nt(S0, S) :- S = [word|S0]). 
\end{verbatim}
\end{quote}
\noindent
This non-terminal \code{nt} represents an empty terminal sequence (cf. \ref{sssection:emptySequence}), but constrains
further parsing to take place with  \code{word} as next token.\\

\noindent
4\hspace{1.5em} It should be noted that \code{phrase/2} (cf \ref{sssection:bootstrappedPredicates}) cannot succeed when applied to a grammar rule, whose head contains a non empty semicontext, as in the case above.\\
% Modified JPEH 
% KD OK

\noindent
5 \hspace{1.5em} Some processors allow a cut in the semicontext; e.g.\\ 

\code{a, !, [word] --> b.}\\
Moving this
cut to the end of the grammar body, c.f. \code{a, [word] --> b, !.} leads to identical execution.
Thus this TR does not permit a cut in the semicontext.


\subsubsection{Non-terminal indicator}

\label{ssection:nonterminalIndicator}

A \textsl{non-terminal indicator} is a compound term \code{//(A, N)} where \code{A} is an atom and \code
{N} is a non-negative integer.\\

\noindent
The non-terminal indicator \code{//(A, N)} indicates the non-terminal of the head of a grammar rule where \code{A} is an atom, representing the non-terminal, and  \code{N} is its arity, a non-negative integer\\

\medskip
\noindent
NOTES\\

\noindent
1\hspace{1.5em}In Prolog text, including ISO/IEC 13211--1 and this TR, a non-terminal indicator \code{//(A, N)} is normally written as \code{A//N}
or as \code{(A)//N} depending on whether or not A is an operator (cf. 7.1.6.6 of 13211--1).\\

\noindent
2\hspace{1.5em}The concept of non-terminal indicator is similar to the concept of \textsl{predicate indicator} defined in subclauses 3.131 and 7.1.6.6 of the ISO/IEC 13211--1 Prolog. Non-terminal indicators may be used in exception terms thrown when processing or using grammar rules. In addition, non-terminal indicators may appear at some places, where a predicate indicator as defined in ISO/IEC 13211--1 can appear. See \ref{sssection:prologDirectives}.  Furthermore non-terminal indicators may be used in a predicate property (cf. subsection \ref{ssection:predicateProperties}). In particular, using non-terminal indicators in predicate directives allows the details of the expansion of grammar rules into Prolog clauses to be abstracted.




\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}

\paragraph{Examples}

\ \vspace{1em}

\noindent
For example, given the following grammar rule:
\begin{quote}
\begin{verbatim}
sentence --> noun_phrase, verb_phrase.
\end{verbatim}
\end{quote}

\noindent
The corresponding non-terminal indicator for the grammar rule left-hand side non-terminal is \code{sentence//0}. \\
\noindent
\begin{quote}
\begin{verbatim}
:- multifile(sentence//0).
\end{verbatim}
\end{quote}

\noindent
So grammar rules for \code{sentence//0} may be distributed over several files.\\

\begin{comment}

%MODULES STUFF, and context-dependency stuff.
:- export(sentence//0).
\end{verbatim}
\end{quote}

\noindent
So the grammar rules of M for the non-terminal \code{sentence//0} can be used outside module M.

% was decided on Istanbul conference. Contents should occur in 7.15.7

\subsubsection{Prolog goals in grammar rules}

\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}

\paragraph{Description}

\ \vspace{1em}

\noindent
In the body of grammar rules, curly brackets enclose a Prolog goal that is executed when the grammar rule, prepared for execution, is executed.\\

\noindent
\code{\{\}/1} is a functor of a \code{grammar-goal}  \{prolog\_goal\} (cf. Definition 3.12). After expansion 
\code{prolog\_goal} is unchanged and is handled as a ordinary prolog goal according to subclause 7.7 of ISO/IEC 13211-1 Prolog.\\

\medskip
\noindent
NOTE --- The ISO/IEC 13211--1 Prolog standard defines, in subclause 6.3.6, a \textsl{curly bracketed term} as a compound term with principal functor \code{'\{\}'/1}, whose argument may also be expressed by enclosing its argument in curly brackets.


\paragraph{Examples}

\ \vspace{1em}

\noindent
Consider, for example, the following grammar rule:
\begin{quote}
\begin{verbatim}
move(Dist) --> step(Dist).
move(Dist) --> step(Dist1), move(Dist2), {Dist is Dist1 + Dist2}.
step(1) --> up.
step(-1)--> down.
\end{verbatim}
\end{quote}
This grammar generates steps of a robot. The second rule computes a constraining distance for several move patterns.

\end{comment}

\subsection{Grammar control constructs}
\label{ssection:controlConstructs}

\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}

This definition of each grammar control construct gives its logical meaning and the procedural effects 
for executing it wrt. its arguments, if any, after preparing it for execution.\\


\noindent
Expansion of grammar control constructs is not simply a replacement by Prolog control constructs. 
For the expansion of every grammar control construct there is a formal definition in subclause \ref{section:logicalExpansion}.\\
The correspondence between the following subclauses and the corresponding formal definitions is given by the
argument of the clauses of predicate \code{dcg\_constr/1} or, respectively, by the 
principal functor of the first argument of the clauses of predicate \code{dcg\_cbody/4} in subclause \ref{section:logicalExpansion}\\

\noindent
After preparation for execution of Grammar Rules, named ``Grammar Rule expansion'' or ``expansion'' for short, the non-terminals, with exception of phrase//1, 
result in control constructs, respectively built-in predicates of ISO/IEC 13211-1 Prolog. 
Grammar Rule expansion is defined by using the built-in predicate \code{phrase/3}  
(see subclause \ref{sssection:phraseSpecification}) and subclause \ref{section:logicalExpansion}.\\

\noindent 
The following subclauses explicate the linkages between the terminal sequences upon expansion of the control constructs.
\noindent

\subsubsection{\code{[]//0} -- empty terminal-sequence}
\label{sssection:emptySequence}

\paragraph{Description}

\ \vspace{1em}

\noindent
In \code{phrase([ ], S0, S)} the expansion result of the grammar control construct \code{empty terminal-sequence} 
(a terminal sequence without contents) unifies the 
remaining terminal sequence \code{S} with the comprehensive terminal sequence \code{S0},
i.e. has no effect on parsing resp. generating during execution.\\ 


\subsubsection{\code{('.')//2} -- terminal sequence}

\paragraph{Description}

\ \vspace{1em}

\code{('.')} used as a non-terminal \code{('.')//2} separates its first argument, the terminal on its left hand side
from the second argument, the terminal sequence on its right hand side.

\noindent
\subsubsection{\code{(',')//2} -- concatenation}

\paragraph{Description}

\ \vspace{1em}

\noindent
In the body of a grammar-rule the non-terminal \code{(',')//2} acts as principal functor of a \code{grammar-body-sequence} (cf. Definition 3.11) 
with a first grammar body GBFirst and a second grammar body GBSecond. Each of them is then subject to subsequent separate 
expansion - GBFirst first, and then GBSecond. After being completely expanded, the expansions of GBFirst and GBSecond shall be arguments of 
a conjunction wrt. subclause 7.8.5 of ISO/IEC 13211-1 Prolog, which results from expansion of \code{(',')//2}. \\

\noindent
If contained directly in the head(of a grammar rule), \code{(',')//2} acts simply as main functor \code{(',')/2} of a term consisting of an 
expanded grammar-rule-head and a semicontext;
cf \ref{sssection:rightHandcontext}.

\subsubsection{\code{(;)//2} -- alternative}

\label{sssection:alternative}

\paragraph{Description}

\ \vspace{1em}

\noindent
An alternative grammar control construct, whose first argument is of the form \code{->( \_ , \_ )} shall be an if-then-else grammar control construct.
In the body of a grammar rule \code{(;)//2} acts as principal functor of an \\ \code{alternative}. (cf. Definition 3.1) with a first grammar body GBFirst and a second grammar body GBSecond. 
Each of them is subject to subsequent separate expansion. The alternative is expanded to the disjunction \code{(;)/2}; cf subclause 7.8.6 of ISO/IEC 13211-1 Prolog. 
After being expanded, the expansion of GBFirst shall be the first, and the expansion of GBSecond shall be the second argument of the disjunction, which results from expansion of \code{(;)//2}.\\ 

\medskip
\noindent
NOTE  ---  The effect of comma and semicolon, \code{(',')//2}, \code{(;)//2}, may be understood best by application of \code{write\_canonical/1} (see subclause 8.14.2.5 of ISO/IEC 13211--1) on a grammar rule, containing them:

\begin{quote}
\begin{verbatim}
?- write_canonical((sentence --> subject, verb, object;
                                object, verb, subject)).

--> (sentence, ;(','(subject, ','(verb, object)),
                (','(object, ','(verb, subject))))
yes
\end{verbatim}
\end{quote}
\noindent
This may lead to the following Prolog clause after preparation for execution: 

\begin{quote}
\begin{verbatim}
sentence(S0, S) :-
   ( subject(S0, S1),
     verb(S1, S2),
     object(S2, S)
   ; object(S0, S3),
     verb(S3, S4),
     subject(S4, S)
   ).
\end{verbatim}
\end{quote}

\subsubsection{\code{(;)//2} with \code{(->)//2} -- if-then-else}

\label{sssection:ifThenElse}

\paragraph{Description}

\ \vspace{1em}

\noindent
NOTE -- \code{(;)//2} (cf. \ref{sssection:alternative}) serves two different functions depending on whether or not its first argument is a compound term
with grammar control construct \code{(->)//2}.\
See \ref{sssection:alternative} for the use of \code{(;)//2} for \code{alternative}, when
the first argument of \code{(;)//2} does not immediately contain a grammar control construct \code{(->)//2}.\


\paragraph{Description}

\ \vspace{1em}

\noindent
In the grammar control construct \code{ ;(->(GRIf, GRThen),GRElse)} 
the grammar control construct \code{(;)//2} has as arguments a grammar rule body \code{->(GRIf, GRThen)} and a second grammar rule body GRElse. \\
The grammar rule bodies GRIf, GRThen and GRElse are subject to separate expansion to  If, Then and Else, respectively.\\ 
The result of expansion is an if-then-else 
(cf subclause 7.8.8 of ISO/IEC 13211-1),
with an If resulting from grammar rule body GrIf, a Then resulting from grammar rule body GrThen,
and an else construct Or resulting from grammar rule body GRElse.


\subsubsection{\code{('|')//2} -- second form of alternative}

\paragraph{Description}

\ \vspace{1em}


\code{'|'} used as a non-terminal \code{('|')//2} has the same behaviour as  \code{(;)//2}, when used
for an alternative. See subclause \ref{sssection:alternative}. The use of \code{('|')//2} instead of \code{(;)//2} in an if-then-else, cf \ref{sssection:ifThenElse},
shall be implementation-dependent.


%NOTE  ---  \code{('|')//2} is not equivalent to \code{(;)//2}, when \code{(;)//2} is 
%used for "if-then-else", as \code{('|')//2} shall not be used for "if-then-else". See subclause \ref{sssection:ifThenElse}.

\subsubsection{\code{\{\}//1} -- grammar-body-goal}

\paragraph{Description}

\ \vspace{1em}

\noindent
The non-terminal \code{\{G\}}, with \code{G} a Prolog goal, according to ISO/IEC 13211-1:1995, can stand at any place of a non-terminal inside a grammar-rule-body. After expansion the 
braces are omitted, the goal G is unchanged. On execution G is executed like any Prolog goal. \\
\noindent 
If {G} immediately contains a cut ('!'), this is handled like a grammar-body-cut (cf. \ref{ssection:grammarCut}),
i.e. the effect of the cut extends outside the non-terminal \code{\{G\}}.
 
\subsubsection{call//1}


\paragraph{Description}

\ \vspace{1em}

\noindent
Expanding, i.e. preparing for execution of the non-terminal 

\medskip

\code{call//1} 

\medskip
\noindent
shall result after the expansion in the goal for the built-in predicate
 
\medskip

\code{call/3} 

\medskip

\noindent
which is required by this TR and defined in  8.15.4 of ISO/IEC 13211-1:1995/Cor.2:2012(E).\


\medskip
\noindent
NOTE --- Consider the following example for the correspondence for grammar rules between \code{call//1} and \code{call/3}:

\noindent
\begin{quote}
\begin{verbatim}

atom_charsdiff(Atom, Xs0, Xs):-
    atom_chars(Atom, Chars),
    append(Chars, Xs, Xs0).

atomchars(Atom) --> call(atom_charsdiff(Atom)).

at_eos_pred([ ], [ ]).

at_eos --> call(at_eos_pred).

\end{verbatim}
\end{quote}
 
\subsubsection{\code{phrase//1}}

\paragraph{Description}

\ \vspace{1em}

% modified JPEH

\noindent
\code{phrase//1} is a grammar rule built-in predicate for using the built-in predicate \code{phrase/3}.
 
\medskip
\noindent 
Expanding, i.e. preparing for execution of the non-terminal 

\medskip

\code{phrase//1} 

\medskip
\noindent
with argument \code{G}  

\medskip
\noindent
shall result in a goal for the built-in predicate 

\medskip

\code{phrase/3} with first argument \code{G}.

\medskip
\noindent
For a definition of the built-in predicate \code{phrase/3} see subclause \ref{sssection:phraseSpecification}.\\

\subsubsection{\code{!//0} -- grammar-body-cut}
\label{ssection:grammarCut}

\paragraph{Description}

\ \vspace{1em}

\noindent
In the body of a grammar rule \code{!//0} is  a \code{grammar-body-cut}. After expansion the grammar-body-cut becomes the control construct cut, \code{!/0}, as in subclause 7.8.4 of ISO/IEC 13211-1 Prolog.\
\noindent
 
\medskip
\noindent
Implementations conforming to this TR shall not define or use a predicate \code{!/2}.

\subsubsection{\code{($\backslash$+)//1} -- grammar-body-not}

\noindent
The effect of \code{($\backslash$+)//1}  in grammar rules shall be implementation dependent.\\

\paragraph{Description}

\ \vspace{1em}

\noindent
The grammar-body-not \code{($\backslash$+)//1} with a grammar body as argument becomes the principal functor \code{($\backslash$+)/1}, the not provable operator. 
This functor \code{($\backslash$+)/1} is applied to the expanded grammar body of the
\code{grammar-body-not}. If the resulting goal succeeds the expanded rule does not change the comprehensive terminal sequence.\\


\medskip
\noindent
Implementations conforming to this TR shall not define or use a predicate \code{($\backslash$+)/3}.  \\

\noindent
NOTE  ---  The effect of \code{($\backslash$+)//1}  can be seen in the following example.\\ 

\noindent
The grammar rule 

\begin{quote}
\begin{verbatim}
a --> \+ b.
\end{verbatim}
\end{quote}

\noindent
may be expanded to:

\begin{quote}
\begin{verbatim}
a(S0, S) :- \+ b(S0, _), S0 = S.
\end{verbatim}
\end{quote}


\subsubsection{\code{->//2} - if-then}

\noindent
The effect of \code{(->)//2} in grammar rules except in the first argument of an alternative (cf. 7.14.5) shall be implementation dependent. 


\def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}


\subsection{Executing clauses expanded from grammar rules}


If a grammar rule to be prepared for execution has a non-terminal indicator NT//N, and NT is the name of the predicate indicator NT/M, with M is N + 2, of a built-in predicate, the result of expansion and the behaviour of the prepared grammar rule on execution is implementation dependent. This does not hold for the required non-terminals expanding to built-in predicates defined in \ref{ssection:controlConstructs}.\\

\noindent
When the database does not contain a procedure, prepared for execution from one or more grammar rules 
with non-terminal indicator NT//N during execution of a goal, prepared for execution from a 
non-terminal with non-terminal indicator NT//N, the behaviour of
the processor shall be as follows:

If the error handling of the processor is standard conforming
as specified in subclause 7.7.7 of ISO/IEC 13211--1, then the error term as specified 
in subclause 7.7.7b of ISO/IEC 13211--1 when the flag \code{unknown} is set to \code{error} 
shall be:

\begin{quote}
\begin{verbatim} existence_error(procedure, NT/M)
\end{verbatim}
\end{quote}

\medskip
\noindent
If the error handling of the processor supports definite clause grammar errors, 
then the error term shall be:
\begin{quote}
\begin{verbatim} existence_error(grammar_rule, NT/M)
\end{verbatim}
\end{quote}

\medskip
\noindent
In other cases the behaviour shall be implementation specific.

\medskip
\noindent
NOTES\\

\noindent
1\hspace{1.5em}Prolog processors shall report errors resulting from execution of grammar rules at the same abstraction level as grammar rules whenever possible.\\

\noindent
2\hspace{1.5em}Parsing resp. generating of terminal sequences using grammar rules is defined in subclause \ref{sssection:phraseSpecification}. Grammar rules are expanded there into Prolog clauses during preparation for execution, which maps the parsing or generating with a grammar-rule-body into executing a goal given a sequence of predicate clauses. See subclause 7.7 of ISO/IEC 13211--1 for details.


\section{ Built-in predicates}

\setcounter{subsection}{17}

\subsection{Grammar rule built-in predicates}



\subsubsection{phrase/3, phrase/2}
\label{sssection:phraseSpecification}

% \def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}}
\paragraph{Description}

\ \vspace{1em}

\noindent
\code{phrase(GRBody, S0, S)}  is true iff  \code{S0} either unifies with the concatenation of the grammar-body-sequence of \code{GRBody}, if any, (cf. Definition 3.11) with the remaining terminal-sequence \code{S}, or with the concatenation of a terminal-sequence resulting from generation by the non-terminal, if any, of \code{GRBody} w.r.t. the current Grammar rules with the remaining terminal-sequence \code{S}.\\

\noindent
Execution of the predicate \code{phrase/3} serves two goals: Firstly the final expansion(of a grammar rule) (cf. Definition 3.7),
when this has not taken place earlier, i.e. preparation for execution of its body and arguments; 
thereafter, secondly, the execution of the resulting Prolog goals. \\

\noindent
NOTE 1 ---	An \code{A} of a \code{B} means, construct \code{A} is directly contained in construct \code{B}. This is general standard wording for programming languages.

\medskip
\noindent
NOTE 2 ---	The simple grammar of example 7.14.1.1 may be prepared here for execution.\\

\noindent
Then with

\begin{quote}
\begin{verbatim}
GRBody: non-terminal: 				noun_phrase
S0: comprehensive terminal-sequence:	[the, dog, barks]
S:  remaining terminal-sequence:		[barks]
\end{verbatim}
\end{quote}

\noindent
\code{phrase(noun\_phrase, [the, dog, barks], [barks])} is true.\

\medskip
\noindent
If the non-terminal of \code{GRBody}, if any, is followed by a semicontext (cf. Definition 3.21), then the semicontext shall be prefixed to the remaining terminal sequence after having been parsed resp. generated wrt. the non-terminal of \code{GRBody}.\\
\noindent
Procedurally, \code{phrase(GRBody, S0, S)} is executed by calling the Prolog goal corresponding to the expansion of the grammar-rule-body \code{GRBody}, given the terminal-sequences \code{S0} and \code{S}, according to the logical expansion of grammar rules described in subclause \ref{section:logicalExpansion}. See in particular the clauses for \code{dcg\_rule/4}.\\

\noindent
\code{phrase(GRBody, S0, S)} shall be steadfast (cf. 3.22) in its third argument S. 

\paragraph{Template and modes}

\ \vspace{1em}

\noindent
\code{phrase(+grammar-rule-body, ?comprehensive-terminal-sequence,}\\
\code{?remaining-terminal-sequence)}\\
\ \vspace{1em}

\noindent
For definitions of
\code{comprehensive-terminal-sequence and remaining-terminal-sequence}
see Definitions 3.25 resp. 3.26,
for \code{grammar-rule-body} see Definition 3.14.

\paragraph{Bootstrapped built-in predicates}
\label{sssection:bootstrappedPredicates}

\ \vspace{1em}

\noindent
The built-in predicate \code{phrase/2} provides similar functionality to \code{phrase/3}. The goal \code{phrase(GRBody, S0)} is true when all terminals in the terminal-sequence S0 are consumed and accepted respectively generated.
\begin{quote}
\begin{verbatim}
phrase(GRBody, S0) :-
    phrase(GRBody, S0, []).
\end{verbatim}
\end{quote}


\paragraph{Errors}
\label{sssection:phraseErrors}

\begin{list}{\alph{Lcount})}{\usecounter{Lcount}}
	\item \code{GRBody} is a variable\\
	--- \code{instantiation\_error}
	\item \code{GRBody} is neither a variable nor a callable term\\
	--- \code{type\_error(callable, GRBody)}

\noindent
 The following two errors are implementation defined
 if applied to \code{phrase/3}, i.e. 
 no error checking is required on S0 and S by this TR
 for \code{phrase/3}. 
 If, however, a Prolog processor offers them, 
 their form and consequence must be the following:


	\item \code{S0} is not a terminal-sequence\\
	--- \code{type\_error(terminal\_sequence, S0)}

For \code{phrase/2} error clause \code{c} is required.

	\item \code{S} is not a terminal-sequence\\
	--- \code{type\_error(terminal\_sequence, S)}

\end{list} 
\noindent
NOTE ---
\hspace{1.5em}This relaxation is allowed because handling these errors could overburden a Prolog processor.

\paragraph{Examples}


\ \vspace{1em}

\noindent
These examples assume that the following grammar rules has been correctly prepared for execution and are part of the complete database:
\begin{quote}
\begin{verbatim}
determiner --> [the].
determiner --> [a].

noun --> [boy].
noun --> [girl].

verb --> [likes].
verb --> [scares].

noun_phrase --> determiner, noun.
noun_phrase --> noun.

verb_phrase --> verb.
verb_phrase --> verb, noun_phrase.

sentence --> noun_phrase, verb_phrase.
\end{verbatim}
\end{quote}

\noindent
Some example calls of \code{phrase/2} and \code{phrase/3}:

\begin{quote}
\begin{verbatim}
| ?- phrase([the], [the]).
yes

| ?- phrase(sentence, [the, girl, likes, the, boy]).
yes

| ?- phrase(sentence, [the, girl, likes, the, boy, today]).
no

| ?- phrase(sentence, [the, girl, likes]). 
yes

| ?- phrase(sentence, Sentence).

Sentence = [the, boy, likes]
yes

| ?- phrase(noun_phrase, [the, girl, scares, the, boy], Rest).

Rest = [scares, the, boy]
yes
\end{verbatim}
\end{quote}

\begin{comment}
% I left it inside the source for the moment, to wait which results the discussion brings.

\subsubsection{expand\_term/2}
\label{sssection:expandterm}

\paragraph{Description}

\ \vspace{1em}

\noindent
\code{expand\_term(Term, Expansion)} is true iff:\\

\noindent
--- \code{Expansion} unifies with the expansion of \code{Term}.\\

\noindent
Procedurally, \code{expand\_term(Term, Expansion)} is executed as follows:

\begin{list}{\alph{Lcount})}{\usecounter{Lcount}}
	\item If \code{Term} is a variable, unifies \code{Expansion} with \code{Term}
	\item Else if the goal \code{term\_expansion(Term, Expand)} is true then \code{Expansion} is unified with \code{Expand}
	\item Else if the principal functor of \code{Term} is \code{(-->)/2} then it is assumed that it represents a grammar rule and \code{Expansion} is unified with its expansion into a Prolog clause
	\item Else if the principal functor of \code{Term} is not \code{(-->)/2} then \code{Expansion} is unified with \code{Term}
	\item Else the goal fails
\end{list}


\noindent
NOTE --- The predicate \code{term\_expansion/2} is described in subclause \ref{sssection:termExpansion}.


\paragraph{Template and modes}

\ \vspace{1em}

\noindent
\code{expand\_term(?term, ?term)}


\paragraph{Errors}
 \ \vspace{1em}

\noindent
None.

\paragraph{Examples}


\ \vspace{1em}

\noindent
These examples assume that the following clauses for the \code{term\_expansion/2} predicate have been prepared for execution:
\begin{quote}

\begin{verbatim}
term_expansion(succ(A, B), pred(B, A)).
term_expansion(0, zero).
term_expansion(1, one).
\end{verbatim}
\end{quote}
Some example calls of \code{expand\_term/2}:
\begin{quote}
\begin{verbatim}
?- expand_term(Term, Expansion).

Term = Expansion
yes 
 ?- expand_term(succ(1, 2), Expansion).

Expansion = pred(2, 1)
yes

?- expand_term(1, one).

yes

?- expand_term(odd(1), Expansion).

Expansion = odd(1)
yes
\end{verbatim}
\end{quote}
The next query returns an implementation-dependent Prolog clause; therefore the example below illustrates one  possible answer:
\begin{quote}
\begin{verbatim}

?- expand_term((noun_phrase --> noun), Expansion)

Expansion = noun_phrase(A, B) :- noun(A, B)
yes
\end{verbatim}
\end{quote}


\medskip
\noindent
NOTES\\

\noindent
1\hspace{1.5em}Despite the fact that \code{expand\_term/2} may be used to retrieve the translation of a grammar rule to a Prolog clause, users should not rely on a specific translation of a grammar rule, which is implementation-dependent.\\

\noindent
2\hspace{1.5em}Users may use alternate grammar rule translators by defining suitable clauses for \code{term\_expansion/2}. Prolog 
implementers may use this mechanism to ensure backward compatibility with code written for older translators that are  
not compliant with this TR. 
\medskip

\noindent 
3.  \hspace{1.5em} Some Prolog systems provide support for term expansion mechanisms, based on \code{term\_expansion/2} and 
\code{expand\_term/2} predicates, that may be used when compiling Prolog source files. The specification of such mechanisms --- in 
particular how term expansion is performed during the compilation of Prolog source code --- is outside the scope of this technical report.

\end{comment}

\section{Evaluable functors}


NOTE --- No changes from the ISO/IEC 13211--1 Prolog standard.

\begin{comment}
%KD: term_expansion and expand_term are flipflops. Lets wait for results of discussion

\section{User-defined predicates}

\subsection{Grammar rule user-defined predicates}

\subsubsection{term\_expansion/2}
\label{sssection:termExpansion}

\paragraph{Description}
\ \vspace{1em}

\noindent
\code{term\_expansion(Term, Expansion)} is a user-defined, dynamic, and multifile predicate, which may be used for the rewriting of terms. The predicate is automatically called by the built-in predicate \code{expand\_term/2},  see \ref{sssection:expandterm}. This predicate exists even if it has no clauses.


\paragraph{Template and modes}

\ \vspace{1em}

\noindent
\code{term\_expansion(?term, ?term)}


\paragraph{Errors}

\ \vspace{1em}

\noindent
None.

\paragraph{Examples}

\noindent
\begin{quote}
\begin{verbatim}
term_expansion(next(Previous, Next), previous(Next, Previous)).
\end{verbatim}
\end{quote}

\end{comment}

\section{Logical Expansion}

\label{section:logicalExpansion}


\verbatiminput{dcgs_exp.pl}

\end{document}




