Matching templates against a tree - any ideas?

[skaller]

Ian Clarke wrote:

> While recently thinking of good ways to automatically solve equations, I
> came across the problem of trying to find an efficient method to match a
> tree, or subtree of that tree, against a template - so that a
> transformation could be applied.

Lets see if I understand: you have a template

and you want to match them against EVERY subtree of a given

tree, efficiently. Question: what happens if there is more

than one overlapping match?

Now, this problem is reminiscent of parsing,

so you might use a parser. If you convert your

template into a syntax directed grammar, and provide

it with tokens found by iterating over the tree in some

order, the parser will rebuild the tree, and the 'reduce'

steps can be used to do the optimisations.

Since it is likely your problem is context free,

and Early parser will always work, but it is

a backtracking parser with O(n^3) performance :-(

OTOH, if you can write LALR(1) grammars for your templates,

you'll be able to use Yacc and an LR(1) parser. This is

very efficient: only one token look ahead.

The size of the input tree is irrelevant with a such a parser,

but you may kill the parser generator easily if there are

two many templates (leading to too many states).

Writing the grammars by hand is the thing to do first,

but then you will need to automate it, which suggests

writing a 'compiler' which reads the templates and produces

parse tables.

If LALR(1) is too restrictive, you can consider the Early parser

with cuts. This is what JavaCC seems to be using.

Finally, although I am not sure I completely understood,

I just read an article (posted to comp.theory) which I think proves

that arbitrary context free languages can be parsed in O(N).

--
John Skaller, mailto:skaller at maxtal.com.au
1/10 Toxteth Rd Glebe NSW 2037 Australia
homepage: http://www.maxtal.com.au/~skaller
downloads: http://www.triode.net.au/~skaller