[antlr-interest] RE: cgram

mzukowski at yci.com mzukowski at yci.com
Tue May 7 12:39:17 PDT 2002 

> It looks like you've done this by slighlty changing the parser.
> Am I right? Or have I misunderstood?
> 
> What I was expecting to do was to use your GnuCTreeParser to 
> create the
> AST, write my own functions which manipulate the AST, and 
> then use your
> GnuCEmitter to tranlsate back to source code. 
> 
> I think I need some functions for pulling apart and putting 
> together your
> AST. Is this a sensible approach?
>

Excellent question.  I keep forgetting that people are going to look at this
toolkit who aren't familiar with antlr.

You could in fact write your own routines to manipulate the AST, but there's
a better way.  You'll notice that I subclassed GnuCTreeParser, not
GnuCParser.  The tree grammar itself defines the exact structure of the
trees, which makes it easy to pick and choose the structures you want to
deal with.  

Tree grammars are a powerful abstraction in antlr.  The argument goes: why
write a parser by hand when you have a grammatical tool like antlr?  Now
that you're manipulating trees why write it by hand when you can use antlr's
tree grammars.  Tree parsing is special because a tree has two
dimensions--child and sibling.  For this reason it is limited to k=1.  When
I created the C AST I took care to make the tree well structured and easily
parsable.  Studying the parser and the tree parser side by side you will see
the latter to be much more clear and concise.

A tree grammar can also give you the proper context of the tree structure
you are analyzing.  For instance if you wanted to do something special with
only those expressions used in a case statement, you could write some rules
like:

statementBody:
...
#( "case" caseExpr (statement)? )
...

caseExpr: expr {your analysis here of the case expr...;} ;

Now only expressions that are for the case decision will ever make it
through caseExpr, and you can do your special analysis in that rule.  

The reason I created GnuCTreeParser was to have a grammar to subclass from.
Each pass of a transformation system would be a separate subclass of it.
The first passes are usually just for analysis, and they have the option
"buildAST=false" so they don't alter the tree.  Transformation passes have
the option "buildAST=true" since they are changing the tree.  The chain of
transformations is controlled by you feeding the resulting tree into the
next stage, the final stage probably being to the GnuCTreeEmitter for source
output.  During development you can feed the resulting tree into
GnuCTreeParser after every stage to detect malformed trees.

Do you have any more specific examples of analysis or transformation that I
can try to explain in terms of tree grammars?  If so I would very much like
to continue this discussion on the antlr-interest at yahoogroups.com list or in
the antlr forum http://www.jguru.com/forums/ANTLR.  I suspect there are
others out there with similar questions.  It might make a good FAQ entry.

Monty
www.codetransform.com

> -----Original Message-----
> From: Sebastian Danicic [mailto:mas01sd at gold.ac.uk]
> Sent: Tuesday, May 07, 2002 10:33 AM
> To: mzukowski at yci.com
> Subject: RE: cgram
> 
> 
> Dear Monty,
> 
> It looks like you've done this by slighlty changing the parser.
> Am I right? Or have I misunderstood?
> 
> What I was expecting to do was to use your GnuCTreeParser to 
> create the
> AST, write my own functions which manipulate the AST, and 
> then use your
> GnuCEmitter to tranlsate back to source code. 
> 
> I think I need some functions for pulling apart and putting 
> together your
> AST. Is this a sensible approach?
> 
> thanks again
> 
> Sebastian
> 
> 
> 
> On Tue, 7 May 2002 mzukowski at yci.com wrote:
> 
> > Sebastian, with your permission I will post the following to the
> > antlr-interest list.  If you decline permission I will 
> simply post the
> > question and answer without references to your name, email 
> or website.
> > 
> > > From: Sebastian Danicic [mailto:mas01sd at gold.ac.uk]
> > > Would it be possible for you to show me a little example 
> of a simple
> > > program transformation?
> > > 
> > > A good one would be something that converts:
> > > 
> > > if (B) s1 else s2 => if (B) s2 else s1
> > > 
> > > or something equally simple. Just so I understand how to 
> > > manipulate the AST.
> > 
> > I would make an antlr "grammar subclass" of GnuCTreeGrammar 
> with just this
> > method in it, with the "if" section modified as below.  The 
> subclass must be
> > marked with the "buildAST=true" option.  
> > 
> > The entire statementBody method must be here, you can't 
> just subclass an
> > alternative.  Of course if you had a need to, you could refactor
> > GnuCTreeGrammar into one more suited to your needs.  For instance
> > statementBody could reference a few rules, one for plain 
> statements, one for
> > iterations, one for jumps, one for labeled statments, one 
> for selection
> > statements.  So if you were doing lots of different passes 
> that just looked
> > at iteration statements you would only need to subclass the
> > iterationStatement rule.  
> > 
> > For the "if" alternative I turned off the automatic tree 
> building since I
> > want to construct the tree in a different order.  If I were 
> simply modifying
> > the nodes in place (changing their text) then I would let 
> antlr build the
> > tree.  Once a tree is built, however, it is hard to swap 
> those nodes around
> > because nodes contain within them links to their firstChild 
> and nextSibling.
> > A common mistake is to let antlr build the tree and then 
> swap two nodes
> > accidently creating a circular structure.
> > 
> > Then I labeled all the elements I want for my tree.  Note 
> that antlr does
> > not have any positional notation for nodes--you can't say 
> #1, #2, etc.
> > Finally I construct the tree as I want it, in this case 
> with the statements
> > switched. 
> > 
> > statementBody
> >         :       SEMI                    // Empty statements
> > 
> >         |       compoundStatement       // Group of statements
> > 
> >         |       #(NStatementExpr expr)                    
> // Expressions
> > 
> > // Iteration statements:
> > 
> >         |       #( "while" expr statement )
> >         |       #( "do" statement expr )
> >         |       #( "for"
> >                 expr expr expr
> >                 statement
> >                 )
> > 
> > 
> > // Jump statements:
> > 
> >         |       #( "goto" expr )
> >         |       "continue" 
> >         |       "break"
> >         |       #( "return" ( expr )? )
> > 
> > 
> > // Labeled statements:
> >         |       #( NLabel ID (statement)? )
> >         |       #( "case" expr (statement)? )
> >         |       #( "default" (statement)? )
> > 
> > 
> > 
> > // Selection statements:
> > 
> >         |       #(! ifst:"if"
> >                     e:expr s1:statement  
> >                     ( el:"else" s2:statement )?
> >                  ) {##=#(ifst, e, s2, el, s1);}
> >         |       #( "switch" expr statement )
> > 
> > 
> > 
> >         ;
> > 
> > Monty
> > 
> > > -----Original Message-----
> > > From: Sebastian Danicic [mailto:mas01sd at gold.ac.uk]
> > > Sent: Tuesday, May 07, 2002 1:53 AM
> > > To: mzukowski at bco.com
> > > Subject: cgram
> > > 
> > > 
> > > Dear Monty,
> > > 
> > > I'm a member of the VASTT 
> (http://www.brunel.ac.uk/~csstmmh2/vast/).
> > > We would like to write a slicer and other program 
> > > transformations for C
> > > using your system.
> > > 
> > > Would it be possible for you to show me a little example 
> of a simple
> > > program transformation.
> > > 
> > > A good one would be something that converts:
> > > 
> > > if (B) s1 else s2 => if (B) s2 else s1
> > > 
> > > or something equally simple. Just so I understand how to 
> > > manipulate the
> > > AST.
> > > 
> > > Thank you very much in advance for your help.
> > > 
> > > Sebastian Danicic (http://www.mcs.gold.ac.uk/~mas01sd/)
> > > 
> > > 
> > 
> 
> 

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

More information about the antlr-interest mailing list