Skip to Main Content
Language Implementation Patterns
book

Language Implementation Patterns

by Terence Parr
December 2009
Intermediate to advanced content levelIntermediate to advanced
380 pages
9h 2m
English
Pragmatic Bookshelf
Content preview from Language Implementation Patterns
Pattern 15Tree 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 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Implementation Patterns

Implementation Patterns

Kent Beck

Publisher Resources

ISBN: 9781680500097Errata Page