Language Implementation Patterns

Chapter 5Walking and Rewriting Trees

In the previous chapter, we learned how to build ASTs, and in the following chapters, we’ll start extracting information from them. We’re even going to restructure the trees for simplification and translation purposes. For example, we might want to simplify x+0 to x or translate x==y to strcmp(x,y). To support such data extraction and rewriting operations, we’ll need to know about tree walking. Tree walking is one of the key processes going on in a large language application.

At first glance, tree walking seems like no big deal. Many of us learned to write simple recursive functions to walk trees fairly early in our programming careers. In real applications, though, tree walking gets surprisingly complicated. ...