Production Grammar Framework for .NET with Applications to Testing

• Download source from DotNetWiki

Introduction

In this article, I will present a framework for defining and executing production grammars. The production grammars described in "Using Production Grammars for Software Testing" (see [1]) are very similar to classic "LALR" grammars, in terms of understanding and semantics. The difference is that production grammars reversed the work of grammar, since they are used to produce output instead of analyze input.

Production grammars can do anything, ranging form generating data, piloting your application, and generating test case, ... Since we are looking at testing applications, here are a few applications that we will be interested on:

• Manipulate the Implementation Under Test (IUT).
• Generate test case that manipulate the IUT. In this case, the grammar is a code generator.
• If you want to test IUT against input data, generate a wide range of possible inputs.
• etc...

Note for those who know Spart, this is just reversing the process :)

Oracle problem

"Production grammars are well-suited for test generation not only because they can create diverse test cases effectively, but also because they can provide guidance on how the test cases they generate ought to behave. It is often hard to determine the correct system behavior for automatically generated test cases -- a fundamental difficulty known as the Oracle problem (see [2]). In the worst case, automated test generation may require reverse engineering and manual examination to determine the expected behavior of the system on the given test input." The authors of [1] propose two ways of dealing with the oracle problem:

• comparing difference with another implementation,
• generating verification code along with the test code.

Since the PGF is based on .NET code, you can theoretically add any verification code, and if available, compare with any other implementation. This will be illustrated in the example.

What is a Production Grammar:

"A production grammar is a collection of non-terminal rules to terminal rules that resembles a regular parsing grammar, but is used �in reverse.� That is, instead of parsing a sequence of tokens into higher level constructs, a production grammar generates a stream of tokens from a set of non-terminals that specify the overall structure of the stream".

Let's see that on a simple example. Consider the following comma separated list of names:

John,Paul,Marc

A valid EBNF grammar to parse this stream would be ([A-Z] designs capital letters, [a-z] lower case letters, + one or more occurrence, * zero or more occurrence):

name := [A-Z] [a-z]+
names := name (',' name)*

In the case of production grammar, we want to create that list of names. In C#, a possible implementation of the production grammar would be as follows:

public class NamesGrammar
{
   public string Name()
   {
        // gets a random int

        int count = nextRandom();
        // getUpper return upper case, getLowerString

        // returns lower cased string

        return getUpper() + getLowerString(count);        
   }
   public string Names()
   {
        int count = nextRandom();
        string names = Name();
        for(int i=0;i!=count;++i)
           names += ',' + Name();
        return names;
   }
}

The example will generate a list name when the Names method is called, we have production :). This is just a dummy example, it is 100% hard-coded and very difficult to maintain.

Production Grammar Framework

Before starting to work on an example (guess which), let us define important notations/interfaces of the PGF:

• a rule (IRule) is an object that produces something. A rule can be terminal, it does not have any sub-rules, or non-terminal. Example of non-terminal rule is the + operator, terminal rule would be writing a string to a stream.
• a production (IProduction) represents a production process (you can think of it as batch). It is passed on between the rules and can be stored to transmit the context or finish production,
• Each time a rule wants to produce, it asks the production for a production token (IProductionToken). If the request is successful, the production goes on; otherwise, the production finishes. Using this mechanism, you can easily design production that will stop on a finite number of rule production.
• a grammar (IGrammar) encapsulates a start rule and is used to launch the production process.

Those five interfaces form the kernel of the PGF, the rest of the framework is built on top and around them to help the user implement grammars.

The working example: a Stack

In order to crystallize the ideas presented here, we will consider the problem of testing a Stack (as in Test Driven Development in .NET, see [4]). A simple unbounded stack can be formalized by the following interface:

public interface IStack
{
    void Push(Object);
    Object Pop();
    Object Peek(); // equivalent to Pop() in TDD

    bool IsEmpty {get;}
}

The grammar

Before writing down the grammar in C#, it is useful to formalize it in a "pseudo" EBNF-like notation. In this example, there are three terminals: Push, Pop, Peek (we omit IsEmpty for now):

push := stack.Push(...)
pop := stack.Pop()
peek := stack.Peek()

Since Pop and Peek can throw if the stack is empty, we create a special non-terminal rule that guards production against a specific exception type. This gives us the two following non-terminal rules:

gardedPop := gard( pop, InvalidOperationException )
gardedPeek := gard( peek, InvalidOperationException )

Of course, we need to be able to decided whether we want to execute the guarded rule or the non guarded. Again, we define a new non-terminal rule that works as a "if-then-else". This gives us one more non-terminal rule:

nonEmpty := push | pop | peek
empty := push | gardedPop | guardedPeek
stackRule := if(isEmpty) { empty } else { nonEmpty }

The final step is to decide how many executions we want. Since we can break the production at the IProduction level, we go for infinite:

stackGrammar := stackRule*

The full grammar can be summarized as:

push := stack.Push(...)
pop := stack.Pop()
peek := stack.Peek()
gardedPop := gard( pop, InvalidOperationException )
gardedPeek := gard( peek, InvalidOperationException )
nonEmpty := push | pop | peek
empty := push | gardedPop | guardedPeek
stackRule := if(isEmpty) { empty } else { nonEmpty }
stackGrammar := stackRule*

At this point, we have defined a grammar for piloting the stack written in a "pseudo"-EBNF language. The simplicity of the notation, let us concentrate on the problem and not on the tool to solve it. However, as it is, the grammar is pretty much useless, since it is missing verification code. We will see that the verification code can be easily added while writing the grammar in C#.

Rewriting the grammar in C# with PGF

The PGF contains a bunch of built-in non-terminal rules and helpers that will help you translate a grammar into functional C# code. In this example, we will encapsulate the grammar in a StackFixture class that contains a stack field:

public class StackFixture 
{
    private Stack stack = new Stack();
}

Step 1: Creating the terminal methods

Following the way we constructed the grammar, we begin by defining the terminals. The easiest solution is to define one method for each terminal and then wrap it into a IRule. For example, the push terminal is implemented as follows:

public class StackFixture 
{
    private Stack stack = new Stack();
    private IRule push;

    public void Push()
    {
        this.stack.Push(null);
    }

    public void CreateGrammar()
    {
        this.push = Rules.Method(new DefaultMethodDelegate(this.Push));
    }
}

We have added three things: a IRule field member to store the "push" terminal, a Push method that actually pushes something on the tested stack, and a CreateRules method that will be used to create the grammar. The Rules.Method is a static helper class that encapsulates the call to a member method into a rule. The same operation can be repeated for pop and peek.

Step 2: Adding code for the Oracle problem

In order to be able to verify assertion on the fixture, we need to solve the Oracle problem. For this specific case, we can do the Comparison testing approach where we execute the operations on another implementation and verify that outputs are different (NC, not NSC).

public class StackFixture 
{
    private ArrayList list = new ArrayList();
    private Stack stack = new Stack();
    private IRule push;

    public void Push()
    {
        this.stack.Push(null);
        this.list.Add(null);
        Assert.AreEqual(list.Count==0, stack.IsEmpty);
        Assert.AreEqual(list[list.Count-1], stack.Peek());
    }
    ...
}

Step 3: Creating the non-terminal rules

From this step, the PGF provides the "classic" non-terminal rules and helper classes to create them (Rules) that makes the rest of the implementation straightforward:

public class StackFixture
{
    ...
    IRule push, pop, peek;
    IRule guardedPop, guardedPeek;
    IRule empty, nonEmpty;
    IRule stackRule;
    IRule stackGrammar;
    ...

    // returns true if stack is empty

    public bool IsEmpty()
    {
         return this.stack.IsEmpty;
    }

    public void CreateGrammar()
    {
        push = Rules.Method(new DefaultMethodDelegate(Push));
        pop = Rules.Method(new DefaultMethodDelegate(Pop));
        peek = Rules.Method(new DefaultMethodDelegate(Peek));

        // gard( pop, InvalidOperationException)

        guardedPop = Rules.Guard( pop, 
           typeof(InvalidOperationException) );
        // gard( pop, InvalidOperationException)

        guardedPeek = Rules.Guard( peek, 
           typeof(InvalidOperationException) );

        nonEmpty = Rules.Alt( push, pop, peek); // push | pop | peek

        empty = Rules.Alt( push, guardedPop, guardedPeek);
 
        stackRule = Rules.If(new ConditionDelegate(IsEmpty), 
               empty, nonEmpty); // if(IsEmtpy) empty else nonEmpty


        stackGrammar = Rules.Kleene(stackRule); // stackRule*

    }
}

Step 4: Creating a grammar and executing a production

In order to simplify our lives, we make StackFixture inherit from the Grammar class (which implements IGrammar) provided by the PGF. This class takes care of setting up the production factory and launching productions. Of course, this part of the framework can be easily customized and extended to plug in into your existing test automaton (MbUnit, NUnit, csUnit, ...).

public class StackFixture : Grammar
{
    public StackFixture()
    { 
        this.CreateRules();
    }
    public void CreateRules()
    {
        ...
        // required for Grammar

        this.StartRule = this.stackGrammar;
    }
}

A production can then be executed by launching the Produce method:

StackFixture fixture =new StackFixture();
fixture.Produce();

Want some more?

Other applications of the PGF and news about it can be monitored through my blog.

Conclusion

Production Grammar Framework is an effective tool to create and implement production grammar. Production grammar are used to model the complex behavior of applications and automate the creation of complex test cases. In fact, you could easily reuse your existing Unit Test cases with a production grammar! In a near future, PGF will be part of MbUnit.

Possible application of production grammars are:

• database testing,
• data generation for user input testing,
• unit test case generation using CodeDom,
• etc...

The quiz question: How does this relate to model based testing?

References

1. Using Production Grammar for Software Testing, Emin Sirer and N. Bershad.
2. Using Oracles in Test Automation, Douglas Hoffman.
3. Model Based Testing page, Harry Robinson.
4. Test Driven Development in C#, Chapter 2, James A. Newkirk & Alexei Vorontsov.