[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