On Jul 13, 2010, at 1:54 PM, bion oren wrote: > So, I've been debugging ANTLR's NFA to DFA conversion and looking into how > that's done theoretically with powerset construction, and I had an idea that > should allow generating left recursive grammars. > > Currently, the generated DFA (org.antlr.runtime.DFA) checks if the current > state is an accept state. If it's not, it looks for a valid transition from > the current state. Why wouldn't you want to look for transitions as long as > possible and then, when there are no valid transitions, check if you arrived > at an accept state?
Hi Bion, I believe that the DFA does look for valid transitions as long as possible to get the longest match. > > If you can do that, then you should be able to allow self references in the > DFA (nodes that can transition to themselves). And, if the start node can > transition to itself, and other nodes can transition to the start node, you > can allow left-recursive grammars. > > Unless I'm missing something...? Left version is in the NFA conversion not in the resulting runtime DFA. Not sure that this is very clear from the code but I'm working on the academic paper as we speak. I'll be submitting it in the fall. it should prove illuminating T _______________________________________________ antlr-dev mailing list [email protected] http://www.antlr.org/mailman/listinfo/antlr-dev
