% FILE. . . . . /home/hak/hlt/src/hlt/language/syntax/xml/user-manual/main.tex
% EDIT BY . . . Hassan Ait-Kaci
% ON MACHINE. . Hak-Laptop
% STARTED ON. . Thu Jan 23 15:59:21 2014

% Last modified on Sun Feb 16 17:21:46 2014 by hak

\documentclass{article}

\input{main.mac}
\title{A Generic XML-Generating Metacompiler}
\author{\hak \\ {\small\texttt{hak@acm.org}}}

\begin{document}

\maketitle

\begin{abstract}\footnotesize
\noindent This describes a feature of \jacc,\footnote{\underline{J}ust
\underline{a}nother \underline{c}ompiler \underline{c}ompiler.} a
Java-based system in the fashion of \yacc,\footnote{\underline{Y}et
\underline{a}nother \underline{c}ompiler \underline{c}ompiler.} the
well-known metacompiler, where a minimalistic set of simple annotations
may be specified on a few grammar's rules and terminal symbols to guide
the automatic generation of code in XML format. The annotations
basically specify how to produce an XML construct out of the bits and
pieces of a concrete syntax tree (CST). The information is then used at
parse-time by the generated parser to build the actual XML tree in
accordance with the specified patterns.  This annotation-driven process
is one of \textit{tree transduction} (from CST to XML tree). Compilers
generated from such annotated \jacc\ grammars can generate XML code for
a wide class of possible formats depending on the syle of annotation
chosen for serializing a piece of syntax corresponding to a few grammar
rules and terminals. In this document, we present the simple notation
\jacc\ uses for such annotations decorating a \yacc-style BNF grammar,
and its operational semantics. We illustrate each construct with
examples of its use. We also discuss benefits and limitations of the
current system.  \vfil
\begin{center}\hskip-.5\tabcolsep
\begin{tabular}{ll}
\textbf{\textsc{Keywords:}}&
\parbox{.6\textwidth}{Metacompilers, XML, Annotation-driven XML pattern generation}
\end{tabular}
\vfil
{\fboxsep4ex\fbox{\parbox{.7\textwidth}{\scriptsize\tableofcontents}}}
\end{center}
\end{abstract}
\pagebreak

\section{Introduction}

\subsection{Motivation}

One of the nice consequences of the advent of the W3C eXtended Markup
Language (XML) is that is has become the universal format for producing
code. 

\subsection{Approach}

Our approach is simple: we use a simple grammar annotation scheme that
drives XML-code generation. 

\subsection{Organization of contents}

The rest of this document is organized as follows.  In
Section~\ref{review}, we review extant work in relation to the work
presented here.  Section~\ref{jacc} overviews the functionality of
\jacc.  In Section~\ref{xml}, the XML annotation notation is described
in detail.  Section~\ref{rif} illustrates how to use \jacc\ using a
complete annotated grammar example.  We conclude in
Section~\ref{conclusion} with some comments on the usefulness and future
potential evolution of this tool.

\section{Review of related work}
\label{review}

\section{Quick overview of \jacc}
\label{jacc}

At first sight, \jacc\ may be seen as a ``100\% Pure Java''
implementation of an LALR(1) parser generator~\cite{dragonbook} in the
fashion of the well known UNIX tool \yacc---``yet another compiler
compiler''~\cite{yacc}. However, \jacc\ is much more than\ldots\
\textit{just another compiler compiler\/}: it extends \yacc\ to enable
the generation of flexible and efficient Java-based parsers and provides
enhanced functionality rarely available in other similar systems.

The fact that \jacc\ uses \yacc's metasyntax makes it readily usable on
most \yacc\ grammars. Other Java-based parser generators all depart from
\yacc's format, requiring nontrivial metasyntactic preprocessing to be
used on existing \yacc\ grammars---which abound in the world, \yacc\
being by far the most popular tool for parser generation. Importantly,
\jacc\ is programmed in pure Java---this makes it fully portable to all
existing platforms, and immediately exploitable for web-based software
applications.

\jacc\ further stands out among other known parser generators, whether
Java-based or not, thanks to several additional features. The most
notable are:
\begin{itemize}

\item \jacc\ uses the most efficient algorithm known to date for its
      most critical computation (\viz, the propagation of LALR(1)
      lookahead sets). Traditional \yacc\ implementations use the method
      originally developed by DeRemer and
      Penello~\cite{DeremerPenello}. \jacc\ uses an improved method due
      to Park, Choe, and Chang~\cite{ParkChoeChang}, which drastically
      ameliorates the method of by DeRemer and Penello. To this author's
      best knowledge, no other (available) Java-based metacompiler
      system implements the Park, Choe, and Chang method~\cite{choe}.

\item \jacc\ allows the user to define a complete class hierarchy of
      parse node classes (the objects pushed on the parse stack and that
      make up the parse tree: nonterminal and terminal symbols), along
      with any Java attributes to be used in semantic actions annotating
      grammar rules. All these attributes are accessible directly on any
      pseudo-variable associated with a grammar rule constituents (\ie,
      \verb+$$+, \verb+$1+, \verb+$2+, \etc).

\item \jacc\ makes use of all the well-known conveniences defining
      precedences and associativity associated to some terminal symbols
      for resolving parser conflicts that may arise. While such
      conflicts may in theory be eliminated for any LALR(1) grammar,
      such a grammar is rarely completely obtainable. In that case,
      \yacc\ technology falls short of providing a safe parser for
      non-LALR grammar. Yet, \jacc\ can accommodate any such eventual
      unresolved conflict using non-deter\-mi\-nistic parse actions that
      may be tried and undone.

\item Further still, \jacc\ can also tolerate non-deter\-mi\-nistic
      tokens. In other words, the same token may be categorized as
      several distinct lexical units to be tried in turn. This allows,
      for example, parsing languages that use no reserved keywords (or
      more precisely, whose keywords may also be tokenized as
      identifiers, for instance).

\item Better yet, \jacc\ allows dynamically (re-)definable operators in
      the style of the Prolog language (\ie, at parse-time). This
      offers great flexibility for on-the-fly syntax customization, as
      well as a much greater recognition power, even where operator
      symbols may be overloaded (\ie, specified to have several
      precedences and/or associativity for different arities).

\item \jacc\ supports partial parsing. In other words, in a grammar, one
      may indicate any nonterminal as a parse root. Then, constructs
      from the corresponding sublanguage may be parsed independently
      from a reader stream or a string.

\item \jacc\ automatically generates a full HTML documentation of a
      grammar as a set of interlinked files from annotated
      \verb+/**...*/+ \texttt{javadoc}-style comments in the grammar
      file, including a navigatable pure grammar in ``\yacc\ form,''
      obtained after removing all semantic and serialization
      annotations, leaving only the bare syntactic rules.

\item \jacc\ may be directed to build a parse-tree automatically (for
      the concrete syntax, but also for a more implicit form which rids
      a concrete syntax tree of most of its useless information). By
      contrast, regular \yacc\ necessitates that a programmer add
      explicit semantic actions for this purpose.

\item \jacc\ supports a simple annotational scheme for automatic XML
  serialization of complex Abstract Syntax Trees (ASTs). Grammar rules
  and non-punctuation terminal symbols (\ie, any meaning-carrying tokens
  such as, \eg, identifiers, numbers, \etc) may be annotated with simple
  XML templates expressing their XML forms. \jacc\ may then use these
  templates to transform the Concrete Parse Tree (CST) into an AST of
  radically different structure, constructed as a \jdom\ XML
  document.\flink{http://www.jdom.org/} This yields a
  convenient declarative specification of a tree transduction process
  guided by just a few simple annotations, where \jacc's ``sensible''
  behavior on unannotated rules and terminals works ``as expected.''
  This greatly eases the task of retargeting the serialization of a
  language depending on variable or evolving XML vocabularies.

\end{itemize}

With \jacc, a grammar can be specified using the usual familiar \yacc\
syntax with semantic actions specified as Java code. The format of the
grammar file is essentially the same as that required by \yacc, with
some minor differences, and a few additional powerful features. Not
using the additional features makes it essentially similar to the \yacc\
format.

For details on how \jacc\ extends \yacc\ to support Prolog-style dynamic
operators, see Section~\ref{prologops}. For instructions on how to
organize a \jacc\ grammar, please refer to the documentation of the
grammar format, or to the description of grammar
commands.\FLINK{http://hassan-ait-kaci.net/hlt/doc/hlt/jaccdoc/000_START_HERE.html}{http://hassan-ait-kaci.net/hlt/doc/hlt/jaccdoc/000\_START\_HERE.html}
If you wish to use \jacc, follow these simple steps. You may also want
to peruse the code of \jacc\ grammar examples.  References For detailed
explanations of most constructions and algorithms used by this package,
please refer to the following.

\section{XML serialization annotation}
\label{xml}

We need a means to annotate a \jacc\ grammar so as to ease and automate
the process of specifying an XML serialization for the language defined
by the grammar. The way we proceed is by annotating some rules and
terminals to produce an XML form built out of those XML forms built for
the constituents of the CST (\ie, from a terminal's contents or a rule's
RHS).

To this end, \jacc\ will come handy. This section describes a
(meta-)grammar for a simple annotation language meant to enable passing
XML formatting information from a \jacc\ grammar to a \jacc\
parser. This language is that of the forms that go between square
brackets either in the \XMLINFO\ command annotating a terminal or
appearing in a rule being annotated for XML conversion for serialization
purposes. Doing this gives us great flexibility for extending or
modifying the annotation meta-syntax simply by:
\begin{enumerate}\itemsep-2pt
\item modifying the \jacc\ grammar source file;
\item running the \texttt{jacc} command on it to regenerate the
      \texttt{XmlAnnotationParser} Java source;
\item recompiling.
\end{enumerate}
\textit{Et voil\`a ! ...}

\subsection{Basic annotation notation}

We first introduce the basic annotation notation for the very common
case when the XML tree to be constructed from the CST is homomorphic to
the CST in that it only needs information that is local to the CST
node. We will extend this notation later when the tree construction is
heteromorphic, needing information from below this node.

In order for the parser of the annotation notation to stay small and
light-weight, as well as avoiding ambiguity and stay strictly within
LALR(1) recognition power, we will adopt the following very simple
keyword-driven syntax. For example:
\begin{show}\hskip-.5\tabcolsep%
\begin{tabular}{lclcl}
A$_0$ & : & \multicolumn{3}{l}{A$_1$ A$_2$ A$_3$ A$_4$} \\
   & [ \\
   &   & \PREFIX{nsprefix} & : & \PREFIX{"foo"} \\
   &   & \LOCAL{localname} & : & \LOCAL{"Azero"} \\
   &   & \ATT{attributes}  & : & \ATT{\{a = "bar blah", b="blech"\}} \\
   &   & \CHILD{children}  & : & \CHILD{(2, 3)} \\
   & ] \\
   & ;
\end{tabular}%
\end{show}  
means that the XML form of an \texttt{A$_0$} node (created when the
parser uses this grammar rule bottom-up) will look like:
\begin{show}
\begin{tabular}{l}
<\PREFIX{foo}:\LOCAL{Azero} \ATT{a="bar blah" b="blech"}>\\
\textit{\small(XML form of \CHILD{A$_2$})}\\
\textit{\small(XML form of \CHILD{A$_3$})}\\
</\PREFIX{foo}:\LOCAL{Azero}>
\end{tabular}
\end{show}  

In such an annotation, appearing in any order, the notation
\texttt{"keyword : value"} is such that keyword is an admissible
keyword. An admissible keyword is such that there may be at most one
occurrence per annotation of \PREFIX{nsprefix}, \LOCAL{localname},
\ATT{attributes}, or \CHILD{children}.
  
Such an admissible keyword is followed by a value, which may be either
an identifier, a single- or double-quoted string, or a list between
curly braces \texttt{\{\ldots\}}, or parentheses \texttt{(\ldots)}, the
nature of this list's brackets and elements depending on the keyword
(see the annotation grammar for details).

The annotation is meant to be light-weight. So, all these keywords may
be abbreviated to any non-empty case-insensitive prefix of their full
form, and some punctuation may be used interchangeably or simply
omitted: \eg, the `\texttt{:}' separating keywords and values, the
`\texttt{,}' separating list elements, as well as unnecessary quotes,
are all in fact optional. The following key/value separator symbols may
be used: `\texttt{:}' `\texttt{=}' `\texttt{->}' `\texttt{=>}' or they
may be simply omitted. Similarly, the following list separator symbols
may be used: `\texttt{,}' (comma), `\texttt{;}' (semicolon), or they may
be simply omitted.

For example, the annotation shown above could as well be written as
follows:
\begin{show}\hskip-.5\tabcolsep%
\begin{tabular}{lclcl}
A$_0$ & : & \multicolumn{3}{l}{A$_1$ A$_2$ A$_3$ A$_4$} \\
   & [ \\
   &   & \PREFIX{NS} & : & \PREFIX{foo} \\
   &   & \LOCAL{LO}  & : & \LOCAL{Azero} \\
   &   & \ATT{AT}    & : & \ATT{\{a -> 'bar blah'; b -> blech\}} \\
   &   & \CHILD{CH}  & : & \CHILD{(2 3)} \\
   & ] \\
   & ;
\end{tabular}%
\end{show}  

\subsection{More complex annotation notation}

The simple notation above is all one needs in many common cases: it
works whenever the XML serialization pattern is constructible only from
the immediate constituents of the rule's LHS (\texttt{A0})---\ie, the
XML trees of the rule's RHS symbols (when $n>0$). It is, however,
insufficient for expressing XML serialization patterns that depend on
sub-elements contained within those of the XML serialization of the RHS
symbols. The simple case is called \textit{homomorphic} tree
transduction, while the more complex case is called
\textit{heteromorphic} tree transduction.\footnote{The Greek etymology
of the words says precisely that: \textit{``homo-morphic'' = ``similar
form''} (from the Greek
``$\eta\omicron\mu\omicron$-$\mu\omicron\varrho\varphi\omicron\varsigma$,'' meaning
``same shape''), and \textit{``hetero-morphic'' = ``of dissimilar
form''} (from the Greek
``$\eta\varepsilon\tau\varepsilon\varrho\omicron$-$\mu\omicron\varrho\varphi\omicron\varsigma$,''
meaning ``different shape'').}

A more elaborate XML annotation is described next. It extends the above
basic notation by allowing the values of attributes and children in the
annotation to take on more complex forms. These forms denote references
to existing XML constructs within the XML trees already built for the
CST children of this node. We will illustrate the meaning of these
extended forms using simple color-coded examples. These show how the
basic notation for homomorphic tree-transduction annotations for
attribute and children can be extended to express some heteromorphic
tree-transduction as well.

\subsubsection{Children annotation}

The full form of the annotation expression for specifying children is:
\begin{display}
CH:(... \WRAPPER{w$_1$ ... w$_n$}\CHILD{c}\PATH{[x$_1$. ... .x$_m$]}\ATT{/a} ...)
\end{display}
of which only \CHILD{c} is mandatory. The four parts of a child
specification expression are such as described next.
\begin{enumerate}
\item The wrapper path \WRAPPER{w$_1${\ldots}w$_n$} is optional: each
  wrapper \WRAPPER{w$_i$} is a pair made of a (unquoted, single-quoted,
  or double-quoted) string (an XML tag), followed by a distribution
  marker, which is either a dot (`\texttt{.}'), or an asterisk
  (`\texttt{*}'). Using a dot triggers single wrapping, while using an
  asterisk triggers distributive wrapping (at the nesting level
  specified).

\item The child---there are two cases:
      \begin{enumerate}
      \item in a rule's annotation, \CHILD{c} is a positive
            integer and denotes a position in the rule's RHS (\ie,
            a position in the CST) and refers to the XML tree
            corresponding to the child CST at this position;
      \item if not a number, \CHILD{c} must be a \textit{special
            form}. In this case, there may be nothing trailing after
            \CHILD{c}; \ie, \PATH{[x$_1$.~\ldots~.x$_m$]}\ATT{/a} is
            empty.
      \end{enumerate}

 \item The XML tree path \PATH{[x$_1$.~\ldots~.x$_m$]} is optional; if
   not empty, it denotes a path in the XML tree. This path corresponds
   either to a single XML component of a CST node, or the set of all XML
   components of a CST node. In the first case (single component), each
   \PATH{x$_j$} is a positive integer denoting a component position in the
   XML tree rooted in this referring CST child. This is also true in the
   second case (all children), except for the last (\PATH{x$_m$}) which is
   then equal to \PATH{0}. In particular, it may be reduced to just the form
   \CHILD{c}\PATH{[0]}, in which case it refers to the set of all the
   XML components of the XML form of the CST node in position \CHILD{c}.

\item The attribute reference \ATT{/a} is optional; when present,
      \ATT{a} is a (possibly unquoted, single-quoted, or double-quoted)
      string; it must be the name of an XML attribute in the ultimate
      XML tree referred to by \CHILD{c}\PATH{[x$_1$.~\ldots~.x$_m$]},
      and denotes the string content making up the value of that XML
      attribute. When an attribute reference is specified, the XML tree
      path may not end with \PATH{0} (since it then does not refer to
      one node, but to a set of nodes).

\end{enumerate}

\subsubsection{Examples of children annotation}

\paragraph{Basic children annotation}

The notation:
\begin{display}
CH:(\cA2, \cB4)
\end{display}
specifies that the XML children are, in this order:
\begin{enumerate}
\item the XML form of \cA{2$^{nd}$} child CST,
\item the XML form of \cB{4$^{th}$} child CST.
\end{enumerate}

\paragraph{Extended children annotation}

\begin{itemize}
\item\textit{Grandchild reference}---the notation:
\begin{display}
CH:(\cA2[\cB1], \cC4[\cD2])
\end{display}
specifies that the XML children are, in this order:
\begin{enumerate}
\item the \cB{1$^{st}$} XML component of the XML form of \cA{2$^{nd}$} child CST,
\item the \cD{2$^{nd}$} XML component of the XML form of \cC{4$^{th}$} child CST.
\end{enumerate}

\item\textit{Grandchildren set reference}---the notation:
\begin{display}
CH:(\cA2[\cB0], \cC4[\cD2])
\end{display}
specifies that the XML children are, in this order:
\begin{enumerate}
\item all the XML components of the XML form of \cA{2$^{nd}$} child CST,
\item the \cD{2$^{nd}$} XML component of the XML form of \cC{4$^{th}$} child CST.
\end{enumerate}

\item\textit{Descendant reference}---the notation:
\begin{display}
CH:(\cA2[\cB1.\cC4], \cD1[\cE2.\cF1.\cG3])
\end{display}
specifies that the XML children are, in this order:
\begin{enumerate}
\item the \cC{4$^{th}$} XML component of \cB{1$^{st}$} XML component of the XML form
      of \cA{2$^{nd}$} child CST,
\item the \cG{3$^{rd}$} XML component of \cF{1$^{st}$} XML component of \cE{2$^{nd}$} XML
      component of the XML form of \cD{1$^{st}$} child CST.
\end{enumerate}

\item\textit{Attribute reference}---the notation:
\begin{display}
CH:(\cA2[\cB1.\cC4]/\cD{foo})
\end{display}
specifies that the only XML child is the string value of the
attribute named \cD{foo} of the \cC{4$^{th}$} XML component of \cB{1$^{st}$} XML
component of the XML form of \cA{2$^{nd}$} child CST.

\item\textit{Wrappers}---the notation:
\begin{display}
CH:(\cA{foo}.\cB2, \cC{bar}.\cD{fuz}.\cE4)
\end{display}
specifies that the XML children are, in this order:
\begin{enumerate}
\item \texttt{<\cA{foo}>}{\small\it(XML form of \cB{2$^{nd}$} child CST)}\texttt{</\cA{foo}>}
\item \texttt{<\cC{bar}><\cD{fuz}>}{\small\it(XML form of \cE{4$^{th}$} child CST)}\texttt{</\cD{fuz}></\cC{bar}>}
\end{enumerate}

By default, wrappers do not distribute over their contents. In other
words, the resulting form will be one with all the contents wrapped in a
single nesting of wrappers. If it is desired to override this default
behavior and actually distribute a wrapper tag path over the sequence
making up the contents being wrapped, then one uses an asterisk
(`\cA*') instead of a dot (`\cB.'), as in, \eg:
\begin{display}
CH:(foo\cA*2, bar\cA*fuz\cB.4)
\end{display}
Thus, using an asterisk rather than a dot in specifying a wrapper path
triggers one of three things depending on whether the contents being
wrapped is:
\begin{enumerate}
\item\textit{nothing}---in which case nothing is generated;
\item\textit{a single XML element}---in which case the wrapped
      single element  is generated;
\item\textit{a sequence of XML elements}---in which case the
      corresponding sequence of wrapped elements is generated.
\end{enumerate}
\end{itemize}

\subsubsection{Attributes annotation}

The full form of the annotation expression for specifying an attribute
is:
\begin{display}
AT:\{... \ATT{foo}=\CHILD{c}\PATH{[x$_1$. ... .x$_m$]}\ATT{/a} ...\}
\end{display}
of which only \CHILD{c} is mandatory.

\begin{itemize}
\item If \PATH{[x$_1$.~\ldots~.x$_m$]}\ATT{/a} is missing, then
      \CHILD{c} may be only one of:
      \begin{enumerate}
      \item a literal string---\eg, \CHILD{"bar"}; or,
      \item a special form---\ie, \VALUE\ or \TEXT.
      \end{enumerate}

\item If \PATH{[x$_1$.~\ldots~.x$_m$]} is present, the \PATH{x$_i$}'s
      are a sequence of dot-separated positive integers, an XML tree
      path referencing an XML subtree.  Then, the annotation must be
      that of a rule and \CHILD{c} must be a positive integer denoting
      the position a child CST for the current rule (a position in the
      rule's RHS). It refers to the XML tree of child CST at that
      position.
      
      If \ATT{/a} is present, it must be the name of an attribute in the
      XML tree so referenced. This annotation denotes the string value
      of this attribute in that XML tree. If \ATT{/a} is missing, then
      the annotation denotes the text content of the XML tree so
      referenced.
\end{itemize}

\subsubsection{Examples of attribute notation}

\paragraph{Basic attribute annotation}

The notation:
\begin{display}
AT:\{\cA{foo}=\cB{"bar"}\}
\end{display}
sets the attribute named \cA{foo} to the literal string value
\cB{"bar"}.

\paragraph{Extended attribute annotation}

\begin{itemize}
\item\textit{Child's text value}---the notation:
\begin{display}
AT:\{\cA{foo}=\cB3\}
\end{display}
sets the attribute named \cA{foo} to the text value of the XML
form of \cB{3$^{rd}$} child CST.

\item\textit{Child's attribute value}---the notation:
\begin{display}
AT:\{\cA{foo}=\cB3/\cC{bar}\}
\end{display}
sets the attribute named \cA{foo} to the value of the attribute named
\cC{bar} in the XML form of \cB{3$^{rd}$} child CST.

\item\textit{Descendant's text value}---the notation:
\begin{display}
AT:\{\cA{foo}=\cB3[\cC1.\cD2]\}
\end{display}
sets the attribute named \cA{foo} to the text value of the \cD{2$^{nd}$}
XML component of the \cC{1$^{st}$} XML component of the XML form of
the \cB{3$^{rd}$} child CST.

\item\textit{Descendant's attribute value}---the notation:
\begin{display}
AT:\{\cA{foo}=\cB3[\cC1.\cD2]/\cE{bar}\}
\end{display}
sets the attribute named \cA{foo} to the value of the attribute named
\cE{bar} located in the \cD{2$^{nd}$} XML component of the \cC{1$^{st}$}
XML component of the XML form of the \cB{3$^{rd}$} child CST.

\item\textit{Terminal value}---in a terminal's annotation only, the notation:
\begin{display}
AT:\{\cA{foo}=\VALUE\}
\end{display}
sets the attribute named \cA{foo} to the value of the terminal
node actually parsed.
\end{itemize}

\subsubsection{Interpreted special forms}

In addition to the above notation (and default behavior), we provide the
following conveniences to specify finer details on the XML appearance
from the information present in the CST thanks to the following built-in
special forms, which all starting with a dollar sign (`\verb+$+'),
followed by the (case-insensitive) form identifier and possible
arguments between parentheses and separated by a legal list separator;
namely, blank space, `\texttt{,}' (comma), or `\texttt{;}' (semicolon).

\paragraph{Extracting the value of a terminal}

The notation \VALUE\ may appear in an XML annotation expression for
either a rule or a terminal whenever the CST construct it refers to is
that of a terminal. For example:
\begin{itemize}
\item \textsl{an attribute value string;} \eg, the notation:
%\begin{small}
\begin{display}
\XMLINFO \cA{SHTOONG} [ L:\cB{"BAR"} N:\cC{"Foo"} A:\{ \cD{fuz} = \VALUE \} ]
\end{display}
%\end{small}
specifies that a terminal symbol \cA{SHTOONG} with print value
\cA{"Gloop"} will be serialized as follows:
\begin{display}
<\cC{Foo}:\cB{BAR} \cD{fuz}=\cA{"Gloop"}/>
\end{display}

\item \textsl{a single XML content string;} \eg, the notation:
%\begin{small}
\begin{display}
\XMLINFO \cA{SHTOONG} [ L:\cB{"BAR"} N:\cC{"Foo"} C:( \VALUE ) ]
\end{display}
%\end{small}
specifies that a terminal symbol \cA{SHTOONG} with print value
\cA{"Gloop"} will be serialized as follows:
\begin{display}
<\cC{Foo}:\cB{BAR}>\cA{Gloop}</\cC{Foo}:\cB{BAR}>
\end{display}
\end{itemize}

\paragraph{Concatenating pieces of text}

Wherever text is expected, we may use the notation
\TEXT\texttt{(\ldots)} to denote the text string resulting from the
concatenation of the text strings denoted by its arguments, each of
which may be either a literal (possibly single- or double-quoted)
string, or a reference to a text value deeper in a descendant CST's XML
structure using the XML tree reference notation
\CHILD{c}\PATH{[x$_1${\ldots}x$_n$]}\ATT{/a}, where the
\PATH{[x$_1${\ldots}x$_n$]} and \ATT{/a} parts are optional.

This construct comes handy for composing a text string on the fly to make
up the text value of a child or an attribute. For example, given the
annotations in Figure~\ref{topless},
\begin{figure}[htb]
\begin{cshow}\small
\begin{tabular}{lllll}
\hline \\ \\
\XMLINFO  & \multicolumn{4}{l}{ID} \\
          & [ \\
          &   & \LOCAL{L} & : & \LOCAL{"Identifier"} \\
          &   & \ATT{A}   & : & \ATT{\{ name = \VALUE \}} \\
          & ] \\
\\
\XMLINFO  & STR \\
          & [ \\
          &   & \LOCAL{L} & : & \LOCAL{"String"} \\
          &   & \ATT{A}   & : & \ATT{\{ value = \VALUE \}} \\
          & ] \\
\\
Type & : & \multicolumn{3}{l}{ID ':' ID} \\
          & [ \\
          &   & \LOCAL{L} & : & \LOCAL{"Type"} \\
          &   & \ATT{A}   & : & \ATT{\{ general = \CHILD{1}/name special = \CHILD{3}/name \}} \\
          & ] \\
          & ; \\
\\
Entry     & : & \multicolumn{3}{l}{STR '\OP' Type} \\
          & [ \\
          &   & \LOCAL{L} & : & \LOCAL{"Place"} \\
          &   & \ATT{A}   & : & \ATT{\{ type = \TEXT ( "[" \CHILD{3}/special "]" \CHILD{3}/general ) \}} \\
          &   & \CHILD{C} & : & \CHILD{( 1/\ATT{value} )} \\
          & ] \\
          & ; \\
\\
\hline
\end{tabular}
\end{cshow}
\caption{Example of annotations using the \VALUE\ and \TEXT\ special forms}
\label{topless}
\end{figure}
the piece of \texttt{Entry} syntax:
\begin{display}
\cA{bar}{\OP}\cB{less}:\cC{top}
\end{display}
gets serialized as:
\begin{display}
<\LOCAL{Place} \ATT{type}="[\cC{top}]\cB{less}">\cA{bar}</\LOCAL{Place}>
\end{display}

\subsection{Checking annotation consistency}

We need to enforce consistent number referencing in the tree addresses
used in the notation---\ie, the numbers that refer to RHS nodes and XML
elements (the \texttt{c}$_i$'s and the \texttt{x}$_i$'s below). Indeed,
they should (be made to) obey the following necessary conditions (all
easy to justify):
\begin{itemize}

\item\textbf{Condition 1:} An annotation for a terminal, or for a rule
     with an empty RHS, should not be allowed to use a tree address in
     any attribute specifier (only symbol, quoted string, or number). A
     terminal's annotation \CHILD{CH} may only contain wrappers and a
     reference to \VALUE.

\item\textbf{Condition 2:} In an annotation \ATT{AT:\{\ldots\}}, the
     name of an attribute following an XML tree reference must be a
     legal attribute of the element so referenced.

\item\textbf{Condition 3:} In a rule annotation
     \texttt{CH:({\ldots}\CHILD{c}$_i$[\ldots]\ldots)}, the number of
     \CHILD{c}$_i$'s must be between $1$ and the length of the rule's
     RHS.

\item\textbf{Condition 4:} In an annotation \texttt{CH:(\ldots)}, two
     distinct occurrences of XML content references must not be allowed
     to be one another's prefix or duplicate address. In other words, no
     tree address may occur more that once in the same annotation; and,
     whenever a tree address occurs in an annotation, none of its
     prefixes may occur in the same annotation.

     In other words, whenever the child path expression
     \CHILD{c}\PATH{[x$_1$.~\ldots~.x$_n$]} occurs in a \texttt{CH}
     annotation, then neither
     \CHILD{c}\PATH{[x$_1$.~\ldots~.x$_{n-1}$]}, nor
     \CHILD{c}\PATH{[x$_1$.~\ldots~.x$_{n-2}$]}, \ldots, nor
     \CHILD{c}\PATH{[x$_1$]}, nor \CHILD{c} may be allowed to occur in
     the same \texttt{CH} annotation.

     For example, both the \texttt{CH} annotations \texttt{CH:}\cGood{(1 2)} and
     \texttt{CH:}\cGood{(1~2[1]~2[2])} are legal; how\-ever, neither
     \texttt{CH:}\cBad{(1~2~1)} nor \texttt{CH:}\cBad{(1~2[1]~1[2])} are.

\item\textbf{Condition 5:} Whenever a tree address of the form
     \CHILD{c}\PATH{[x$_1$.x$_2$.~\ldots~.x$_n$]} occurs, then for it to
     be consistent, this entails that the XML form of the CST node
     referenced by \CHILD{c} must consist of exactly one XML
     element---as opposed to none or many. This is true iff the
     referenced RHS symbol is either a value-carrying terminal, or a
     non-terminal all of whose possible XML forms are each single XML
     elements. This must be verified statically at grammar analysis
     time.

\item\textbf{Condition 6:} Whenever a tree address of the form
  \CHILD{c}\PATH{[x$_1$.x$_2$.~\ldots~.x$_n$.0]} occurs, (with
  $n\geq0$), it refers to the set of all children of the node
  \CHILD{c}\PATH{[x$_1$.x$_2$.~\ldots~.x$_n$]}. Therefore, it may not be
  followed with an attribute, and no other tree address other than this
  one may be of the form
  \CHILD{c}\PATH{[x$_1$.x$_2$.~\ldots~.x$_n$.\ldots]}. This goes also
  for $n=0$; for example, \texttt{CH:}\cBad{(2[1]~2[0])} is forbidden
  since the 1st XML child of the 2nd CST child is referred twice (first
  explicitly individually, then implicitly in the set of all children of
  the same node).

\end{itemize}

Violation of any of these conditions at parser-generation time should
raise an exception and be reported as an error.  If all these conditions
hold, then the code for the method \texttt{xmlify(Element container)}
defined in the class \texttt{ParseNode}, and the method
\texttt{createXmlForm(ParseNode node, Element root)} defined in the
class \texttt{XmlInfo}, is guaranteed to work safely. 

%% \subsection{DTD/Schema extraction}

%% Note that when all annotations are consistent, we may wish to extract
%% more static information from the annotated grammar. It is indeed
%% possible to infer the global nature of the admissible XML documents
%% generated from a specific annotated grammar at parser-generation time
%% using simple static analysis of the grammar. From this we may then
%% generate a DTD or an XML Schema describing the type of XML documents
%% produced from serializing well-formed syntactic units. This may then be
%% optionally adjoined to the produced XML document as a seal of verifiable
%% well-formedness.

%% Extracting the types of XML elements from annotations For verifying a
%% property such as [Condition 2] above, it is necessary to know the XML
%% "element type" of the referenced XML node. This "type", of the form
%% nsPrefix:localName, may be computed statically by analyzing the
%% grammar's annotations, and deriving the exact XML element "type" for
%% each tree reference in the annotations. This is done as follows.

%% To each grammar symbol A, we associate its _xmlFormType: a
%% RegularExpression denoting the set of possible XML element types that A
%% may expand into when serialized into its XML form:

%%     * if A is an unannotated terminal that does not carry a value, then
%%       A's _xmlFormType is empty (i.e., RegularExpression.EMPTY);

%%     * if A is an annotated or value-carrying terminal, then A's
%%       _xmlFormType is a single XML element whose name is the symbol's
%%       name if non-annotated, or specified by the annotation, otherwise;

%%     * if A is a non-terminal whose ruleset is:

%%                 A : A$_11$ ... A$_1{n_1}$
%%                   | A$_21$ ... A$_2{n_2}$
%%                   | ...
%%                   | A$_m1$ ... A$_m{n_m}$
%%                   ;
                

%%       then A's _xmlFormType is the union, for each rule index i, of the
%%       Xi's, where each Xi is the _xmlFormType corresponding to the ith
%%       rule for A (for 0?i?m), and computed as follows:

%%           o if the ith rule for A is annotated, then Xi is the XML type
%%             of the single XML element specified by the annotation;

%%           o otherwise, Xi is the concatenation of those of the Aij's (for 0<j<ni). 

%% Computing a DTD by fix-point closure of regular expressions

%% The idea is simply to iterate the above step until a fix point is
%% reached (i.e., until no change occurs in any of the computed
%% _xmlFormType's from one iteration to the next). Therefore, in order to
%% enable effective comparison of RE's, the _xmlFormType's are kept in
%% normal form.  Example Consider the following annotated grammar:

%%   Sexp : Atom
%%        | '(' List ')' [ LO: List   CH: (2) ]
%%        ;
 
%%   Atom : NUMBER     [ LO: Number AT: \{value = \VALUE\} ]
%%        | NAME       [ LO: Name   AT: \{value = \VALUE\} ]
%%        | NIL        [ LO: Nil ]
%%        ;
 
%%   List :            [ LO: Nil ]
%%        | List Sexp
%%        ;
  

\section{Example}
\label{example}

\section{Conclusion}
\label{conclusion}

\subsection{Recapitulation}

\subsection{Further work}

\bibliographystyle{acm}
\bibliography{main}

\label{endpage}
\end{document}
