[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Parser implemented in XSL -- stack overflow

Subject: Parser implemented in XSL -- stack overflow
From: Bill Cohagan <bill.cohagan@xxxxxxxxxxxxx>
Date: Tue, 1 Apr 2003 16:36:22 -0600
xsl stack overflow
I am experiencing stack overflow with an XSL program and don't understand
why. Following is a description of the program and some sample code.

I have an application that generates XSL code that is intended to implement
a "parser" (actually a Deterministic Finite State Transducer). This parser
accepts a "flat" sequence of elements and transforms it into a nested
structure according to a grammar (XSD) that is used by my app to generate
the XSL. Obviously there are other ways to do this, one being simply to
implement a DFST interpreter in Java, VB, etc. Being an XSL fan however I
decided to try it in XSL.

The two problems to be solved were to process the input "left to right" and
to implement "states" somehow. I avoided generating/using named templates
due to past experience with stack overflow. So what I did was to use
template modes to specify state and to use a select expression on my
apply-templates calls so that only the "next" input element would be
considered. Here's a "typical" template from my XSL program:

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  <xsl:template match="node()[@Style = 'H-stage-level']" mode="sn1">
    <xsl:param name="parents" />
    <!--Push-->
    <xsl:variable name="adjustedParents" select="$parents" />
    <xsl:variable name="ID" select="generate-id()" />
    <MaturityStage Style="H-stage-level" ParaNumber="{@ParaNumber}"
id="{$ID}" parent="{substring-before($adjustedParents, ',')}" />
    <xsl:apply-templates select="following-sibling::*[1]" mode="sn5">
      <xsl:with-param name="parents" select="concat($ID, ',',
$adjustedParents)" />
    </xsl:apply-templates>
  </xsl:template>

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

So this template matches an input element that has the indicated Style
attribute. In DFST terms this template corresponds to the action to take if
you encounter an H-stage-level input while in state "sn1". That action is to
emit a MaturityStage element and transition to state "sn5". Note the use of
following-sibling::[1] to restrict the match to the next element in the
input. The "parents" paramater is a csv string used like a stack to control
creation of "parent pointers" in the emitted elements.

All of the templates are of this general form, although some of them do a
"pop" on the csv; e.g., 

  <xsl:variable name="adjustedParents" select="substring-after($parents,
',')" />

Again, there are NO call-template elements in the XSL, only
xsl:apply-templates calls of the general form above. It is also the case
that all such apply-template calls are tail recursive.

I have experienced stack overflow with MSXML4, with the MS .Net XSL engine
and with Saxon6.5.2 (which I believe implements proper tail recursion.) The
stack growth appears to be proportional to the XML input size; i.e., for
files up to a "certain size" there is no overflow and the transformation
works as expected.

Can anyone explain to me why this "style" of XSL should cause stack growth
proportional to input size? Obviously it is not generally the case that
stack growth is proportional to input size -- or XSL wouldn't be very
interesting!

Thanks in advance,
 Bill Cohagan


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.