Invent your own language… using Oslo Part II

Article
05/24/2009

Alsalam alikom wa ra7mat Allah wa barakatoh (Peace Upon You)

Part II: Consume the Abstract Syntax Tree
… Do some action! …

If you have not read Part I, we have created our first grammar to recognize this language:

 Send "D:\Reports\Templates\Regular.tmpl" to sm1@hotmail.com
Send "D:\Reports\Templates\Special.tmpl" to sm2@hotmail.com,sm3@hotmail.com

Visit here [Part I link] to find the reporter.mg file listing at the end.

In this post, we will explore how to compile/parse the generated tree programmatically. And we will dig a little bit one cool way to do .NET code generation works.

Create a new project (You can pick a console one for simplicity), Add Reference to:

C:\Program Files\Microsoft Oslo SDK 1.0\Bin\Microsoft.M.Grammar.dll and

C:\Program Files\Microsoft Oslo SDK 1.0\Bin\System.Dataflow.dll

Microsoft.M.Grammar.dll contains MGrammarCompiler which we will use to compile our .mg file into .mgx (just as we used mg.exe tool)

System.Dataflow.dll contains DynamicParser class which will be our starting point to parse the generated AST.

This is the compile function:

 private static void Compile()
{
    MGrammarCompiler compiler = new MGrammarCompiler();
    compiler.FileNames = new string[] { 
        @"C:\Users\HaythamAlaa\Documents\reporter.mg" };
    compiler.OutFile = "reporter.mgx";
    compiler.Execute(ErrorReporter.Standard);
}

Basically, we pass the fileName(s) and output file then just call Execute and you are done.

Then, we add a Parse method:

 private static void Parse()
{
    FileStream mgxFile = File.OpenRead("reporter.mgx");
    DynamicParser parser = DynamicParser.LoadFromMgx(mgxFile, 
                                "Basic.Languages.Reporter");
    object root = parser.Parse<object>(
            @"C:\Users\HaythamAlaa\Documents\reportsData.bundle", 
            null, ErrorReporter.Standard);
    IGraphBuilder graphBuilder = parser.GraphBuilder;

    Traverse(root, graphBuilder);

DynamicParser loads the mgx file we compiled earlier, and then we ask it to parse the bundle file… note that parser.Parse<object> object is obligatory (I believe this will be refactored in the release)

As all nodes returned of type object, parser provides an IGraphBuilder object that helps us traverse and query the AST.

Traverse method should just loop over all nodes (and sub nodes) and output their values.

Traverse is very straight forward. However, there is a couple of tricks we need to be aware of while traversing the tree…

First, here is the basic Traverse Method:
```
 private static void Traverse(object root, IGraphBuilder graphBuilder)
{
    if (root is string)
    {
        Console.WriteLine(root.ToString());
        return;
    }

    Console.WriteLine("->" + graphBuilder.GetLabel(root));

    foreach (object childNode in graphBuilder.GetSuccessors(root))
    {
        Traverse(childNode, graphBuilder);
    }
}
```
The output should be like this:
```
 ->Commands
->Send
D:\Reports\Templates\Regular.tmpl
->Emails
sm1@hotmail.com
->Send
D:\Reports\Templates\Special.tmpl
->Emails
sm2@hotmail.com
sm3@hotmail.com
```
First thing to notice, this is a simple Depth First Search (or Visitor Pattern as architects like to call it).

Second, The leaf nodes of the tree are all strings, the non-leaf ones can be of type SimpleNode or SequenceNode (or something else?) depending on how they were projected in MGrammar.

e.g:
```
 => Send{. . .};
```
Would produce:
```
 Send{
...


}
```
That will be parsed as SimpleNode

While,
```
 => Send[. . .];
```
Would produce:
```
 Send[
.....
]
```
And will be parsed as SequenceNode

I didn’t read any recommendation on when to use what… but I personally prefer to use {} when you are thinking of a Class and use [] when you are thinking of an Array… more of this will come later when we start generating code.

Third, GetSuccessor: This method can visit any node and iterate over its children. There is also GetSequenceElements and GetEntityMembers… probably what we want to do is something like this:

if (graphBuilder.IsEntity(root))

foreach (… graphBuilder.GetEntityMembers(root))

else if (graphBuilder.IsSequence(root))

foreach (… graphBuilder.GetSequenceElements(root))

… same thing for IsNode

Note the order of checking is important, (e.g IsSequence before IsNode) because a sequence node is also a “node”…
Let the fun begin, first, let’s declare a method that accepts a path and a list of emails as parameters,
```
 public static void Send(string reportPath, params string[] contacts)
{
    Console.WriteLine(reportPath);
    foreach (string str in contacts)
        Console.WriteLine("->" + str);
}
```
Now, we want to map every Send node into a method call with the right parameters…

We will use System.Linq.Expressions namespace [MSDN Link].

This namespace contains virtually all types of operations you can perform in .NET, Assignment, MethodCall, Lambda Expression, ArrayIndexing…. etc

2 things we are interested in for now, are MethodCallExpression (to be able to represent our Send method) and Lambda Expression to be able to compile into MSIL and actually run these instructions

Here is an example for this in action
```
 MethodCallExpression expression = 
    Expression.Call(typeof(Program).GetMethod("Send"),
    new Expression[] { Expression.Constant(path, typeof(string)),
                       Expression.Constant(emails, typeof(string[])) });
LambdaExpression lambda = Expression.Lambda(expression);
lambda.DynamicInvoke();
```
Expression is an abstract base class that contains static methods to instantiate all types of expressions.. here we call Expression.Call to create a MethodCallExpression.

It accepts a MethodInfo for the method you want to call…

and a list of parameters.

You can then call lambda.DynamicInvoke() to compile into MSIL and execute whatever expressions are inside…

Here is the full listing for creating the lambda expressions out of a passed node:

    1: private static LambdaExpression[] TraverseAndBuildTree(object root, 
    2:                                         IGraphBuilder graphBuilder)
    3: {
    4:   if (graphBuilder.GetLabel(root).ToString().ToLower() == "send")
    5:   {
    6:     IEnumerable<object> childs = graphBuilder.GetSuccessors(root);
    7:  
    8:     string path = 
    9:         graphBuilder.GetSuccessors(childs.First()).First().ToString(
   10:     List<string> emails = new List<string>();
   11:     foreach (object objContact in
   12:         graphBuilder.GetSequenceElements(childs.Last()))
   13:     {
   14:       emails.Add(objContact.ToString());
   15:     }
   16:  
   17:     MethodCallExpression expression = 
   18:       Expression.Call(typeof(Program).GetMethod("Send"),
   19:       new Expression[] { Expression.Constant(path, typeof(string)),
   20:           Expression.Constant(emails.ToArray(), typeof(string[])) })
   21:     LambdaExpression lambda = Expression.Lambda(expression);
   22:     return new LambdaExpression[] { lambda };
   23:   }
   24:  
   25:   List<LambdaExpression> expressions = new List<LambdaExpression>();
   26:   if (graphBuilder.IsSequence(root))
   27:     foreach (object childNode in 
   28:         graphBuilder.GetSequenceElements(root))
   29:     {
   30:       expressions.AddRange(
   31:           TraverseAndBuildTree(childNode, graphBuilder));
   32:     }
   33:   else if (graphBuilder.IsNode(root))
   34:     foreach (object childNode in 
   35:         graphBuilder.GetSuccessors(root))
   36:     {
   37:       expressions.AddRange(
   38:           TraverseAndBuildTree(childNode, graphBuilder));
   39:     }
   40:   return expressions.ToArray();
   41: }

25 – 40: We just traverse all nodes available and concatenate the lambda expressions into one big list.

6 – 15: We get the values of path and email parameters from AST.

17 – 22: We create the Call Expression.

You can then use this method like this:

 LambdaExpression[] lambdas = TraverseAndBuildTree(root, graphBuilder);
foreach (LambdaExpression lambda in lambdas)
    lambda.Compile().DynamicInvoke();

That’s it ! Spend sometime and play around with expressions ;)

Congrats, you’ve reached your 2nd Checkpoint!

The technique described here works well with simple languages, but once your language gets more complicated, you will need a more structured design (and hopefully an automated process) which we will explore in the next part.

Part I: Create the Grammar (What your users write).

Part II: Consume the abstract syntax tree (Do some action). [This post]

Path III: Compile your language into MSIL.

Invent your own language… using Oslo Part II

Additional resources