[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Parser implemented in 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
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|