ixml and operator precedence grammars (was: Re: a surprising whitespace-related ambiguity)

"C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com> writes:

> ...
> (1) Given an ambiguous context-free grammar G and a rule R which
> chooses, for any ambiguous sentence in L(G), one of the possible parse
> trees, under what circumstances is it possible to create an unambiguous
> context-free grammar G' such that (a) L(G') = L(G) and (b) the parse
> trees produced by G' are compatible with those produced by G?  
> ...
>
> (2) A more concrete formulation of the question: given a yacc grammar G
> with some operator-precedence and -associativity declarations, can we
> construct an unambiguous grammar G' that accepts the same sentences and
> produces compatible parse trees?

For further discussion of these questions, interested readers (should
any exist) are directed to a working paper at [1] and related materials
in the same Github repository.  (Cut to the chase: I do not yet know a
way to model, in an unambiguous ixml grammar, the ambiguity resolution
behavior of a yacc or CUP parser using operator precedence rules.  Some
cases work, some have thus far eluded me.)

[1]  https://github.com/MLCD-code/Alloy-XML/blob/main/docs/bop-pop-sop/bop-sop-pop.org


For those interested in seeing ixml succeed as a tool for working with
arbitrary real-world formats, the questions identified above may be
important, since so many real-world languages are de facto defined using
a yacc or yacc-style parser.

One way to make such languages tractable for ixml would be a pragma
instructing the ixml processor how to resolve ambiguities.  But at the
moment, I don't even see a way to answer a third question of possible
interest:

(3) Can the ambiguity-resolution behavior of yacc and similar tools
guided by operator-precedence rules be formulated in a way that does not
appeal to a procedural description of LR parsing but relies instead only
on properties of the grammar rules or of the competing parse trees and
would be intelligible in the context of an Earley parser, a GLL parser,
or any parser using a general parsing algorithm for context-free
grammars?

-- 
C. M. Sperberg-McQueen
Black Mesa Technologies LLC
http://blackmesatech.com

Received on Friday, 22 March 2024 17:56:20 UTC