Ambiguity happens; removing ambiguity from grammars tends to make them much more difficult to understand, and can affect their time performance. It’s also a brittle process. So rather than flat-out disallowing ambiguity, we need to disambiguate.
Alternation currently disambiguates with a leftmost-wins strategy. This is straightforward, but limiting; instead, we should have disambiguation strategies like “parse & produce all” with an Ambiguity type:
enum Ambiguity<T, U> {
case Left(Box<T>)
case Right(Box<U>)
case Both(Box<(T, U)>)
}
This could clearly then be disambiguated in the parse tree with -->. This is extremely flexible, as context available in the parse tree can enable disambiguation without complecting the grammar.
However, alternations performed in this way have significant drawbacks:
they always attempt both their branches, potentially causing exponential complexity in time;
they can double the size of the parse, potentially causing exponential complexity in space
So we might also want to make it convenient to filter at the point of alternation such that context which has been accrued thus far can prompt some other strategy. This is basically x >>- f with f disambiguating, but we might end up finding more convenient API to describe it than that.
Ambiguity happens; removing ambiguity from grammars tends to make them much more difficult to understand, and can affect their time performance. It’s also a brittle process. So rather than flat-out disallowing ambiguity, we need to disambiguate.
Alternation currently disambiguates with a leftmost-wins strategy. This is straightforward, but limiting; instead, we should have disambiguation strategies like “parse & produce all” with an
Ambiguitytype:This could clearly then be disambiguated in the parse tree with
-->. This is extremely flexible, as context available in the parse tree can enable disambiguation without complecting the grammar.However, alternations performed in this way have significant drawbacks:
So we might also want to make it convenient to filter at the point of alternation such that context which has been accrued thus far can prompt some other strategy. This is basically
x >>- fwithfdisambiguating, but we might end up finding more convenient API to describe it than that.