RE: [XPath] A.2.2 Parsing note

Hi Scott

The current working draft grammar is much better than a year ago when I had
some
difficulties constructing an LALR grammar and I think I pointed out the need
to reserve
function  names. It's now almost trivial, so while you say you have an LL
grammar you actually have a better LALR(1) one.

I have now trimmed my NiceXSL grammar of which XPath is a part, so that
I can verify the ambiguity issues. The grammar is attached. It requires
just one %prec to resolve the leading "/" problem. (The inlining of a number
of single-use productions was necessary to avoid a 65535 byte count limit
in the generated NceXSL parser. I don't think it makes any difference to
the grammar ambiguity.)

There is no dangling-else ambiguity with "if", because the "else" clause
is not optional.

Thgere is no function call ambiguity with "if", because "if" is not a valid
function name.

So the EBNF needs just one <..> grouping to resolve leading "/".

	Regards

		Ed Willink

> -----Original Message-----
> From: scott_boag@us.ibm.com [mailto:scott_boag@us.ibm.com]
> Sent: 28 January 2004 14:44
> To: Willink, Ed
> Cc: 'public-qt-comments@w3.org'
> Subject: Re: [XPath] A.2.2 Parsing note
> 
> 
> Ed, thank you for your last call comment.  It will be 
> processed by the 
> working group.
> 
> A point of clarification.  I believe you're saying that, without <> 
> grouping and any lexical states or lexical lookahead, that 
> the BNF can 
> produce an unambiguous LALR parser (with a standard tool... YACC for 
> instance), except for leading "/"?  I'm a little surprised to 
> hear this, 
> though I am aware that the groupings can be at least greatly 
> reduced with 
> LALR(1).  Without reserved keywords, it's hard to see how "if" can be 
> unambiguously lexed and serve a useful purpose to the parser. 
>  There would 
> seem to be lots of other issues of this kind.  I do have a test LALR 
> parser, but so far it is a fairly straight-forward 
> transformation of the 
> LL grammar and lexical constructs, i.e. it uses the pretty 
> much the same 
> lexer as the LL parser.  It would be a useful exercise to 
> remove as much 
> of the grouping as lex states as possible.
> 
> > All other <> grouping annotations and lexical tables should be a
> > non-normative
> > guide that may be of assistance to those pursuing an LL approach.
> 
> The WG has considered this in the past, at least for the 
> lexical tables, 
> and has so far concluded they should be normative.  But we'll 
> take a fresh 
> look at it... I don't think there's any question that it 
> would be better 
> if they were non-normative.  The issue is only if they carry some 
> information that is not stated elsewhere.  In some ways, this 
> has been a 
> changing picture as the grammar has evolved, so it may be 
> that they used 
> to carry unique information, but no longer do.
> 
> Also, given the grammar is LL, the parsing rules should be 
> stated in LL 
> and not LALR, I think.
> 
> -scott
> 
> public-qt-comments-request@w3.org wrote on 01/27/2004 07:00:24 AM:
> 
> > 
> > Hi
> > 
> > The tables are _not_ a declarative way to specify 
> behaviour. They are
> > a highly imperative imposition of a solution that then has to be 
> disclaimed
> > except in so far as it still has to be observed.
> > 
> > The declarative approach is to specify that the preceding BNF when
> > interpreted
> > at a lexical level maximising the length of tokens such as 
> QName and 
> then
> > in the conventional LALR(1) shift-reduce fashion has exactly one
> > shift-reduce
> > conflict on a leading "/" that is to be resolved as per
> > grammar-note:leading-lone-slash.
> > 
> > All other <> grouping annotations and lexical tables should be a
> > non-normative
> > guide that may be of assistance to those pursuing an LL approach.
> > 
> >    Regards
> > 
> >       Ed Willink
> > 
> > 
> --------------------------------------------------------------
> ----------
> > E.D.Willink,                             Email: 
mailto:EdWillink@iee.org
> Thales Research and Technology (UK) Ltd, Tel:  +44 118 923 8278 (direct)
> Worton Drive,                            or  +44 118 986 8601 (ext 8278)
> Worton Grange Business Park,             Fax:  +44 118 923 8399
> Reading,   RG2 0SB
> ENGLAND          http://www.computing.surrey.ac.uk/personal/pg/E.Willink
> ------------------------------------------------------------------------
>