[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: UPA and schema handling

• To: Bob Foster <bob@o...>
• Subject: Re: UPA and schema handling
• From: Burak Emir <Burak.Emir@e...>
• Date: Sat, 23 Oct 2004 10:04:15 +0200
• Cc: Joe English <jenglish@f...>, xml-dev@l...
• In-reply-to: <4179C6D6.8070207@o...>
• References: <87lldyv5zk.fsf@n...> <41729D89.6020906@u...> <4172BD45.7040409@o...> <4172F10A.1070002@u...> <4173151B.90700@o...> <4173201E.20001@u...> <f5bu0smra97.fsf@e...> <41794B8B.9080709@m...> <200410222154.i9MLsFV09885@d...> <4179C6D6.8070207@o...>
• User-agent: Mozilla Thunderbird 0.7.3 (X11/20040803)

Bob Foster wrote:

> Joe English wrote:
>
>> But even SGML doesn't require conforming systems to report
>> this condition; [4.267] says an ambiguous content model is not
>> a "reportable markup error".
>>
>> (That's probably because nobody knew *how* to detect this condition
>> until 1992 when Anne Bruegemann-Klein figured it out, but still...)
>
>
> Lots of people knew how to detect it, but they all did it differently. 
> Bruegemann-Klein's great contribution was to provide a rigorous 
> definition for the condition. (She then went on to show that if a 
> grammar was deterministic by her definition, a DFA could be built for 
> it in linear time. That was pretty nice, too.)
>
I don't want to downplay that contribution, but the essential idea goes 
back to Gerard Berry and Ravi Sethi's 1984 paper (although XML did not 
exist at that point). Some people mention Glushkov, somewhere in the 
60s. Some call the automata "position automata". Brueggemann-Klein 
applied this idea to SGML and XML content models, but these are just 
regular expressions.

If you look into the construction, you find first,last and follow sets, 
which are also pretty common when dealing with context-free grammars. 
What is nice that if people do it correctly, than they do it in somehow 
the same way : )

cheers,
Burak

http://lamp.epfl.ch/~buraq

• References:
  • Re: UPA and schema handling
    • From: Norman Walsh <ndw@n...>
  • UPA and schema handling
    • From: Ian Graham <ian.graham@u...>
  • Re: UPA and schema handling
    • From: Bob Foster <bob@o...>
  • Re: UPA and schema handling
    • From: Ian Graham <ian.graham@u...>
  • Re: UPA and schema handling
    • From: Bob Foster <bob@o...>
  • Re: UPA and schema handling
    • From: Ian Graham <ian.graham@u...>
  • Re: UPA and schema handling
    • From: ht@i... (Henry S. Thompson)
  • Re: UPA and schema handling
    • From: Elliotte Harold <elharo@m...>
  • Re: UPA and schema handling
    • From: Joe English <jenglish@f...>
  • Re: UPA and schema handling
    • From: Bob Foster <bob@o...>

• Prev by Date: Re: XML Data Modellling/Linking (was RE: AfterXQuery, are we done?)
• Next by Date: Re: XML Data Modellling/Linking (was RE: AfterXQuery, are we done?)
• Previous by thread: Re: UPA and schema handling
• Next by thread: Re: UPA and schema handling
• Index(es):
  • Date
  • Thread