James Clark wrote:
> Incidentally, this has nothing to do with attribute wildcards. You could
> equally well cause blow-up in the current JTREX implementation with a
> sufficiently large choice of attributes.
In my understanding, JTREX explodes when:
1) <oneOrMore> directly or indiretly contain <group> or <interleave>
patterns.
2) at least one of them directly or indirectly contains multiple
subpatterns with which many attributes of a single element match. That
subpattern may be an attribute wildcard or large choice of attributes.
For each of the many attributes of the element, we can consume one of the
multiple subpatterns. If we have many attributes, combinatory explosion
will usually happen.
> This is just a limitation of JTREX. It doesn't memoize the construction of
> derivatives for attributes. Just to prove to myself that this really was
> the problem, I implemented a simple caching scheme for attribute
> derivitives; with this fix, it could handle your cases with any exponential
> increase in computation time.
By memorizing derivatives, different branches will merge and thus
combinatory explosion can be avoided.
Cool, but too cool. I do not see any advantages in allowing
patterns I described above.
Cheers,
Makoto
