A | B != B | A about cats-parse HOT 12 CLOSED

@johnynek thanks, I will rewrite my code. It's a very useful advice.

from cats-parse.

While it is true that | is not commutative (a.backtrack | b.backtrack would be), having an infix operator is very nice.

Do you have any other suggestions?

from cats-parse.

maybe | would act like oneOf.

I just write graphql schema parser.
Parser2.scala.
there are some user experience to share:

1. need insert lots of whitespaces, maybe it's a good idea to create ParserContext, just like fastparse to handle whitespaces.
2. so much backtrack, and ? always need backtrack. maybe it's my code fault, there would have nice way to avoid using so much backtrack.
3. P[A] ~ (P[B].surround(whitespaces).backtrack.? ~ P[C].surround(whitespaces).backtrack.?) will read whitespaces twice when P[B] fails. but I don't know how to avoid.

from cats-parse.

PEGs use / for their non-commutative "or" for this reason - would that fit here?

from cats-parse.

Sorry I'm slow to reply on the weekend.

You definitely don't always need backtrack with ?. I'll rewrite some of your examples without backtrack and it might give you a feel for how to do it.

A big design property of this library is to encourage you to write parsers avoiding backtracking since that can easily result in accidental exponential complexity and also it generally results in poor descriptions of what went wrong.

That said, we could probably do with better educational materials to help people get started.

from cats-parse.

Also note | does act like oneOf. It is a synonym. oneOf is also not commutative, it matches left to right.

from cats-parse.

@johnynek thanks. And I'm sorry that I misunderstand the usage of |. It's good.

from cats-parse.

intuitively, i'd expect | to be commutative, too and therefore rename it to /. or is this a problem concerning operator precedence?

from cats-parse.

related to #184

from cats-parse.

While / is a good suggestion, the cost of breaking compatibility is significant... I can imagine adding / as another synonym of orElse but then we have three equivalent methods: orElse, / and |.

I'd like to take it a bit slow.

from cats-parse.

Hey @timzaak you have quite a bit of nice parsing code. One thing you don't seem to be using is "soft products", A normal product a ~ b will have an arresting failure if a parses and b has any failure at all... So, once a parses you expect b MUST come next. A soft product only fails if at least one has an arresting failure. So, a.soft ~ b will not be an arresting failure if a parses but b has an epsilon error (it fails to parse without a partial parse).

So, for instance:

pa ~ (pb.surround(whitespaces).backtrack.? ~ pc.surround(whitespaces).backtrack.?)

we can write instead as:

val hasB = pb ~ (whitespaces.soft *> pc).?
pa ~ (whitespaces.soft *> (hasB | pc)).?

So, now, we are very precise in the backtracking: only over the whitespace part. We are not erasing an arresting error as we did above: see pb.surround(whitespaces).backtrack what if you hit something in pb that could not parse: an arresting failure indicates a partial parse which we generally strive to be a real syntax error. By backtracking there, we are hiding from the user the real cause of the problem and presenting them with a confusing error when instead we wind up hitting the None branches in ?. This is the key goal of avoiding backtracking: it very easily hides the true syntax error from the user.

Does this help @timzaak ?

from cats-parse.

@johnynek thanks again, I rewrite the code, and it looks good to me now.

from cats-parse.