[antlr-interest] Tree Transformation, can problem be solved easily with ANTLR??

Terence Parr parrt at cs.usfca.edu
Tue Jul 4 08:49:57 PDT 2006


On Jul 4, 2006, at 7:06 AM, Daniel Shane wrote:

> Hi!
>
> I have nearly finished my new Lucene query builder using ANTLR, and  
> it works like a charm, in fact I'm about to release it to the  
> Lucene community, but I have one case that I cant seem to resolve  
> easily. Maybe its just because I dont have that much experience in  
> tree transformations, but here is the problem.
>
> I have an operator, call N_PROXIMITY, which takes the form "/n"  
> like /1, /12, /200 etc... and this operator is binary (takes 2  
> operands).
>
> If someone enters this :
>
> A /1 B /2 C /3 D
>
> I would like ANTLR to reorder the priority to this :
>
> (((A /1 B) /2 C) /3 D)
>
> Meaning that the lowest numbers have the highest priority.
>
> If this was the query :
>
> A /3 B /2 C
>
> This would be the result :
>
> (A /3 (B /2 C))

Hi...thank gawd somebody is fixing that ridiculously bad parser in  
lucene!!!!!

i've only got a few seconds, but sounds to me like you really need a  
sem pred and oddly enough left recursion

expr : {something smart here}? expr '/' INT expr
        | term
        ;

that predicate will need to look past a term and see the next  
operator.  For examle

A /2 B /1 C

the pred should scan past A as LA(1) and see the operator value.  I  
did a trick with recursion levels to do left recursion 10 years ago  
but can't remember.  seems with unfixed priority levels this could be  
bad actually.  ok nevermind.

Try building a data structure that tracks the list of operators  
(tracking operands) and then sorts them.  *then* build a tree quickly  
from the operands pointed to by the operators.  Might be simpler than  
transforming a tree.

Ter



More information about the antlr-interest mailing list