ch03_01.htm

Perl & XML. by Erik T. Ray and Jason McIntosh ISBN 0-596-00205-X First Edition, published April

interesting code that uses one of the many available XML-parsing Perl
modules. To that end, we'll write only a fraction of
a pure-Perl XML parser with a very specific goal in mind.
</p>

<a name="ch03-4-fm2xml" /><blockquote><b>WARNING:</b> 
Feel free to play with this program, but please
don't try to use this code in a production
environment! It's not a real Perl and XML solution,
but an illustration of the sorts of things that parsers do. Also,
it's incomplete and will not always give correct
results, as we'll show later. Don't
worry; the rest of this book talks about real XML parsers and Perl
tools you'll want to use.
</p>
</blockquote>

<p>The program is a <a name="INDEX-182" />loop in which regular expressions match
XML markup objects and pluck them out of the text. The loop runs
until nothing is left to remove, meaning the document is well formed,
or until the regular expressions can't match
anything in the remaining text, in which case it's
not well-formed. A few other tests could abort the parsing, such as
when an end tag is found that doesn't match the name
of the currently open start tag. It won't be
perfect, but it should give you a good idea of how a well-formedness
parser might work.
</p>

<p><a href="ch03_01.htm#perlxml-CHP-3-EX-1">Example 3-1</a> is a routine that parses a string of XML
text, tests to see if it is well-formed, and returns a boolean value.
We've added some pattern variables to make it easier
to understand the regular expressions. For example, the string
<tt class="literal">$ident</tt> contains regular expression code to match
an XML identifier, which is used for elements, attributes, and
processing instructions.
</p>

<a name="perlxml-CHP-3-EX-1" /><div class="example">
<h4 class="objtitle">Example 3-1. A rudimentary XML parser </h4>
<blockquote><pre class="code">sub is_well_formed {
    my $text = shift;                     # XML text to check

    # match patterns
    my $ident = '[:_A-Za-z][:A-Za-z0-9\-\._]*';   # identifier
    my $optsp = '\s*';                            # optional space
    my $att1 = "$ident$optsp=$optsp\"[^\"]*\"";   # attribute
    my $att2 = "$ident$optsp=$optsp'[^']*'";      # attr. variant
    my $att = "($att1|$att2)";                    # any attribute

    my @elements = ( );                    # stack of open elems

    # loop through the string to pull out XML markup objects
    while( length($text) ) {

        # match an empty element
        if( $text =~ /^&amp;($ident)(\s+$att)*\s*\/&gt;/ ) {
            $text = $';

        # match an element start tag
        } elsif( $text =~ /^&amp;($ident)(\s+$att)*\s*&gt;/ ) {
            push( @elements, $1 );
            $text = $';

        # match an element end tag
        } elsif( $text =~ /^&amp;\/($ident)\s*&gt;/ ) {
            return unless( $1 eq pop( @elements ));
            $text = $';

        # match a comment
        } elsif( $text =~ /^&amp;!--/ ) {
            $text = $';
            # bite off the rest of the comment
            if( $text =~ /--&gt;/ ) {
                $text = $';
                return if( $` =~ /--/ );  # comments can't
                                            # contain '--'
            } else {
                return;
            }

        # match a CDATA section
        } elsif( $text =~ /^&amp;!\[CDATA\[/ ) {
            $text = $';
            # bite off the rest of the comment
            if( $text =~ /\]\]&gt;/ ) {
                $text = $';
            } else {
                return;
            }

        # match a processing instruction
        } elsif( $text =~ m|^&amp;\?$ident\s*[^\?]+\?&gt;| ) {
            $text = $';

        # match extra whitespace
        # (in case there is space outside the root element)
        } elsif( $text =~ m|^\s+| ) {
            $text = $';

        # match character data
        } elsif( $text =~ /(^[^&amp;&amp;&gt;]+)/ ) {
            my $data = $1;
            # make sure the data is inside an element
            return if( $data =~ /\S/ and not( @elements ));
            $text = $';
            
        # match entity reference
        } elsif( $text =~ /^&amp;$ident;+/ ) {
            $text = $';
         
        # something unexpected
        } else {
            return;
        }
    }
    return if( @elements );     # the stack should be empty
    return 1;
}</pre></blockquote>
</div>

<p>Perl's <a name="INDEX-183" />arrays are so useful partly due to their
ability to masquerade as more abstract computer science data
constructs.<a href="#FOOTNOTE-14">[14]</a> Here, we use a data structure called a
<em class="emphasis">stack</em><a name="INDEX-184" />, which is really just an
array that we access with <tt class="literal">push( )</tt> and
<tt class="literal">pop( )</tt>. Items in a stack
are<a name="INDEX-185" /> <a name="INDEX-186" /> last-in, first-out (LIFO), meaning
that the last thing put into it will be the first thing to be removed
from it. This arrangement is convenient for remembering the names of
currently open elements because at any time, the next element to be
closed was the last element pushed onto the stack. Whenever we
encounter a start tag, it will be pushed onto the stack, and it will
be popped from the stack when we find an end tag. To be well-formed,
every end tag must match the previous start tag, which is why we need
the stack.
</p><blockquote class="footnote"> <a name="FOOTNOTE-14" /><p>[14]The O'Reilly book
<em class="citetitle">Mastering Algorithms with Perl</em> by Jon Orwant,
Jarkko Hietaniemi, and John Macdonald devotes a chapter to this
topic.</p> </blockquote>

<p>The stack represents all the elements along a branch of the XML tree,
from the root down to the current element being processed. Elements
are processed in the order in which they appear in a document; if you
view the document as a tree, it looks like you're
going from the root all the way down to the tip of a branch, then
back up to another branch, and so on. This is called
<em class="emphasis">depth-first
order</em><a name="INDEX-187" />, the canonical way all XML documents are
processed.
</p>

<p>There are a few places where we deviate from the simple looping
scheme to do some extra testing. The code for matching a comment is
several steps, since it ends with a three-character delimiter, and we
also have to check for an illegal string of dashes
"<tt class="literal">--</tt>" inside the
comment. The character data matcher, which performs an extra check to
see if the stack is empty, is also noteworthy; if the stack is empty,
that's an error because nonwhitespace text is not
allowed outside of the root element. Here is a short list of
well-formedness errors that would cause the parser to return a false
result:
</p>

<ul><li>
<p>An identifier in an element or attribute is malformed (examples:
"<tt class="literal">12foo</tt>,"
"<tt class="literal">-bla</tt>," and
"<tt class="literal">..</tt>").
</p>
</li><li>
<p>A nonwhitespace character is found outside of the root element. </p>
</li><li>
<p>An element end tag doesn't match the last discovered
start tag.
</p>
</li><li>
<p>An attribute is unquoted or uses a bad combination of quote
characters.
</p>
</li><li>
<p>An empty element is missing a <a name="INDEX-188" /> <a name="INDEX-189" />slash character (<tt class="literal">/</tt>) at
the end of its tag.
</p>
</li><li>
<p>An illegal character, such as a lone <a name="INDEX-190" /> <a name="INDEX-191" />ampersand (<tt class="literal">&amp;</tt>)
or an <a name="INDEX-192" /> <a name="INDEX-193" />angle bracket
(<tt class="literal">&lt;</tt>), is found in character data.
</p>
</li><li>
<p>A malformed markup tag (examples:
"<tt class="literal">&lt;fooby&lt;</tt>"
and "<tt class="literal">&lt;
?bubba?&gt;</tt>") is found.
</p>
</li></ul>
<p>Try the parser out on some test cases. Probably the simplest
complete, well-formed XML document you will ever see is this:
</p>

<blockquote><pre class="code">&lt;:-/&gt; </pre></blockquote>

<p>The next document should cause the parser to halt with an error.
(Hint: look at the <tt class="literal">&lt;message&gt;</tt> end tag.)
</p>

<blockquote><pre class="code">&lt;memo&gt;
  &lt;to&gt;self&lt;/to&gt;
  &lt;message&gt;Don't forget to mow the car and wash the
  lawn.&lt;message&gt;
&lt;/memo&gt;</pre></blockquote>

<p>Many other kinds of <a name="INDEX-194" />syntax errors could appear in a
document, and our program picks up most of them. However, it does
miss a few. For example, there should be exactly one root element,
but our program will accept more than one:
</p>

<blockquote><pre class="code">&lt;root&gt;I am the one, true root!&lt;/root&gt;
&lt;root&gt;No, I am!&lt;/root&gt;
&lt;root&gt;Uh oh...&lt;/root&gt;</pre></blockquote>

<p>Other problems? The parser cannot handle a document type declaration.
This structure is sometimes seen at the top of a document that
specifies a <a name="INDEX-195" />DTD for validating parsers, and it
may also declare some entities. With a specialized syntax of its own,
we'd have to write another loop just for the
document type declaration.
</p>

<p>Our parser's most significant omission is the
resolution of <a name="INDEX-196" />entity references.
It can check basic entity reference syntax, but
doesn't bother to expand the entity and insert it
into the text. Why is that bad? Consider that an entity can contain
more than just some character data. It can contain any amount of
markup, too, from an element to a big, external file. Entities can
also contain other entity references, so it might require many passes
to resolve one entity reference completely. The parser
doesn't even check to see if the entities are
declared (it couldn't anyway, since it
doesn't know how to read a document type declaration
syntax). Clearly, there is a lot of room for errors to creep into a
document through entities, right under the nose of our parser. To fix
the problems just mentioned, follow these steps:
</p>

<ol><li>
<p>Add a parsing loop to read in a document type declaration before any
other parsing occurs. Any entity declarations would be parsed and
stored, so we can resolve entity references later in the document.
</p>
</li><li>
<p>Parse the DTD, if the document type declaration mentions one, to read
any entity declarations.
</p>
</li><li>
<p>In the main loop, resolve all entity references when we come across
them. These entities have to be parsed, and there may be entity
references within them, too. The process can be rather loopy, with
loops inside loops, recursion, or other complex programming stunts.
</p>
</li></ol>
<p>What started out as a simple parser now has grown into a complex
beast. That tells us two things: that the theory of parsing XML is
easy to grasp; and that, in practice, it gets complicated very
quickly. This exercise was useful because it showed issues involved
in parsing XML, but we don't encourage you to write
code like this. On the contrary, we expect you to take advantage of
the exhaustive work already put into making ready-made parsers.
Let's leave the dark ages and walk into the
happy<a name="INDEX-197" />
land of prepackaged<a name="INDEX-198" /> parsers.
</p>

</div>
</div>


















<hr width="684" align="left" />
<div class="navbar"><table width="684" border="0"><tr><td align="left" valign="top" width="228"><a href="ch02_12.htm"><img alt="Previous" border="0" src="../gifs/txtpreva.gif" /></a></td><td align="center" valign="top" width="228"><a href="index.htm"><img alt="Home" border="0" src="../gifs/txthome.gif" /></a></td><td align="right" valign="top" width="228"><a href="ch03_02.htm"><img alt="Next" border="0" src="../gifs/txtnexta.gif" /></a></td></tr><tr><td align="left" valign="top" width="228">2.12. Transformations</td><td align="center" valign="top" width="228"><a href="index/index.htm"><img alt="Book Index" border="0" src="../gifs/index.gif" /></a></td><td align="right" valign="top" width="228">3.2. XML::Parser</td></tr></table></div>
<hr width="684" align="left" />

<img alt="Library Navigation Links" border="0" src="../gifs/navbar.gif" usemap="#library-map" />
<p><p><font size="-1"><a href="copyrght.htm">Copyright &copy; 2002</a> O'Reilly &amp; Associates. All rights reserved.</font></p>

<map name="library-map"><area shape="rect" coords="1,0,85,94" href="../index.htm"><area shape="rect" coords="86,1,178,103" href="../lwp/index.htm"><area shape="rect" coords="180,0,265,103" href="../lperl/index.htm"><area shape="rect" coords="267,0,353,105" href="../perlnut/index.htm"><area shape="rect" coords="354,1,446,115" href="../prog/index.htm"><area shape="rect" coords="448,0,526,132" href="../tk/index.htm"><area shape="rect" coords="528,1,615,119" href="../cookbook/index.htm"><area shape="rect" coords="617,0,690,135" href="../pxml/index.htm"></map>

</body></html>