We have encountered the same issue when developing an SQL parser. Basically, my takeaway was that parsers such as many and choice are mostly useless if we want to produce a precise error report. Perhaps there is a way to make it work, I’m not super familiar with various parsing techniques, so I’ll explain what we did instead.

We had multiple variations of the problem you describe here, e.g. when parsing arithmetic expressions, or handling joins and subqueries. Our strategy was to abandon many and choice. Instead, we would “commit” to a parsing path based on the next token. In your example grammar, if the next token is b, we’ll commit to parsing the pair bc. If that fails, we’ll emit an error. If that succeeds, we’ll try to parse another bc if the next token is b. I believe that this technique is called “lookahead”.

To make it work, we introduced two additional parsers. The most important one is called switch. Let’s see an example:

switch([
  {char(?b), char(?c)},
  {char(?d), char(?e)},
])

This will parse bc or de, returning a proper error if the second char is invalid. Basically the switch parser commits to the given “branch” if the first parser in some tuple succeeds. If the rest of that branch errors, that error is returned by the switch parser. If no branch can be selected, the parser will return a generic error (similar to choice). If the parser succeeds, it will emit {result_of_the_first_parser, result_of_the_second_parser}

Now in your example we don’t want to return an error if no branch can be selected. Instead, we want to just stop parsing. To make this happen, we added the support for the :else clause, and introduced another parser called noop which always succeeds consuming nothing from the input. So parsing bc or nothing can be now expressed as:

switch([
  {char(?b), char(?c)},
  {:else, noop()}
])

And now, we can parse zero or more bc pairs as:

defp bc_pairs do
  switch([
    {char(?b), sequence([char(?c), lazy(&bc_pairs/0)])},
    {:else, noop()}
  ])
end

The emitted term will be a bit weird, something like:

{?b, [?c, {?b, [?c, nil]}]}

The final nil is emitted by the noop parser. This can be transformed into a list (e.g. ["bc", "bc", ...]) with the map parser.

I’m not sure if there’s a more elegant way, but this is what we did, and it worked fine. The code was definitely more complicated than the naive approach with many, but it was still understandable. Most importantly, our error reports were much more precise and informative.

For completness, we also wrote a parser called choice_deepest_error, which would work like a choice (aka one_of):

choice_deepest_error([
  parser1(),
  parser2(),
  ...
])

This parser emits either the result of parser1, parser2, etc. If no parser succeeds, it returns the error from the parser that consumed most of the input. I personally wasn’t a fan of this approach, because I found it hard to reason about. The “deepest error” isn’t necessarily the correct error. So personally I prefer the lookahead technique.

So many() being “zero or more” essentially means this is an optional match. Your goal seems to be making it clear that either parsing ?d was the issue if many() was indeed meant to be empty, or parsing the many() step failed for some reason. So how about:

either(
  sequence([
    many(
      sequence([
        char(?b),
        char(?c),
      ])
    ),
    char(?d)
  ]),
  char(?d)
)

Which will communicate the two different states explicitly to the parser. If both branches fail the error can communicate both expectations instead of just one.

Thanks for thinking it through.

It’s possible that I am missing something in what you’re saying — I feel I am quite close to the problem and that has its own challenges but it seems to me that the focus on the zero-or-more semantics of many here is possibly a misdirect.

If we imagine a parser like:

program = many(elixir_statement)
elxir_statement = choice([case_expr, for_expr, def_expr, with_expr, …])
case_expr = sequence([literal("case"), expr, literal("do"), …, literal("end")])
# and so on

if the input is

case x# do … end

then the case_expr will fail but it’s not the case that for_expr, with_expr, def_expr or anything could match. From the moment it parsed "case " there was no other valid option and something is wrong with the input.

So the case_expr fails, causing the choice to fail and that rolls up into the many which expects its child parser to fail at some point because it treats that as “end of sequence” and then it returns success.

My problem is how to differentiate between the child parser of many failing in the expected “end of sequence” case or the unexpected “malformed choice” case because the error is different in each.

It seems Saša & co. didn’t attempt to solve this but rather worked around it through writing parsers differently.

Looking at your suggestion it seems to me we don’t want to attempt char(?d) because the input is invalid and char(?d) cannot match. It might be that some of these errors could be recovered to continue parsing (in my example of a # in an expression we could clearly attempt to continue parsing since the structure is sound but in other cases, it may not be). What I am trying to do is report the right error (i.e. we need to bubble an error out of many when that’s not its typical behaviour).

Thanks.

Matt