Debian Codegraph @

paper.html

raw
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>&lt;!DOCTYPE joke SYSTEM &quot;my.dtd&quot;&gt;
119 &lt;joke&gt;&lt;line&gt;My appartment is so small&lt;/line&gt; &lt;suspense/&gt;
120 &lt;line type='punch-line'&gt;the mice are round-shouldered&lt;/line&gt;&lt;/joke&gt;
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>&lt;!-- my.dtd: Small DTD for jokes (just for fun). --&gt;
128 &lt;!ELEMENT joke (line,(line|suspense)*)&gt;
129 &lt;!ELEMENT line (#PCDATA)&gt;
130 &lt;!ATTLIST line type (normal|question|punch-line) 'normal'&gt;
131 &lt;!ELEMENT suspense EMPTY&gt;
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>&lt;!DOCTYPE actions SYSTEM &quot;flexml-act.dtd&quot;&gt;
145 &lt;actions&gt;
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>&lt;top&gt;&lt;![CDATA[
164 char* terminator = &quot;.&quot;;
165 ]]&gt;&lt;/top&gt;
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>&lt;start tag='line'&gt;&lt;![CDATA[
176 switch ( {type} ) {
177 case {!type}: terminator = &quot;...&quot;; break;
178 case {type=normal}: terminator = &quot;.&quot;; break;
179 case {type=question}: terminator = &quot;??&quot;; break;
180 case {type=punch-line}: terminator = &quot;!!&quot;; break;
181 }
182 ]]&gt;&lt;/start&gt;
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>&lt;/line&gt;</code>. Since it prints something, however,
203 we first need to add the appropriate header inclusion.
204
205 <blockquote><code><pre>&lt;top&gt;&lt;![CDATA[
206 #include &lt;stdio.h&gt;
207 ]]&gt;&lt;/top&gt;
208
209 &lt;end tag='line'&gt;&lt;![CDATA[
210 printf(&quot;%s%s\n&quot;, pcdata, terminator);
211 ]]&gt;&lt;/end&gt;
212 </pre></code></blockquote></p>
213
214 <p>
215 Finally, we will make the application amusing by `displaying'
216 the <code>&lt;suspense/&gt;</code> empty tag as a short delay;
217 this also involves a header inclusion.
218
219 <blockquote><code><pre>&lt;top&gt;&lt;![CDATA[
220 #include &lt;unistd.h&gt;
221 ]]&gt;&lt;/top&gt;
222
223 &lt;start tag='suspense'&gt;&lt;![CDATA[
224 sleep(2);
225 ]]&gt;&lt;/start&gt;
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>&lt;/actions&gt;
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>&lt;!DOCTYPE actions SYSTEM &quot;flexml-act.dtd&quot;&gt;
265 &lt;actions&gt;
266
267 &lt;top&gt;&lt;![CDATA[
268 #include &lt;stdio.h&gt;
269 ]]&gt;&lt;/top&gt;
270
271 &lt;start tag='a'&gt;&lt;![CDATA[
272 if ({href}) printf(&quot;%s\n&quot;, {href});
273 ]]&gt;&lt;/start&gt;
274
275 &lt;/actions&gt;
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>&lt;AL_line&gt;{
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 "&gt;" {
317 LEAVE; STag_line(); pcdata = BUFFERSET(pcdata); ENTER(IN_line);
318 }
319 "/&gt;" {
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>&lt;AL_line&gt;</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>