[antlr-interest] a left recursive walker rule
Bryan Ewbank
ewbank at gmail.com
Mon Jul 17 08:20:47 PDT 2006
> "��� Jigang (Robert) Sun" <sunjigang1965 at yahoo.com.cn> wrote:
> Hi,
> I have a rule in tree walker, which is left recursive: A : (A|B)+ C ,
>
> so I am trying to eliminate it
> ...
I think this matches the same regex:
A : ( (B)+ (C)+ )+ ;
This is more intuitive than anything else, by exploring the strings generated;
it therefore might be wrong (I didn't test it rigorously), but it might be good
place to start explorations.
Look at the strings generated by "A : (A|B)+ C", assuming B and C are
terminals: "A" must, in any final application, generate "(B)+C"; and "A"
itself ends with "C", so "B(C)+" is generated by recursion.
Hope I didn't miss something, and hope this helps a bit,
- Bryan
More information about the antlr-interest
mailing list