Automated Tree Drawing: XSLT and SVG
by Jirka Kosek | Pages: 1, 2, 3

Parsing the Compact Syntax

Given the minimalist set of string functions in XPath/XSLT, parsing the compact syntax of trees is the most challenging part of our task. Fortunately it is possible to create a parser with a combination of elementary string-manipulation functions and recursive processing. The XSLT template hedge2xml implements the following simple parsing algorithm:

1. Get the name of a node. (It's the first letter to process or text between curly braces if the first character is '{'.)

2. If the next token is '(' process text between matching parenthesis by this algorithm and place it inside the element labeled with the name from the first step. Then process the rest of the text after matching ')' by this algorithm.

3. If the next token is not '(' emit the empty element labeled with the name from the first step and process the rest of the text by this algorithm.

<!--Simple text parser generates tree of nodes from
compact syntax -->
<xsl:template name="hedge2xml">
  <xsl:param name="hedge"/>
  <!-- Extract first token -->
  <xsl:param name="head" select="substring($hedge, 1, 1)"/>

<!-- If there is something left to parse then parse it -->
  <xsl:if test="$hedge != ''">
    <xsl:variable name="next" select="substring($hedge, 2, 1)"/>
    <xsl:variable name="tail" select="substring($hedge, 3)"/>

    <xsl:choose>

<!-- Node name is enclosed between { and }. Grab it into
$head and proceed. -->
      <xsl:when test="$head = '{'">
        <xsl:call-template name="hedge2xml">
<xsl:with-param name="hedge"
select="concat(' ', substring-after(concat($next, $tail), '}'))"/>
<xsl:with-param name="head"
select="substring-before(concat($next, $tail), '}')"/>
        </xsl:call-template>
      </xsl:when>

<!-- End of the sub-level. Proceed with next tokens. -->
      <xsl:when test="$head = ')'">
        <xsl:call-template name="hedge2xml">
          <xsl:with-param name="hedge"
            select="concat($next, $tail)"/>
        </xsl:call-template>
      </xsl:when>

<!-- There is no node name. Emit error message. -->
    <xsl:when test="$head = '('">
      <xsl:message>
        <xsl:text>Unexpected ( found in '</xsl:text>
        <xsl:value-of select="concat($head, $next, $tail)"/>
        <xsl:text>'.&#10;</xsl:text>
        </xsl:message>
      </xsl:when>
      
      <!-- Start of the sub-level. -->
      <xsl:when test="$next = '('">
        <!-- Find the end of the sub-level. -->
        <xsl:variable name="endPos"
                        select="my:closingParenPos($tail)"/>
        <!-- Create wrapper node and process content of the
         sub-level. -->
        <node label="{$head}">
          <xsl:call-template name="hedge2xml">

          <xsl:with-param name="hedge"
                     select="substring($tail, 1, $endPos)"/>
          </xsl:call-template>
        </node>
        <!-- Process content after the sub-level. -->
        <xsl:call-template name="hedge2xml">
          <xsl:with-param name="hedge"
                        select="substring($tail, $endPos)"/>
          </xsl:call-template>
      </xsl:when>

      <!-- Output node and process next nodes. -->
      <xsl:otherwise>
        <node label="{$head}"/>
        <xsl:call-template name="hedge2xml">
          <xsl:with-param name="hedge"
                            select="concat($next, $tail)"/>
        </xsl:call-template>
      </xsl:otherwise>
      
    </xsl:choose>
  </xsl:if>
  
</xsl:template>

I am using a custom function, my:closingParenPos, to find the position of the matching closing parenthesis. I decided to implement it as an EXSLT function because a regularly named template would be too verbose. The function scans the input string for parenthesis and counts the depth of nesting. The function ends when the closing parenthesis is found.

<!-- Find position of the matching right parenthesis -->
<func:function name = "my:closingParenPos">
  <xsl:param name = "text"/>
  <xsl:param name = "depth" select = "1"/>
  <xsl:param name = "pos" select = "1"/>
  <xsl:choose>
    <!-- Found closing ) which is not nested. We are done. -->
    <xsl:when test = "substring($text, 1, 1) = ')' and $depth = 1">
      <func:result select = "$pos"/>
    </xsl:when>
    <!-- Found opening (. Increase nesting depth and continue. -->
    <xsl:when test = "substring($text, 1, 1) = '('">
      <func:result select = "my:closingParenPos(substring($text, 2), $depth + 1, $pos+1)"/>
    </xsl:when>
    <!-- Found closing ) which is nested. Unwrap and continue on a shallower level. -->
    <xsl:when test = "substring($text, 1, 1) = ')'">
      <func:result select = "my:closingParenPos(substring($text, 2), $depth - 1, $pos+1)"/>
    </xsl:when>
    <!-- End of text while nested. Something is wrong with input. -->
    <xsl:when test = "$text = '' and $depth != 0">
      <xsl:message>
        <xsl:text>Warning. Unbalanced parenthesis.&#10;</xsl:text>
      </xsl:message>
    </xsl:when>
    <!-- In all other cases scan rest of the input for parenthesis. -->
    <xsl:otherwise>
      <func:result select = "my:closingParenPos(substring($text, 2), $depth, $pos+1)"/>
    </xsl:otherwise>
  </xsl:choose>
</func:function>

Adding Layout Information

Now that we have a tree structure captured as an XML fragment we must calculate the layout of the individual nodes. In order to do this we must know the depth and width of each node in the tree. The following templates in xml2layout mode copy node elements intact and add width and depth as attributes to each node.

<xsl:template match="node[node]" mode="xml2layout">
  <xsl:param name="depth" select="1"/>
  <xsl:variable name="subTree">
    <xsl:apply-templates select="node" mode="xml2layout">
      <xsl:with-param name="depth" select="$depth+1"/>
    </xsl:apply-templates>
  </xsl:variable>

  <!-- Add layout attributes to the existing node -->
  <node depth="{$depth}" width="{sum(exsl:node-set($subTree)/node/@width)}">
    <!-- Copy original attributes and content -->
    <xsl:copy-of select="@*"/>
    <xsl:copy-of select="$subTree"/>
  </node>

</xsl:template>

<!-- Add layout attributes to leaf nodes -->
<xsl:template match="node" mode="xml2layout">
  <xsl:param name="depth" select="1"/>
  <node depth="{$depth}" width="1">
    <xsl:copy-of select="@*"/>
  </node>
</xsl:template>

Pages: 1, 2, 3

Next Page