This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 8882 - XQuery scripting extension grammar is not LL(k)
Summary: XQuery scripting extension grammar is not LL(k)
Status: CLOSED FIXED
Alias: None
Product: XPath / XQuery / XSLT
Classification: Unclassified
Component: Scripting Extensions 3.0 (show other bugs)
Version: Working drafts
Hardware: PC Linux
: P2 normal
Target Milestone: ---
Assignee: John Snelson
QA Contact: Mailing list for public feedback on specs from XSL and XML Query WGs
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-02-04 20:37 UTC by Nikolay Ognyanov
Modified: 2010-04-12 10:58 UTC (History)
0 users

See Also:

Attachments

Description Nikolay Ognyanov 2010-02-04 20:37:31 UTC 
Top level expression grammar of XQuery scripting extension is :

Expr       ::= ApplyExpr | ConcatExpr
ApplyExpr  ::= (ConcatExpr ";")+
ConcatExpr ::= ExprSingle ("," ExprSingle)*

To distinguish between ApplyExpr and ConcatExpr alternatives in the rule for Expr an LL parser would need to look beyond a list of ExprSingle to see whether terminating ";" follows it. This can obviously not be done with fixed amount of lookahead. 

An LL(k) grammar for the same language is e.g. this :

Expr       ::= ExprSingle ((',' | ';') ExprSingle)* ';'?

It does not match well semantics of the language, so possibly the choice to sacrifice LL(k) was conscious. If this is the case though then the fact probably deserves some comments in the specification since generally XQuery related grammars are LL(1) (with the exception of some explicitly defined extra-grammatical constraints).
Comment 1 John Snelson 2010-02-05 11:07:27 UTC 
Hi Nikolay,

Thanks for your comments. The XQuery WG has already addressed this issue in an internal draft of the XQuery Scripting Extensions, so the next version will contain this decision.

John
Comment 2 Nikolay Ognyanov 2010-02-05 19:24:26 UTC 
Hi John,

Thank you for the information. I will be looking forward to the next draft. Any projections as to when it may come out?

Regards
Nikolay
Comment 3 John Snelson 2010-02-05 23:30:15 UTC 
Soon, I hope.
Comment 4 John Snelson 2010-02-09 18:13:02 UTC 
On the XQuery Working Group teleconference today, the working group confirmed comment #1 was correct, and that this grammar problem has already been fixed.