W3C home > Mailing lists > Public > public-qt-comments@w3.org > March 2005

Re: Is XQuery a CFG or CSG ?

From: <scott_boag@us.ibm.com>
Date: Wed, 9 Mar 2005 11:08:36 -0500
To: Frank Yung-Fong Tang <franktang@gmail.com>
Cc: public-qt-comments@w3.org
Message-ID: <OFFF6D294F.5944B80E-ON85256FBF.0058351D-85256FBF.0058AD7D@lotus.com>

Actually, a colleague of mine (who can identify himself if he wants), as 
corrected me:

...although the grammar used for parsing is a 
context free grammar, XQuery's very likely a context sensitive language, 
as are most programming languages, due to the additional constraints 
placed on the language by the prose in the XQuery document - for instance, 

variables must be declared before they're used, they can't be twice 
declared, etc.

Those constraints can typically be described only by using a context 
sensitive grammar, but not a context free grammar.  It's not worth the 
bother to define context sensitive grammars that enforce those 
constraints, so everybody uses context free grammars and parsers for them 
with additional constraint checking built on top.

(I was thinking of the language more in terms of the syntax.  In any case, 
all a bit academic.)


Scott Boag/Cambridge/IBM wrote on 03/09/2005 06:28:11 AM:

> > Is the language expressed by XQuery (not the XQuery grammar itself,
> > but the expression power carried by XQuery)
> You've lost me here.  The language is described by the grammar.
> >  a Conext Free Grammar or
> > Context Sensitive Grammar?
> XQuery has a Context free grammar, and is a context free language. 
> But every context-free language is context-sensitive (but not every 
> context-sensitive language is context-free), so there you go.  See 
> http://en.wikipedia.org/wiki/Chomsky_hierarchy.
> -scott
Received on Wednesday, 9 March 2005 16:44:08 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:45:23 UTC