7.1 Concrete Syntax Tree vs Abstract Syntax Tree

A parser first proves that tokens form a legal sentence. The tree it produces can either keep the grammar almost literally or keep only the program structure that later phases need. A concrete syntax tree (CST) records grammar productions, punctuation, keywords, and helper rules. An abstract syntax tree (AST) removes grammar scaffolding after its meaning has been captured.

For let total = price * count + 3;, a CST may contain LetKeyword, Identifier, Equal, Expr, Term, ExprTail, Plus, and Semicolon. A useful AST is smaller:

LetStmt(total,
  Binary(Binary(Name(price), *, Name(count)), +, Int(3)))

The AST has not lost precedence. Multiplication appears inside the left child of addition, so the grouping is explicit. The semicolon is no longer a semantic child, but its source range can still be retained for diagnostics.

What Survives the CST-to-AST Step

The guiding question for each row is whether removing it would change what a later phase computes. Anything that only helped the parser prove legality can go; anything a consumer still reads must stay.

Choose the Tree for Its Consumer

Formatters, refactoring tools, and source-to-source transforms often need comments, whitespace, exact parentheses, and spelling. They use a CST or a lossless syntax tree. Name resolution, type checking, and code generation usually want an AST because they need declarations, expressions, statements, and control flow rather than every comma.

Do not remove syntax merely because it looks cosmetic. Parentheses can disappear only after their grouping effect is reflected by tree shape. A type annotation may not change runtime code but is essential to the type checker. A reliable rule is: discard syntax only when it is redundant for every later consumer you support.

Desugaring Is a Semantics-Preserving Transformation

Users may write convenient syntax that the core compiler does not need to carry. A for init; test; step { body } loop can become a block containing init and a while whose body executes step after body. This is desugaring. It reduces later compiler complexity, but it must preserve scope, continue behavior, evaluation order, and diagnostics.

Keep an origin range for synthesized nodes. Otherwise a type error in a lowered while can point at code the user never wrote. Test desugaring with an empty test, nested loops, break, continue, and a variable declared in init.

Practical Hint

Print a CST and AST for one small program. If the AST still contains ExprTail and semicolon nodes, it is likely too concrete. If it cannot distinguish a + b * c from (a + b) * c, it is too abstract.

Worked Comparison: Parentheses and Comments

Compare a + (b * c) // subtotal with a + b * c. A language may give both expressions the same AST because precedence already groups multiplication. A formatter that promises to preserve the comment location cannot work from that AST alone: it needs trivia attached to tokens or a lossless tree. Conversely, a type checker does not want to walk comment nodes before reaching a binary expression. This is why production tooling may retain two related representations instead of forcing one tree to do incompatible jobs.

Desugaring has a similar boundary. x += f() can become x = x + f() only if reading x once and assigning it once has the same behavior. For array[index()] += f(), naive lowering could evaluate index() twice. A safe lowering introduces temporaries, preserving evaluation count and order.

Questions to Ask Before Dropping a Node

• Does removing it erase user-visible grouping, comments, type syntax, or an error location?

• Does a lowered form evaluate any source expression more times than before?

• Can a formatter or refactoring tool round-trip the construct with the representation it receives?