RELAX NG Implementation Cook Book: Day 1

Since they are combinators, they have two child expressions.

These expressions have one child expression and one name class. The child expression represents the content model of an attribute/element, and the child name class represents its tag name (or its attribute name).

These expressions have one child expression. But except that, they don't have much in common.

DataExp has a dattype object, which will validate a string. It also has a child expression that represents the "except" clause of the <data> pattern.

ValueExp has a datatype object and one value object. This datatype object is used to compare the value object with a string literal to see if they are the "same".

Since these expressions have no children and they don't have any parameters, there is no need to create multiple instances of them. Therefore, we'll use the singleton design pattern here. (you just create one instance for each type, and reuse the same instance.)

For a reason that I'll describe later, in fact we MUST use the singleton design pattern.

ReferenceExp has one child expression and a name. One ReferenceExp object is created for each named pattern.

Grammar has (1) one ReferenceExp that represents the <start> pattern and (2) a map from pattern names to ReferenceExps, which allow you to retrieve ReferenceExps by their names.

It also have (3) a parent grammar, which designates its parent grammar. The parent grammar is used to resolve <parentRef> pattern.

The first step is to make all Expressions immutable. That is, once you create an Expression object, you'll never change its field values. This is necessary because an Expression object can be possibly shared by multiple Expressions, and changing it will cause unexpected side effect.

For example, in Java, you can use the "final" keyword on all fields to make them immutable. If your language doesn't support immutable fields, you have to be careful not to modify them. The following snippet shows the C# version.

public class OneOrMoreExp : Expression {
    public readonly Expression child;
    ....
}

The next step is to create a scheme to reuse expressions. There are many ways to do this, but one way to do is to use a hash table and keep all expressions in it.

For example, you can implement the hashCode method and the equals method for GroupExp as follows:

int hashCode() {
  return leftExp.hashCode() + rightExp.hashCode() + 713/*constant_for_group*/;
}
boolean equals( Object o ) {
	if(!(o instanceof GroupExp))   return false;
	GroupExp rhs = (GroupExp)o;
	return this.leftExp==rhs.leftExp && this.rightExp==rhs.rightExp;
}

You have to implement the hashCode method and the equals method correctly for all expressions.

Then you can use the following unify method to "internalize" expressions.

Hashtable h;
Expression unify( Expression e ) {
	Expression u = h.get(e);
	if(u!=null)  return u;
	
	h.put(e,e);
	return e;
}

Then the createOneOrMore method would be like this:

Expression createOneOrMore( Expression child ) {
	return unify( new OneOrMoreExp(child) );
}

ExpBuilder should perform some of simplification tasks. One of them is <notAllowed/> propagation (4.19 of the spec) For example, abovementioned createOneOrMore method is actually implemented as follows:

Expression createOneOrMore( Expression child ) {
	// <oneOrMore><notAllowed/></oneOrMore>  => <notAllowed/>
	if( child==Expression.notAllowed )	return child;
	// other cases
	return unify( new OneOrMoreExp(child) );
}

As long as you handle <notAllowed/> correctly, your validator will work correctly.

However, ExpBuilder can do a lot of things to encourage the reuse and thus achive higher performance. For example, you can simplify patterns that contain <empty> pattern.

One of the technique which is frequently used is to make combinators either "left-associative" or "right-associative". If associativity is not enforced, it becomes difficult to detect that two patterns (A,B),C and A,(B,C) are identical. ExpBuilder is an ideal place to set associativity and enforce it.

Another technique, which is also frequently used, is to prevent expressions like A|B|C|A from being created by removing redundant items from a <choice> pattern.

Different implementations adopt slightly different techniques, so you would learn a lot by examining other people's code.

In our core grammar model, we don't have classes for <zeroOrMore> or <optional>. However, it is a good idea to implement the createZeroOrMore method or the createOptional method.

They can be easily implemented by using other expressions:

Expression createZeroOrMore( Expression e ) {
	return createOptional(createOneOrMore(e));
}
Expression createOptional( Expression e ) {
	return createChoice( e, Expression.empty );
}

OK, that's it. It's time for you to implement your own ExpBuilder now.