File: paper.html%2Cv

package info (click to toggle)
flexml 1-5
links: PTS
area: main
in suites: potato, woody
size: 884 kB
ctags: 203
sloc: perl: 2,016; makefile: 160; ansic: 56; xml: 28
file content (1942 lines) | stat: -rw-r--r-- 66,798 bytes
head	1.10;
access;
symbols;
locks; strict;
comment	@# @;


1.10
date	99.12.09.08.22.01;	author krisrose;	state Exp;
branches;
next	1.9;

1.9
date	99.12.06.21.08.09;	author krisrose;	state Exp;
branches;
next	1.8;

1.8
date	99.12.02.00.32.24;	author krisrose;	state Exp;
branches;
next	1.7;

1.7
date	99.11.29.16.09.02;	author krisrose;	state Exp;
branches;
next	1.6;

1.6
date	99.11.25.18.37.39;	author krisrose;	state Exp;
branches;
next	1.5;

1.5
date	99.11.25.03.01.47;	author krisrose;	state Exp;
branches;
next	1.4;

1.4
date	99.11.23.17.28.07;	author krisrose;	state Exp;
branches;
next	1.3;

1.3
date	99.11.23.10.10.36;	author krisrose;	state Exp;
branches;
next	1.2;

1.2
date	99.11.23.04.03.05;	author krisrose;	state Exp;
branches;
next	1.1;

1.1
date	99.11.22.18.41.48;	author krisrose;	state Exp;
branches;
next	;


desc
@Started on submission...late :)
@


1.10
log
@Oops: tricky stopped working...holding...
@
text
@<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
  <head>
    <title>Generating Fast Validating XML Processors</title>
    <!--$Id: paper.html,v 1.9 1999/12/06 21:08:09 krisrose Exp krisrose $-->
    <style type="text/css">
<!--
 BODY { BACKGROUND-COLOR: #ffffff; FONT-FAMILY: arial, times new roman, sans-serif; }
 A:link, A:visited, A:active { TEXT-DECORATION: none; FONT-WEIGHT: bold; COLOR: #0000FF}
  
 H1, H2 { TEXT-ALIGN: center; FONT-WEIGHT: bold; }
 H3, H4, H5 { TEXT-ALIGN: left; FONT-WEIGHT: bold; }
 H6 { TEXT-ALIGN: center; FONT-WEIGHT: bold; FONT-SIZE: small; }
 H6.CAPTION { TEXT-ALIGN: center; FONT-WEIGHT: bold; FONT-SIZE: small; FONT-STYLE: italic; }
  
 P { TEXT-INDENT: 1em; }
 P.CODE { TEXT-INDENT: 0; COLOR: #FF0000; }
  
 UL, OL, DL { FONT-SIZE: small; }
 UL { list-style: square; }
 LI { FONT-SIZE: small; FONT-WEIGHT: bold; }
 UL EM, OL EM { FONT-WEIGHT: bold; }
 CODE, CITE { FONT-WEIGHT: bold; }
  
 BLOCKQUOTE { MARGIN-LEFT: 1em; MARGIN-RIGHT: 1em }
 IMG { VERTICAL-ALIGN: top; ALIGN: center; }
 SUP { COLOR: #0000FF; FONT-SIZE: small; }
-->
    </style>
  </head>
  <body>

    <h2>
      Generating Fast Validating XML Processors
    </h2>

    <h6>
      (Extended Abstract)
    </h6>

    <h6>
      <a href="http://www.ens-lyon.fr/~krisrose">Kristoffer Rose</a><br>
      <a href="http://www.ens-lyon.fr/LIP">LIP, ENS-Lyon</a><br>
      <a href="mailto:krisrose@@debian.org">krisrose@@debian.org</a>
    </h6>

    <h6> Abstract </h6>

    We present <em>FleXML</em>, a program that generates fast
    validating XML processors from `self-contained' XML DTDs.  It uses
    the <em>flex</em> (lexical analyser generator) program to
    translate the DTD into a <em>finite automaton</em> enriched with a
    stack with the `element context'.  This means that the XML
    processor will act directly on each character received.  The
    program is freely redistributable and modifyable (under GNU
    `copyleft').

    <h6> Keywords </h6>

    Validating XML, DTD, lexical analysis, finite automata.


    <h4> Overview </h4>

    The `X' of XML stands for <em>Extensible</em> [<cite><a
    href="#XML">XML</a></cite>].  This signifies that each and every
    XML document specifies in its header the details of the format
    that it will use and <em>may</em> change its format a bit relative
    to the used base format.
    <p>
      This has influenced the tools available to write validating XML
      processors: they use a <em>call-back</em> model where the XML
      processor passes strings with the tags and attributes names and
      values to the application.  These call-backs must be generic
      because one cannot know whether a document will start by
      extending its own notation with more tags and attributes.  For
      <em>well-formed</em> but non-validated XML documents this makes
      a lot of sense, of course, but we would in general like to
      exploit the information in the DTD for optimizations.
    <p>
      In particular, for many applications a <em>fixed</em> format
      suffices in the sense that a single DTD is used without
      individual extensions for a large number of documents.  In that
      case we can do much better because the possible tags and
      attributes are static.
    <p>
      We have implemented an XML processor <em>generator</em> using
      the <cite><a href="#Flex">Flex</a></cite> scanner generator that
      produces deterministic finite automata [<cite><a
      href="#ASU">ASU</a></cite>].  Which means that there is almost
      no overhead for XML processing: the generated XML processors
      read the XML document character by character and can immediately
      dispatch the actions associated with each element (or reject the
      document as invalid).
    <p>
      Furthermore we have devised a simple extension of the C
      programming language that facilitates the writing of `element
      actions' in C, making it easy to write really fast XML
      applications.  In particular we represent XML attribute values
      efficiently in C when this is possible, thus avoiding the
      otherwise ubiquitous conversions between strings and data
      values.
    <p>
      FleXML is available for free (from <a
      href="http://www.ens-lyon.fr/~krisrose/">the author's web
      page</a>).  In this paper we present FleXML through an
      elaborated <a href="#what">example</a> and discuss some of the
      <a href="#how">technical issues</a>.


    <h4><a name="what">What can it do?</a></h4>

      Assume that we have an XML document <code>my-joke.xml</code>
      containing the classical joke

<blockquote><code><pre>&lt;!DOCTYPE joke SYSTEM &quot;my.dtd&quot;&gt;
&lt;joke&gt;&lt;line&gt;My appartment is so small&lt;/line&gt; &lt;suspense/&gt;
&lt;line type='punch-line'&gt;the mice are round-shouldered&lt;/line&gt;&lt;/joke&gt;
</pre></code></blockquote>

      (and many others like it, of course).  We wish to create an XML
      processor to validate it with respect to the DTD in the file
      <code>my.dtd</code> containing

<blockquote><code><pre>&lt;!-- my.dtd: Small DTD for jokes (just for fun). --&gt;
&lt;!ELEMENT joke (line,(line|suspense)*)&gt;
&lt;!ELEMENT line (#PCDATA)&gt;
&lt;!ATTLIST line type (normal|question|punch-line) 'normal'&gt;
&lt;!ELEMENT suspense EMPTY&gt;
</pre></code></blockquote>

      and, furthermore, we wish to write an XML application for
      displaying such messages in an amusing way.
    <p>
      With FleXML this can be done by creating an `actions file'
      <code>my-show.act</code> which implements the desired actions
      for each element.  The remainder of this section explains the
      contents of such an actions file.
    <p>
      An actions file is itself an XML document which must begin with

<blockquote><code><pre>&lt;!DOCTYPE actions SYSTEM &quot;flexml-act.dtd&quot;&gt;
&lt;actions&gt;
</pre></code></blockquote>

      (the <code>flexml-act.dtd</code> DTD is part of the FleXML
      system and is reproduced in the manual page.
    <p>
      We decide that our application should react to a
      <code>line</code> element by printing the text inside it, and
      that it should differentiate between the three possible `type'
      attribute values by printing corresponding trailing punctuation.
    <p>
      This introduces a slight complication, because the attribute
      values are available when parsing the start tag whereas the
      element text is not available until we parse the end tag (where
      it has been read).
    <p>
      This means that we must declare a top-level variable.

<blockquote><code><pre>&lt;top&gt;&lt;![CDATA[
char* terminator = &quot;.&quot;;
]]&gt;&lt;/top&gt;
</pre></code></blockquote>

      Notice how we use <code>CDATA</code> sections to make sure that
      all characters (including white-space) are passed unmodified to
      the C compiler.
    <p>
      With this we can write the action to set it when reading the
      <code>line</code> start tag as

<blockquote><code><pre>&lt;start tag='line'&gt;&lt;![CDATA[
  switch ( {type} ) {
    case {!type}: terminator = &quot;...&quot;; break;
    case {type=normal}: terminator = &quot;.&quot;; break;
    case {type=question}: terminator = &quot;??&quot;; break;
    case {type=punch-line}: terminator = &quot;!!&quot;; break;
  }
]]&gt;&lt;/start&gt;
</pre></code></blockquote>

    <p>
      The idea is that the enumeration attribute <code>type</code> is
      implemented in C as if it had been declared by

<blockquote><code><pre>enum { {!type}, {type=normal}, {type=question}, {type=punch-line} } {type};
</pre></code></blockquote>

      (understanding the <code>{...}</code> units as C identifiers),
      hence the possibility of using the fast C <code>switch</code>
      statement to pick the right choice directly.  Note that the
      first choice, <code>{!<em>type</em>}</code>, corresponds to not
      setting the attribute; in this example the attribute has a
      default value so this can never happen, however, we include the
      choice anyway to prevent the C compiler from issuing warnings
      about missing choices in <code>switch</code> statements.
    <p>
      With this in place we can write the action for
      <code>&lt;/line&gt;</code>.  Since it prints something, however,
      we first need to add the appropriate header inclusion.

<blockquote><code><pre>&lt;top&gt;&lt;![CDATA[
#include &lt;stdio.h&gt;
]]&gt;&lt;/top&gt;

&lt;end tag='line'&gt;&lt;![CDATA[
  printf(&quot;%s%s\n&quot;, pcdata, terminator);
]]&gt;&lt;/end&gt;
</pre></code></blockquote>

    <p>
      Finally, we will make the application amusing by `displaying'
      the <code>&lt;suspense/&gt;</code> empty tag as a short delay;
      this also involves a header inclusion.

<blockquote><code><pre>&lt;top&gt;&lt;![CDATA[
#include &lt;unistd.h&gt;
]]&gt;&lt;/top&gt;

&lt;start tag='suspense'&gt;&lt;![CDATA[
  sleep(2);
]]&gt;&lt;/start&gt;
</pre></code></blockquote>

    <p>
      That is all; the only remaining thing is to terminate the action
      file properly.

<blockquote><code><pre>&lt;/actions&gt;
</pre></code></blockquote>

    <p>
      We can now run FleXML with the DTD and the actions file as input
      and will get an XML application as output that, when run (after
      processing by flex and a C compiler), will indeed print

<blockquote><code><pre>My appartment is so small.
the mice are round-shouldered!!
</pre></code></blockquote>

      as expected, pausing duly for two seconds between the lines.  On
      the authors system the above output was achieved with the
      command sequence

<blockquote><code><pre>flexml -A -a my-show.act my.dtd 
flex -omy-show.c my-show.l
cc -omy-show my-show.c
./my-show <./my-joke.xml
</pre></code></blockquote>

    (see the manual page for the exact meaning of the FleXML options).

    <p>
      An important aspect of the design of FleXML is that the only
      thing that should matter to the programmer should be the
      complexity of the <em>application</em>, not of the used DTD.  As
      an example the following action file prints the
      <code>href</code> attribute of all hyperlinks in an XHTML
      document:

<blockquote><code><pre>&lt;!DOCTYPE actions SYSTEM &quot;flexml-act.dtd&quot;&gt;
&lt;actions&gt;

&lt;top&gt;&lt;![CDATA[
#include &lt;stdio.h&gt;
]]&gt;&lt;/top&gt;

&lt;start tag='a'&gt;&lt;![CDATA[
if ({href}) printf(&quot;%s\n&quot;, {href});
]]&gt;&lt;/start&gt;

&lt;/actions&gt;
</pre></code></blockquote>

      which was compiled into a running application on the author's
      system with the commands

<blockquote><code><pre>flexml $(FLEXDEBUG) -rhtml -p'-//IETF//DTD XHTML 1.0 Transitional//EN' \
  'http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd'
gcc -Wall -ansi -pedantic -O2 -g -c xhtml-href.c -o xhtml-href.o
flex -Bsv -Ca -oxhtml1-transitional.c xhtml1-transitional.l
gcc -Wall -ansi -pedantic -O2 -g   -c xhtml1-transitional.c -o xhtml1-transitional.o
gcc -Wall -ansi -pedantic   xhtml-href.o xhtml1-transitional.o   -o xhtml-href
</pre></code></blockquote>

      generating the XML processor directly from the official DTD on
      the web (which in fact required a patch to flex to enlarge the
      possible table size).


    <h4><a name="how">How does it work?</a></h4>

    <p>
      FleXML is a perl script [<cite><a href="#Perl">Perl</a></cite>]
      which reads and interprets a DTD and subsequently produces an
      <em>XML processor</em> source file for the <em>flex</em> scanner
      and optionally an <em>XML application</em> with the C source of
      the element actions from an actions file.  The DTD is used to
      construct the rules used by flex to match the individual XML
      components in such a way that only valid documents match.
    <p>
      For example, the flex code for scanning an attribute declaration
      of the <code>line</code> tag is the following:

<blockquote><code><pre>&lt;AL_line&gt;{
 "type"{Eq}"'normal'"  |
 "type"{Eq}"\"normal\""  A_line_type = A_line_type_normal;
 "type"{Eq}"'question'"  |
 "type"{Eq}"\"question\""  A_line_type = A_line_type_question;
 "type"{Eq}"'punch-line'"  |
 "type"{Eq}"\"punch-line\""  A_line_type = A_line_type_punch_d_line;

 "&gt;" {
  LEAVE; STag_line(); pcdata = BUFFERSET(pcdata); ENTER(IN_line);
 }
 "/&gt;" {
  LEAVE; STag_line(); pcdata = ""; ETag_line();
  switch (YY_START) {
   case ROOT_line: SET(EPILOG); break;
   case S_joke: SET(S_joke_1); break;
   case S_joke_1: case S_joke_2: case S_joke_3: SET(S_joke_3); break;
}}}
</pre></code></blockquote>

    (with <code>{Eq}</code> an alias for the regular expression
    matching an equal sign (corresponding to production `[25] Eq' of
    the XML specification).
    <p>
      This reads as follows: when the XML processor is reading the
      attribute list of the <code>line</code> tag, i.e., when it is in
      the <code>&lt;AL_line&gt;</code> state, a `<code>t</code>' will
      enter an internal state where a `<code>y</code>' proceeds to
      another internal state but other characters makes the document
      invalid (because no rule permits it).  Once the equal sign has
      been scanned, the next characters determine the attribute value,
      and at the end one of the flex actions is performed, setting the
      attribute value (<code>A_line_type</code> is the real C for what
      we wrote as <code>{type}</code>, etc.).  The important thing is
      that one can ensure by careful tuning of the flex rules that a
      valid document will proceed only by looking each character up in
      a table and determining the subsequent `state' and `action'.
      One must avoid pairs of rules such as

<blockquote><code><pre>"-->"		LEAVE(COMMENT);
.		SKIP;
</pre></code></blockquote>

    (a single `<code>.</code>' matches any character) because they
    mean that the scanner will not be sure after having read a
    `<code>-</code>' character whether it is part of a comment
    terminator or `just' a dash.  In such cases an extra rule must be
    inserted because for the set

<blockquote><code><pre>"-->"		LEAVE(COMMENT);
"--"            |
.		SKIP;
</pre></code></blockquote>

    the problem goes away.
    <p>
      After the actual attribute rules, two rules handle termination
      of the attribute list.  There are two cases corresponding to
      whether we just read a start tag or an empty element.  In case
      it was a start tag then we must enter the `inner' mode of the
      element called <code>IN_line</code> for the <code>line</code>
      element.  The <code>switch</code> handles the state changes
      needed for the line element resulting from the fact that the
      element can appear in different contexts.  This is always
      possible to construct because of the requirement that an XML DTD
      must be <em>deterministic</em>: we just need an element content
      stack (this is what the <code>LEAVE</code> and
      <code>ENTER</code> macros are for).

    <h4><a name="why">Why is it useful?</a></h4>

    <p>
      In comparison with the forthcoming XML Style-sheet Language
      [<cite><a href="#XSL">XSL</a></cite>] our approach is much more
      primitive for better and worse: only a limited range of
      applications can be produced with FleXML but those will be very
      fast.
    <p>
      This is useful for XML applications that are meant to process a
      large number of documents in a fixed format.  One such
      application is the NTSys -payment transaction server which is
      implemented as an Apache module where performance is of premium
      importance.  Using FleXML permits a highly modular development
      of modules for the various transaction types based on a common
      DTD and a collection of applications that are generated
      separately and all linked together with the common processor.
    <p>
      FleXML is still under development: please try it out (either
      from <a "http://www.ens-lyon.fr/~krisrose/">the author's web
      page</a> or from the <a href="www.debian.org">Debian
      GNU/Linux</a> distribution where FleXML is include from release
      2.2.  The author would welcome comments as to how the system can
      best evolve.  Two things that are definitely on the agenda is a
      limited `context condition' language for expressing constraints
      on the position of an element in a document (corresponding to
      the Xpath subset of XSL), and an efficient way to combine
      several DTDs into one large t facilitate general XML servers
      (that can even dispatch to a generic XML interface in cases
      where the FleXML restrictions are not respected by a document).


    <h4> Acknowledgements </h4>

    <p>
      I am grateful to <a href="http://www.ntsys.fr">NTSys</a> for
      supporting the development of FleXML. Finally extend my sincere
      thanks to Jef Poskanzer, Vern Paxson, and the rest of the
      <em>flex</em> maintainers for a great tool.

    <h4> References </h4>

    <dl compact>

      <dt><a name="ASU"><cite>ASU</cite></a>
      <dd>
	Alfred Aho, Ravi Sethi and Jeffrey Ullman: <em>Compilers:
	Principles, Techniques and Tools</em>, Addison-Wesley
	(1986).<p>

      <dt><a name="Flex"><cite>Flex</cite></a>
      <dd>
	Jef Poskanzer, Vern Paxson, <em>et. al.</em>: <em>Flex - fast
	lexical analyzer generator</em>.<p>

      <dt><a name="Perl"><cite>Perl</cite></a>
      <dd>
	Larry Wall, <em>Perl - Practical Extraction and Report
	  Language</em>.<p>

      <dt><a name="XML"><cite>XML</cite></a>
      <dd>
	Extensible Markup Language (XML) 1.0 (W3C
	Recommendation REC-xml-1998-0210).<p>

      <dt><a name="XSL"><cite>XSL</cite></a>
      <dd>
	Extensible Stylesheet Language (XSL) (W3C Working Draft).<p>

    </dl>
    <hr>
    <address>Copyright 
      <a href="mailto:Kristoffer.Rose@@ens-lyon.fr">Kristoffer Rose</a>.
<!-- Created: Thu Dec  9 08:09:41 CET 1999 -->
<!-- hhmts start -->
Last modified: Thu Dec  9 09:20:06 CET 1999
<!-- hhmts end -->
    </address>

  </body>
</html>
@


1.9
log
@Releasing.
@
text
@d5 1
a5 1
    <!--$Id: paper.html,v 1.8 1999/12/02 00:32:24 krisrose Exp krisrose $-->
d34 1
a34 2
      Generating Fast Validating XML Processors<br>
      <strong>Unfinished draft!</strong>
d74 1
a74 1
      values to the application.  These call-backs must be dynamic
d126 1
a126 1
&lt;!ELEMENT joke (line|suspense)*&gt;
d147 1
a147 2
      system and is reproduced in the <a href="#ACTION_FILES">manual
      page in the appendix</a>).
d235 2
a236 2
      and will get an XML application as output that when run (after
      processing by flex and a C compiler) will, indeed, print
d252 39
a290 2
    (see the manual page in the appendix for the exact meaning of the
    FleXML options).
d294 8
a301 7
    FleXML is a perl script [<cite><a href="#Perl">Perl</a></cite>]
    which reads and interprets a DTD and subsequently produces an
    <em>XML processor</em> source file for the <em>flex</em> scanner
    and optionally an <em>XML application</em> with the C source of
    the element actions from an actions file.  The DTD is used to
    construct the rules used by flex to match the individual XML
    components in such a way that only valid documents match.
d314 10
a323 4
 "&gt;"  LEAVE(AL_line); STag_line(); pcdata = BUFFERSET(pcdata); ENTER(IN_line);
 "/&gt;" LEAVE(AL_line); STag_line(); pcdata = ""; ETag_line(); CHECKEPILOG(line);
 {S}     SKIP;
}
d328 1
a328 1
    the XML specification) and <code>{S}</code> an alias for spacing).
d362 2
a363 2
      After the actual attribute rules two rules handle termination of
      the attribute list.  There are two cases corresponding to
d365 9
a373 10
      it wasa start tag then we must enter the `inner' mode of the
      element called <code>IN_line</code> for the <line> tag.
    <p>
      The last rule is strightforward: it just expresses that spaces
      are ignored in attribute lists.
    <p>


  /> -> action.

d375 1
d378 27
a404 25
      In fact this principle works even at the element level because
      XML requires that element content declarations be
      <em>deterministic</em>.  The only extension is that element
      contents is <em>recursive</em> so we must maintain a stack of
      `outer' states: this is what the <code>LEAVE</code> and
      <code>ENTER</code> macros are for.

In order to pull the same trick for the regular expressions 


      This is how the XML processor will match character by character,
      first the <code>type</code> attribute name, then the equality
      sign, then either




    <h4><a name="why">Why is it useful?</a></h4>

    The W3C is developing a standard for 

    These days everyone is talking about [<cite><a
    href="#XSL">XSL</a></cite>], the XML Stylesheet Language


d409 5
a413 283
    I am grateful to <a href="http://www.ntsys.fr">NTSys</a> for
    supporting the development of FleXML. Finally extend my sincere
    thanks to Jef Poskanzer, Vern Paxson, and the rest of the
    <EM>flex</EM> maintainers and GNU developers for a great tool.


    <h4> Appendix: manual page </h4>

    This appendix contains the unix manual page for FleXML (adapted to
    the form of this paper).

<DL>

<p><dt><A NAME="NAME">NAME</A><dd>

flexml - generate validating XML processor and applications from DTD

<p><dt><A NAME="SYNOPSIS">SYNOPSIS</A><dd>
<STRONG>flexml</STRONG>
[<STRONG>-ASHDvdnLXV</STRONG>] [<STRONG>-s</STRONG><EM>skel</EM>] [<STRONG>-p</STRONG><EM>pubid</EM>] [<STRONG>-u</STRONG><EM>uri</EM>] [<STRONG>-r</STRONG><EM>rootags</EM>] [<STRONG>-a</STRONG><EM>actions</EM>]
<EM>name</EM>[<EM>.dtd</EM>]

<P>
<HR>
<p><dt><A NAME="DESCRIPTION">DESCRIPTION</A><dd>
<EM>Flexml</EM> reads <EM>name</EM><EM>.dtd</EM> which must be a DTD (Document Type Definition) describing the format of XML
(Extensible Markup Language) documents, and produces a ``validating'' XML <EM>processor</EM> with an interface to support XML <EM>application</EM>s. Proper applications can be generated optionally from special ``action
files'', either for linking or textual combination with the processor

<P>
The generated processor will only validate documents that conform strictly
to the DTD, <EM>without extending it</EM>, more precisely we in practice restrict XML rule [28] to

<P>
<PRE>  [28r] doctypedecl ::= '&lt;!DOCTYPE' S Name S ExternalID S? '&gt;'
</PRE>
<P>
where the <CODE>ExternalId</CODE> denotes the used DTD.

<P>
The generated processor is a <EM>flex</EM>(1) scanner, by default named
<EM>name</EM><EM>.l</EM> with a corresponding C header file <EM>name</EM><EM>.h</EM> for separate compilation of generated applications.  

<P>
Optionally <EM>flexml</EM> takes an <EM>actions</EM> file with per-element actions and produces a C file with element functions
for an XML application with entry points called from the XML processor (it
can also fold the XML application into the XML processor to make
stand-alone XML applications but this prevents sharing of the processor
between applications).

<P>
In <A HREF="#OPTIONS">OPTIONS</A> we list the possible options, in <A HREF="#ACTION_FILE_FORMAT">ACTION FILE FORMAT</A>
we explain how to write applications, and in <A HREF="#BUGS">BUGS</A> we list the current limitations of the system before giving standard
references.

<P>
<HR>
<p><dt><A NAME="OPTIONS">OPTIONS</A><dd>
<EM>Flexml</EM> takes the following options.

<DL>
<DT><STRONG><A NAME="item__A">-A</A></STRONG><DD>
<P>
Generate a <EM>stand-alone</EM> scanner application. If combined with
<STRONG>-a</STRONG><EM>actions</EM> then the application will be named as <EM>actions</EM> with the extension replaced by <EM>.l</EM>, otherwise it will be in <EM>name</EM><EM>.l</EM>. Conflicts with <STRONG>-S</STRONG>, <STRONG>-H</STRONG>, and <STRONG>-D</STRONG>.

<DT><STRONG><A NAME="item__a">-a actions</A></STRONG><DD>
<P>
Uses the <EM>actions</EM> file to produce an XML application in the file with the same name as <EM>actions</EM> after replacing the extension with
<EM>.c</EM>. If combined with <STRONG>-A</STRONG> then instead the stand-alone application will include the action functions.

<DT><STRONG><A NAME="item__D">-D</A></STRONG><DD>
<P>
Generate a dummy application <EM>name</EM><EM>-dummy.c</EM> with just empty functions to be called by the XML processor. If combined
with
<STRONG>-a</STRONG><EM>actions</EM> then the application will insert the specified actions and be named as <EM>actions</EM> with the extension replaced by
<EM>.c</EM>. Conflicts with <STRONG>-A</STRONG>; implied by <STRONG>-a</STRONG> unless either of
<STRONG>-SHD</STRONG> is specified.

<DT><STRONG><A NAME="item__d">-d</A></STRONG><DD>
<P>
Turns on debug mode in the flex scanner and also prints out the details of
the DTD analysis performed by <EM>flexml</EM>.

<DT><STRONG><A NAME="item__H">-H</A></STRONG><DD>
<P>
Generate the header file <EM>name</EM><EM>.h</EM>. Conflicts with <STRONG>-A</STRONG>; on by default if none of <STRONG>-SHD</STRONG> specified.

<DT><STRONG><A NAME="item__L">-L</A></STRONG><DD>
<P>
Makes the XML processor (as produced by <EM>flex</EM>(1)) count the lines in the input and keep it available to XML application
actions in the integer <CODE>yylineno</CODE>. (This is off by default as the performance overhead is significant.)

<DT><STRONG><A NAME="item__n">-n</A></STRONG><DD>
<P>
``Dry-run'': do not produce any of the output files.

<DT><STRONG><A NAME="item__p">-p pubid</A></STRONG><DD>
<P>
Sets the document type to be <CODE>PUBLIC</CODE> with the identifier <EM>pubid</EM>
instead of <CODE>SYSTEM</CODE>, the default. If both <STRONG>-p</STRONG> and <STRONG>-u</STRONG> are specified then both will be permitted.

<DT><STRONG><A NAME="item__r">-r roottags</A></STRONG><DD>
<P>
Restricts the XML processor to validate only documents with one of the root
elements listed in the comma-separated <EM>roottags</EM>.

<DT><STRONG><A NAME="item__S">-S</A></STRONG><DD>
<P>
Generate the scanner <EM>name</EM><EM>.l</EM>. Conflicts with <STRONG>-A</STRONG>; on by default if none of <STRONG>-SHD</STRONG> specified.

<DT><STRONG><A NAME="item__s">-s skel</A></STRONG><DD>
<P>
Use the skeleton scanner <EM>skel</EM> instead of the default.

<DT><STRONG><A NAME="item__u">-u uri</A></STRONG><DD>
<P>
Sets the URI of the DTD, used in the <CODE>DOCTYPE</CODE> header, to the specified <EM>uri</EM>. (The default is the file name of the DTD.)

<DT><STRONG><A NAME="item__v">-v</A></STRONG><DD>
<P>
Be verbose: echo each DTD declaration (after parameter expansion).

<DT><STRONG><A NAME="item__V">-V</A></STRONG><DD>
<P>
Print the version of <EM>flexml</EM> and exit.

</DL>
<P>
<HR>
<p><dt><A NAME="ACTION_FILE_FORMAT">ACTION FILE FORMAT</A><dd>
Action files, passed to the <STRONG>-a</STRONG> option, are XML documents conforming to the DTD <EM>flexml-act.dtd</EM> which is the following:

<P>
<PRE>  &lt;!ELEMENT actions ((top|start|end)*,main?)&gt;
  &lt;!ENTITY % C-code &quot;(#PCDATA)&quot;&gt;
  &lt;!ELEMENT top   %C-code;&gt;
  &lt;!ELEMENT start %C-code;&gt;  &lt;!ATTLIST start tag NMTOKEN #REQUIRED&gt;
  &lt;!ELEMENT end   %C-code;&gt;  &lt;!ATTLIST end   tag NMTOKEN #REQUIRED&gt;
  &lt;!ELEMENT main  %C-code;&gt;
</PRE>
<DL>
<DT><STRONG><A NAME="item_top">top</A></STRONG><DD>
<P>
Use for top-level C code such as global declarations, utility functions,
etc.

<DT><STRONG><A NAME="item_start">start</A></STRONG><DD>
<P>
Attaches the code as an action to the element with the name of the required
``<CODE>tag</CODE>'' attribute. The ``<CODE>%C-code;</CODE>'' component should be C code suitable for inclusion in a C block (i.e.,
within <CODE>{</CODE>...<CODE>}</CODE> so it may contain local variables); furthermore the following extensions
are available:

<DL>
<DT><STRONG><A NAME="item__attribute_">{attribute}</A></STRONG><DD>
<P>
Can be used to access the value of the <EM>attribute</EM> as set with
<EM>attribute</EM><CODE>=</CODE><EM>value</EM> in the start tag. In C, <CODE>{</CODE><EM>attribute</EM><CODE>}</CODE>
will be interpreted depending on the declaration of the attribute. If the
attribute is declared as an enumerated type like

<P>
<PRE>  &lt;!ATTLIST attrib (alt1 | alt2 |...) ...&gt;
</PRE>
<P>
then the C attribute value is of an enumerated type with the elements
written <CODE>{</CODE><EM>attribute</EM><CODE>=</CODE><EM>alt1</EM><CODE>}</CODE>,
<CODE>{</CODE><EM>attribute</EM><CODE>=</CODE><EM>alt2</EM><CODE>}</CODE>, etc.; furthermore an <EM>unset</EM>
attribute has the ``value'' <CODE>{!</CODE><EM>attribute</EM><CODE>}</CODE>. If the attribute is not an enumeration then <CODE>{</CODE><EM>attribute</EM><CODE>}</CODE> is a null-terminated C string (of type <CODE>char*</CODE>) and <CODE>{!</CODE><EM>attribute</EM><CODE>}</CODE> is <CODE>NULL</CODE>.

</DL>
<DT><STRONG><A NAME="item_end">end</A></STRONG><DD>
<P>
Similarly attaches the code as an action to the end tag with the name of
the required ``<CODE>tag</CODE>'' attribute; also here the ``<CODE>%C-code;</CODE>'' component should be C code suitable for inclusion in a C block. In case
the element has ``Mixed'' contents, i.e, was declared to permit
<CODE>#PCDATA</CODE>, then the following variable is available:

<DL>
<DT><STRONG><A NAME="item_pcdata">pcdata</A></STRONG><DD>
<P>
Contains the text (<CODE>#PCDATA</CODE>) of the element as a null-terminated C string (of type <CODE>char*</CODE>). In case the Mixed contents element actually mixed text and child
elements then <A HREF="#item_pcdata">pcdata</A> contains the plain concatenation of the text fragments as one string.

</DL>
<DT><STRONG><A NAME="item_main">main</A></STRONG><DD>
<P>
Finally, an optional ``<A HREF="#item_main">main</A>'' element can contain the C <A HREF="#item_main">main</A>
function of the XML application. Normally the <A HREF="#item_main">main</A> function should include (at least) one call of the XML processor:

<DL>
<DT><STRONG><A NAME="item_yylex">yylex()</A></STRONG><DD>
<P>
Invokes the XML processor produced by <EM>flex</EM>(1) on the XML document found on the standard input (actually the <CODE>yyin</CODE> file handle: see the manual for <EM>flex</EM>(1) for information on how to change this as well as the name <A HREF="#item_yylex">yylex</A>).

</DL>
<P>
If no <A HREF="#item_main">main</A> action is provided then the following is used:

<P>
<PRE>  int main() { exit(yylex()); }
</PRE>
<P>
It is advisable to use XML &lt;<CODE>![CDATA[</CODE> ... <CODE>]]</CODE>&gt; sections for the C code to make sure that all characters are properly
passed to the output file.

</DL>
<P>
Finally note that <EM>Flexml</EM> handles empty elements
&lt;<EM>tag</EM><CODE>/</CODE>&gt; as equivalent to
&lt;<EM>tag</EM>&gt;&lt;<CODE>/</CODE><EM>tag</EM>&gt;.

<P>
<HR>
<p><dt><A NAME="BUGS">BUGS</A><dd>
The present version of <EM>flexml</EM> is to be considered in ``late alpha'' state thus bugs should be expected
(and the author would like to hear about them). Here are some known
restrictions that we hope to overcome in the future:

<UL>
<LI>
<P>
The character set is merely ASCII (actually <EM>flex</EM>(1) handles 8 bit characters but only the ASCII character set is common
with the XML default UTF-8 encoding).

<LI>
<CODE>ID</CODE> type attributes are not validated for uniqueness; <CODE>IDREF</CODE> and
<CODE>IDREFS</CODE> attributes are not validated for existence.
<P>

<LI>
The <CODE>ENTITY</CODE> and <CODE>ENTITIES</CODE> attribute types are not supported.
<P>

<LI>
The various <CODE>xml:</CODE>-attributes are treated like any other attributes; in particular <CODE>xml:spaces</CODE> should be supported.
<P>

<LI>
The DTD parser is presently a perl hack so it may parse some DTDs badly; in
particular the expansion of parameter entities may not conform fully to the
XML specification.
<P>

<LI>
A child should be able to ``return'' a value for the parent (also called a <EM>synthesised attribute</EM>). Similarly an element in Mixed contents should be able to inject text
into the <A HREF="#item_pcdata">pcdata</A> of the parent.
</UL>
<P>
<p><dt><A NAME="FILES">FILES</A></H1>
<DL>
<DT><STRONG><A NAME="item__usr_share_flexml_skel">/usr/share/flexml/skel</A></STRONG><DD>
<P>
The skeleton scanner with the generic parts of XML scanning.

<DT><STRONG><A NAME="item__usr_share_doc_flexml_">/usr/share/doc/flexml/</A></STRONG><DD>
<P>
License, further documentation, and examples.

</DL>

<p><dt><A NAME="SEE_ALSO">SEE ALSO</A><dd>
<EM>flex</EM>(1), Extensible Markup Language (XML) 1.0 (W3C Recommendation
REC-xml-1998-0210).

<p><dt><A NAME="AUTHOR">AUTHOR</A><dd>
<EM>Flexml</EM> was written by Kristoffer Hgsbro Rose,
&lt;<CODE>krisrose@@debian.org</CODE>&gt;.

<p><dt><A NAME="COPYRIGHT">COPYRIGHT</A><dd>
The program is Copyright (c) 1999 Kristoffer Rose (all rights reserved) and
distributed under the GNU General Public License (GPL, also known as
``copyleft'', which clarifies that the author provides absolutely no
warranty for <EM>flexml</EM> and ensures that <EM>flexml</EM> is and will remain available for all uses, even comercial).

<p><dt><A NAME="ACKNOWLEDGEMENT">ACKNOWLEDGEMENT</A><dd>
I am grateful to NTSys (France) for supporting the development of
<EM>flexml</EM>. Finally extend my severe thanks to Jef Poskanzer, Vern Paxson, and the
rest of the <EM>flex</EM> maintainers and GNU developers for a great tool.

</DL>

d440 4
d445 8
a452 16


    <h4> Vitae </h4>

    Kristoffer Rose teaches computing science at the Ecole Normale
    Suprieure elite university in Lyon except when he is busy with
    hacking code within the Debian GNU/Linux developer group or
    document processing macros within the TeX user's group.  He has
    been working in industry and academia for the last fifteen years
    in the areas of text processing and programming language design;
    the best known example of his synthesising these two areas is
    found in the <a
    href="http://www.ens-lyon.fr/~krisrose/Xy-pic.html">Xy-pic</a> diagram
    drawing system.  Recently he has been helping <a
    href="http://www.ntsys.fr">NTSys</a> basing their system for
    `-payment transactions' on XML.
@


1.8
log
@Manual updated...
@
text
@d5 1
a5 1
    <!--$Id: paper.html,v 1.7 1999/11/29 16:09:02 krisrose Exp krisrose $-->
d34 2
a35 1
      Generating Fast Validating XML Processors
a382 1

d384 1
a384 4
[<STRONG>-ASHDdLX</STRONG>]
[<STRONG>-s</STRONG><EM>skel</EM>]
[<STRONG>-u</STRONG><EM>uri</EM>]
[<STRONG>-a</STRONG><EM>actions</EM>]
d387 2
d390 13
d404 10
a413 15
<EM>Flexml</EM> reads <EM>name</EM><EM>.dtd</EM> which must be a DTD
(Document Type Definition) describing the format of XML (Extensible
Markup Language) documents. It produces a validating XML processor for
the DTD in the form of a <EM>flex</EM>(1) scanner
<EM>name</EM><EM>.l</EM> with a corresponding C header file
<EM>name</EM><EM>.h</EM>. (Not all XML DTDs are supported: see <A
HREF="#BUGS">BUGS</A> for a description of what is not (yet)
implemented.)

<P>
Optionally it takes an <EM>actions</EM> file with per-element actions
and produces a C file with element functions for an XML application
called from the XML processor (it can also fold the XML application
into the XML processor to make stand-alone XML applications but this
prevents sharing of the processor between applications).
d416 3
a418 1
The generated processor and applications are designed for speed.
d420 2
d423 34
d458 13
a470 58
<EM>Flexml</EM> takes the following options; note that if none of
<STRONG>-SHDA</STRONG> options have been specified the default is
<STRONG>-SH</STRONG> without and <STRONG>-SHD</STRONG> with the
<STRONG>-a</STRONG> option.

<DL COMPACT>

<P><DT><STRONG><A NAME="item__A">-A</A></STRONG>
<DD>Generate a <EM>stand-alone</EM> scanner application. If combined
with <STRONG>-a</STRONG><EM>actions</EM> then the application will be named
as <EM>actions</EM> with the extension replaced by <EM>.l</EM>,
otherwise it will be in <EM>name</EM><EM>.l</EM>.  <STRONG>-A</STRONG>
conflicts with <STRONG>-S</STRONG>, <STRONG>-H</STRONG>, and
<STRONG>-D</STRONG>.

<P><DT><STRONG><A NAME="item__aactions">-a</STRONG> <EM>actions</EM></A>
<DD>Uses the <EM>actions</EM> file to produce an XML application in
the file with the same name as <EM>actions</EM> after replacing the
extension with <EM>.c</EM>. (If combined with <STRONG>-A</STRONG> then
instead the stand-alone application will include the action functions.)

<P><DT><STRONG><A NAME="item__D">-D</A></STRONG>
<DD>Generate the dummy application <EM>name</EM><EM>-dummy.c</EM>. If
combined with <STRONG>-a</STRONG><EM>actions</EM> then the application
will include the specified actions and be named as <EM>actions</EM>
with the extension replaced with <EM>.c</EM>.

<P><DT><STRONG><A NAME="item__d">-d</A></STRONG>
<DD>Turns on debug mode in the flex scanner and also prints out the
details of the DTD analysis performed by <EM>flexml</EM>.

<P><DT><STRONG><A NAME="item__H">-H</A></STRONG>
<DD>Generate the header file <EM>name</EM><EM>.h</EM>.

<P><DT><STRONG><A NAME="item__L">-L</A></STRONG>
<DD>Makes the XML processor count the lines in the input and keep it
available to XML application actions as <CODE>yylineno</CODE>. (This
is not the default as the performance overhead is significant.)

<P><DT><STRONG><A NAME="item__S">-S</A></STRONG>
<DD>Generate the scanner <EM>name</EM><EM>.l</EM>.

<P><DT><STRONG><A NAME="item__sskel">-s</STRONG> <EM>skel</EM></A>
<DD>Use the skeleton scanner <EM>skel</EM> instead of the default.

<P><DT><STRONG><A NAME="item__uuri">-u</STRONG> <EM>uri</EM></A>
<DD>Sets the URI of the DTD, used in the <CODE>DOCTYPE</CODE> header,
to the specified <EM>uri</EM>. (The default is the file name of the
DTD.)

<P><DT><STRONG><A NAME="item__X">-X</STRONG></A>
<DD>Omits all failure rules (so the <em>flex</em> ``default rule'' is
applied whenever a document is invalid).  This is useful when combined
with the <strong>-s</strong> option to <em>flex</em> because it means
that the generated scanner will be completely without ``backup''
states (and thus run in time linear with the document size for valid
documents) but the disadvantage is that it will exit with an
uninformative ``scanner jammed'' error for invalid documents.
d472 3
a474 1
</DL>
d476 3
a478 1
<p><dt><A NAME="ACTION_FILES">ACTION FILES</A><dd>
d480 3
a482 30
Action files, passed to the <STRONG>-a</STRONG> option, are XML
documents conforming to the DTD <EM>flexml-act.dtd</EM> which is the
following:

<code><pre>&lt;!ELEMENT actions ((top|start|end)*,main)&gt;
&lt;!ENTITY % C-code &quot;(#PCDATA)&quot;&gt;
&lt;!ELEMENT top   %C-code;&gt;
&lt;!ELEMENT start %C-code;&gt;  &lt;!ATTLIST start tag NMTOKEN #REQUIRED&gt;
&lt;!ELEMENT end   %C-code;&gt;  &lt;!ATTLIST end   tag NMTOKEN #REQUIRED&gt;
&lt;!ELEMENT main  %C-code;&gt;
</pre></code>

The contents of ``<CODE>top</CODE>'' elements should be used for
top-level C code such as global declarations, utility functions, etc.

<P>
A ``<CODE>start</CODE>'' element attaches the code as an action to the
element with the name of the requred ``<CODE>tag</CODE>''
attribute. The ``<CODE>%C-code;</CODE>'' component should be C code
suitable for inclusion in a C block (i.e., within
<CODE>{...}</CODE> so it may contain local variables);
furthermore the following extensions are available:

<DL COMPACT>
<P><DT><CODE><A NAME="item__attribute_">{<EM>attribute</EM>}</A></CODE>
<DD>Can be used to access the value of the <EM>attribute</EM> as set
with <CODE><EM>attribute</EM>=<EM>value</EM></CODE> in the start
tag. In C, <CODE>{<EM>attribute</EM>}</CODE> appears as a
null-terminated C string (of type <CODE>char*</CODE>) except if the
attribute is declared as an enumerated type like
d484 3
a486 2
<code><pre>&lt;!ATTLIST <EM>attribute</EM> (<EM>alt1</EM> | <EM>alt2</EM> |...)*&gt;
</pre></code>
d488 3
a490 5
in which case an the attribute is of an enumerated type with the
elements written <CODE>{<EM>attribute</EM>=<EM>alt1</EM>}</CODE>,
<CODE>{<EM>attribute</EM>=<EM>alt2</EM>}</CODE>, etc.; furthermore an
<EM>unset</EM> attribute has the ``value''
<CODE>{!<EM>attribute</EM>}</CODE>.
d494 3
a496 14
An ``<CODE>end</CODE>'' element similarly attaches the code as an
action to the end tag names as the required ``<CODE>tag</CODE>''
attribute. The ``<CODE>%C-code;</CODE>'' component should be C code
suitable for inclusion in a C block (i.e., within
<CODE>{...}</CODE>). In case the element has ``Mixed'' contents then
the following variable is available:

<DL COMPACT>
<P><DT><CODE><A NAME="item_pcdata">pcdata</A></CODE>
<DD>Contains the text (<CODE>#PCDATA</CODE>) of the element as a
null-terminated C string (of type <CODE>char*</CODE>). In case the
Mixed contents element actually mixed text and child elements then <A
HREF="#item_pcdata">pcdata</A> contains the plain concatenation of the
text fragments as one string.
a497 1
</DL>
d499 12
a510 11
Finally, a ``<CODE>main</CODE>'' element should contain the entire C
<CODE>main</CODE> function of the XML application. Normally the
<CODE>main</CODE> function should include (at least) one call of the
XML processor:

<DL COMPACT>
<P><DT><CODE><A NAME="item_yylex">yylex()</A></CODE>
<DD>Invokes the XML processor produced by <EM>flex</EM>(1) on the XML
document found on the standard input (actually the <CODE>yyin</CODE>
file handle: see the manual for <EM>flex</EM>(1) for information on
how to change this).
d512 1
a512 1
</DL>
d514 4
a517 1
If no <CODE>main</CODE> action is provided then the following default is provided:
d519 7
a525 2
<code><pre>int main() { exit(yylex()); }
</pre></code>
d527 8
a534 3
It is advisable to use XML &lt;<CODE>![CDATA[...]]</CODE>&gt; sections
for the C code to make sure that all characters are properly passed to
the output file.
d536 2
d539 4
a542 3
Note: <EM>Flexml</EM> handles empty elements
<CODE>&lt;<EM>tag</EM>/&gt;</CODE> as equivalent to
<CODE>&lt;<EM>tag</EM>&gt;&lt;/<EM>tag</EM>&gt;</CODE>.
d544 2
d547 2
d550 5
a554 1
<p><dt><A NAME="BUGS">BUGS</A><dd>
d556 4
a559 2
<EM>Flexml</EM> is restricted (by design) to validate XML documents
with a document type declaration of the simple form
d561 3
a563 2
<code><pre>&lt;!DOCTYPE root SYSTEM &quot;uri&quot;&gt;
</pre></code>
d565 6
a570 2
because these can be efficiently parsed. However, the present prototype version
has more serious restrictions that we will eliminate in the future:
d572 5
a576 6
<P><UL>
<LI>
Element-content is restricted to declarations of the form
<code>&lt;!ELEMENT <em>tag</em> (<em>child1</em> | <em>child2</em>
|...)*&gt;</code> (essentially as Mixed contents without
<CODE>#PCDATA</CODE>). This is being fixed.
d578 6
a583 4
<LI>
The character set is merely ASCII (actually <EM>flex</EM>(1) handles 8
bit characters but this only has the ASCII character set in common
with the UTF-8 encoding required by XML).
d585 1
d587 3
a589 2
Text is read into a static buffer limiting the maxmial size of the
<code>pcdata</code> string.
d592 3
a594 2
A child should be able to insert a ``cookie'' (also called a
<EM>synthesised attribute</EM>) in the data stream of the parent.
d597 2
a598 1
<CODE>ID</CODE>/<CODE>IDREF</CODE> consistency is not validated.
d601 2
a602 1
The <CODE>ENTITY</CODE> attribute type is not supported.
d605 4
a608 3
Only internal (general and parameter) entities are handled.
<EM>Flexml</EM> currently rejects DTDs using or declaring external
entities, notations, etc.
d611 9
a619 2
The various <CODE>xml:</CODE>-attributes are not handled specially (in
particular <CODE>xml:spaces</CODE> would be useful).
d621 3
a623 1
</UL><P>
d625 1
a625 6
There are further restrictions on the form of DTDs because the present
DTD parser does not conform to the XML specification, however,
<EM>flexml</EM> will complain rather than produce incorrect XML
processors.

<p><dt><A NAME="FILES">FILES</A><dd>
d627 18
a644 3
<DL COMPACT>
<P><DT><CODE><A NAME="item__usr_share_flexml_skel">/usr/share/flexml/skel</A></CODE>
<DD>The skeleton scanner with the generic parts of XML scanning.
a645 4
<P><DT><CODE><A NAME="item__usr_share_doc_flexml_">/usr/share/doc/flexml/</A></CODE>
<DD>License, further documentation, and examples.

</DL>
@


1.7
log
@Full DTD parsing in progress...currently not working.
@
text
@d5 1
a5 1
    <!--$Id: paper.html,v 1.6 1999/11/25 18:37:39 krisrose Exp krisrose $-->
d384 2
a385 1
[<STRONG>-ASHDdL</STRONG>]
a386 1
[<STRONG>-s</STRONG><EM>skel</EM>]
d413 4
a416 1
<EM>Flexml</EM> takes the following options:
d422 1
a422 1
with <STRONG>-a</STRONG><EM>actions</EM> the aplication will be named
d431 2
a432 2
extension with <EM>.c</EM>. If combined with <STRONG>-A</STRONG> then
instead the stand-alone application will include the action functions.
d441 1
a441 1
<DD>Turns on debug mode in the flex scanner and also prints out a the
@


1.6
log
@Up to date now, only needs add technical issues section :)
@
text
@d5 1
a5 1
    <!--$Id: paper.html,v 1.5 1999/11/25 03:01:47 krisrose Exp krisrose $-->
d60 1
a60 1
    Validating XML, DTD, lexical analaysis, finite automata.
d138 1
a138 1
      contents of the actions file.
d185 1
a185 1
      The idea as that the enumeration attribute <code>type</code> is
d191 5
a195 5
      (understanding the <code>{</code>...<code>}</code> units as C
      identifiers), hence the possibility of using the fast C
      <code>switch</code> statement to pick the right choice directly.
      Note that the first choice, <code>{!type}</code>, corresponds to
      not setting the attribute; in this example the attribute has a
d231 1
a231 1
<blockquote><code><pre>    &lt;/actions&gt;
d262 96
a357 1
    the element actions from an actions file.
a358 1
    <strong>TO BE FINISHED.</strong>
d365 2
a366 2
    supporting the development of <EM>FleXML</EM>. Finally extend my
    sincere thanks to Jef Poskanzer, Vern Paxson, and the rest of the
d417 11
a427 10
<P><DT><STRONG><A NAME="item__A">-A</A></STRONG><DD>
Generate a <EM>stand-alone</EM> scanner application. If combined with
<STRONG>-a</STRONG> the aplication will be names as <EM>actions</EM>
with the extension replaced with <EM>.l</EM>, otherwise it will be in
<EM>name</EM><EM>.l</EM>.  <STRONG>-A</STRONG> conflicts with
<STRONG>-S</STRONG>, <STRONG>-H</STRONG>, and <STRONG>-D</STRONG>.

<P><DT><STRONG><A NAME="item__aactions">-a</STRONG> <EM>actions</EM></A><DD>
Uses the <EM>actions</EM> file to produce an XML application in the
file with the same name as <EM>actions</EM> after replacing the
d431 2
a432 2
<P><DT><STRONG><A NAME="item__D">-D</A></STRONG><DD>
Generate the dummy application <EM>name</EM><EM>-dummy.c</EM>. If
d437 2
a438 2
<P><DT><STRONG><A NAME="item__d">-d</A></STRONG><DD>
Turns on debug mode in the flex scanner and also prints out a the
d441 2
a442 2
<P><DT><STRONG><A NAME="item__H">-H</A></STRONG><DD>
Generate the header file <EM>name</EM><EM>.h</EM>.
d444 2
a445 2
<P><DT><STRONG><A NAME="item__L">-L</A></STRONG><DD>
Makes the XML processor count the lines in the input and keep it
d449 2
a450 2
<P><DT><STRONG><A NAME="item__S">-S</A></STRONG><DD>
Generate the scanner <EM>name</EM><EM>.l</EM>.
d452 2
a453 2
<P><DT><STRONG><A NAME="item__sskel">-s</STRONG> <EM>skel</EM></A><DD>
Use the skeleton scanner <EM>skel</EM> instead of the default.
d455 13
a467 3
<P><DT><STRONG><A NAME="item__uuri">-u</STRONG> <EM>uri</EM></A><DD>
Sets the URI of the DTD, used in the <CODE>DOCTYPE</CODE> header, to
the specified <EM>uri</EM>. (The default is the file name of the DTD.)
d493 1
a493 1
<CODE>{</CODE>...<CODE>}</CODE> so it may contain local variables);
d497 6
a502 4
<P><DT><STRONG><A NAME="item__attribute_">{attribute}</A></STRONG><DD>
Can be used to access the value of the <EM>attribute</EM> as set with
<EM>attribute</EM><CODE>=</CODE><EM>value</EM> in the start tag. In C, <CODE>{</CODE><EM>attribute</EM><CODE>}</CODE>
appears as a null-terminated C string (of type <CODE>char*</CODE>) except if the attribute is declared as an enumerated type like
d504 1
a504 1
<code><pre>&lt;!ATTLIST attrib (alt1 | alt2 |...)*&gt;
d508 4
a511 5
elements written
<CODE>{</CODE><EM>attribute</EM><CODE>=</CODE><EM>alt1</EM><CODE>}</CODE>,
<CODE>{</CODE><EM>attribute</EM><CODE>=</CODE><EM>alt2</EM><CODE>}</CODE>,
etc.; furthermore an <EM>unset</EM> attribute has the ``value''
<CODE>{!</CODE><EM>attribute</EM><CODE>}</CODE>.
d519 2
a520 2
<CODE>{</CODE>...<CODE>}</CODE>). In case the element has ``Mixed''
contents then the following variable is available:
d523 2
a524 2
<P><DT><STRONG><A NAME="item_pcdata">pcdata</A></STRONG><DD>
Contains the text (<CODE>#PCDATA</CODE>) of the element as a
d538 2
a539 2
<P><DT><STRONG><A NAME="item_yylex">yylex()</A></STRONG><DD>
Invokes the XML processor produced by <EM>flex</EM>(1) on the XML
d551 3
a553 3
It is advisable to use XML &lt;<CODE>![CDATA[</CODE>
... <CODE>]]</CODE>&gt; sections for the C code to make sure that all
characters are properly passed to the output file.
d556 3
a558 1
Note: <EM>Flexml</EM> handles empty elements &lt;<EM>tag</EM><CODE>/</CODE>&gt; as equivalent to &lt;<EM>tag</EM>&gt;&lt;<CODE>/</CODE><EM>tag</EM>&gt;.
d570 2
a571 2
because these can be efficiently parsed. However, the present version
has more serious restrictions that we hope to overcome in the future:
d575 6
d586 2
a587 4
Element-content is restricted to declarations of the form
<code>&lt;!ELEMENT tag (child1 | child2 | ... )*&gt;</code>
(essentially as Mixed contents without <CODE>#PCDATA</CODE>). This is
being fixed.
d618 2
a619 2
<P><DT><STRONG><A NAME="item__usr_share_flexml_skel">/usr/share/flexml/skel</A></STRONG><DD>
The skeleton scanner with the generic parts of XML scanning.
d621 2
a622 2
<P><DT><STRONG><A NAME="item__usr_share_doc_flexml_">/usr/share/doc/flexml/</A></STRONG><DD>
License, further documentation, and examples.
d664 3
a666 3
    the best known example of his synthesing these two areas is found
    in the <a
    href="http://www.ens-lyon.fr/~krisrose/Xy-pic">Xy-pic</a> diagram
@


1.5
log
@Almost ready...
@
text
@d5 1
a5 1
    <!--$Id: paper.html,v 1.4 1999/11/23 17:28:07 krisrose Exp krisrose $-->
a23 1
 DD { MARGIN-TOP: 5em; margin-left: 5em }
d34 1
a34 2
      Generating Fast Validating XML Processors<br>
      Extended Abstract
d38 4
d48 9
a56 10
    <p>
      We present <em>FleXML</em>, a program that generates fast
      validating XML processors from `self-contained' XML DTDs.  It
      uses the <em>flex</em> (lexical analyser generator) program to
      translate the DTD into a <em>finite automaton</em> enriched with
      a stack with the `element context'.  This means that the XML
      processor will act directly on each character received.  The
      program is freely redistributable and modifyable (under GNU
      `copyleft').
    </p>
d59 3
a61 3
    <p>
      Validating XML, DTD, lexical analaysis, finite automata.
    </p>
d65 5
a69 6
    <p>
      The `X' of XML stands for <em>Extensible</em> [<cite><a
      href="#XML">XML</a></cite>].  This signifies that each and every
      XML document specifies in its header the details of the format
      that it will use and <em>may</em> change its format a bit
      relative to the used base format.
d107 3
a109 3
      elaborated <a href="#ex">example</a> and discuss some of the <a
      href="#tech">technical issues</a>.
    </p>
d111 1
a111 1
    <h4><a name="ex">Walk-through</a></h4>
a112 1
    <p>
d116 4
a119 4
<code><pre>  &lt;!DOCTYPE joke SYSTEM &quot;my.dtd&quot;&gt;
  &lt;joke&gt;&lt;line&gt;My appartment is so small&lt;/line&gt; &lt;suspense/&gt;
   &lt;line type='punch-line'&gt;the mice are round-shouldered&lt;/line&gt;&lt;/joke&gt;
</pre></code>
d125 6
a130 6
<code><pre>  &lt;!-- my.dtd: Small DTD for jokes (just for fun). --&gt;
  &lt;!ELEMENT joke (line|pause)*&gt;
  &lt;!ELEMENT line (#PCDATA)&gt;
   &lt;!ATTLIST line type (normal|question|punch-line) 'normal'&gt;
  &lt;!ELEMENT suspense EMPTY&gt;
</pre></code>
d135 6
a140 2
      Flexml can do this in the following easy steps:
    </p>
d142 3
d146 8
a153 1
    <h5> Generate XML processor </h5>
d155 6
a160 6
      We run FleXML on the DTD to produce a fast validating XML
      processor for the DTD together with a `do-nothing' dummy XML
      application in C.  This can be immediately run (after processing
      with the flex scanner generator and compilation with a C or C++
      compiler).
    </p>
d162 4
d167 3
a169 1
    <h5> Write element actions </h5>
d171 2
a172 3
      We add an <em>actions</em> specification with actions to be
      performed for each element.  Here is a sample such action file
      for <code>my.dtd</code>:
d174 9
a182 1
<code><pre>  &lt;!DOCTYPE actions SYSTEM &quot;flexml-act.dtd&quot;&gt;
d184 3
a186 1
  &lt;actions&gt;
d188 2
a189 3
  &lt;top&gt;&lt;![CDATA[
  #include &lt;unistd.h&gt;
  #include &lt;stdio.h&gt;
d191 16
a206 2
  char* terminator = &quot;.&quot;;
  ]]&gt;&lt;/top&gt;
d208 4
a211 8
  &lt;start tag='line'&gt;&lt;![CDATA[
    switch ( {type} ) {
      case {!type}: terminator = &quot;.&quot;; break;
      case {type=normal}: terminator = &quot;.&quot;; break;
      case {type=question}: terminator = &quot;??&quot;; break;
      case {type=punch-line}: terminator = &quot;!!&quot;; break;
    }
  ]]&gt;&lt;/start&gt;
d213 4
a216 3
  &lt;end tag='line'&gt;&lt;![CDATA[
    printf(&quot;%s%s\n&quot;, pcdata, terminator);
  ]]&gt;&lt;/end&gt;
d218 15
a232 3
  &lt;start tag='suspense'&gt;&lt;![CDATA[ sleep(2); ]]&gt;&lt;/start&gt;
  &lt;/actions&gt;
</pre></code>
a233 29
      It is itself, as you can see, an XML document.  The
      <code>flexml-act.dtd</code> DTD is part of the FleXML system and
      is reproduced in the <a href="#ACTION_FILES">manual page in the
      appendix</a> along with the conventions used for accessing the
      parsed attribute and text values.  (Notice that we use
      <code>CDATA</code> sections to ensure that the C code can be
      entered directly.)
    <p>
      The addition to the C notation is the use of special
      <code>{</code>...<code>}</code> annotations.  In this example
      you can see that the action for the <code>&lt;line&gt;</code>
      start tag will investigate the <code>type</code> attribute and
      set the <code>terminator</code> variable according to which
      attribute assignment was in effect given in the tag.  This
      variable is then stored globally so it is available when we
      reach the end tag where it is printed after the text (denoted
      <code>pcdata</code>).  We even cater for the case where the
      attribute was not assigned to: this is the <code>{!type}</code>
      choice.
    <p>
      Finally we implement the <code>&lt;suspense/&gt</code> empty tag
      by pausing for two seconds.
    </p>

    <h5> Generate XML application </h5>
    <p>
      Run FleXML on the action file to produce the XML application
      which can be run immediately after compilation with a C compiler 
      and linkage with the XML processor.
d235 7
a241 1
      When run on the above example the produced program will print
d243 20
a262 3
<code><pre>  My appartment is so small.
  the mice are round-shouldered!!
</pre></code>
d264 1
a264 2
      as expected, pausing duly for two seconds between the lines.
    </p>
a265 4
    <h4> Technical Issues </h4>
    <p>
      TBD.
    </p>
d269 6
a274 6
    <p>
      I am grateful to <a href="http://www.ntsys.fr">NTSys</a> for
      supporting the development of <EM>flexml</EM>. Finally extend my
      sincere thanks to Jef Poskanzer, Vern Paxson, and the rest of the
      <EM>flex</EM> maintainers and GNU developers for a great tool.
    </p>
a276 4
    <p>
      This appendix contains the unix manual page for FleXML (adapted
      to the form of this paper).
    </p>
d278 11
a288 2
<h5><A NAME="SYNOPSIS">SYNOPSIS</A></h5>
<P>
d290 4
a293 1
[<STRONG>-dSHD</STRONG>] [<STRONG>-u</STRONG><EM>uri</EM>] [<STRONG>-a</STRONG><EM>actions</EM>] [<STRONG>-s</STRONG><EM>skel</EM>]
d296 2
a297 2
<h5><A NAME="DESCRIPTION">DESCRIPTION</A></h5>
<P>
d300 3
a302 3
Markup Language) documents. From this <EM>flexml</EM> produces a
validating XML processor for the DTD in the form of a <EM>flex</EM>(1)
scanner <EM>name</EM><EM>.l</EM> with a corresponding C header file
d310 3
a312 1
called from the XML processor.
a313 1
<h5><A NAME="OPTIONS">OPTIONS</A></h5>
d315 4
d321 8
a328 6
<DL>
<DT><STRONG><A NAME="item__S">-S -H -D</A></STRONG><DD>
These options make it explicit that only the scanner, header, and/or
(dummy) application files should be generated. If none of them are
given the default is <STRONG>-SH</STRONG> (except <STRONG>-a</STRONG>
below implies <STRONG>-A</STRONG>).
d330 1
a330 1
<DT><A NAME="item__aactions"><STRONG>-a</STRONG> <EM>actions</EM></A><DD>
d332 9
a340 2
file with the same name as <EM>actions</EM> after stripping the
extension.
d342 19
a360 1
<DT><A NAME="item__uuri"><STRONG>-u</STRONG> <EM>uri</EM></A><DD>
d364 1
a364 2
<DT><A NAME="item__sskel"><STRONG>-s</STRONG> <EM>skel</EM></A><DD>
Use the skeleton scanner <EM>skel</EM> instead of the default.
d366 1
a366 4
<DT><A NAME="item__d"><STRONG>-d</STRONG></A><DD>
Turns on debug mode in the flex scanner and also prints out a the
details of the DTD analysis performed by <EM>flexml</EM>.
</DL>
a367 2
<h5><A NAME="ACTION_FILES">ACTION FILES</A></h5>
<P>
d372 8
a379 7
<PRE>  &lt;!ELEMENT actions ((top|start|end)*,main)&gt;
  &lt;!ENTITY % C-code &quot;(#PCDATA)&quot;&gt;
  &lt;!ELEMENT top   %C-code;&gt;
  &lt;!ELEMENT start %C-code;&gt;  &lt;!ATTLIST start tag NMTOKEN #REQUIRED&gt;
  &lt;!ELEMENT end   %C-code;&gt;  &lt;!ATTLIST end   tag NMTOKEN #REQUIRED&gt;
</PRE>
<P>
d391 2
a392 2
<DL>
<DT><A NAME="item__attribute_"><STRONG>{</STRONG><EM>attribute</EM><STRONG>}</STRONG></A><DD>
d394 2
a395 4
<EM>attribute</EM><CODE>=</CODE><EM>value</EM> in the start tag. In C,
<CODE>{</CODE><EM>attribute</EM><CODE>}</CODE> appears as a
null-terminated C string (of type <CODE>char*</CODE>) except if the
attribute is declared as an enumerated type like
d397 2
a398 2
<PRE>  &lt;!ATTLIST tag attrib (alt1 | alt2 |...)*&gt;
</PRE>
d401 4
a404 3
elements written <CODE>{attrib=alt1}</CODE>,
<CODE>{attrib=alt2}</CODE>, etc.; furthermore an <EM>unset</EM>
attribute has the `value'
d416 2
a417 2
<DL>
<DT><A NAME="item_pcdata"><CODE>pcdata</CODE></A><DD>
d423 1
a429 1
</P>
d431 2
a432 2
<DL>
<DT><STRONG><A NAME="item_yylex">yylex()</A></STRONG><DD>
d437 1
d439 2
d442 2
a443 3
<P>
If no <CODE>main</CODE> action is provided then the following default
is provided:
d445 3
a447 2
<PRE>  int main() { exit(yylex()); }
</PRE>
a448 2
It is advisable to use XML &lt;<CODE>![CDATA[</CODE> ... <CODE>]]</CODE>&gt; sections for the C code to make sure that all characters are properly
passed to the output file.
a451 1
<h5><A NAME="BUGS">BUGS</A></h5>
d453 3
d459 2
a460 2
<PRE>  &lt;!DOCTYPE root SYSTEM &quot;uri&quot;&gt;
</PRE>
d462 2
a463 2
because these can be efficiently parsed. However, the present version has
more serious restrictions that we hope to overcome in the future:
d465 1
a465 1
<UL>
d467 3
a469 2
The character set is merely ASCII (actually <EM>flex</EM>(1) handles 8 bit characters but this only has the ASCII character set in
common with the UTF-8 encoding required by XML).
d473 3
a475 5

<PRE>  &lt;!ELEMENT tag (child1 | child2 | ... )*&gt;
</PRE>

(essentially as Mixed contents without <CODE>#PCDATA</CODE>). This is being fixed.
d485 1
a485 1
<CODE>ENTITY</CODE> attributes are not recognised.
d491 7
a497 2
</UL>
<P>
d503 4
a506 3
<h5><A NAME="FILES">FILES</A></h5>
<DL>
<DT><TT><A NAME="item__usr_share_flexml_skel">/usr/share/flexml/skel</A></TT><DD>
d509 1
a509 1
<DT><TT><A NAME="item__usr_share_doc_flexml_">/usr/share/doc/flexml/</A></TT><DD>
d511 2
d518 8
a525 1
    <dl>
d529 6
a534 1
	lexical analyzer generator</em>, manual page.
d539 3
a541 1
	Recommendation REC-xml-1998-0210).
a542 4
      <dt><a name="ASU"><cite>ASU</cite></a>
      <dd>
	Alfred Aho, Ravi Sethi and Jeffrey Ullman: <em>Compilers:
	Principles, Techniques and Tools</em>, Addison-Wesley (1986).
d544 1
a544 1
    </ol>
d546 12
a557 3
    <h4>
      Vitae
    </h4>
a558 6
    <p>
      Kristoffer Rose teaches computing science at the Ecole Normale
      Suprieure elite university in Lyon except when he is busy with
      hacking unix within the Debian GNU/Linux developer group or
      document processing code with the TeX user's group.
    </p>
@


1.4
log
@Works but manual/paper still in flux...
@
text
@d5 1
a5 1
    <!--$Id$-->
d42 1
a42 1
      <a href="mailto:Kristoffer.Rose@@ENS-Lyon.fr">Kristoffer.Rose@@ENS-Lyon.fr</a>
d47 8
a54 7
      We present <code>FleXML</code>, a program that generates fast
      validating XML processors from XML DTDs for documents defined by
      a single, external DTD.  It works by translating a DTD into a
      <em>finite automaton</em> with a stack of active elements using
      the <code>flex</code> program meaning that the XML processor
      will act directly on each character received.  The program is
      freely redistributable and modifyable (under GNU `copyleft').
d62 1
a62 1
    <h4> Introduction </h4>
d65 44
a108 70
      The `X' of XML stands for <em>Extensible</em>.  This signifies
      that each and every XML document specifies in its header the
      details of the format that it will use.  This has influenced the
      tools available to write validating XML processors: they use a
      <em>call-back</em> model where the XML processor passes strings
      with the tags and attributes names and values to the
      application.  These call-backs must be dynamic because one
      cannot know whether a document will start by extending its own
      notation with more tags and attributes.
    <p>
      However, for many applications a <em>fixed</em> format suffices
      in the sense that a single DTD is used <em>without
      extensions</em> for a very large number of documents.  In that
      case we can do much better than usual because the possible tags
      and attributes are static.  We can, in fact, use lexical scanner
      generators to automatically create XML processors that read the
      document character by character and immediately dispatch the
      actions associated with each element.
    <p>
      In order to make this really fast we have decided to use the
      <code>flex</code> scanner generator and specify the `semantic
      actions' directly in the C programming language so that there is
      no parsing overhead during XML processing: instead of comparing
      strings the processor will use table lookup indexed by the
      incoming characters to directly branch to the XML application
      `action' corresponding to the parsed element.  <a
      href="#fig1">Figure 1</a> contains a sample DTD which we will
      use in the following.
    </p>

    <blockquote><code>
      &lt;!--$Id: paper.html,v 1.3 1999/11/23 10:10:36 krisrose Exp krisrose $<br>
      &npsp;DTD for jokes (just for fun). --&gt;<br>
      <br>
      &lt;!ENTITY % bool "yes|no"&gt;<br>
      <br>
      &lt;!ELEMENT collection (joke)*&gt;<br>
      <br>
      &lt;!ELEMENT joke (setup|pause|punch-line|annotation)*&gt;<br>
      &lt;!ATTLIST joke label ID #REQUIRED<br>
		     refs IDREFS<br>
		     offensive (%bool;) 'no'<br>
		     ethnical (%bool;) #FIXED 'no'&gt;<br>
      <br>
      &lt;!ELEMENT setup (#PCDATA|emph)*&gt;<br>
      &lt;!ATTLIST setup type (normal|question) 'normal'&gt;<br>
      <br>
      &lt;!ELEMENT punch-line (#PCDATA|emph)*&gt;<br>
      &lt;!ATTLIST punch-line type ( normal | question ) 'normal'&gt;<br>
      <br>
      &lt;!ELEMENT emph (#PCDATA)&gt;<br>
      <br>
      &lt;!ELEMENT pause EMPTY&gt;<br>
      &lt;!ATTLIST pause seconds CDATA&gt;<br>
      <br>
      &lt;!ELEMENT annotation ANY&gt;<br>
      &lt;!ATTLIST annotation refs IDREFS #IMPLIED&gt;</code>
    </blockquote>
    <h6 class=caption align=center> Sample `joke' DTD.</h6>

    <p>
      The usual approach to writing XML applications is to `register',
      at run-time, call-back procedures for specific elements; for the
      advanced systems this can even be configured in a way that is
      parametrised on the element context.
    <p>
      These call-backs <em>have</em> to be registered at run-time
      because of the dynamic nature of XML: 
      procedures have a completely uniform structure, then, since they
      must function independently of the element type, etc.  
d111 1
d113 3
d117 15
d133 5
d140 9
a148 1
    <h4> What can it do? </h4>
d150 53
d204 22
a225 1
      The basic technique used is to 
a227 1
    <h4> </h4>
d230 6
d238 194
d434 17
a450 2
    <ol>
      <li></li>
d456 7
a462 1
    <p>Kristoffer Rose teaches computing science </p>
@


1.3
log
@Spellling mistakes fixed...
@
text
@d5 1
a72 2
    </p>

a81 2
    </p>

d95 1
a95 1
      &lt;!--$Id: paper.html,v 1.2 1999/11/23 04:03:05 krisrose Exp krisrose $<br>
d125 7
a131 4
      The usual approach to writing XML applications is to `register'
      call-back procedures with specific elements.  Since this is 

These call-back
@


1.2
log
@Works for simple examples
@
text
@d4 1
a4 1
    <title>Fast Validating XML Processors</title>
d34 1
a34 1
      Genertating Fast Validating XML Processors<br>
d98 1
a98 1
      &lt;!--$Id: joke.dtd,v 1.1 1999/11/22 18:41:48 krisrose Exp krisrose $<br>
d127 3
d131 3
a133 2
    <p>
      
@


1.1
log
@Working like mad...
@
text
@d97 29
a125 15
    <center>
<pre>
<!-- $Id: test.dtd,v 1.3 1999/09/10 15:45:05 krisrose Exp $
  --
  -- Test DTD for jokes [sic].
  -->

<!ENTITY % bool "yes|no">

<!ENTITY copyright
  "Copyright  1999 Yours Truly. Use as you Please.">

<!ELEMENT joke (line|annotation|pause)*><!ELEMENT annotation ANY>
<!ATTLIST joke offensive (%bool;) 'no'
               ethnical (%bool;) 'no'>
a126 2
<!ELEMENT line (#PCDATA)>
<!ATTLIST line type (normal|question|punch) 'normal'>
d128 1
a128 2
<!ELEMENT pause EMPTY>
<!ATTLIST pause delay NMTOKEN>
d131 4
a134 1
    <h6 class=caption> Sample `joke' DTD.</h6>
@