| 1 |
<?xml version="1.0" encoding="iso-8859-1"?> |
| 2 |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" |
| 3 |
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> |
| 4 |
<html> |
| 5 |
<head> |
| 6 |
<title>Generating Fast Validating XML Processors</title> |
| 7 |
<!--$Id: paper.html,v 1.13 2006/07/18 18:21:13 mquinson Exp $--> |
| 8 |
<style type="text/css"> |
| 9 |
<!-- |
| 10 |
BODY { BACKGROUND-COLOR: #ffffff; FONT-FAMILY: arial, times new roman, sans-serif; } |
| 11 |
A:link, A:visited, A:active { TEXT-DECORATION: none; FONT-WEIGHT: bold; COLOR: #0000FF} |
| 12 |
|
| 13 |
H1, H2 { TEXT-ALIGN: center; FONT-WEIGHT: bold; } |
| 14 |
H3, H4, H5 { TEXT-ALIGN: left; FONT-WEIGHT: bold; } |
| 15 |
H6 { TEXT-ALIGN: center; FONT-WEIGHT: bold; FONT-SIZE: small; } |
| 16 |
H6.CAPTION { TEXT-ALIGN: center; FONT-WEIGHT: bold; FONT-SIZE: small; FONT-STYLE: italic; } |
| 17 |
|
| 18 |
P { TEXT-INDENT: 1em; } |
| 19 |
P.CODE { TEXT-INDENT: 0; COLOR: #FF0000; } |
| 20 |
|
| 21 |
UL, OL, DL { FONT-SIZE: small; } |
| 22 |
UL { list-style: square; } |
| 23 |
LI { FONT-SIZE: small; FONT-WEIGHT: bold; } |
| 24 |
UL EM, OL EM { FONT-WEIGHT: bold; } |
| 25 |
CODE, CITE { FONT-WEIGHT: bold; } |
| 26 |
|
| 27 |
BLOCKQUOTE { MARGIN-LEFT: 1em; MARGIN-RIGHT: 1em } |
| 28 |
IMG { VERTICAL-ALIGN: top; ALIGN: center; } |
| 29 |
SUP { COLOR: #0000FF; FONT-SIZE: small; } |
| 30 |
--> |
| 31 |
</style> |
| 32 |
</head> |
| 33 |
<body> |
| 34 |
|
| 35 |
<h2> |
| 36 |
Generating Fast Validating XML Processors |
| 37 |
</h2> |
| 38 |
|
| 39 |
<h6> |
| 40 |
(Extended Abstract) |
| 41 |
</h6> |
| 42 |
|
| 43 |
<h6> |
| 44 |
Kristoffer Rose<br/> |
| 45 |
LIP, ENS-Lyon<br/> |
| 46 |
<a href="mailto:[email protected]">[email protected]</a> |
| 47 |
</h6> |
| 48 |
|
| 49 |
<h6> Abstract </h6> |
| 50 |
|
| 51 |
<p>We present <em>FleXML</em>, a program that generates fast |
| 52 |
validating XML processors from `self-contained' XML DTDs. It uses |
| 53 |
the <em>flex</em> (lexical analyser generator) program to |
| 54 |
translate the DTD into a <em>finite automaton</em> enriched with a |
| 55 |
stack with the `element context'. This means that the XML |
| 56 |
processor will act directly on each character received. The |
| 57 |
program is freely redistributable and modifyable (under GNU |
| 58 |
`copyleft').</p> |
| 59 |
|
| 60 |
<h6> Keywords </h6> |
| 61 |
|
| 62 |
<p>Validating XML, DTD, lexical analysis, finite automata.</p> |
| 63 |
|
| 64 |
|
| 65 |
<h4> Overview </h4> |
| 66 |
|
| 67 |
<p>The `X' of XML stands for <em>Extensible</em> [<cite><a |
| 68 |
href="#XML">XML</a></cite>]. This signifies that each and every |
| 69 |
XML document specifies in its header the details of the format |
| 70 |
that it will use and <em>may</em> change its format a bit relative |
| 71 |
to the used base format.</p> |
| 72 |
<p> |
| 73 |
This has influenced the tools available to write validating XML |
| 74 |
processors: they use a <em>call-back</em> model where the XML |
| 75 |
processor passes strings with the tags and attributes names and |
| 76 |
values to the application. These call-backs must be generic |
| 77 |
because one cannot know whether a document will start by |
| 78 |
extending its own notation with more tags and attributes. For |
| 79 |
<em>well-formed</em> but non-validated XML documents this makes |
| 80 |
a lot of sense, of course, but we would in general like to |
| 81 |
exploit the information in the DTD for optimizations.</p> |
| 82 |
<p> |
| 83 |
In particular, for many applications a <em>fixed</em> format |
| 84 |
suffices in the sense that a single DTD is used without |
| 85 |
individual extensions for a large number of documents. In that |
| 86 |
case we can do much better because the possible tags and |
| 87 |
attributes are static.</p> |
| 88 |
<p> |
| 89 |
We have implemented an XML processor <em>generator</em> using |
| 90 |
the <cite><a href="#Flex">Flex</a></cite> scanner generator that |
| 91 |
produces deterministic finite automata [<cite><a |
| 92 |
href="#ASU">ASU</a></cite>]. Which means that there is almost |
| 93 |
no overhead for XML processing: the generated XML processors |
| 94 |
read the XML document character by character and can immediately |
| 95 |
dispatch the actions associated with each element (or reject the |
| 96 |
document as invalid).</p> |
| 97 |
<p> |
| 98 |
Furthermore we have devised a simple extension of the C |
| 99 |
programming language that facilitates the writing of `element |
| 100 |
actions' in C, making it easy to write really fast XML |
| 101 |
applications. In particular we represent XML attribute values |
| 102 |
efficiently in C when this is possible, thus avoiding the |
| 103 |
otherwise ubiquitous conversions between strings and data |
| 104 |
values.</p> |
| 105 |
<p> |
| 106 |
FleXML is available for free |
| 107 |
(from <a href="http://flexml.sourceforge.net">SourceForge</a>). |
| 108 |
In this paper we present FleXML through an |
| 109 |
elaborated <a href="#what">example</a> and discuss some of the |
| 110 |
<a href="#how">technical issues</a>.</p> |
| 111 |
|
| 112 |
|
| 113 |
<h4><a name="what">What can it do?</a></h4> |
| 114 |
|
| 115 |
<p>Assume that we have an XML document <code>my-joke.xml</code> |
| 116 |
containing the classical joke |
| 117 |
|
| 118 |
<blockquote><code><pre><!DOCTYPE joke SYSTEM "my.dtd"> |
| 119 |
<joke><line>My appartment is so small</line> <suspense/> |
| 120 |
<line type='punch-line'>the mice are round-shouldered</line></joke> |
| 121 |
</pre></code></blockquote> |
| 122 |
|
| 123 |
(and many others like it, of course). We wish to create an XML |
| 124 |
processor to validate it with respect to the DTD in the file |
| 125 |
<code>my.dtd</code> containing |
| 126 |
|
| 127 |
<blockquote><code><pre><!-- my.dtd: Small DTD for jokes (just for fun). --> |
| 128 |
<!ELEMENT joke (line,(line|suspense)*)> |
| 129 |
<!ELEMENT line (#PCDATA)> |
| 130 |
<!ATTLIST line type (normal|question|punch-line) 'normal'> |
| 131 |
<!ELEMENT suspense EMPTY> |
| 132 |
</pre></code></blockquote> |
| 133 |
|
| 134 |
and, furthermore, we wish to write an XML application for |
| 135 |
displaying such messages in an amusing way.</p> |
| 136 |
<p> |
| 137 |
With FleXML this can be done by creating an `actions file' |
| 138 |
<code>my-show.act</code> which implements the desired actions |
| 139 |
for each element. The remainder of this section explains the |
| 140 |
contents of such an actions file.</p> |
| 141 |
<p> |
| 142 |
An actions file is itself an XML document which must begin with |
| 143 |
|
| 144 |
<blockquote><code><pre><!DOCTYPE actions SYSTEM "flexml-act.dtd"> |
| 145 |
<actions> |
| 146 |
</pre></code></blockquote> |
| 147 |
|
| 148 |
(the <code>flexml-act.dtd</code> DTD is part of the FleXML |
| 149 |
system and is reproduced in the manual page.</p> |
| 150 |
<p> |
| 151 |
We decide that our application should react to a |
| 152 |
<code>line</code> element by printing the text inside it, and |
| 153 |
that it should differentiate between the three possible `type' |
| 154 |
attribute values by printing corresponding trailing punctuation.</p> |
| 155 |
<p> |
| 156 |
This introduces a slight complication, because the attribute |
| 157 |
values are available when parsing the start tag whereas the |
| 158 |
element text is not available until we parse the end tag (where |
| 159 |
it has been read).</p> |
| 160 |
<p> |
| 161 |
This means that we must declare a top-level variable. |
| 162 |
|
| 163 |
<blockquote><code><pre><top><![CDATA[ |
| 164 |
char* terminator = "."; |
| 165 |
]]></top> |
| 166 |
</pre></code></blockquote> |
| 167 |
|
| 168 |
Notice how we use <code>CDATA</code> sections to make sure that |
| 169 |
all characters (including white-space) are passed unmodified to |
| 170 |
the C compiler.</p> |
| 171 |
<p> |
| 172 |
With this we can write the action to set it when reading the |
| 173 |
<code>line</code> start tag as |
| 174 |
|
| 175 |
<blockquote><code><pre><start tag='line'><![CDATA[ |
| 176 |
switch ( {type} ) { |
| 177 |
case {!type}: terminator = "..."; break; |
| 178 |
case {type=normal}: terminator = "."; break; |
| 179 |
case {type=question}: terminator = "??"; break; |
| 180 |
case {type=punch-line}: terminator = "!!"; break; |
| 181 |
} |
| 182 |
]]></start> |
| 183 |
</pre></code></blockquote></p> |
| 184 |
|
| 185 |
<p> |
| 186 |
The idea is that the enumeration attribute <code>type</code> is |
| 187 |
implemented in C as if it had been declared by |
| 188 |
|
| 189 |
<blockquote><code><pre>enum { {!type}, {type=normal}, {type=question}, {type=punch-line} } {type}; |
| 190 |
</pre></code></blockquote> |
| 191 |
|
| 192 |
(understanding the <code>{...}</code> units as C identifiers), |
| 193 |
hence the possibility of using the fast C <code>switch</code> |
| 194 |
statement to pick the right choice directly. Note that the |
| 195 |
first choice, <code>{!<em>type</em>}</code>, corresponds to not |
| 196 |
setting the attribute; in this example the attribute has a |
| 197 |
default value so this can never happen, however, we include the |
| 198 |
choice anyway to prevent the C compiler from issuing warnings |
| 199 |
about missing choices in <code>switch</code> statements.</p> |
| 200 |
<p> |
| 201 |
With this in place we can write the action for |
| 202 |
<code></line></code>. Since it prints something, however, |
| 203 |
we first need to add the appropriate header inclusion. |
| 204 |
|
| 205 |
<blockquote><code><pre><top><![CDATA[ |
| 206 |
#include <stdio.h> |
| 207 |
]]></top> |
| 208 |
|
| 209 |
<end tag='line'><![CDATA[ |
| 210 |
printf("%s%s\n", pcdata, terminator); |
| 211 |
]]></end> |
| 212 |
</pre></code></blockquote></p> |
| 213 |
|
| 214 |
<p> |
| 215 |
Finally, we will make the application amusing by `displaying' |
| 216 |
the <code><suspense/></code> empty tag as a short delay; |
| 217 |
this also involves a header inclusion. |
| 218 |
|
| 219 |
<blockquote><code><pre><top><![CDATA[ |
| 220 |
#include <unistd.h> |
| 221 |
]]></top> |
| 222 |
|
| 223 |
<start tag='suspense'><![CDATA[ |
| 224 |
sleep(2); |
| 225 |
]]></start> |
| 226 |
</pre></code></blockquote></p> |
| 227 |
|
| 228 |
<p> |
| 229 |
That is all; the only remaining thing is to terminate the action |
| 230 |
file properly. |
| 231 |
|
| 232 |
<blockquote><code><pre></actions> |
| 233 |
</pre></code></blockquote> |
| 234 |
|
| 235 |
<p> |
| 236 |
We can now run FleXML with the DTD and the actions file as input |
| 237 |
and will get an XML application as output that, when run (after |
| 238 |
processing by flex and a C compiler), will indeed print |
| 239 |
|
| 240 |
<blockquote><code><pre>My appartment is so small. |
| 241 |
the mice are round-shouldered!! |
| 242 |
</pre></code></blockquote> |
| 243 |
|
| 244 |
as expected, pausing duly for two seconds between the lines. On |
| 245 |
the authors system the above output was achieved with the |
| 246 |
command sequence |
| 247 |
|
| 248 |
<blockquote><code><pre>flexml -A -a my-show.act my.dtd |
| 249 |
flex -omy-show.c my-show.l |
| 250 |
cc -omy-show my-show.c |
| 251 |
./my-show <./my-joke.xml |
| 252 |
</pre></code></blockquote> |
| 253 |
|
| 254 |
(see the manual page for the exact meaning of the FleXML options). |
| 255 |
|
| 256 |
<p> |
| 257 |
An important aspect of the design of FleXML is that the only |
| 258 |
thing that should matter to the programmer should be the |
| 259 |
complexity of the <em>application</em>, not of the used DTD. As |
| 260 |
an example the following action file prints the |
| 261 |
<code>href</code> attribute of all hyperlinks in an XHTML |
| 262 |
document: |
| 263 |
|
| 264 |
<blockquote><code><pre><!DOCTYPE actions SYSTEM "flexml-act.dtd"> |
| 265 |
<actions> |
| 266 |
|
| 267 |
<top><![CDATA[ |
| 268 |
#include <stdio.h> |
| 269 |
]]></top> |
| 270 |
|
| 271 |
<start tag='a'><![CDATA[ |
| 272 |
if ({href}) printf("%s\n", {href}); |
| 273 |
]]></start> |
| 274 |
|
| 275 |
</actions> |
| 276 |
</pre></code></blockquote> |
| 277 |
|
| 278 |
which was compiled into a running application on the author's |
| 279 |
system with the commands |
| 280 |
|
| 281 |
<blockquote><code><pre>flexml $(FLEXDEBUG) -rhtml -p'-//IETF//DTD XHTML 1.0 Transitional//EN' \ |
| 282 |
'http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd' |
| 283 |
gcc -Wall -ansi -pedantic -O2 -g -c xhtml-href.c -o xhtml-href.o |
| 284 |
flex -Bsv -Ca -oxhtml1-transitional.c xhtml1-transitional.l |
| 285 |
gcc -Wall -ansi -pedantic -O2 -g -c xhtml1-transitional.c -o xhtml1-transitional.o |
| 286 |
gcc -Wall -ansi -pedantic xhtml-href.o xhtml1-transitional.o -o xhtml-href |
| 287 |
</pre></code></blockquote> |
| 288 |
|
| 289 |
generating the XML processor directly from the official DTD on |
| 290 |
the web (which in fact required a patch to flex to enlarge the |
| 291 |
possible table size). |
| 292 |
|
| 293 |
|
| 294 |
<h4><a name="how">How does it work?</a></h4> |
| 295 |
|
| 296 |
<p> |
| 297 |
FleXML is a perl script [<cite><a href="#Perl">Perl</a></cite>] |
| 298 |
which reads and interprets a DTD and subsequently produces an |
| 299 |
<em>XML processor</em> source file for the <em>flex</em> scanner |
| 300 |
and optionally an <em>XML application</em> with the C source of |
| 301 |
the element actions from an actions file. The DTD is used to |
| 302 |
construct the rules used by flex to match the individual XML |
| 303 |
components in such a way that only valid documents match. |
| 304 |
<p> |
| 305 |
For example, the flex code for scanning an attribute declaration |
| 306 |
of the <code>line</code> tag is the following: |
| 307 |
|
| 308 |
<blockquote><code><pre><AL_line>{ |
| 309 |
"type"{Eq}"'normal'" | |
| 310 |
"type"{Eq}"\"normal\"" A_line_type = A_line_type_normal; |
| 311 |
"type"{Eq}"'question'" | |
| 312 |
"type"{Eq}"\"question\"" A_line_type = A_line_type_question; |
| 313 |
"type"{Eq}"'punch-line'" | |
| 314 |
"type"{Eq}"\"punch-line\"" A_line_type = A_line_type_punch_d_line; |
| 315 |
|
| 316 |
">" { |
| 317 |
LEAVE; STag_line(); pcdata = BUFFERSET(pcdata); ENTER(IN_line); |
| 318 |
} |
| 319 |
"/>" { |
| 320 |
LEAVE; STag_line(); pcdata = ""; ETag_line(); |
| 321 |
switch (YY_START) { |
| 322 |
case ROOT_line: SET(EPILOG); break; |
| 323 |
case S_joke: SET(S_joke_1); break; |
| 324 |
case S_joke_1: case S_joke_2: case S_joke_3: SET(S_joke_3); break; |
| 325 |
}}} |
| 326 |
</pre></code></blockquote> |
| 327 |
|
| 328 |
(with <code>{Eq}</code> an alias for the regular expression |
| 329 |
matching an equal sign (corresponding to production `[25] Eq' of |
| 330 |
the XML specification). |
| 331 |
<p> |
| 332 |
This reads as follows: when the XML processor is reading the |
| 333 |
attribute list of the <code>line</code> tag, i.e., when it is in |
| 334 |
the <code><AL_line></code> state, a `<code>t</code>' will |
| 335 |
enter an internal state where a `<code>y</code>' proceeds to |
| 336 |
another internal state but other characters makes the document |
| 337 |
invalid (because no rule permits it). Once the equal sign has |
| 338 |
been scanned, the next characters determine the attribute value, |
| 339 |
and at the end one of the flex actions is performed, setting the |
| 340 |
attribute value (<code>A_line_type</code> is the real C for what |
| 341 |
we wrote as <code>{type}</code>, etc.). The important thing is |
| 342 |
that one can ensure by careful tuning of the flex rules that a |
| 343 |
valid document will proceed only by looking each character up in |
| 344 |
a table and determining the subsequent `state' and `action'. |
| 345 |
One must avoid pairs of rules such as |
| 346 |
|
| 347 |
<blockquote><code><pre>"-->" LEAVE(COMMENT); |
| 348 |
. SKIP; |
| 349 |
</pre></code></blockquote> |
| 350 |
|
| 351 |
(a single `<code>.</code>' matches any character) because they |
| 352 |
mean that the scanner will not be sure after having read a |
| 353 |
`<code>-</code>' character whether it is part of a comment |
| 354 |
terminator or `just' a dash. In such cases an extra rule must be |
| 355 |
inserted because for the set |
| 356 |
|
| 357 |
<blockquote><code><pre>"-->" LEAVE(COMMENT); |
| 358 |
"--" | |
| 359 |
. SKIP; |
| 360 |
</pre></code></blockquote> |
| 361 |
|
| 362 |
the problem goes away. |
| 363 |
<p> |
| 364 |
After the actual attribute rules, two rules handle termination |
| 365 |
of the attribute list. There are two cases corresponding to |
| 366 |
whether we just read a start tag or an empty element. In case |
| 367 |
it was a start tag then we must enter the `inner' mode of the |
| 368 |
element called <code>IN_line</code> for the <code>line</code> |
| 369 |
element. The <code>switch</code> handles the state changes |
| 370 |
needed for the line element resulting from the fact that the |
| 371 |
element can appear in different contexts. This is always |
| 372 |
possible to construct because of the requirement that an XML DTD |
| 373 |
must be <em>deterministic</em>: we just need an element content |
| 374 |
stack (this is what the <code>LEAVE</code> and |
| 375 |
<code>ENTER</code> macros are for). |
| 376 |
|
| 377 |
<h4><a name="why">Why is it useful?</a></h4> |
| 378 |
|
| 379 |
<p> |
| 380 |
In comparison with the forthcoming XML Style-sheet Language |
| 381 |
[<cite><a href="#XSL">XSL</a></cite>] our approach is much more |
| 382 |
primitive for better and worse: only a limited range of |
| 383 |
applications can be produced with FleXML but those will be very |
| 384 |
fast. |
| 385 |
<p> |
| 386 |
This is useful for XML applications that are meant to process a |
| 387 |
large number of documents in a fixed format. One such |
| 388 |
application is the NTSys u-payment transaction server which is |
| 389 |
implemented as an Apache module where performance is of premium |
| 390 |
importance. Using FleXML permits a highly modular development |
| 391 |
of modules for the various transaction types based on a common |
| 392 |
DTD and a collection of applications that are generated |
| 393 |
separately and all linked together with the common processor. |
| 394 |
<p> |
| 395 |
FleXML is still under development: please try it out (either |
| 396 |
from <a "http://flexml.sourceforge.net">SourceForge</a> |
| 397 |
or from the <a href="www.debian.org">Debian |
| 398 |
GNU/Linux</a> distribution where FleXML is include from release |
| 399 |
2.2. The author would welcome comments as to how the system can |
| 400 |
best evolve. Two things that are definitely on the agenda is a |
| 401 |
limited `context condition' language for expressing constraints |
| 402 |
on the position of an element in a document (corresponding to |
| 403 |
the Xpath subset of XSL), and an efficient way to combine |
| 404 |
several DTDs into one large t facilitate general XML servers |
| 405 |
(that can even dispatch to a generic XML interface in cases |
| 406 |
where the FleXML restrictions are not respected by a document). |
| 407 |
|
| 408 |
|
| 409 |
<h4> Acknowledgements </h4> |
| 410 |
|
| 411 |
<p> |
| 412 |
I am grateful to <a href="http://www.ntsys.fr">NTSys</a> for |
| 413 |
supporting the development of FleXML. Finally extend my sincere |
| 414 |
thanks to Jef Poskanzer, Vern Paxson, and the rest of the |
| 415 |
<em>flex</em> maintainers for a great tool. |
| 416 |
|
| 417 |
<h4> References </h4> |
| 418 |
|
| 419 |
<dl compact> |
| 420 |
|
| 421 |
<dt><a name="ASU"><cite>ASU</cite></a> |
| 422 |
<dd> |
| 423 |
Alfred Aho, Ravi Sethi and Jeffrey Ullman: <em>Compilers: |
| 424 |
Principles, Techniques and Tools</em>, Addison-Wesley |
| 425 |
(1986).<p> |
| 426 |
|
| 427 |
<dt><a name="Flex"><cite>Flex</cite></a> |
| 428 |
<dd> |
| 429 |
Jef Poskanzer, Vern Paxson, <em>et. al.</em>: <em>Flex - fast |
| 430 |
lexical analyzer generator</em>.<p> |
| 431 |
|
| 432 |
<dt><a name="Perl"><cite>Perl</cite></a> |
| 433 |
<dd> |
| 434 |
Larry Wall, <em>Perl - Practical Extraction and Report |
| 435 |
Language</em>.<p> |
| 436 |
|
| 437 |
<dt><a name="XML"><cite>XML</cite></a> |
| 438 |
<dd> |
| 439 |
Extensible Markup Language (XML) 1.0 (W3C |
| 440 |
Recommendation REC-xml-1998-0210).<p> |
| 441 |
|
| 442 |
<dt><a name="XSL"><cite>XSL</cite></a> |
| 443 |
<dd> |
| 444 |
Extensible Stylesheet Language (XSL) (W3C Working Draft).<p> |
| 445 |
|
| 446 |
</dl> |
| 447 |
<hr> |
| 448 |
<address>Copyright (c) |
| 449 |
<a href="mailto:[email protected]">Kristoffer Rose</a>. |
| 450 |
<!-- Created: Thu Dec 9 08:09:41 CET 1999 --> |
| 451 |
<!-- hhmts start -->Last modified: Tue Feb 11 13:56:40 EST 2003 <!-- hhmts end --> |
| 452 |
</address> |
| 453 |
|
| 454 |
</body> |
| 455 |
</html> |