What does a compiler drop when it converts a parse tree into an abstract syntax tree?
answer
- one records a proof, one a meaning
- the derivation versus the program
- chain nodes with one child vanish
- shape carries what parentheses said
- positions stay, punctuation goes
basics
~20 sAn abstract syntax tree keeps operators, operands and structure, and drops what only guided the parser: grouping parentheses, separators and terminators, layout, and single-child chain nodes from precedence rules. The tree's shape already encodes the grouping those tokens expressed.
solid answer
~50 sA parse tree records the derivation: one node per grammar production applied and one leaf per token consumed, including punctuation and the chain of non-terminals a precedence-layered grammar needs (`expr` to `term` to `factor`). An abstract syntax tree records the program's meaning instead. From `(rate + delta) * 2` it keeps `Mul(Add(rate, delta), 2)` and drops the parentheses, the chain nodes with a single child, and the separators — because the grouping the parentheses expressed is now carried by the tree shape, with the addition node sitting under the multiplication node. What it keeps beyond operators and operands is source positions, so later diagnostics can point back at what the programmer wrote, and empty slots that later passes fill in. Layout and comments are usually set aside as trivia, though a tool that must reprint the original text keeps them attached.
go deeper
Recall that a compiler builds a tree from the tokens, and that the tree it actually works on is a trimmed version holding operators and operands rather than every bracket and comma the programmer typed.
Explain the mechanics: one interior node per production in the parse tree, versus one node per meaningful construct in the AST, and be able to name what carries the grouping after parentheses are dropped.
Show the judgment of someone who has shipped a tool over a tree: which information you must retain on AST nodes — positions, trivia attachments — so diagnostics and reprinting still work after the abstraction.
Frame it as an interface decision. The AST is the contract every later pass depends on, so what it abstracts away determines which tools your compiler can ever host and what a schema change costs downstream.
## Two trees, two jobs A parser has one job: decide whether a token stream can be derived from the grammar, and record how. The **parse tree** (also called the *concrete syntax tree*) is that record. It has one interior node for every production applied and one leaf for every token consumed — including tokens that exist only so the parser can tell one shape from another. The **abstract syntax tree (AST)** is a different artefact with a different job: it is the data structure every later pass in the front end walks. It records *what the program means*, not *how the parser proved it well formed*. Think of a small stream-transformation language and the source line: ``` out = filter(in, (rate + delta) * 2 > limit) ``` A precedence-layered grammar derives the condition through a ladder of non-terminals — comparison, then additive, then multiplicative, then primary — so the parse tree for that one condition can easily run to a dozen interior nodes, most of them with exactly one child. The AST for the same condition is five nodes: `Gt(Mul(Add(rate, delta), 2), limit)`. ## What the AST keeps - The **construct at each node**: an operator, a call, an assignment, a conditional. - Its **operands as children**, in the order the language assigns them. - **Source positions** — a line and column, or a byte span — so a later message can point at the text the programmer typed. - **Slots later passes fill in**, such as the declaration a name resolves to or the type an expression carries. ## What it drops, and why that is safe | Concrete item | In the AST? | Why it can go | |---|---|---| | Grouping parentheses | No | Their whole effect is the tree's shape, and the shape survives | | Separators and terminators (commas, semicolons) | No | They separate children that are already distinct children | | Marker keywords (`then`, `do`, `begin`) | No | The node kind already says which construct this is | | Single-child chain nodes from precedence layers | No | A node with one child adds no information | | Operator and operands | Yes | This is the meaning | | Source position | Yes | Diagnostics and debug information need it | | Comments and layout (trivia) | Usually not | Kept aside, or attached when a tool must reprint the source | The rule behind the table: **an item may be dropped when the information it carried is recoverable from the tree's shape, or is irrelevant to every pass that will read the tree.** Parentheses are the cleanest case. `(rate + delta) * 2` and `rate + delta * 2` parse to *different* trees; once the first has `Add` as a child of `Mul`, the parentheses have done their whole job. A printer that knows the operators' precedence can even put them back when it needs to render the tree as text. ## The conversion is a design decision, not a fixed step There are two common arrangements, and interviewers accept either: 1. **Build the parse tree, then walk it** and construct the AST as a separate pass. Easier to reason about; costs one extra traversal and one extra data structure. 2. **Build the AST directly** in the parser's actions, never materialising a full parse tree. This is what most hand-written front ends do. Either way the AST is a *normal form*: several different surface spellings can land on the same tree, which is exactly why the rest of the compiler is simpler. ## When you must not drop it The abstraction is a default, not a law. A formatter, a refactoring tool or an editor that must hand back a file with the author's spacing and comments intact cannot work from a tree that discarded them. Such tools either keep the concrete syntax or attach trivia to AST nodes as leading and trailing attachments. If a candidate says an AST *always* throws layout away, that is the claim to probe. ## What interviewers listen for The strong answer names a specific dropped item and explains *what now carries its meaning* — parentheses gone, grouping carried by parent-child structure. The weak answer describes the AST as "a smaller parse tree" without saying what determines which parts shrink, or claims the AST is what the parser produces by definition, missing that it is a deliberately designed structure.
- If parentheses are dropped, how can a printer regenerate them from the AST?The printer walks the tree and compares each child's operator precedence with its parent's. Where a child binds more loosely than its parent's position requires — an addition node under a multiplication node — it emits parentheses. It does not reproduce redundant parentheses the author wrote, only those the shape demands.
- Why does an AST node need a source position at all, if it has already been checked for syntax?Every message produced after parsing — a name that does not resolve, a type disagreement, a runtime trap mapped back to source — has to point somewhere in the file. Positions are also what debug information is built from. Losing them means later passes can only say a problem exists, not where.
- Do two different source texts ever produce the same AST?Routinely. Redundant parentheses, different spacing, and surface forms that desugar to the same core construct all converge on one tree. That convergence is the point: later passes then handle one shape rather than every way it could have been written.
saying these in an interview costs you the question
- Says the AST keeps parentheses so grouping is not lost
- Treats parse tree and AST as two names for one structure
- Claims an AST never carries source positions
- Says every grammar non-terminal becomes an AST node
- Assumes the AST can always be reprinted as the exact original text