This is the fourth part in our series of talks on creating a programming language. In this session on building our toy programming language, we focus on the parser, specifically on parsing expressions using recursive descent.
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.
Meet the parser
The parser verifies whether input conforms to the grammar and, if successful, builds an abstract syntax tree (AST). Yuri walks through the grammar for additive, multiplicative, unary, parenthesized, and literal expressions, explaining how precedence and left associativity are baked into the grammar structure.
Parser implementation
It begins with a straightforward but repetitive version, where separate functions handle additive and multiplicative expressions. This leads to code duplication, especially as more binary operators are added. To solve this, the presenter introduces a generic binary expression function that uses a precedence enum and recursive calls with an increased index. This approach eliminates duplication and handles all binary operators uniformly.
Yuri demonstrates how the parser descends through the grammar, consuming tokens and building nested structures, with left associativity ensured by loops that repeatedly consume operators of the same precedence.
The session concludes with a preview of future topics: building an AST, implementing a builder and printer, and using the visitor pattern.
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. AST.
If you'd like to learn more about PVS-Studio analyzer, check out our website.
See ya!
