Hello PEG-ers, I think I've found a problem with the algorithm for left-recursive rules in Warth, Douglass and Millstein's PEPM 2008 paper. If this is old news, sorry.
The bug is parsing this grammar: start := xs eof xs := xs x / (nothing) x := "x" This fails to recognize a sequence of "xxxx" etc. This equivalent grammar succeeds: start := xs eof xs := xs "x" / (nothing) The problem is RECALL. In the first grammar, when APPLY-RULE(x, 0) calls RECALL(x, 0), RECALL decides that x isn't involved in left recursion (there is no MEMO entry for x because we've never seen it before, but there is a HEAD for position 0--xs, but x is neither that head, nor involved with that left recursion) and RECALL returns failure for x. This is only an issue for nullable left-recursion. For non-nullable left recursion, RECALL doesn't find a HEAD entry for the position and RECALL replies "no result" instead of fail. It seems like RECALL should be more permissive for rules invoked by recursive rules. Is there any more recent work that I should be aware of that corrects this? Dominic
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
