\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{fontenc}
\usepackage{hyperref}

\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{
	Editors: Klaus.Daessler\\
	klaus.daessler@mathint.com\\}
\date{\today}

\maketitle

\setcounter{secnumdepth}{-1}
\section{Introduction}

This technical recommendation (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 shall do so in compliance with this technical recommendation.

Grammar rules provide convenient and simple functionality for parsing and processing text in a variety of languages. They have been implemented in many Prolog systems. As such, they are deemed an worthy extension to the ISO/IEC 13211 Prolog standard. 

This TR is an extension to the ISO/IEC 13211--1 Prolog standard, adopting a similar structure. Specifically, this TR either adds new sections and clauses to, or modifies the reading of existing clauses on ISO/IEC 13211--1.


\medskip
\noindent
This draft may contain in several places informative text, type-set in \textsl{italics}. Such informative text is used for editorial comments deemed useful during the development of this draft and may not be included in the final version.


\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) and the authors of the two drafts cited above, and Richard as I have included here some contributions from him that I found on the net. PM. }

\begin{itemize}
	\item Bart Demoen (Belgium)
	\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 Mats Carlsson (Sweden)
	\item Paulo Moura (Portugal)
	\item Pierre Deransart (France)
	\item Péter Szabó (Hungary)
	\item Péter Szeredi (Hungary)
	\item Richard O'Keefe (NZ)
	\item Roger Scowen (UK)
	\item Tony Dodd (UK)
	\item Ulrich Neumerkel (Austria)
	\item Vítor 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. As such, 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 and expanding grammar rules
	\item Reference implementations and tests for the specified built-in predicates and for a grammar rule translator \end{list}
NOTE --- This part of ISO/IEC 13211 will supplement ISO/IEC 13211--1:1995.


\section{Normative references}

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


\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{body (of a grammar-rule):} The second argument of a grammar-rule. A grammar-body-sequence, or a grammar-body-alternative, or a grammar-body-choice, or a grammar-body-element. 

\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 clause 3.33 of ISO/IEC 13211--1).

\paragraph{definite clause grammar:} A sequence of grammar-rules.

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

\paragraph{expansion (of a grammar-rule):} The preparation for execution (cf. ISO/IEC 13211--1, section 7.5.1) of a grammar rule.

\paragraph{generating (wrt. a definite clause grammar):} Producing legal terminal-sequences  of a grammar, obeying right-hand-contexts, if any.

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

\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 cut (the atom \code{!}), or a grammar-body-goal, or a non-terminal, or a terminal-sequence.

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

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

\paragraph{grammar-body-terminals:} A terminal-sequence. 

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

\paragraph{grammar-rule-term:} A read-term \code{T.} where \code{T} is a grammar-rule. 

\paragraph{head (of a grammar-rule):}\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}, the first argument is a non-terminal (of a grammar), and the second argument is a right-hand-context. 

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

\paragraph{non-terminal (of a grammar):} An atom or compound term that denotes a non-terminal symbol of the grammar. 

\paragraph{non-terminal indicator:} 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. 

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

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

\paragraph{right-hand-context:} A terminal-sequence occuring as second argument of a grammar-rule-head, restricting parsing resp. generating after completing this grammar rule. 

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

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

\paragraph{terminal-sequence, comprehensive:} Terminal sequence containing as (possibly empty) prefix a terminal-sequence described by a grammar rule body in combination with
other grammar rules of a grammar.

\paragraph{terminal-sequence, remaining:} Rest of comprehensive terminal-sequence without the leading terminal-sequence corresponding to a non-terminal.

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


\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 corresponding section of ISO/IEC 13211--1.

\subsection{Prolog text}

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 section on 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 on the ISO/IEC 13211--1 Prolog standard. 

\subsection{Extensions}

\noindent
\textsl{The corresponding section on 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 on the ISO/IEC 13211--1 Prolog standard. 


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

\textsl{Please see section \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 section on 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 section extends, with the specified number, the corresponding ISO/IEC 13211--1 section.}


\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{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{$S_{i}$} represents the initial terminal-sequence, the variable \code{$S_{i+1}$} will represent the remaining terminal-sequence after processing \code{Si} with a grammar rule.

 
\subsection{Prolog text and data}

\noindent
\textsl{The first paragraph of this section 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 section on 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{No changes from the ISO/IEC 13211--1 Prolog standard.}

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

\noindent
\textsl{The corresponding section on 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 defines how each clause becomes part of the database.\\

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

\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 --- Section \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.

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

NOTE --- The operator \code{-->/2}, specified in section 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 section extends, with the specified number, the corresponding ISO/IEC 13211--1 section:}

\setcounter{subsection}{12}
\subsection{Predicate properties}
\label{ssection:predicateProperties}


The following optional property is added to the list of predicate properties:

\begin{itemize}
	\item \code{expanded\_from(non\_terminal, A//N)} --- The predicate results from the expansion of a grammar rule for the non-terminal \code{A//N}
\end{itemize}

\noindent
NOTE --- the \code{expanded\_from/2} property name was chosen in order to account for other possible, implementation-specific expansions.


\subsection{Grammar rules}


\subsubsection{Terminals and non-terminals}

Zero or more terminals are represented by terms contained in lists in order to distinguish them from non-terminals (string notation may be used as an alternative to lists when terminals are characters and the flag "double\_quotes" has value "chars"; see sections 6.3.7 and 6.4.6 of ISO/IEC 13211--1). Non-terminals are represented by callable terms.\\

\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.18 and 3.22).


\subsubsection{Format of grammar rules}

A grammar rule has the format:
\begin{quote}
\begin{verbatim}
GRHead --> GRBody.
\end{verbatim}
\end{quote}
A grammar rule is interpreted as stating that its head, \code{GRHead}, can be rewritten by its body, \code{GRBody}. The head and the body of grammar rules are constructed from \textsl{non-terminals} and \textsl{terminals}. The head of a grammar rule is a non-terminal or the conjunction of a non-terminal and, following, a terminal-sequence (a \textsl{right-hand-context}, see \ref{sssection:rightHandcontext}):
\begin{quote}
\begin{verbatim}
NonTerminal --> GRBody.

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


\noindent
The control constructs that may be used on a grammar rule body are described in section \ref{ssection:controlConstructs}. An empty grammar rule body is represented by an empty list:
\begin{quote}
\begin{verbatim}
GRHead --> [].
\end{verbatim}
\end{quote}
The empty list cannot be omitted, i.e. there is no \code{-->/1} form for grammar rules.


\subsubsection{Right Hand Contexts}
\label{sssection:rightHandcontext}

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

\paragraph{Description}

\ \vspace{1em}

\noindent
A \textsl{right-hand-context} is a terminal-sequence, as an optional second argument of the head of a grammar rule (see \ref{defGrammarRuleHead}). A right-hand-context contains terminals that are prefixed to the remaining terminal-sequence after successful application of the grammar rule.

\paragraph{Syntax}

 \begin{quote}
\begin{verbatim}

GrammarRuleHead    = NonTerminal
GrammarRuleHead    = NonTerminal, RightHandContext 
RightHandContext   = TerminalSequence

\end{verbatim}
\end{quote}

\paragraph{Examples}

\ \vspace{1em}

\noindent
Assume that we need rules to \textsl{look-ahead} one or two tokens that would be consumed next. This could be accomplished by the following two 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 right-hand-context:

\begin{quote}
\begin{verbatim}

phrase1, [word] --> phrase2, phrase3.
\end{verbatim}
\end{quote}

\noindent
After preparation for execution this occurs in the database as follows:

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

phrase1(CTS, RTSfinal):-
    phrase2(CTS, RTS2),
    phrase3(RTS2, RTS3),
    RTSfinal = [word | RTS3].

or, respectively

phrase1(CTS, [word |RTS3]) :-
    phrase2(CTS, RTS2),
    phrase3(RTS2, RTS3).

\end{verbatim}
\end{quote}

\noindent
Here \code{CTS} shall denote the comprehensive terminal-sequence for parsing/generating wrt. \code{phrase1}. \code{RTS2} and \code{RTS3} shall denote, respectively, the remaining terminal sequences after application of the nonterminals \code{phrase2} and \code{phrase3}.\\

\noindent
NOTES\\


\noindent
1\hspace{1.5em} In case of parsing, as soon as \code{phrase2} and \code{phrase3} are recognized in the comprehensive terminal-sequence (input list) \code{CTS}, the terminal \code{word} is prefixed to the remaining terminal-sequence \code{RTS3} of \code{phrase1}. \code{word} is then the first terminal to be taken in respect for further parsing after \code{phrase1}. Thus the path of further parsing is constrained by the right-hand-context.\\

\noindent
2\hspace{1.5em} Sometimes the concept of  \textsl{comprehensive terminal-sequence} resp. \textsl{remaining terminal-sequence} are named \textsl{input list} resp. \textsl{output list}. This is misleading, because it only takes in respect the case of parsing by a grammar. There a terminal list shall be parsed wrt. nonterminals, and a rest will remain after a parsing step. The inverse case of generating sentences by grammars, where the comprehensive terminal-sequence is the real output list, is ignored by such wording.\\

\noindent
3\hspace{1.5em}  There are exotic cases, where the remaining terminal-sequence seems not to be trailing part of the comprehensive terminal-sequence, e.g. with the following grammar rule...but it is:

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

nt,[word] --> [].

\end{verbatim}
\end{quote}

\noindent

which is expanded by preparation for execution to:

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

nt(CTS,[word|RTS]) :-
    CTS = RTS.

\end{verbatim}
\end{quote}

\noindent
This nonterminal \code{nt} represents an empty terminal sequence, but constrains
further parsing to take in respect \code{word} as next token. The comprehensive terminal-sequence is identical with the remaining terminal-sequence for that nonterminal.

\subsubsection{Non-terminal indicator}

A \textsl{non-terminal indicator} is a compound term with the format \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 grammar rule non-terminal whose functor is \code{A} and whose arity is \code{N}.\\

\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}.\\

\noindent
2\hspace{1.5em}The concept of non-terminal indicator is similar to the concept of \textsl{predicate indicator} defined in sections 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 wherever a predicate indicator as defined in ISO/IEC 13211--1 can appear. Furthermore non-terminal indicators may be used as predicate property (cf. section \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}
The corresponding non-terminal indicator for the grammar rule left-hand side non-terminal is \code{sentence//0}. Assuming a \code{public/1} directive for declaring predicate scope, we could write:
\begin{quote}
\begin{verbatim}
:- public(sentence//0).
\end{verbatim}
\end{quote}
in order to be possible to use grammar rules for the non-terminal \code{sentence//0} outside its encapsulation unit.


%\subsubsection{Non-terminal indicator sequence}


%\subsubsection{Non-terminal indicator list}



\subsubsection{Prolog goals in grammar rules}

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

\paragraph{Description}

\noindent
In the body of grammar rules, curly brackets enclose a non-empty sequence of Prolog goals that are executed when the grammar rule, prepared for execution, is processed.\\

\noindent
NOTE --- The ISO/IEC 13211--1 Prolog standard defines, in section 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}
digit(D) --> [C], {0'0 =< C, C =< 0'9, D is C - 0'0}.
\end{verbatim}
\end{quote}
This rule recognizes a single terminal as the code of a character representing a digit when the corresponding numeric value can be unified with the non-terminal argument.


\subsubsection{Control constructs and built-in predicates supported by grammar rules}
\label{ssection:controlConstructs}

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

\noindent
This section describes the meaning of special nonterminals which are part of grammar rules, and in certain respect correlate with control constructs resp. built-in predicates of ISO/IEC 13211-Prolog. 

\paragraph{The nonterminal (',')//2}

\ \vspace{1em}

\noindent
In the body of a grammar rule \code{(',')\//2} is principal functor of a \code{grammar-body-sequence} (cf. Definition 3.11). If occuring in the head of a grammar rule, \code{(',')//2} is main functor of a term consisting of a nonterminal and a right-hand-context.\\


\paragraph{The nonterminal (';')//2}

\ \vspace{1em}

\noindent
In the body of a grammar rule \code{(';')\//2} is principal functor of a \code{grammar-body-alternative}.\\


\noindent
NOTE  ---  The effect of comma and semicolon, \code{(',')//2}, \code{(';')//2}, maybe understood best by application of \code{(write\_canonical)/1} (see section 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 leads to the following Prolog clause during preparation for execution :
\begin{quote}
\begin{verbatim}
sentence(CTS, RTS) :-
            subject(CTS, ITS1),
            verb(ITS1, ITS2),
            object(ITS2, RTS)
      ;
            object(CTS, ITS3),
            verb(ITS3, ITS4),
            subject(ITS4, RTS).

\end{verbatim}
\end{quote}
\noindent
\code{ITS1}  .. \code{ITS4} are the respective intermediate terminal sequences, arising during
continued parsing resp. generating the comprehensive terminal sequence \code{CTS} 
with two alternative forms.\\


\paragraph{The nonterminal \code{('->')//2} together with \code{(';')//2} (choice)} 

\ \vspace{1em}

\noindent
In the body of a grammar rule \code{('->')\//2} is principal functor of a \code{grammar-body-choice}. See section \ref{section:logicalExpansion}.\\


\paragraph{The nonterminal ('!')//}

\ \vspace{1em}

\noindent
During execution of a grammar rule \code{('!')//2} commits parsing resp. generation to that grammar rule; no other grammar rule with same non-terminal indicator can be applied during execution of the respective comprehensive terminal sequence. \\
If occuring in the right-hand-context of the head of a grammar rule, \code{('!')//2} is prefixed to the remaining terminal sequence of that nonterminal, where it may commit further parsing or generating. The actual nonterminal is not influenced. See section \ref{section:logicalExpansion}.\\


\subsubsection{The nonterminal call//1}

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

\paragraph{Description}

\ \vspace{1em}

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

\ \vspace{1em}

\code{call//1} 

\ \vspace{1em}

\noindent
shall lead to an expansion result
 
\ \vspace{1em}

\code{call/3} 

\ \vspace{1em}


\noindent
which is a legal goal for the control construct \code{call/3} which is required by this DTR and defined in 7.14.8. 

\noindent A Prolog processor may support additional control constructs. Examples include \textsl{soft-cuts} and control constructs that enable the use of grammar rules stored on encapsulation units other than modules, such as objects. These additional control constructs must be treated as non-terminals by a Prolog processor working on a strictly conforming mode (see \ref{strictMode}e).

\ \vspace{1em}
 \noindent
NOTE --- Consider the following example for the correlation of Grammar Rules, \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{The control construct \code{call/3}}

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

\ \vspace{1em}

\code{call(G, A1, A2)} is true iff G is a goal which is true when activated using the implementation defined arguments A1 and A2.
For the definition of G, and Error cases restricted to G, see section 7.8.3 of ISO/IEC 13211-1.

\noindent
The definitions of the arguments A1 and A2, examples and the error cases of \code{call/3} shall be supplied in the implementation specific documentation.

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

\ \vspace{1em}

\code{call(+callable\_term, ?argument1, ?argument2)}

 \subsubsection{Executing procedures expanded from grammar rules}


If a grammar rule to be prepared for execution has a non-terminal indicator N//A, and N is the name of the predicate indicator N/A' of a built-in predicate in the complete database, the result of expansion and the behaviour of the prepared grammar rule on execution is implementation dependent. This does not hold for the built-in predicates defined in \ref{ssection:controlConstructs}.\\

\noindent
When the database does not contain a grammar rule with non-terminal indicator N//A during execution of a non-terminal with non-terminal indicator N//A , the error term as specified in clause 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, N//A)
\end{verbatim}
\end{quote}


\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 texts with grammar rules is defined in section \ref{sssection:phraseSpecification}. Grammar rules are expanded 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 section 7.7 of ISO/IEC 13211--1 for details.


\section{Built-in predicates}


\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 the comprehensive terminal sequence \code{S0} unifies with the concatenation of either a terminal sequence of the grammar rule body \code{GRBody} or a terminal sequence resulting
from generation by the nonterminal of \code{GRBody} w.r.t. the current Grammar rules, both extended by the remaining terminal sequence, where \code{S} unifies with the remaining terminal sequence.\\
If the nonterminal of \code{GRBody} is followed by a right-hand-context (cf. definition 3.2), then the right-hand-context shall be prefixed to the remaining terminal sequence after having parsed resp. generated wrt. the nonterminal 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 section \ref{section:logicalExpansion}.

\paragraph{Template and modes}

\ \vspace{1em}


\noindent
\code{phrase(+terminal-sequence, ?terminal-sequence, ?terminal-sequence)} 
\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, i.e. if a Prolog 
processor offers them, their form must be the following:

	\item \code{S0} is not a terminal-sequence\\
	--- \code{type\_error(terminal-sequence, S0)}
	\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{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 recognized resp. generated:
\begin{quote}
\begin{verbatim}
phrase(GRBody, S0) :-
    phrase(GRBody, S0, []).
\end{verbatim}
\end{quote}

\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]. 
sentence --> noun_phrase, verb_phrase.

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

verb_phrase --> verb.
verb_phrase --> verb, noun_phrase.
\end{verbatim}
\end{quote}
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]).
 no

| ?- phrase(sentence, Sentence).

Sentence = [the, girl, likes, the, boy]
yes

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

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



 %\subsubsection{expand\_term/2}

%\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 section \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 loaded into the Prolog interactive session:
%\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; as such the example below illustrates just a 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 not compliant with this TR. 
%\medskip
%\noindent
%3. 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 recommendation.


\section{Evaluable functors}

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


%\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}, which is described below. 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}

%\ \vspace{1em}

%\noindent
%Example clause for \code{term\_expansion/2}:
%\begin{quote}
%\begin{verbatim}
%term_expansion(next(Previous, Next), previous(Next, Previous)).
%\end{verbatim}
%\end{quote}


\section{Prolog text specification of phrase/3}

\ \vspace{1em}

\begin{verbatim}


iso_phrase(GRBody, S0, S) :-
   dcg_body(GRBody, S0, S, Goal),
   call(Goal).


% dcg_rule(DCGrule, S0, S, Expansion).
% Translates a DCG rule into a Prolog rule, when no error condition applies.

dcg_rule((NonTerminal, Terminals --> GRBody), S0, S, (Head :- Body)) :-
   !,
   dcg_non_terminal(NonTerminal, S0, S, Head),
   dcg_body(GRBody, S0, S1, Goal1),
   dcg_terminals(Terminals, S, S1, Goal2),
   Body = (Goal1, Goal2).

dcg_rule((NonTerminal --> GRBody), S0, S, (Head :- Body)) :-
   dcg_non_terminal(NonTerminal, S0, S, Head),
   dcg_body(GRBody, S0, S, Body).

% translates a grammar goal non-terminal:

dcg_non_terminal(NonTerminal, S0, S, Goal) :-
   NonTerminal =.. NonTerminalUniv,
   append(NonTerminalUniv, [S0, S], GoalUniv),
   Goal =.. GoalUniv.

% translates a terminal-sequence:

dcg_terminals(Terminals, S0, S, S0 = List) :-
   append(Terminals, S, List).

% translates a grammar rule body:

dcg_body(Var, S0, S, Body) :-
   var(Var),
   !,
   Body = phrase(Var, S0, S).
dcg_body(GRBody, S0, S, Body) :-
   dcg_constr(GRBody),
   !,
   dcg_cbody(GRBody, S0, S, Body).
dcg_body(NonTerminal, S0, S, Goal) :-
   \+ dcg_constr(NonTerminal),
   dcg_non_terminal(NonTerminal, S0, S, Goal).

dcg_constr([]).
dcg_constr([_|_]).
dcg_constr((_,_)).
dcg_constr((_;_)).
dcg_constr((_|_)).
dcg_constr(call(_)).
dcg_constr({_}).
dcg_constr(\+_).
dcg_constr(!).


dcg_cbody([], S0, S, (S0=S)).
dcg_cbody([T|Ts], S0, S, Goal) :-
   dcg_terminals([T|Ts], S0, S, Goal).
dcg_cbody(( GRFirst, GRSecond ), S0, S, ( First, Second )) :-
   dcg_body(GRFirst, S0, S1, First),
   dcg_body(GRSecond, S1, S, Second).
dcg_cbody(( GREither ; GROr ), S0, S, ( Either ; Or )) :-
   dcg_body(GREither, S0, S, Either),
   dcg_body(GROr, S0, S, Or).
dcg_cbody(( GREither | GROr ), S0, S, ( Either ; Or )) :-
   dcg_body(GREither, S0, S, Either),
   dcg_body(GROr, S0, S, Or).
dcg_cbody(call(Cont), S0, S, call(Cont, S0, S)).
dcg_cbody({Goal}, S0, S, (Goal, S0 = S)).
dcg_cbody(\+ GRBody, S0, S, (\+ Goal, S0 = S)) :-
   dcg_body(GRBody, S0, _, Goal).
dcg_cbody(!, S0, S, (!, S0 = S)).
dcg_cbody(( GRIf -> GRThen ), S0, S, ( If -> Then )) :-
   dcg_body(GRIf, S0, S1, If),
   dcg_body(GRThen, S1, S, Then).





\end{verbatim}


\end{document}

