Re: Non-deterministic content model

[Arthur Rother <rother@jps.net>]

Hi

 > ((a, b)*, a?)

You can start unrolling this one, but you will never end it. It would look 
something like

(a,(b,(a,(b,(a,(..)?)?)?)?)?)?

So

 > 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 
do so.

(a,(b,( (a,b)* a?) ?)?)?

If the unroller (dtd parser) comes to this situation, it could recognize 
the loop.
If this is the only endless case, one could hardcode this in the parser.

but it is easier to disallow 1-unambiguous content models.

How do

 > 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?

Arthur