[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Non-deterministic content model
- From: Arthur Rother <email@example.com>
- To: firstname.lastname@example.org
- Date: Thu, 14 Jun 2001 02:22:56 +0200
> ((a, b)*, a?)
You can start unrolling this one, but you will never end it. It would look
> It is provable that _every_ non-deterministic content model can be
> converted to a deterministic content model. The trick is basically to
> manually 'unroll' the content model.
would take you for ever to do so.
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?)
I quickly loosed confidence in the power of content models.
luckily in the real world, one need not to be as restrictive.
the automation for recognizing a pattern following above rule is a very
small and easy one as in
> A B
>0 1 -
>1 - 0
So you create kind of a simple loop. The trick, if one would write a parser
that can parse
((a, b)*, a?)
is to unroll while you are parsing. but this is hard to recognize when to
(a,(b,( (a,b)* a?) ?)?)?
If the unroller (dtd parser) comes to this situation, it could recognize
If this is the only endless case, one could hardcode this in the parser.
but it is easier to disallow 1-unambiguous content models.
> It is a point of incompatibility: From experience,
> XML Spy and XMetal (I work for Softquad) will accept
> it, msxml will not.
these tools deal with it?