Re: resolving ambiguity

If we had the "greedy by default" rule, as regular expression do, then the
first path <S><Left>ab</Left><Right>c</Right></S> wins because 'Left'
consumed as much as it could. While preventing ambiguous grammars does not
seem achievable, the rule could make a grammar more deterministic.

On Wed, 14 Apr 2021 at 14:52, Tom Hillman <tom@expertml.com> wrote:

> In fairness, I suggested it nervously, and only then as part of an
> approach for the input consumption discussion: I would prefer it if we
> leave the choice open.
>
> I think the answer to your first rule wins question is <S>(<a>a </a>)</S>..
> That is possibly because recursing into each non-terminal before handling
> its siblings is second nature to me because it mirrors the document order
> of XML trees ;)
>
> Tom
>
> _________________
> Tomos Hillman
> eXpertML Ltd
> +44 7793 242058
> On 14 Apr 2021, 01:42 +0100, C. M. Sperberg-McQueen <
> cmsmcq@blackmesatech.com>, wrote:
>
> On today’s call, Tom suggested that the spec might usefully say which tree
> should be returned, in case of ambiguity.
>
> I am nervous about this suggestion; I think that the choice of tree is
> better left open.
>
> "First rule wins" seems plausible enough when it applies, but I have not
> thought enough about it to know whether it always applies, whether it
> always provides a unique solution, or how to extend the Earley algorithm
> (or any of the other general algorithms) to keep track of such things in a
> way that would guarantee the selection of the correct tree. Consider this
> grammar:
>
> S: Left, Right.
> Left: "a", "b"; "a".
> Right: "b", "c"; "c".
>
> If I'm not mistaken, this has two parse trees:
>
> <S><Left>ab</Left><Right>c</Right></S>
> <S><Left>a</Left><Right>bc</Right></S>
>
> The first tree uses the first RHS for Left and the second RHS for Right.
> The second tree is the other way round. Does the "first rule wins"
> principle give an answer here? I suppose we can say that it's the choice of
> rules for 'Left' that matters, because 'Left' precedes 'Right'. And I guess
> that's what you meant.
>
> But consider:
>
> S: '(', a, s?, ')'.
> a: s?, 'a', s?.
> s: #20+.
>
> and the input string "(a )". Which of the parses is preferred by the
> first-rule-wins rule?
>
> <S>(<a>a </a>)</S>
> <S>(<a>a</a> )</S>
>
>
> Michael
>
> ********************************************
> C. M. Sperberg-McQueen
> Black Mesa Technologies LLC
> cmsmcq@blackmesatech.com
> http://www.blackmesatech.com
> ********************************************
>
>
>