Re: resolving ambiguity

On Tue, 2021-04-13 at 18:42 -0600, C. M. Sperberg-McQueen 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.  

[helpful examples gleefully elided]

[ok, not gleefully.]

I've been looking at Parsing Expression Grammmars (PEGs) lately, in 
which the parser explicitly tries the branches in a choice in order,
preferring the first match.

The advantage is eliminating many (all?) of this sort of ambiguity. The
disadvantage is that even with a "packrat" memoising parser such as
Earley, memory use can be higher.  A parsing technique called "pika"
which parses input from  right to left and bottom-up shows promise  but
obviously can't stream.

The notes for XML::Invisible say, "if an "any" group is given, the
first one that matches will be selected"  so there's at least  one
implementation that works this way (and is in fact built on top of the
Perl PEG implementation, Pegex)

https://en.wikipedia.org/wiki/Parsing_expression_grammar
pika:  https://arxiv.org/pdf/2005.06444.pdf
and pika code: https://github.com/lukehutch/pikaparser
PEG for JS:  https://pegjs.org/
Ed J.'s Invisible XML implementation on top of Pegex:
https://metacpan.org/pod/XML::Invisible

I'm not sure if this helps the discussion, except that (1) there's some
implementation experience with one particular choice, and (2) it might
be interesting to grammar geeks who have not been following PEGs :) I
admit when i first saw them  i started wondering about applications of
parsing expression grammars could help resolve ambiguities in hedge 
automata, but i'm  pretty sure i saw a fox in the hedge last night.

Liam

-- 
Liam Quin, https://www.delightfulcomputing.com/
Available for XML/Document/Information Architecture/XSLT/
XSL/XQuery/Web/Text Processing/A11Y training, work & consulting.
Barefoot Web-slave, antique illustrations:  http://www.fromoldbooks.org

Received on Wednesday, 14 April 2021 03:28:11 UTC