I would like to write from scratch a tree pattern matching algorithm. Well actually, not just a matching algorithm, and not even a tree transducer, but a sort of tree constructor that takes basically a tree grammar ("tree pattern"), and an input tree instance like an XML tree, and constructs objects out of the instance tree (like constructing a JSON tree that differs significantly in structure from an original XML tree).

In the tree grammar/automaton, tree nodes are basically as described in that post: they can match sequences of zero/one or more (like regular expressions, but on trees), handle wildcards, and arbitrarily nested sequences/wildcards.

The question is, how can you apply the theory of tree automata (tree pattern recognizers) to constructing new trees from trees matching patterns? Can you work off of or build off of the idea of tree automata in this situation? If so, what must be added to allow for constructing trees that match the pattern, and where must it be added? If not, why not, must you write a hand-crafted algorithm for traversing the pattern tree and instance tree to construct the output tree in that case?

Basically wondering what research direction I should be looking into for inspiration, and if this is a solved problem. (Though, I would like to reinvent the wheel here, to learn how to implement it from scratch). In practice, I would like to handle errors gracefully (with helpful user messages) if trees are malformatted, for example. So the research shouldn't be too simplistic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.