Cart
[Home] [By Thread] [By Date] [Recent Entries]
Arthur Rother wrote: > I came across this one in my first lessons on learning DTD's, where I tried > to write a DTD for a game of chess: > > ((whitemove, blackmove)*, whitemove?) That's a neat example. It's well-known that ((a,b)*,a?) is hopelessly ambiguous (i.e., there's no way to write it as deterministic content model), but I've never seen a real-world example where that construct was useful before now. > If this is the only endless case, one could hardcode this in the parser. It's not -- there's an infinite number of "hopelessly ambiguous" regular languages. > How do [XML Spy and XMetal] deal with it? There are plenty of algorithms for regular expression matching besides the one prescribed for SGML. You can convert to a DFA (lex), backtrack (Perl), use derivatives (TREX), or simulate an NDFA, to name a few. The only real problem with nondeterministic content models in SGML has to do with start-tag inference (and even that can be worked around). Since XML doesn't support this feature, it's not as big of a problem for implementations. --Joe English jenglish@f...
|
