Re: Explosion

[Murata Makoto <mura034@attglobal.net>]

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