W3C home > Mailing lists > Public > www-xml-query-comments@w3.org > July 2001

XQuery: nasty ambiguity

From: Michael Dyck <MichaelDyck@home.com>
Date: Wed, 11 Jul 2001 22:41:45 -0700
Message-ID: <3B4D3899.EF67E981@home.com>
To: www-xml-query-comments@w3.org
XQuery 1.0: An XML Query Language
W3C Working Draft 07 June 2001

I've found a nasty ambiguity in the XQuery grammar.
I can demonstrate it with the phrase

    /<QName>stuff</QName>/QName

It looks odd, but it's a grammatically valid expression with two quite
different parses: [view these parse trees in a fixed-width font]


                  PathExpr
                     |
           +---------+----------+
           |                    |
           |             RelativePathExpr
           |                    |
           |           +------------+------+
           |           |            |      |
           |        StepExpr        |   StepExpr
           |           |            |      |
           |      OtherStepExpr     | OtherStepExpr
           |           |            |      |
           |        Primary         |   Primary
           |           |            |      |
           |   ElementConstructor   |   NodeTest
           |           |            |      |
           | +--+--+---+---+---+--+ |   NameTest
           | |  |  |   |   |   |  | |      |
           / <QName> stuff </QName> /    QName


                               RelationalExpr
                                     |
                          +----------+------+----+
                          |                 |    |
                    RelationalExpr          |    |
                          |                 |    |
                   +------+---+----+        |    |
                   |          |    |        |    |
             RelationalExpr   |   Expr      |   Expr
                   |          |    |        |    |
             +-----+--+---+   | PathExpr    | PathExpr
             |        |   |   |    |        |    |
       RelationalExpr |  Expr | +--+--+     | +--+--+
             |        |   |   | |     |     | |     |
       +-----+---+    |   |   | |  StepExpr | |  StepExpr
       |     |   |    |   |   | |     :     | |     :
      Expr   |  Expr  |   |   | |     :     | |     :
       |     |   :    |   |   | |     :     | |     :
    PathExpr |   :    |   |   | |     :     | |     :
       |     |   :    |   |   | |     :     | |     :
       /     < QName  > stuff < /   QName   > /   QName


One way to eliminate the ambiguity would be to somehow disallow an
ElementConstructor as a StepExpr. However,
(a) this would complicate the grammar; and
(b) it would eliminate a potentially useful construct. (Not that the
    example shown is useful, but I can imagine cases where having an
    ElementConstructor as the *first* step in a relative path would
    be useful.)

Or you could disallow cascading RelationalExprs, but
(a) that too would complicate the grammar; and
(b) you'd still have a shift-reduce conflict that would require 3
    symbols of lookahead to resolve.

Probably the simplest fix would be to replace the relational operators
("<" and ">") with keywords ("lt" and "gt"). [I notice that the XQuery
Core Syntax does this.] True, it does decrease readability slightly,
but presumably people working with XML would be used to the idea of
angle-brackets being reserved for tag-delimiting only.

-Michael Dyck
Received on Thursday, 12 July 2001 01:46:57 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 2 February 2007 00:13:02 GMT