On Sunday, 24. February 2013 16:04:11 Tillmann Rendel wrote:
Both approaches are essentially equivalent, of course: Before considering the very same nonterminal again, we should have consumed at least one token.
I see. Thanks So for the laymen: expr ::= expr "+" expr is a problem, because the parser considers expr again without having consumed any input. expr ::= literal pluses pluses ::= many ("+" expr) is not a problem, because by the time the parser gets to the rightmost expr is has consumes at least one "+". Instead of literal we can put anything which promises not to be left-recursive expr ::= exprNonLr "+" expr exprNonLr := ... As exprNonLr gets more complicated, we may end up with a whole set of nonLr parsers. I wonder if I can enforce the nonNr property somehow, i.e. enforce the rule "will not consider the same nonterminal again without having consumed any input". -- Martin