Open dominiccooney opened 14 years ago
Interestingly this equivalent grammar succeeds:
(gg-grammar
(start n := xs eof -> n)
(xs
n := xs ?x -> (1+ n)
| -> 0))
I think this is a bug in the left-recursive PEG algorithm; pinged gurus at https://lists.csail.mit.edu/pipermail/peg/2009-November/000244.html
I think the best thing to do is to disallow nullable left-recursive rules, probably by warning about them and failing if they're activated.
After adding some tracing, the problem is the heuristic in gg-recall that doesn't activate rules which aren't involved in the recursion. In the first grammar above, rule a is not involved in the recursion (only a is) and so gg-recall eagerly memoizes failure for it.
If that heuristic is relaxed, the parser succeeds and computes the right result. However this has bad downstream effects when a is right-recursive. Laurence Tratt has drafted a paper about this at https://lists.csail.mit.edu/pipermail/peg/2009-November/000248.html
This grammar fails to parse "aaaa":
The intent is similar to this grammar:
It seems nullable left-recursive rules fail, perhaps because they're not "making progress."