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? 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...? _______________________________________________ antlr-dev mailing list [email protected] http://www.antlr.org/mailman/listinfo/antlr-dev
