Try later alternatives when earlier success can't complete parsing

[drhagen]

Under no circumstances will Parsita attempt later alternatives if an early alternative succeeds. This behavior, which is typical in parser combinators, can be unexpected.

from parsita import *

class FunctionParsers(TextParsers):
    id = reg('[a-z]+')
    function = id & '(' >> repsep(id, ',') << ')'
    expression_good = function | id
    expression_bad = id | function

FunctionParsers.expression_good.parse('a(b)').or_die()
# ['a', ['b']]

FunctionParsers.expression_bad.parse('a(b)').or_die()
# parsita.state.ParseError: Expected end of source but found '('
# Line 1, character 2
# a(b)
#  ^  

That is because consume returns a single result--in the case of the AlternativeParser, the first result found among the alternatives. The typical workaround is to always put the longest alternative first if multiple may match. This is annoying, counterintuitive, and for some complex grammars, hard to achieve. It would be better if Parsita would keep trying alternatives if it could not succeed.

The consume method would have to be rewritten into a generator where each alternative of a parsers argument is tried before failing. This is probably doable, but would be a pretty big change to the internals of Parsita.

Implementing this could lead to very bad performance in cases where the text could not be parsed. Parsita would have to explore every avenue before giving up, which may take a while. It is possible that this feature would require a packrat parser to be usable.

[drhagen]

An alternative to the generator design is to make a LongestAlternativeParser that tries all alternatives and returns the longest one. This should also play much nicer with the packrat parser.