Re: [relax-ng] What's ambiguous for Relax NG?

[Eric van der Vlist <vdv@dyomedea.com>]

On Sat, 2003-07-05 at 17:54, MURATA Makoto (FAMILY Given) wrote:
> > Do you classify unambiguity of name classes as unambiguity of regular
> > expressions?
> 
> I did not think about that while I was writing my mail.  However, disambiguation 
> of name classes is not difficult.
> 
> > I am not sure I understand the difference between regular expressions
> > and hedge grammars. Do you use them as two different levels?
> 
> Simply put, in a simplified RNG schema, regular expressions are second
> children of <element>s, and represent sets of sequences of
> <ref name="..."/>.  Meanwhile, regular hedge grammars are 
> a bunch of <define>s having regular sets of <ref name=".."/>  (i.e., 
> we do not care which regular expression is used to represent such a regular set)..

Sorry to insist, but I'd like to be sure I understand!

Do you mean that regular expressions do not "cross the boundary of
elements", ie that you don't have element patterns in regular
expressions but only combinations of references to element definitions
while the regular hedge grammar is the whole Relax NG grammar?
>  
> > > We can combine these three kinds of unambiguity and introduce quite 
> > > a few variations of unambiguity!  I would argue that different 
> > > tools require different variations of ambiguity.  It does make 
> > > sense to allow ambiguous regular expressions but require 
> > > deterministic top-down hedge automata with one look-ahead.
> > 
> > You mean that it would be a good compromise between flexibility and
> > implementation and allow deterministic type assignment?
> 
> As for validation, I do not see any reasons to require determinism.

No, if the schema validator can support non deterministic model, it is a
waste of time for the user to require determinism.

> (By the way, restrictions on <interleave> is for another type of 
> determinism.)  As for data binding tools, I think that different 
> data binding tools require different types of unambiguity 
> of regular expressions.

Do they require determinism or just unambiguity? I think that's the
question which made me start the thread.

I'd say that what's important for them is that the type assignment gives
a consistant result after each run. Isn't unambiguity enough for this?

Furthermore, I'd say that only "real" unambiguity unlike:

     element foo{token}|element foo{token}

is a problem and that not all the ambiguous schemas are a problem.

I am wondering if we do not find here the difference you made between
regular expressions and regular hedge grammar: after simplification, my
example wouldn't have any ambiguous regular expression but the resulting
grammar would be ambiguous. 

Is this what you mean?

Also, the whole question could be ruled out with a statement specifying
which alternative should be taken if we have two choices matching a
node. If we just said that the "first" one would be taken for type
assignment, ambiguous grammars wouldn't be ambiguous any longer for
"type assigners" (and other classes of validators wouldn't have to
bother with this rule).

Even 

     element foo{xsd:boolean}|element foo{xsd:integer}

would not be ambiguous for a "type assigner" if we defined that the
first definition should be taken if both match.

That's just what WXS does with unions of datatypes and I think that this
could be generalised (we would need to define an "order" for
alternatives which survives the schema simplification but I think that
this should be possible and again it wouldn't apply to RNG processors
not interested by type assigment).  

> > BTW, I have a question about Relax NG... Wouldn't an "except" pattern
> > have been useful out of the scope of datatypes? 
> 
> Arguably, yes.  But this has significant impacts on validation algorithms.  I am 
> reluctant.

I won't argue then. I have always felt that the language would be more
flexible and "balanced" but don't have any strong use case!

Thanks

Eric

> Cheers,
-- 
Lisez-moi sur XMLfr.
                       http://xmlfr.org/index/person/eric+van+der+vlist/
------------------------------------------------------------------------
Upcoming Schema languages tutorial (registration open):
 - July 7th   (Portland, OR)      http://makeashorterlink.com/?K27A527A4
 - August 4th (Montreal, Canada)  http://makeashorterlink.com/?U28A217A4
------------------------------------------------------------------------
Eric van der Vlist       http://xmlfr.org            http://dyomedea.com
(W3C) XML Schema ISBN:0-596-00252-1 http://oreilly.com/catalog/xmlschema
------------------------------------------------------------------------