Brussels / 2 & 3 February 2019


Tree matchings with Behavior Trees

How to recognize a complex subtree in a big tree

Any python data structure could be seen as a big tree of related objects. Would it be useful for you to recognize in this big tree some specific form?

Recognizing of subtrees is really a common aim in compilers implementation. But it's not an easy task. I recently found that I could easily use behavior trees to do such things. However this kind of techniques could be useful in other situation. This talk want to popularize this technique by explaining how behavior trees work in common way, how to adapt then for a bottom-up tree matching algorithm.

For instance, some HTML parser provide CSS Selector function to match one node at the time optionally related to some ancestor. Here, with this kind of matching algorithm you could match many nodes in only one pass.

I create on my github a "treematching" module that use this algorithm to provide an Embedded DSL to write patterns, match any python data structure and in some case, allow you to do tree rewriting.


Photo of Lionel Auroux Lionel Auroux