[
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 : )
cheers,
Burak
http://lamp.epfl.ch/~buraq
|
