[dsdl-discuss] Re: My position on RELAX NG V2

>
>> The difficulty with doing anything in Bali is that you have to change
>> MSV,
>> Bali, the automaton dump format and the validatelets: there would be a
>> lot
>> of extraneous work (such as the visualizer, the C#, etc)
>
> No, that's not the point.
>
> Bali internally uses a non-deterministic tree automaton. If we add the
> concur operator, it will have to use a non-deterministic ALTERNATING
> tree automaton.
>
> http://en.wikipedia.org/wiki/Alternating_finite_automaton

I think we are agreeing: to support it inside the Bali grammar compiler
you would have to change a lot of the code, and everywhere, as you would
expect from a change in the theoretical class.

So I was *not* suggesting changing the part of Bali that converts a single
standard RELAX NG grammar to a single automaton file. Rather the change is
to the validatlet, so that it loads multiple automaton files, and
processes them in parallel without intercommunication. So there is no
change to the non-deterministic tree automaton code per se, merely that
each SAX token drives multiple automatons at the same time. The code for
this is obvious and simple.

So this relies on a preprocessor stage to generate the multiple standard
RELAX NG grammars. This is the place where the dragons certainly could be.

>
>> I think the simplest way to do it would be to preprocess the schema into
>> multiple standard RELAX NG schemas,
>
> Things are not that easy.

It wouldn't surprise me, but I'd love to know why.

> Consider
>
> A = element A { ((B1, B1)| (B2, B2, B2))*}
> B1 = element B { D } and { E }
> B2 = element B { F } and { G }
> D = element foo {D11} and {D12}
> D = element foo {D21} and {D22}
> E = element foo {E11} and {E12}
> E = element foo {E21} and {E22}
> F = element foo {D11} and {D12}
> F = element foo {D21} and {D22}
> G = element foo {E11} and {E12}
> G = element foo {E21} and {E22}
>
> How do you create multiple standard automatons?

I assume you mean

A = element A { ((B1, B1)| (B2, B2, B2))*}
B1 = element B { D } and { E }
B2 = element B { F } and { G }
D = element foo {D11} and {D12}
D |= element foo {D21} and {D22}
E = element foo {E11} and {E12}
E |= element foo {E21} and {E22}
F = element foo {D11} and {D12}
F |= element foo {D21} and {D22}
G = element foo {E11} and {E12}
G |= element foo {E21} and {E22}

And that the problem is that multiple concurrent grammars only allows
a top-level AND of the grammars, while it would seem that ORs may be
required. I.e.:

1a) Remove duplicate definitions (Level 2). (Explosion prevention)

A = element A { ((B1, B1)| (B2, B2, B2))*}
B1 = element B { D } and { E }
B2 = element B { D } and { E }
D = element foo {D11} and {D12}
D |= element foo {D21} and {D22}
E = element foo {E11} and {E12}
E |= element foo {E21} and {E22}

1b) Remove duplicate definitions (Level 3). (Explosion prevention)

A = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element B { D } and { E }
D = element foo {D11} and {D12}
D |= element foo {D21} and {D22}
E = element foo {E11} and {E12}
E |= element foo {E21} and {E22}

2) Substitute

Use Boolean or

A = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element B { D } and { E }
D = element foo ({D11} and {D12}) or ({D21} and {D22})
E = element foo ({E11} and {E12}) or ({E21} and {E22})

3) Distribute to get top-level AND

Convert Boolean or to |

A = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element B { D } and { E }
D = element foo
     { D11 | D21 | D22 } and { D12 | D21 | D22}
            and {D21 | D11 | D12} and { D22 | D11 | D12 }
E = element foo
     { E11 | E21 | E22 } and { E12 | E21 | E22}
            and {E21 | E11 | E12} and { E22 | E11 | E12 }

4a) Split out (level 2): 2 schemas

A = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element B { D }
D = element foo
     { D11 | D21 | D22 } and { D12 | D21 | D22}
            and {D21 | D11 | D12} and { D22 | D11 | D12 }

A' = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element { E }
E = element foo
     { E11 | E21 | E22 } and { E12 | E21 | E22}
            and {E21 | E11 | E12} and { E22 | E11 | E12 }

5a) Split out (level 3): 8 schemas

A = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element B { D }
D = element foo
     { D11 | D21 | D22 }

A = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element B { D }
D = element foo
     { D12 | D21 | D22}

A = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element B { D }
D = element foo
     { D22 | D11 | D12 }

A = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element B { D }
D = element foo
     { D11 | D21 | D22 }

A' = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element { E }
E = element foo
     { E11 | E21 | E22 }

A' = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element { E }
E = element foo
     { E12 | E21 | E22}

A' = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element { E }
E = element foo
            {E21 | E11 | E12}

A' = element A { ((B1, B1)| (B1, B1, B1))*}
B1 = element { E }
E = element foo
      { E22 | E11 | E12 }

I bet there is some silly mistake in my knowledge, but I am keen to learn.
Is their some problem with recursion or interleaving? Is it one of these
things where a few extra constraints makes implementation/thought much
easier?

Cheers
Rick Jelliffe

--
DSDL members discussion list
To unsubscribe, please send a message with the
command  "unsubscribe" to dsdl-discuss-request_at_dsdl.org
(mailto:dsdl-discuss-request_at_dsdl.org?Subject=unsubscribe)