3.3 AST traversal
The compiler requires traversal of the AST to generate IR code. Thus, having a well-structured data structure for tree traversal is paramount for AST design. To put it another way, the design of the AST should prioritize facilitating easy tree traversal. A standard approach in many systems is to have a common base class for all AST nodes. This class typically provides a method to retrieve the node’s children, allowing for tree traversal using popular algorithms such as Breadth-First Search (BFS) [19]. Clang, however, takes a different approach: its AST nodes don’t share a common ancestor. This poses the question: how is tree traversal organized in Clang?
Clang employs three unique techniques:
The Curiously Recurring Template Pattern (CRTP) for visitor class definition
Ad hoc methods tailored specifically for different nodes
Macros, which can be perceived as the connecting layer between the ad hoc methods and CRTP
We will explore these techniques through...
