Cart
[Home] [By Thread] [By Date] [Recent Entries]
Gary Stephenson wrote:
>
> I am trying to implement Relax NG, but am having a hard time
> figuring out how to implement the "interleave" pattern.
The implementation depends on how you're implementing
the *rest* of Relax-NG. 'Interleave' is probably easiest
to implement if you're using an algebraic approach.
The reduction rule is:
(e1 ^ e2) \ sym = ((e1 \ sym) ^ e2) | (e1 ^ (e2 \ sym))
(where '^' = interleave, | = union, and \ is the transition operator).
The following simplification rules also hold:
(e ^ 0) = (0 ^ e) = 0
(e ^ 1) = (1 ^ e) = e
You need to take some care if you're using a finite automaton
based algorithm, since expressions involving '^' can generate
extremely large numbers of states. One approach is to represent
states in M(e1 ^ e2) as _pairs_ of states drawn from M(e1) x M(e2).
> Are there any published algorigthms or open-source implementations
> of a similar nature that I could access and study? (for free!)
James Clark's TREX might be a good place to start.
--Joe English
jenglish@f...
|
