Re: unambiguity constraint

[James Clark <jjc@jclark.com>]

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
>
>
>
>