Creating C++ Interpreters for XML Extension Languages

Like this article? We recommend 

The first mechanism for implementing our own scripting (or extension) XML languages on top of C++ applications is the creation of an interpreter for the XML format into our program. The theory and implementation options behind writing an interpreter can be overwhelming. We are going to stick with a clean and proven--if not the most efficient in every case--pattern called "Little Language."

Creating Program Tree Objects from XML

The following sections describe concepts--such as variables and control flow structures for an XML language--for scripts in a program that manipulates images.

Overview of the Mechanism

Without getting into the details of programming language theory, it can be said that an expression or program can be seen as a tree, where each element can be evaluated to a certain value, either because it is an atomic "terminal" (such as the number "5" in the arithmetic example) or because it can be evaluated by applying the semantics of the "non-terminal" to its children (for example, the result of an "add" element is determined by adding its two children). Figure 1 further illustrates the point.

Figure 1 Expression As Tree

The evaluation of some nodes may produce side effects (for example, a call to printf produces an output according with its arguments).

An XML document, as you well know, is a tree. Therefore, you can represent programs using XML documents where the non-leaf nodes represent functions and control structures, and the leaves represent atomic values. The interpretation of these files will result in object hierarchies as the one that is described in the figure, which can be evaluated at runtime.

Designing the Language

The testImage program is a powerful set of tools to make all sorts of image manipulation, including dozens of effects and support for many file types. The winConvert application is a windows front-end to testImage, adding the ability to select visually the files to treat and the options to use.

winConvert exposes only a very small subset of the functionality of the core program; namely, it allows the transformation of the file into three output formats, cropping to a particular rectangle, and adding a message at the top of the image. winConvert is limited, but the goal is to define XML extension languages, not comprehensive image manipulation. So, it will serve your purposes well (for more about all the possibilities of the testImage program and image manipulation software related to it, go to the postgraphy site.

The goal of this section is to create an XML scripting language for applying winConvert functions automatically to several files.

Philosophy

The first step in the creation of the language is coming up with high-level decisions about what functionality to expose and the paradigm used to do it. In particular, it is important to decide whether XML will reflect the underlying API or provide higher level abstractions.

In this case, the underlying API is basically that of the CImage object (see Figure 2). You could very well expose its methods directly as XML elements, but instead it is preferred to expose a higher-level view of the language. For example, Image objects provide a method to change their own output format, but instead of saying "save this image as JPG" you want to say "all the save operations from this point on should be done using JPG format". The language must reflect such decisions.

Figure 2 CImage Object

Primitives

Following the philosophy for this language, you come to the following basic primitive functions:

• Set output format

• Crop image

• Annotate image

To provide a way to specify the input filename, you will provide a treat element, which can contain both crop and annotate instances. Turning the above into a DTD, you obtain Listing 1.

Listing 1: convertScript_0_1.dtd

<!ELEMENT convertScript  (setOutputFormat|treat)*>
<!ELEMENT setOutputFormat EMPTY>
<!ATTLIST setOutputFormat 
     to       (JPEG|TIFF|GIF)   #REQUIRED>
<!ELEMENT treat      (crop?,annotate?)>
<!ATTLIST treat 
     file      CDATA        #REQUIRED>

<!ELEMENT crop      (x,y,xf,yf)>
<!ELEMENT x        (#PCDATA)>
<!ELEMENT y        (#PCDATA)>
<!ELEMENT xf       (#PCDATA)>
<!ELEMENT yf       (#PCDATA)>

<!ELEMENT annotate    (#PCDATA)>

Using this language, you can already define somewhat interesting scripts, such as the one in Listing 2.

Listing 2: script_0_1.xml

<?xml version="1.0"?>
<!DOCTYPE convertScript SYSTEM "convertScript_0_1.dtd">
<convertScript>
<setOutputFormat to="JPEG"/>
<treat file="c:\temp\Leira.gif">
<crop>
<x>0</x><y>0</y>
<xf>102</xf><yf>49</yf>
</crop>
</treat>
<treat file="c:\temp\Et.tif">
<annotate>second file</annotate>
</treat>
<treat file="c:\temp\Oeluc.gif">
</treat>
<setOutputFormat to="GIF"/>
<!-- treat some more images here...-->
</convertScript>

Variables and Operators

It would be interesting to have the ability to define variables in your language (for example, to reuse an annotation). In Listing 3, the convertScript DTD is expanded to allow the assignment and retrieval of values to/from variables (namely the assign and variable elements). The equal, greater than, and plus operators are also introduced. The improved DTD is shown in Listing 3.

Note that I keep the number of operands at a minimum for space and complexity reasons, but the language can be easily extended with other primitives if you so desire.

Listing 3: Adding Variables and Operators to the Language

<!ELEMENT convertScript  (assign|setOutputFormat|treat)*>

<!ENTITY % operator    "equal|plus|greaterThan">
<!ELEMENT variable     EMPTY>
<!ATTLIST variable
     name       CDATA   #REQUIRED>
<!ELEMENT assign     (variable,value)>
<!ELEMENT value      (#PCDATA|variable|%operator;)*>
<!ELEMENT equal      (operand,operand)>
<!ELEMENT plus      (operand,operand)>
<!ELEMENT greaterThan   (operand,operand)>

<!ELEMENT operand     (#PCDATA|variable)*>

<!ELEMENT setOutputFormat EMPTY>
<!ATTLIST setOutputFormat 
     to       (JPEG|TIFF|GIF)   #REQUIRED>
<!ELEMENT treat      (crop?,annotate?)>
<!ATTLIST treat 
     file      CDATA        #REQUIRED>

<!-- now the values of crop can be also complex expressions -->
<!ELEMENT crop      (x,y,xf,yf)>
<!ELEMENT x        (#PCDATA|variable|%operator;)*>
<!ELEMENT y        (#PCDATA|variable|%operator;)*>
<!ELEMENT xf       (#PCDATA|variable|%operator;)*>
<!ELEMENT yf       (#PCDATA|variable|%operator;)*>

<!ELEMENT annotate    (#PCDATA|variable|%operator;)*>

Control Structures

Finally, you want to illustrate the support for some control structure. So, you add the while statement (again, syntactic sugar such as for, and other control structures such as if, can be added at leisure).

The while element has two children: a condition and a body. Much in the C tradition, the contents of the condition are ultimately evaluated to a value: In case the value is 0, the condition is taken to be false; in any other case, the condition is true. Listing 4 shows the final version of the language.

Listing 4: convertScript_1_0.dtd

<!ELEMENT convertScript  (while|assign|setOutputFormat|treat)*>

<!ENTITY % operator    "equal|plus|greaterThan">
<!ELEMENT variable     EMPTY>
<!ATTLIST variable
     name       CDATA   #REQUIRED>

<!ELEMENT assign     (variable,value)>
<!ELEMENT value      (#PCDATA|variable|%operator;)*>
<!ELEMENT equal      (operand,operand)>
<!ELEMENT plus      (operand,operand)>
<!ELEMENT greaterThan   (operand,operand)>

<!ELEMENT while      (condition,body)>
<!ELEMENT condition    (#PCDATA|variable|%operator;)*>
<!ELEMENT body      (while|assign|setOutputFormat|treat)*>

<!ELEMENT operand     (#PCDATA|variable)*>

<!ELEMENT setOutputFormat EMPTY>
<!ATTLIST setOutputFormat 
     to       (JPEG|TIFF|GIF)   #REQUIRED>
<!ELEMENT treat      (crop?,annotate?)>
<!ATTLIST treat 
     file      CDATA        #REQUIRED>

<!ELEMENT crop      (x,y,xf,yf)>
<!ELEMENT x        (#PCDATA|variable|%operator;)*>
<!ELEMENT y        (#PCDATA|variable|%operator;)*>
<!ELEMENT xf       (#PCDATA|variable|%operator;)*>
<!ELEMENT yf       (#PCDATA|variable|%operator;)*>

<!ELEMENT annotate    (#PCDATA|variable|%operator;)*>

Listing 5 shows a script that uses all the constructs you generated in order to generate multiple crops with different sizes out of a single file.

Listing 5: script_1_0.xml

<?xml version="1.0"?>
<!DOCTYPE convertScript SYSTEM "convertScript_1_0.dtd">
<!-- the following script would be equivalent to the following c++ pseudo-code:
   setOutputFormat(JPEG)
   j = 0;
   while(300 > j)
   {
     f = treatFile("c:\\temp\\face.gif");
     f.crop(0,0,j,j);
     j = j + 50;
   }   
-->
<convertScript>
<setOutputFormat to="JPEG"/>
<assign>
<variable name="j"/>
<value>0</value>
</assign>
<while>
<condition>
<greaterThan>
<operand>300</operand>
<operand><variable name="j"/></operand>
</greaterThan>
</condition>
<body>
<treat file="c:\temp\face.gif">
<crop>
<x>0</x>
<y>0</y>
<xf><variable name="j"/></xf>
<yf><variable name="j"/></yf>
</crop>
</treat>
<assign>
<variable name="j"/>
<value>
<plus>
<operand><variable name="j"/></operand>
<operand>50</operand>
</plus>
</value>
</assign>
</body>
</while>
</convertScript>

This language, as you can see, can already throw somewhat interesting results.

Creating the Object Structure

In order to interpret the programs above, you will construct hierarchies, where every object exposes an eval() method, implementing the logic associated with it (for example, the eval method of Plus will return the addition of its two operands).

The complete script will be represented by a tree of Terms (the base class for Treat, Crop, and all other possible members of the tree). When the eval() method in the root is called, it will recursively call eval() on its children (and so on) finally evaluating the whole program. The following subsections show the implementation of the different types of terms.

Modeling the Primitives

The Treat, Crop, setOutputFormat, and Annotate primitives are modeled by making calls to a global CImage variable, as illustrated in Listing 6. Because you are allowing the one-time setting of the output format via the setOutputFormat element, but the Image object is getting updated all the time, you must also keep track of the format value so that every time Treat is called, it can set the Image format to the correct value.

Listing 6: Crop Implementation

class Crop : public Term {
 public:

  crop(int nx,int ny,int nxf,int nyf) : x(nx), y(ny), xf(nxf), xy(nyf){ }

  int eval() 
  {  
    globalImage.crop(x,y,xf,yf); 
  }

 private:
  int x,y,xf,yf;
};

Listing 7 shows the implementation of the Treat object, which reads the file, applies all the children underneath it, and then writes it back, appending a random number to the filename (in an imperfect way to avoid re-writes when a loop forces the same file to be treated more than once).

Listing 7: Treat Implementation

#include <vector>
#include <string.h>

using namespace std;

class Treat : public Term {
 public:

  void setName(char* newName) 
  {
     strcpy(name,newName);
  }

  void addTerm(Term *t)
  {
     children.push_back(t);
  }

  int eval() 
  { 
     globalImage.read(name);
     // This method sets the output format
     globalImage.Format(format); //format is a global variable, 
                   //set by// the eval method ofsetOutputFormat
     //now, process all the children, thus modifying the image
     for(int i = 0; i < children.size();i++)
      children[i]->eval();
     // the modifications are complete, save
     char randomPostfix[15];
     globalImage.save(strcat(name,itoa(rand()%100,randomPostfix,10)));
     return 1;
  }

 private:
   vector<Term*> children;
   char name[90];
};

Modeling the Control Structures

The implementation of while objects also falls compactly into the term-based scheme we have been using. Listing 8 shows the eval() method for this class.

Listing 8: While::eval()

  int eval()
  { 
   while(condition->eval() != 0)
     for(int i = 0; i < children.size();i++)
      children[i]->eval();
   return 1;
  }

Finally, in order to keep the value of variables, maintain a map of names versus values (for simplicity, all variables will be integers):

static vars<string,int>;

The eval() method of the Variable Object fetches values from this table, while the eval() of Assign updates it.

Constructing the Term Tree

Using the XMLableFR framework (which is included in the book), you can easily write the SAX2 skeleton class that will act as your object hierarchy builder. Filling it out is a matter of creating instances of Crop, Treat, and so on according to an element name. For space reasons, the builder code for Term trees is omitted from the article (it can be found on http://www.cppxml.com).