Language Implementation Patterns

Pattern 15

Tree Pattern Matcher

Purpose

This pattern walks trees, triggering actions or tree rewrites as it encounters tree patterns of interest.

The process of matching and rewriting trees is formally called term rewriting.

Discussion

Using a tree pattern matcher differs from using a tree grammar in two important ways:

• We have to specify patterns only for the subtrees we care about.

• We don’t need to direct the tree walk.

As we saw in ​Decoupling Tree Traversal from Pattern Matching​, a tree pattern matcher is analogous to text rewriting tools such as awk, sed, and perl. We get to focus on input patterns of interest and what to do when we match those patterns. Whichever pattern matcher tool we’re using deals with tree walking and when to apply ...