In this part, we continue the development of a toy programming language by introducing the Abstract Syntax Tree (AST), the data structure that represents the hierarchical structure of source code after parsing.
About the speaker
Yuri Minaev is an experienced C++ developer, architect at PVS-Studio, and a recognized voice in the C++ community who has spoken at CppCast, C++ on Sea, and CppCon. Over the course of ten sessions, he'll guide you through each stage of building your own programming language.
The foundation
Each language construct corresponds to an AST node, while collections of nodes, such as function bodies or parameter lists, are represented by dedicated list nodes. Yuri explains the core node types, including literals, identifiers, unary and binary expressions, assignments, function calls, declarations, statements, and error nodes.
Error nodes allow parsing to continue after syntax errors, enabling the compiler to collect multiple errors instead of stopping at the first one. Invalid nodes propagate their state upward so the entire program can be marked invalid before evaluation.
Let's grow our tree!
A central component of the implementation is the AST builder, which owns every created node and manages memory automatically. As the parser recognizes grammar rules, it instructs the builder to create nodes. Terminal nodes are stored in an internal state, while compound nodes consume previously created child nodes from that state and combine them into larger structures until the root node of the program is produced.
Traversing the Tree
The second half of the talk focuses on traversing the AST with a visitor. The visitor performs a depth-first traversal using preview and visit functions. Preview executes when entering a node and can decide whether to traverse its children, while visit runs after returning from them. This design allows specialized visitors to process only the node types they need.
As an example, Yuri demonstrates an AST printer that uses the visitor to produce a tree-like representation of the program structure, concluding with a preview of future topics covering variables, types, semantics, functions, and evaluation.
Want more?
If you want to watch other talks or see the whole episode, follow this link.
You can also sign up for our upcoming webinars, for example: Let's make a programming language. Variables. We hope to see you there!
If you'd like to learn more about PVS-Studio analyzer, check out our website.
See ya!
Top comments (0)