Week 3 of 125
Crafting Interpreters, chapters 5 and 6
Sign up or sign in to tick these off and give this week a due date.
-
You design the syntax tree for expressions: context-free grammars, the expression grammar for Lox, a small Java program that generates the AST classes, and the Visitor pattern for operating on trees, ending with an AST pretty printer.
Time About 4 hours this week
Why it matters
ASTs are the central data structure of every compiler, linter and code formatter. The Visitor pattern explanation here is one of the clearest anywhere.
How to approach it
Write the GenerateAst tool exactly as shown; it saves a lot of typing later. Spend real time on the section about the expression problem and the Visitor pattern until you can explain why it exists.
Challenges
3 challenges at the end of the chapter.
Challenge 3 (an RPN printer) is short and a nice check that you understand visitors. Challenges 1 and 2 are thought exercises about grammars and functional versus object-oriented style.
Traps
- Forgetting to rerun GenerateAst after changing the grammar, then wondering why classes are missing.
- In other languages, a sum type plus pattern matching (Rust enums, TypeScript unions) can replace the Visitor pattern. That is fine, but understand what the Visitor is doing first.
-
A recursive descent parser for Lox expressions, with precedence and associativity encoded in the grammar, plus syntax error reporting and panic-mode recovery by synchronizing at statement boundaries.
Time About 6 hours this week
Why it matters
Recursive descent is how most production compilers (GCC, Clang, V8, Roslyn) parse. Once you can write one, you can parse almost anything.
How to approach it
Map each grammar rule to its parsing method and check them side by side. Trace the parse of an expression like 1 - 2 * 3 == 4 on paper through the call stack.
Challenges
3 challenges at the end of the chapter.
Challenges 1 (comma operator) and 2 (the ternary ?: operator) are great practice at adding grammar rules with the right precedence. Challenge 3 (error productions for binary operators missing a left operand) teaches good error messages. Do challenges that change Lox's behavior on a separate git branch. The cracked.guide check runs the official test suite for this chapter, and a challenge that changes semantics (new syntax, different errors) can make tests fail on main.
Traps
- Getting associativity wrong by using recursion where the book uses a loop.
- Error recovery that never resynchronizes, causing a cascade of bogus errors.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.