Re: unambiguity constraint

[James Clark <jjc@jclark.com>]

I should also mention that I believe the technique I use here can also be
used for determining whether the intersection of two name classes is empty:

function overlaps(nameClass nc1, nameClass nc2) returns boolean
{
  for x in union(possibleNames(nc1), possibleNames(nc2)) {
     if (contains(nc1, x) and contains(nc2, x)) {
       return true;
     }
  return false;
}

----- Original Message -----
From: "James Clark" <jjc@jclark.com>
To: "Kohsuke KAWAGUCHI" <kohsuke.kawaguchi@eng.sun.com>; "TREX ML"
<trex@lists.oasis-open.org>
Sent: Saturday, May 05, 2001 11:58 AM
Subject: Re: unambiguity constraint


> I think you can use an algorithm along the lines of
>
> http://lists.oasis-open.org/archives/trex/200103/msg00014.html
>
> Define a category to be
>
> category ::= null
>                       | key(NCName)
>                       | keyref(NCName)
>
> function directCategories(pattern p) returns set(category)
> {
>   switch (p) {
>    case <group>p1 p2</group>:
>    case <choice>p1 p2</choice>:
>    case <interleave>p1 p2</interleave>:
>       return union(directCategories(p1), directCategories(p2));
>   case <oneOrMore>p1</oneOrMore>:
>      return directCategories(p1);
>    case <attribute/>:
>    case <element/>:
>       return {};
>    case <data key=s>:
>       return { key(s) };
>    case <data keyref=s>:
>       return { keyref(s) };
>     case <anyString/>:
>     case <data/>:
>     case <string/>:
>        return { null };
>     }
> }
>
> function possibleElements(pattern p) returns set(name) {
>    switch (p) {
>    case <group>p1 p2</group>:
>    case <choice>p1 p2</choice>:
>    case <interleave>p1 p2</interleave>:
>        return union(possibleElements(p1), possibleElements(p2);
>     case <element>nc p1</element>
>         return possibleNames(nc);
>    case <attribute/>;
>     case <anyString/>:
>     case <data/>:
>     case <string/>:
>       return {};
>    }
> }
>
> string MAGIC = "\u0000";  // any string that is illegal in XML will do
>
> function possibleNames(nameClass nc) returns set(name) {
>   switch (nc) {
>     case <name>n</name>:
>        return { expand(n) };
>     case <anyName/>:
>        return { name(MAGIC, MAGIC); }
>     case <nsName ns=ns/>:
>        return { name(ns, MAGIC); }
>      case <not>nc1</not>:
>         return union({ name(MAGIC, MAGIC }, possibleNames(nc1));
>      case <choice>nc1 nc2</choice>:
>      case <difference>nc1 nc2</difference>:
>         return union(possibleNames(nc1), possibleNames(nc2));
>    }
> }
>
> function combinedElementPattern(pattern p, name x) returns pattern {
>    switch (p) {
>    case <group>p1 p2</group>:
>    case <choice>p1 p2</choice>:
>    case <interleave>p1 p2</interleave>:
>        return <choice>combinedElementPattern(p1)
> combinedElementPattern(p2)</choice>;
>     case <element>nc p1</element>:
>        if (contains(nc, x) {
>          return p1;
>        }
>       else
>           return <empty/>;
>     case <attribute/>;
>     case <anyString/>:
>     case <data/>:
>     case <string/>:
>       return <empty/>;
>    }
> }
>
> function checkAmbig(pattern p)
> {
>   if (alreadyChecked(p))
>      return; // avoid infinite recursion.
>    mark p as already checked;
>    if (size(directCategories(p)) > 1)
>      it's ambiguous;
>    for each x in possibleNames(possibleAttributes(p)) {
>      checkAmbig(combinedAttributePattern(p, x));
>    }
>    for each x in possibleNames(possibleElements(p)) {
>       checkAmbig(combinedElementPattern(p, x));
>    }
> }
>
> combinedAttributePattern and possibleAttributes are similar to
> combinedElementPattern and possibleElements
>
> ----- Original Message -----
> From: "Kohsuke KAWAGUCHI" <kohsuke.kawaguchi@eng.sun.com>
> To: "TREX ML" <trex@lists.oasis-open.org>
> Sent: Saturday, May 05, 2001 11:19 AM
> Subject: Re: unambiguity constraint
>
>
> >
> > > The same constraint should be applied to ancestors recursively.
> >
> > That's true. But this makes the language tree-local and therefore
> > impractical.
> >
> > Well, mine is broken. We need a different constraint, I guess....
> >
> > --
> > Kohsuke KAWAGUCHI                          +1 650 786 0721
> > Sun Microsystems                   kohsuke.kawaguchi@eng.sun.com
> >
> >
> >
> >
>
>
>
>