beginnerAST
Why use an AST instead of compiling tokens directly?
Whether the candidate understands that structure is the thing being computed, not a convenience. The discriminating detail is whether they can name a question that a flat token list *cannot* answer at all, as opposed to one it answers awkwardly.
What a strong answer covers
- A token list is flat. It cannot express that
*binds tighter than+, that thiselsebelongs to thatif, or that this expression is the argument of that call. Those are the facts every later phase needs, and they are exactly the facts the grammar assigns. A tree is the representation in which they are recorded. - Once the structure exists, semantic analysis has something to attach to: a symbol on every identifier node, a type on every expression node. You cannot hang a resolved symbol on a token, because a token does not know which scope it is in.
- The tree is also where transformations happen. Desugaring a
for..inloop, constant folding on the tree, inserting an implicit conversion — all of these are rewrites of subtrees. On a token list the same operations are string edits, and every one of them can produce something that no longer parses. - Finally, the AST outlives the compiler that built it. The formatter, the linter, the language server, the refactoring engine and the documentation extractor are all written against the same tree. Building the structure once and sharing it is the difference between a compiler and a toolchain.
✓ Green flags
- Names structure explicitly: nesting, precedence, grouping — facts that exist in the tree and nowhere in the token stream.
- Points out that semantic information needs somewhere to live, and that a node is that place.
- Gives a transformation example — desugaring, folding, an implicit coercion — and notes that tree rewrites cannot produce unparseable output.
- Mentions tooling reuse: the same tree serving the IDE, the linter and the formatter.
- Knows the AST is not the parse tree, and can say what the parse tree has that the AST drops.
✗ Red flags
- "It is easier to read." The AST is a data structure, not a display format; nobody reads it except through a dumper.
- "You could compile tokens directly, an AST is just an optimization." You cannot: precedence and nesting are not present in the token stream, so the information does not exist to compile from.
- "The AST and the parse tree are the same thing." They are not: the parse tree has a node for every grammar rule and every punctuation token, which is why concrete syntax trees exist separately for formatters.
- "The AST is the IR." Two different representations with two different jobs — the AST is shaped by the language, the IR is shaped by the analyses.
Follow-up
A code formatter needs to preserve comments and the author's line breaks. A typical AST discards both. What representation do formatters use instead, and what does that cost?
Implementation challenge
What to ask them to write or trace on a whiteboard.
Draw the AST for f(a + b, c * d) and then the parse tree for the same input under a grammar with the usual expression rules. Circle every node that exists in one and not the other, and say which phase needs it.