Re: ambiguity in XQuery grammar

Damien Fisher wrote:
> 
> Michael Dyck wrote:
> >
> > According to A.3 Precedence Order, InstanceofExpr is at precedence level 6
> > and AdditiveExpr is at level 8. Now, while the exact grammatical meaning of
> > the precedence table has never been given, my interpretation is that an
> > AdditiveExpr cannot have an InstanceofExpr as either of its operands. So
> > both of the suggested parsings are illegal, and in fact, the example query
> > has no legal parse.
> 
> I'm afraid I don't understand your interpretation of the precedence order.

It goes something like this:
   Let LHS ::= RHS be a production where LHS appears in the precedence table
   at level L.
   When 'Expr' occurs in RHS,
      nonterminals at precedence level < L are disallowed,
      nonterminals at precedence level > L are allowed.
   Whether nonterminals at precedence level == L are allowed is a little
   tricky. For instance, if RHS is a simple binary expression
       Expr op Expr
   then the left Expr can be a nonterminal at level L, but the right Expr
   can't (because "operators at the same level are evaluated from left to
   right").

> Unless I am totally mistaken, precedences do not state what are legal or
> illegal operands for an AdditiveExpr

They might, they might not. The problem is that the WG didn't say exactly
what the precedence table means. And the Note in A.3 indicates that they're
probably going to replace it anyhow, in which case this discussion is moot.
But hey, it's fun.

> -- that is the job of the AdditiveExpr rule.
> Precedences are used to disambiguate sentences of a language which
> have multiple possible interpretations under a given set of rules.

That's one possible interpretation.

> For example, 1+2*3 could be (in the absence of precedence information)
> interpretation as (1+2)*3 or 1+(2*3).  However, * binds more tightly
> than +, and so we are restricted to a unique interpretation.

But note that this restriction ensures that a MulitplicativeExpr can never
have an AdditiveExpr as either of its operands, which is what my
interpretation would indicate. In fact, I believe the two interpretations
are equivalent as long as the constructs involved are simple binary and
unary expressions. However, they diverge when constructs like
InstanceofExprs and FLWRExprs are added to the mix.

> AFAICT, the precedence order given in the standard does not disambiguate the
> above expression, which is legal according to the grammar.  The grammar
> explicitly says AdditiveExpr takes operands of type Expr, which includes
> InstanceofExpr -- if the standard did not want to include InstanceofExpr as
> a legal operand, then this would have been replaced by something like
> ExprExceptInstanceofExpr.

But doing so tends to bloat the expression grammar and make it harder to
read. I suspect this is what the WG was trying to avoid by using a
precedence table. However, it looks like they have resigned themselves to
the bloat ("a system of built-in precedence") in the interests of precision.

-Michael Dyck

Received on Thursday, 6 June 2002 02:49:06 UTC