[antlr-interest] Advanced matching in Tree Parsers

Martin Probst mail at martin-probst.com
Fri Apr 15 08:28:45 PDT 2005


Hi,
First of all, thanks for your help Bryan and Monty.

I think I missformulated my email a little bit in the first place, possibly
because I wasn't sure what I wanted myself. It seems I can achieve what I
want implementing your comments but this seems to be quite a hassle.

What I really want to do is match patterns agains the tree. The difference
to how ANTLR is handling this is that I just want to check if the pattern
fits, and if it fits execute some action (e.g. rewrite the tree). If the
pattern is not matched I want to continue recursively through the tree
(recursion, e.g. whole new expressions, can occur only in well defined
places, don't have to match everything). 

This is about optimizing expressions, e.g. some expressions match a specific
pattern and can be rewritten to execute faster, but general translation is
done somewhere else. I really don't want to mix these two phases because I
guess it will create quite a mess, though I'm not yet sure about the
performance implications.

So I got some kind of a mismatch, ANTLR TreeParsers seem to be targeted at
requiring trees to match. I see three approaches for me:

1) Do it yourself
   e.g. by writing java code to traverse and match the tree. Possible, but
creates a lot of ugly code. Could also create a little language to write the
tree patterns in, but this really seems like reinventing the ANTLR tree
parser wheel.
2) Use semantic and syntactic predicates in front of rules
   e.g. ( treespec ) => match, creates ugly syntax and is possibly very slow
as matching is done twice. Doesn't look good to me at the moment.
2) Write ANTLR rules and catch exceptions
   e.g. 
   tryOptimizeSteps: 
     #( tree spec ); 
     exception catch [RecognitionException ex] {
       // return or something like that, or catch the exception in the
calling rule
     }
   I'm still not sure about how to make sure that ANTLR continues at the
correct point in the AST with the next rule, have to look into the code for
that.

Has anyone done something like this before? Can anybody report on possible
problems with one of these approaches?

Regards,
Martin

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org 
> [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Bryan Ewbank
> Sent: Thursday, April 14, 2005 7:27 PM
> To: ANTLR Interest
> Subject: Re: [antlr-interest] Advanced matching in Tree Parsers
> 
> Can you rewrite it with cascading predicates, thus?
> 
>    #( ROOT f:FIRST
>       ( { #f.myfield.equals(something) }? foundit:.
>          {
>             // foundit!  operate on it...
>          }
>       | missedit:.
>          {
>             // ROOT FIRST ..., but not what I wanted
>          }
>       )?
>    )
> 
> Or perhaps with a prepass that does something like:
>   #(ROOT f:FIRST
>      { if (#f.myfield.equals(something)) f->setType(FIRST_MATCH); }
>   );
> And a postpass, if necessary to revert FIRST_MATCH to FIRST.
> 
> On 4/14/05, Martin Probst <mail at martin-probst.com> wrote:
> > Hi all,
> > I have a problem with tree parsers. I'm trying to match 
> tree fragments 
> > in a tree parser. The problem is, we use a special AST node 
> type which 
> > carries lots of payload, and I have to match on that 
> payload in many 
> > cases. I'd like to use a semantic predicate within a syntactic 
> > predicate, but this doesn't seem to work:
> > 
> > E.g.
> > expr:
> >         ( #( ROOT f:FIRST { #f.myfield.equals(something) }? 
> . ) ) => 
> > #( ROOT FIRST . )
> >         | ...
> >         ;
> > 
> > This does not give an error, but it also doesn't assign 
> anything to #f 
> > and consequently results in a null pointer exception. Is 
> there a way 
> > to achieve what I want?
> > 
> > Regards,
> > Martin
> > 
> >
> 
> 



More information about the antlr-interest mailing list