Diverges with sepEndBy from parser-combinator

[tryzniak]

Hello. Thank you for this great library.

I think I found a bug. The grammar below diverges if I use default sepEndBy from parser-combinators:

-- Does not work, but sepEndBy only requires an Applicative instance and we have it
grammar' = rule $ sepEndBy (satisfy (== OpenBracket)) (satisfy (== Dot))

-- but with this one everything is ok
sepEndBy :: Prod r e t a -> Prod r e t b -> Prod r e t [a]
-- btw sepBy can come from parser-combinators, and still no problem here
sepEndBy p sep = sepBy p sep <* optional sep

[ollef]

It looks like sepByEnd is implemented using recursion, which results in an infinitely large production when used with Earley. Earley only supports finite grammars, and recursion (other than many and some which are special-cased) needs to be done with rule. So this is a known limitation. It's a bit unfortunate that it seems like parts of the parser-combinators library can't be used because of this limitation, but I don't see any way around it.

The reason your implementation of sepByEnd works is that sepBy is implemented using many.