\documentclass{article} \usepackage[utf8]{inputenc} \usepackage{fontenc} \usepackage{hyperref} \usepackage{listings} \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 by many Prolog processors. This TR is an extension to the ISO/IEC 13211--1 Prolog standard, adopting a similar structure. In particular, this TR adds new sections and clauses to, or modifies existing clauses on 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 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 Peter Szabo (Hungary) \item Peter Szeredi (Hungary) \item Richard O'Keefe (NZ) \item Roger Scowen (UK) \item Tony Dodd (UK) \item Ulrich Neumerkel (Austria) \item Victor Santos Costa (Portugal) \item Manuel Hermenegildo (Spain) \item Mike Covington (USA) \item David Warren (USA) \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 2 Corrigenda of 13211-1. 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 1 --- This part of ISO/IEC 13211 will supplement ISO/IEC 13211--1:1995 including its corrigenda, and ISO/IEC 13211--2:2000.\\ \noindent NOTE 2 --- The limitations, expressed in clause 1, Scope, of ISO/IEC 13211--1:1995 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{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-not, 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:} 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. % JPEH Is this right? % KD I think so! \paragraph{generating (wrt. a definite clause grammar):} Producing legal terminal-sequences, completely parseable by that grammar, obeying right-hand-contexts, if any. \paragraph{grammar-body-alternative:} A compound term with principal functor \code{(;)/2} with 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-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-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}, where the first argument is a non-terminal (of a grammar), and the second argument is a latent right context. \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):} 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 (cf \ref{ssection:nonterminalIndicator}) . \paragraph{parsing (wrt. a definite clause grammar):} Successively accepting or consuming legal terminal-sequences, assigning them to corresponding non-terminals and obeying right-hand-contexts, if any. \paragraph{remaining terminal-sequence:} See terminal-sequence, remaining. \paragraph{right-hand-context:} A terminal-sequence occurring as optional second argument of a grammar-rule-head, constraining parsing resp. generating during completing this grammar rule application. \paragraph{steadfastness of a goal wrt. an argument} Goal \code{G} is steadfast in argument \code{n} of its argument list, if for any term \code{T} that is the \code{n}th argument in the goal, and the goal \code{Gf} that results by replacing \code{T} by a fresh variable \code{Vf} the results of \code{G} and \code{(Gf, Vf=T)} are 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, 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 a (possibly empty) prefix accepted by \code{phrase/3} (cf \ref{sssection:phraseSpecification}) . \paragraph{terminal-sequence, remaining:} Rest of comprehensive terminal-sequence without the leading terminal-sequence covered 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}}. \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} \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 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 in 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{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 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{Syntactically, there are no changes w.r.t. ISO/IEC 13211--1 Prolog standard, with exception of the operator syntax (cf \ref{ssection:grammarRuleOperator}); for the semantics compare \ref{sssection:prologDirectives}. Whenever directives are applicable to non-terminals, the respective non-terminal indicators (cf \ref{ssection:nonterminalIndicator}) , as arguments of directives, shall be used like predicate indicators.} \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 define how clauses become part of the database.\\ \noindent \textsl{The following subclause extends, 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 --- Clause \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{Right-hand contexts} ~\\ \begin{tabular}{l l l} ~ & \code{right hand context term =} & \code{term}\\ Abstract: & \textsl{rc} & \textsl{rc}\\ Priority: & 1201\\ Condition: & none\\ ~ & \code{right hand context =} & \code{right hand context term}\\ Abstract: & \textsl{r} & \textsl{r}\\ \end{tabular} \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{dynamic/1}, \code{multifile/1}, and \code{discontiguous/1} as specified in subclause 7.4.2 of the ISO/IEC 13211--1 Prolog standard. \medskip \noindent The directives\\ \code{op/3}, \code{char\_conversion/1}, \code{initialization/1}, \code{include/1}, \code{ensure\_loaded/1}, and \code{set\_prolog\_flag/2} \noindent shall not have non-terminal indicators as arguments. \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. \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 optional property is added to the list of predicate properties of subclause 6.8 of ISO/IEC 13211--2: \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} \def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}} Zero, one or more terminals are represented by terms directly 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 subclauses 6.3.7 and 6.4.6 of ISO/IEC 13211--1). Non-terminals are represented by callable terms.\ \paragraph{Example} \ \vspace{1em} \noindent A simple grammar consisting of 9 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 --> nominal_phrase, verbal_phrase. verbal_phrase --> verb. nominal_phrase --> article, noun. article --> [the]. noun --> [dog]. noun --> [nice, cat]. verb --> [runs]. verb --> [barks]. verb --> [bites]. \end{verbatim} \end{quote} \noindent Here the symbols \code{sentence, verbal\_phrase, verb} etc. denote non-terminals, whereas \code{[runs], [nice, cat]} etc. denote terminals. \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.17 and 3.23). \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 (see \ref{defTerminalSequence}), 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} 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 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(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} 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 the path of further parsing is constrained by the right-hand-context.\\ % process from path JPEH % KD fixed \noindent 2\hspace{1.5em} Sometimes the concepts \textsl{comprehensive terminal-sequence} resp. \textsl{remaining terminal-sequence} are named \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 a rest will remain after a parsing step. The inverse case, generating sentences by expanding grammars, where the comprehensive terminal-sequence is the real output list, is ignored by such wording.\\ % Above par modified JPEH % KD OK \noindent 3\hspace{1.5em} There are exotic cases, where the remaining terminal-sequence is not part of the comprehensive terminal-sequence, e.g. with the following grammar rule...but in fact there is a trailing sequence as the following example shows. % Above par modified JPEH % KD OK \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(S0, [word|S]) :- S0 = S. \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. The comprehensive terminal-sequence is identical with the remaining terminal-sequence for that non-terminal.\\ \noindent 4\hspace{1.5em} It should be noted that where the right-hand context is non empty, as in the cases above then \code{phrase/2} (cf \ref{sssection:bootstrappedPredicates}) cannot succeed as the right-hand context is pushed back into the terminal sequence.\\ % Modified JPEH % KD OK \noindent 5 \hspace{1.5em} Some processors allow a cut in the right-hand context; e.g.\\ \code{a, !, [word] --> b.}\\ Moving this cut to the end of the grammar body, c.f. \code{a, [word] --> b, !.} has the identical effect on execution. Thus this TR does not permit a cut in the right hand context. \subsubsection{Non-terminal indicator} \label{ssection:nonterminalIndicator} 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}.\\ \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}.\\ \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 as a predicate property (cf. subclause \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 Example: \\ \begin{quote} \begin{verbatim} :- 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. \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 non-empty sequence of Prolog goals that are executed when the grammar rule, prepared for execution, is processed.\\ \noindent \code{\{\}/1} is a functor of a \code{grammar body goal} \{prolog\_goal\} (cf. Definition 3.9). 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} digit(D) --> [C], {0'0 =< C, C =< 0'9, D is C - 0'0}. \end{verbatim} \end{quote} This rule, which assumes that C is a string consisting of a single character, 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. \subsection{Grammar control constructs} \label{ssection:controlConstructs} \def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}} \noindent This subclause describes the meaning of special non-terminals which are part of grammar rules: \code{[]//0, (',')//2, (;)//2, (->)//2 in an if-then-else, ('|')//2, \{\}//1, phrase//1, !//0, ($\backslash$+)//1 and call//1}. \\ \noindent After preparation for execution of Grammar Rules, named ``Grammar Rule expansion'', or ``expansion'' for short, these non-terminals result in control constructs resp. built-in predicates of ISO/IEC 13211-1 Prolog. \\ Because the expansion is not simply a replacement, but must satisfy some constraints resp. conditions hold, this process may appear somewhat difficult. \\ \noindent The expansion is understood best by describing it wrt. the built-in predicates \code{phrase/3} and \code{phrase/2} (see \ref{sssection:phraseSpecification}). Execution of these predicates serves two goals: Firstly the final Grammar Rule Expansion, when this has not taken place earlier, i.e. preparation for execution of its Grammar Body and arguments; thereafter the execution of the resulting Prolog goals. \\ \noindent >From the parsing viewpoint \code{phrase(NT, S)} is true when the terminal sequence \code{S} is covered by the non-terminal \code{NT}. Or, from the generation viewpoint it is true when \code{NT} generates \code{S}. \noindent The Grammar Body non-terminals are described here informally. Section \ref{section:logicalExpansion} provides a reference implementation that further defines the semantics of expansion. In particular this subclause explicates the linkages between the terminal sequences upon expansion of the control constructs. \noindent \subsubsection{\code{[]//0} -- empty terminal sequence} \label{sssection:emptySequence} \noindent The expansion result of the grammar control construct \code{empty terminal sequence} (a terminal sequence without contents) unifies the actual remaining terminal sequence with the actual comprehensive terminal sequence, i.e. has no effect on parsing resp. generating during execution. % I think we don't need the list separator '.'//2 as non terminal. % then we'd run in problems with syntax, brackets etc. % \subsubsection{\code{'.'//2} -- list separator} \noindent \subsubsection{\code{(',')//2} -- concatenation} \noindent In the body of a grammar rule \code{(',')//2} is the principal functor of a \\ \code{grammar-body-sequence}(cf. Definition 3.12) 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 GBFirst and GBSecond are arguments of a conjunction wrt. subclause 7.8.5 of ISO/IEC 13211-1 Prolog. \\ For a formal description of expansion of concatenation see subclause \ref{section:logicalExpansion}, third clause of \code{dcg\_cbody/4}. \medskip \noindent If contained directly in the head of a grammar rule, \code{(',')//2} is the main functor of a term consisting of a grammar rule body and a right-hand-context; cf \ref{sssection:rightHandcontext}.\\ \subsubsection{\code{('|')//2} -- alternative} The operator \code{('|')} used as a non-terminal \code{'|'/2} has the same behaviour as \code{(;)/2}. See section \ref{sssection:alternative} \medskip For a formal description of expansion this form of alternative see section \ref{section:logicalExpansion}, sixth clause of \code{dcg\_cbody/4}. \subsubsection{\code{(;)//2} -- alternative} \label{sssection:alternative} \noindent In the body of a grammar rule \code{(;)//2} is the principal functor of a \\ \code{grammar-body-alternative}. (cf. definition 3.7) 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 GBFirst and GBSecond shall be arguments of a disjunction \code{(;)/2} wrt. subclause 7.8.6 of ISO/IEC 13211-1 Prolog.\\ For a formal description of expansion of an alternative see section \ref{section:logicalExpansion}, fifth clause of \code{dcg\_cbody/4}. \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 leads 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} \noindent \subsubsection{\code{(;)//2} -- if-then-else} \noindent NOTE --- \code{(;)//2} serves two different functions depending on whether or not the first argument is a compound term with functor \code{(->)/2}.\ See \ref{sssection:alternative} for the use of \code{(;)//2} for \code{alternative}, when the first argument of \code{';'(\_,\_)} does not immediately contain a term with functor \code{'->'(\_,\_)}.\ \vspace{1em} \noindent The grammar control construct \code{(;)/2} may have as arguments a grammar body GBFirst and a second grammar body GBSecond, where the principal functor of GBFirst is \code{(->)/2} with arguments GBIf and GBThen. Each of GBIf, GBThen, and GBSecond is subject to separate expansion to GBIfExpanded, GBThenExpanded and GBSecondExpanded, respectively. The result is a Prolog disjunction with the if-then control construct \code{(->)(GBIfExpanded, GBThenExpanded)} as first, and \code{GBSecondExpanded} as second argument. \medskip \noindent For a formal description of expansion of if-then-else see section \ref{section:logicalExpansion}, fourth clause of \code{dcg\_cbody/4}. \medskip \noindent There shall be no use of \code{(->)/2} in grammar rules except in the first argument of an alternative as described above. Further a conforming proceesr shall not permit the use of \code{(->)/2} in any other way as an implementation specific extension. \subsubsection{\code{\{\}//1} -- extra conditions, external goal} \noindent The argument \code{G} of \code{\{\}//1} is not subject to expansion, i.e. the Prolog goals inside the braces remain unexpanded. \noindent For a formal description of expansion of extra conditions see section \ref{section:logicalExpansion}, ninth clause of \code{dcg\_cbody/4}. \subsubsection{\code{phrase//1}} \noindent Expanding the non-terminal \code{phrase//1} with argument \code{G} shall result in the expansion \code{phrase/3} with first argument \code{G}. % JPEH October 23rd 2012. I think we need another clause for dcg_cbody for this case. % added a clause 7 \medskip \noindent For a formal description of expansion of \code{phrase//1} see section \ref{section:logicalExpansion}, seventh clause of \code{dcg\_cbody/4}. \subsubsection{\code{!//0} -- cut} \noindent In the body of a grammar rule \code{!//0} is functor of a \code{grammar-body-cut}. After expansion the grammar-body-cut becomes the functor \code{!/0} as in subclause 7.8.4 of ISO/IEC 13211-1 Prolog.\ \noindent For a formal description of expansion of \code{!//0} see section \ref{section:logicalExpansion}, eleventh clause of \code{dcg\_cbody/4}. \medskip \noindent Implementations conforming to this DTR shall not define or use a predicate \code{!/2} \\ \subsubsection{\code{($\backslash$+)//1}} \noindent In the body of a grammar rule \code{($\backslash$+)//1} is functor of a \code{grammar-body-not} (cf. Definition 3.10) After expansion of \code{($\backslash$+)//1} the functor \code{($\backslash$+)/1} is applied to the expanded argument of the \code{grammar-body-not}. If the resulting goal succeeds the expanded rule does not change the comprehensive terminal sequence.\\ \noindent For a formal description of expansion of \code{($\backslash$+)//1} see section \ref{section:logicalExpansion}, tenth clause of \code{dcg\_cbody/4}. \medskip \noindent Implementations conforming to this DTR 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} \medskip \def\theparagraph{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}.\arabic{paragraph}} \subsubsection{call//1} \ \vspace{1em} \noindent Expanding, i.e. preparing for execution of the non-terminal \medskip \code{call//1} \medskip \noindent shall result in the expansion \medskip \code{call/3} \medskip \noindent which is a legal goal for \code{call/3} which is required by this DTR and defined in 8.15.4 of ISO/IEC 13211-1:1995/Cor.2:2012(E).\ \medskip \noindent For a formal description of expansion of \code{call//1} see section \ref{section:logicalExpansion}, ninth clause of \code{dcg\_cbody/4}. \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} \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). \subsection{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', with A' == A + 2, of a built-in predicate, existing 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 subclause 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 either with the concatenation of the terminal sequence of \code{GRBody} with the remaining terminal sequence \code{S}, or with the concatenation of a terminal sequence resulting from generation by the non-terminal of \code{GRBody} w.r.t. the current Grammar rules with the remaining terminal sequence \code{S}.\\ If the non-terminal 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 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/2}.\\ \noindent \code{phrase(GRBody, S0, S)} shall be steadfast in its third argument S (cf. Definition 3.22). \paragraph{Template and modes} \ \vspace{1em} \noindent \code{phrase(+terminal-sequence, ?terminal-sequence, ?terminal-sequence)} \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{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} 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} \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. \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}, 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: Prolog Definition of phrase/3} \label{section:logicalExpansion} \begin{verbatim} % To avoid name clashes: if phrase/3 exists already on the processor, % the word phrase may be replaced by iso-phrase or else at two places. % Missing prerequisite definitions as (append/3) shall be defined by % the "Prolog Prologue" (ISO/IEC JTC1 SC22 WG17 N235) phrase(GRBody, S0, S) :- dcg_body(GRBody, S0, S, Goal), call(Goal). % dcg_rule(DCGrule, Expansion). % Translates a DCG rule into a Prolog rule, when no error condition applies. dcg_rule((NonTerminal, Terminals --> GRBody), (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), (Head :- Body)) :- NonTerminal \= (_,_), 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) :- nonvar(GRBody), dcg_constr(GRBody), dcg_cbody(GRBody, S0, S, Body). dcg_body(NonTerminal, S0, S, Goal) :- nonvar(NonTerminal), \+ dcg_constr(NonTerminal), 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 )) :- subsumes_term((_->_),GREither), dcg_cbody_if_then(GREither, S0, S, Either), dcg_body(GROr, S0, S, Or). dcg_cbody(( GREither ; GROr ), S0, S, ( Either ; Or )) :- \+ subsumes_term((_->_),GREither), 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(phrase(Cont), S0, S, phrase(Cont, S0, S)). 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_if_then(( GRIf -> GRThen ), S0, S, ( If -> Then )) :- dcg_body(GRIf, S0, S1, If), dcg_body(GRThen, S1, S, Then). \end{verbatim} \end{document}