- From: Michael Dyck <jmdyck@ibiblio.org>
- Date: Sun, 21 Dec 2003 12:57:00 -0800
- To: www-ql@w3.org
Peter Coppens wrote:
>
> A.4 also contains
>
> "In the cases where a number of operators are a choice at the same
> production level, the expressions are always evaluated from left to right".
>
> Is this reflected in the EBNF? If so, I am not sure I understand how
> that is done.
No, you're right, it isn't reflected in the EBNF.
> To give a more common example: $v1 div $v2 * $v3. I assume this falls
> under : UnaryExpr ( ("*" | "div" | "idiv" | "mod") UnaryExpr )*,
> which I think is ambiguous without the "A.4" sentence.
According to the EBNF, it isn't ambiguous. The (unique) derivation tree
would be:
MultiplicativeExpr
|
+--------+--------+-------+-------+
| | | | |
UnaryExpr "div" UnaryExpr "*" UnaryExpr
| | |
$v1 $v2 $v3
But semantically, yes, you need the left-to-right rule in A.4 to know
how to evaluate it.
In fact, both the informal and formal semantics assume that they're
working on an "operation tree" like this:
MultiplicativeExpr
|
+---------+--+-------+
| | |
MultiplicativeExpr "*" UnaryExpr
| |
+--------+--------+ $v3
| | |
UnaryExpr "div" UnaryExpr
| |
$v1 $v2
In terms of the XQuery processing model, parsing the query ("into an
internal representation called the operation tree") includes both
parsing it according to the EBNF (resulting in trees such as the first)
plus an unstated step in which multi-operand expressions are
restructured into binary expressions (resulting in trees such as the
second).
The XQuery grammar could have been written to generate the second kind
of tree directly, by using rules such as
MultiplicativeExpr ::= MultiplicativeExpr ("*"|...) UnaryExpr
but left-recursive rules like these can be problematical for top-down
parsers, which I suspect is why it wasn't done.
--------------------------------------------------------------------
> > Parsing "some $v in $X satisfies A or B" as
> >
> > OrExpr
> > |
> > +------------+-----------+
> > | | |
> > AndExpr "or" AndExpr
> > | |
> > QuantifiedExpr B
> > |
> > some $v in $X satisfies A
> >
> > is disallowed by Section A.1, because AndExpr does not derive
> > QuantifiedExpr.
>
> Thanks. I missed that....but does that not mean that "some $v in $X
> satisfies A or B" should result in a syntax error according to the
> current EBNF?
It would if there were no valid derivation tree, but this:
QuantifiedExpr
|
+-----+--+----+------+-----------+
| | | | | |
"some" $v "in" $X "satisfies" ExprSingle
|
OrExpr
|
+------------+-----------+
| | |
AndExpr "or" AndExpr
| |
A B
is valid (and is roughly what Scott Boag posted on Friday).
> > The fix is presumably to move "or" from precedence
> > level 2 to a new level between the current levels 2 and 3. I
> > think this is what you meant by
> >
> > > > (3) would it not be possible to add an extra level of precendence
> > > > where the OrExpr comes to sit between QuantifiedExpr and AndExpr
>
> That is what I meant yes. But I have a feeling that needs to be
> reflected in a modified EBNF as well.
I'm pretty sure the EBNF is okay on this point.
-Michael Dyck
Received on Sunday, 21 December 2003 16:00:14 UTC