Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Web Development

XSL Transformations


The Minimal Imperative Language XIM

We can regard an XIM program as an abstract syntax tree representation of a program written in a high-level concrete imperative language with variables of type float, expressions involving arithmetic operators, the usual Boolean expressions, an assignment statement, one conditional construct (if-then-else), and one iteration construct (while). The formal syntax of XIM is specified using an XML Schema (available electronically; see "Resource Center," page 5). XIM constructs are straightforward. Every statement element in XIM has a @seq attribute, which acts like the symbolic address of the element. The @next attribute gives the address of the next instruction to be executed. In <while> and <if> constructs, attributes @true_next (@false_next) determine control flow when the condition is true (false). The values of these attributes are automatically generated, using XSLT, before execution starts. Listing One is an XIM program that computes 5!, demonstrating the use of assignment and while constructs. Listing Two is the same program in pseudocode.

<?xml version="1.0"?> 
<program>
   <vars>
      <var_declare name="fact"> 1 </var_declare>
      <var_declare name="last"> 0 </var_declare>
      <var_declare name="nb"> 5 </var_declare>
   </vars>
   <main>
      <assign varn="last">
         <var_use name="nb"/>
      </assign>
      <while>
         <condition>
            <boolop opname="gt">
               <var_use name="last"/>
               <num> 1</num>
            </boolop>
          </condition>
          <statement_list>
             <assign varn="fact">
                <op opname="*">
                   <var_use name="fact"/>
                   <var_use name="last"/>
                </op>
             </assign>
             <assign varn="last">
                <op opname="-">
                   <var_use name="last"/>
                   <num> 1</num>
                </op>    
             </assign>
          </statement_list>
       </while>
       <end/> <!-- program termination -->
    </main>
</program>
Listing One

var fact <-- 1
var last <-- 0
var nb   <-- 5
begin
    last <-- nb
     while (last>1) do
       fact <-- fact*last
       last  <-- last-1
     end while
end
Listing Two

Operational Semantics of XIM in XSLT

Operational semantics specify the meaning of a program in a source language by giving rules for how the state of an abstract (or real) machine changes for each construct of the source language. The states of the abstract machine can be represented as < code, memory > pairs (called "configurations"), where code represents the remaining computation, and memory is the current contents of the memory of the abstract machine. A transition function specifies the transition from one configuration of the machine to the next. The transition function defines the operational semantics of the language and can also act as an interpreter for it. Using XSLT for specifying the operational semantics of programming languages, a configuration consists of the memory, program, and current value of the "program counter," all inside an XML document. The transition function is specified as XSLT templates.

An XSLT stylesheet implements the operational semantics of XIM. Before execution starts, the stylesheet transforms the XIM program to make it ready for interpretation. First the "program counter" is introduced as a variable in the program, and symbolic addresses are inserted into instructions as @seq attributes. Then the values in the @next, @true_next, and @false_next attributes of the instructions are determined and inserted into the code. These attributes specify the address of the next instruction to execute, as in attribute grammars used in syntax-directed compilation. After the initialization stage, other templates are applied to the transformed XIM program to execute it. The application of templates is an iterative process, which stops when the next instruction is the <end> element.

The top-level template (available electronically) of the stylesheet matches the root and performs the application of templates for initialization and interpretation. Templates for inserting the program counter and calling the Sequencer template (available electronically) insert the "program counter" as an XIM variable named PC and symbolic addresses as @seq attributes. The Sequencer template (available electronically) achieves the insertion of symbolic addresses through the use of the <number> element of XSLT. Values in the @next, @true_next, and @false_next attributes are then inserted by templates that perform a case-by-case analysis of a given node to determine its type, inspect its position relative to other instructions, and set the control flow information as jump addresses accordingly. The template for the implementation of the iterative steps is Interpret and the template for determining the type of current instruction and calling the corresponding template for its execution is Execute; both templates are available electronically. The Assignment template (also available electronically) receives an assignment statement as an XML subtree in the $c parameter. The template also has access to the XML document as a whole via the $prg parameter. The name of the program variable to whom a new value is to be assigned is copied into the XSLT variable $varname. The whole <memory> element of the XML document is recreated to reflect the updated value of the variable, as well as the updated value of the "program counter" PC variable. The template Construct (available electronically) handles the execution of <while> and <if> statements. The instruction, which is an <if> or <while> construct, comes into parameter $c and the code of the program as a whole comes in parameter $prg. The truth value of the condition is determined and assigned to the XSLT variable $condition. Then the <memory> element, with all its children except the PC, is copied. The value of the PC variable is updated depending on the truth value of $condition. When it is "true," the value of the @true_next attribute of the <condition> child of the context node is assigned to the PC variable. Otherwise, the value of the @false_next attribute is assigned to it.

The Evaluate template (available electronically), takes a parameter $n holding an XML subtree representing an expression. Figures 1 and 2 are arithmetic and Boolean expressions, respectively. This template also has access to the whole XIM program in the parameter $p. It first checks whether the incoming parameter is a numerical literal (<num>), a variable (<var_use>), or a complex expression (<op> or <boolop>). If the incoming expression in parameter $n is a <num>, it returns the content of the <num> element. If it is a <var_use> element (an r-value), the value of the <var_declare> element referenced by <var_use> is returned. If the incoming expression is an <op> or <boolop>, the type of operation required is determined from the @opname attribute. The possible values in the @opname attribute for the <op> element are *, +, -, /, intdiv, and mod, while the options for <boolop> are or, and, not, lt, gt, eq, ne, ge, and le, which have their conventional meanings.

[Click image to view at full size]

Figure 1: An arithmetic expression and its corresponding XIM code.

[Click image to view at full size]

Figure 2: Boolean expression and its corresponding XIM code.

Boolean expressions are evaluated fully in the same manner as arithmetic expressions (see the code fragment from template Evaluate that handles Boolean expressions, available electronically).


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.