[Haskell-cafe] Parser left recursion

[Martin Drautzburg]

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