Visitor Pattern for parseTreeNodes

May 26, 2010 at 5:15 PM
Edited May 27, 2010 at 1:35 PM

Hi guys,

I'm very exited with this project. I've used JavaCC and SableCC and this new way of defining Grammar is very interesting.

I'm now trying to navigate through the Concrete Syntaxe Tree (parseTree). I just can't find any AcceptVisitor for the default generated tree. Creation of classes for every Non-Terminal in order to use the ASTNode feature is a bit harsh. Is there a way to simplify the process of visiting all the default generated CST ?

Thx

May 27, 2010 at 4:29 PM

The visitor pattern is just a traversal of the tree where it calls some method (e.g., "visit") on each node.  The visit method is the method that actually processes the node to do what you want.  So why not use just a generic pre-order traversal of the tree and process each node as you please?  (It's the same thing, just not necessarily the "visitor pattern".)

public static IEnumerable<ParseTreeNode> PreOrder(this ParseTreeNode root)
{
   var stack = new Stack<ParseTreeNode>();
   stack.Push(root);

   while (stack.Count > 0)
   {
      var node = stack.Pop();
      yield return node;

      var children = node.ChildNodes;
      // Push children on in reverse order so that they will
      // be evaluated left -> right when popped.
      for (int i = children.Count - 1; i >= 0; i--)
      {
         stack.Push(children[i]);
      }
   }
}

And then you could use this like:

ParseTree parseTree; // Get your parse tree

ParseTreeNode root = parseTree.Root;
foreach(var node in root.PreOrder())
{
  // Process here -- probably "switch" based on token name
  // or whatever you want.
}

Brian

May 27, 2010 at 5:55 PM
Edited May 27, 2010 at 6:02 PM

Hi Brian,

Thanks for the quick answer,

your solution works but I realy wanted to use the Visitor Pattern :). In fact, I added an AcceptVisitor() Method to the ParseTreeNode class and created an interfance ICstVisitor to a new file in Parsing.Parser ICstVisitor.cs. Why not add thoses changes to the project, simple and friendly solution ? Unless there is a specific design...

Here's the code:

ICstVisitor

 

    public interface ICstVisitor
    {
        void BeginVisit(ParseTreeNode node);
        void EndVisit(ParseTreeNode node);
    }

 

AcceptVisitor() (In ParseTree.cs - ParseTreeNode class)

 

    //Visite all the ParseTree nodes.
    public virtual void AcceptVisitor(Irony.Parsing.ICstVisitor visitor)
    {
        visitor.BeginVisit(this);
        if (ChildNodes.Count > 0)
            foreach (ParseTreeNode node in ChildNodes)
                node.AcceptVisitor(visitor);
        visitor.EndVisit(this);
    }

 
 
 


 

May 27, 2010 at 8:58 PM

Why do you want to work with the parse tree when you really should be working with the abstract tree?  It seems that with everything that's already built in to the compiler kit (e.g. processing of binary operations) that you're only left to take care of those things that are really specific to your language.  I ask this somewhat out of ignorance.  I'm to the point in my language where I think I'm about ready to create all my visitors, so I'd like some more understanding on this if anyone has the time.

Thanks

AJG

May 27, 2010 at 9:25 PM

Hi aaron,

for my projet I only needed to count a number of specific expression. I didn't want to create all the possible type of nodes and do the childnodes management. So, a simple visitor for the parseTree saved me a lot of time and testing. But if you are on a big project, then you realy should work with the AST and all the relational information between the nodes (like functionCall targets).

Visitor for CST is still usefull for a language prototype. Well, it was usefull for me.

Dan.

May 28, 2010 at 3:30 PM
Edited May 28, 2010 at 5:15 PM

The AST is only really useful if you are wanting / needing to *EVALUATE* an expression. If you are just needing to do something based on the structure of the parsed tokens, then all you need is the parse tree.

For example, tools like a code colorizer or intellisense need only the parse tree. The code colorizer only cares if a specific word was parsed as a comment, identifier (variable), constant, function call, etc. It doesn't care about actually executing the function call, or evaluating the value of the variable. It just wants to know what to color green, blue, cyan, etc. Likewise, intellisense just wants to keep a list of all of the keywords in your language along with identifiers, function names, etc. that the user has already created. Once again, it doesn't care about evaluating these statements; it just wants to be able to find specific token types.

Personally, I am using about two dozen different AstNode classes since the entire purpose of including Irony in the project was to evaluate various expressions!

Brian

(Sorry about the "blob-like" paragraph. CodePlex seems to be going a little crazy this morning by removing the spacing...) -- FIXED!