OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   Re: [xml-dev] UPA and schema handling

[ Lists Home | Date Index | Thread Index ]

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




News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS