The Applicative versions of sepEndBy and sepEndBy1 cause infinite loops with Earley

[chowells79]

Main.hs:

import Text.Earley
import Control.Applicative.Combinators

main :: IO ()
main = print $ fullParses (parser grammar) "a;a"

grammar :: Grammar r (Prod r () Char String)
grammar = return $ sepEndBy (token 'a') (token ';')

sepEndBy-bugreport.cabal:

cabal-version:      3.4
name:               sepEndBy-bugreport
version:            0.1.0.0

executable sepEndBy-bugreport
    hs-source-dirs:   .
    main-is:          Main.hs

    build-depends:    base >=4 && <5,
                      Earley ==0.13.0.1,
                      parser-combinators ==1.3.0

This program loops forever. Replacing sepEndBy with sepBy makes it terminate. sepEndBy1 loops, sepBy1 does not. Note that the actual input to parse doesn't matter - the issue happens whenever sepEndBy or sepEndBy1 occurs within the parser.

After consulting with some other people, our best guess is that the problem is that generating an Earley parser requires exploring the entire parse tree, broken only by explicit recursion markers. The Prod type in Earley provides implementations of some and many which creates those explicit markers, so working in terms of them will succeed. sepBy and sepBy1 are implemented in terms of many, so they work with Earley. But sepEndBy and sepEndBy1 do not use some or many, and as a result they create infinite parse trees. At least, that's the guess.