Parser combinator libraries, like our very own miniparsec, are often vulnerable to left-recursion:
Expressions with left recursion cannot be encoded by recursive descent parsers and will diverge.
Let's suppose we had the parser:
bad = bad *> char 'a' <|> char 'b'
This could be interpreted as matching a regex like ba*, but using a recursive descent algorithm it will evaluate bad by immediately evaluating... bad. Oops! In order for parsers to be productive, they have to have consumed some input before they recurse again.
Commonly, the grammar can be factored to remove left-recursion, but this exposes implementation details and complicates the grammar, so ideally we could avoid that... I'll have a think.
Parser combinator libraries, like our very own
miniparsec, are often vulnerable to left-recursion:Let's suppose we had the parser:
This could be interpreted as matching a regex like
ba*, but using a recursive descent algorithm it will evaluatebadby immediately evaluating...bad. Oops! In order for parsers to be productive, they have to have consumed some input before they recurse again.Commonly, the grammar can be factored to remove left-recursion, but this exposes implementation details and complicates the grammar, so ideally we could avoid that... I'll have a think.