skip to content

Tokens or Syntax Trees

The gap between a preprocessor that pastes tokens and a transformer that rewrites a parsed tree, and why the first breaks on precedence and side effects. Interviewers use it to test parsing intuition.

on this pageshow

questions

4

Why can a shorthand that substitutes argument text before parsing compute the wrong value inside a larger expression?

level: middleimportance: must knowfreq 62%

answer

  1. substitution runs before the grammar
  2. characters at the call site, not a value
  3. the caller's operators regroup them
  4. argument boundary and result boundary
  5. parenthesise every use and the body

basics

~20 s

Substitution happens before the grammar is applied, so the pasted characters are parsed together with whatever surrounds the call. The caller's operators can bind tighter than the body's, regrouping the expression into something the author never wrote.

solid answer

~50 s

A text-level shorthand is not a call. The compiler never sees `LARGER(width, height)`; it sees the characters the body expanded to, parsed together with the call site's own operators. If the body is `if a > b then a else b` and the call site is `LARGER(width, height) * 2`, the parser reads `if width > height then width else height * 2` — the multiplication binds into the else branch only, so the result is doubled when the second value wins and left unscaled when the first does. Two boundaries leak: the **argument** boundary, where an argument that is itself an expression gets its pieces regrouped by the body's operators, and the **result** boundary, where the body's outermost operator meets the caller's. The textual discipline is to parenthesise every parameter use and the whole body. A transformer that rewrites a parsed tree grafts a finished node instead, so grouping is structural.

code

pseudocode · 9 lines
pseudocode
define LARGER(a, b) as if a > b then a else b

// call site as written
scaled = LARGER(width, height) * 2

// what the parser actually sees after substitution
scaled = if width > height then width else height * 2
// groups as: if width > height then width else (height * 2)
// height wins -> height * 2 (intended); width wins -> width, unscaled

go deeper

for a junior

Recall that a text-level shorthand is pasted into the source before anything is parsed, so it is not a call and nothing about it is worked out in advance.

for a middle

Explain both leak points — arguments regrouped by the body's operators, and the body's outermost operator meeting the caller's — and give the parenthesisation discipline that closes each.

for a senior

Show how the defect hides: the expansion is correct for some inputs, so a passing suite proves nothing, and the way to find it is to read the expanded form rather than the source.

for a principal

Decide what a review standard must demand of any text-level shorthand a team ships, and be honest about who pays when that discipline is only a convention nobody checks.

## What the toolchain actually receives A text-level shorthand is a rule applied **before** the language's grammar is applied. The characters of the call site are replaced by the characters of the body, with every occurrence of a parameter replaced by the characters of the matching argument, and only then is the whole file parsed. Nothing in that sequence knows about operators, operands, precedence or values: at substitution time the program is still text. That is the whole source of the surprise. The mental model most people carry — "the shorthand works out a value and hands it back, like a call" — is right about intent and wrong about mechanism, and the bug lives at the mechanism. ## The two boundaries where grouping leaks - **The argument boundary.** A parameter appears inside the body beside the body's own operators. A squaring shorthand whose body is `v * v` turns the argument `a + b` into `a + b * a + b`, because the multiplication the body supplied binds tighter than the addition the argument contained. - **The result boundary.** The body's outermost operator meets whatever surrounds the call. A body that ends in a loosely binding construct loses to a tighter operator written after the call. - **Neither is visible at the definition.** The definition parses fine on its own; the damage depends entirely on what the call site looks like, which is why a shorthand can be used correctly a hundred times and wrongly on the hundred-and-first. - **The result is often *partly* right.** That is what keeps it alive in a codebase. ## A worked expansion ``` define LARGER(a, b) as if a > b then a else b scaled = LARGER(width, height) * 2 // what the parser sees, and how it groups it scaled = if width > height then width else (height * 2) ``` Trace both branches. When `height` is the larger value, the else branch fires and the result is `height * 2` — exactly what was intended. When `width` is the larger value, the then branch fires and the result is `width`, never scaled. The shorthand is correct for half its inputs. A test that only ever exercises the second ordering passes, and the defect ships. ## The textual discipline, and what it does not cover Where only a text-level facility is available, the convention that closes the precedence hole is mechanical: 1. Parenthesise **every use of every parameter** inside the body, so each substituted argument becomes one grouped operand. 2. Wrap the **entire body** in parentheses, so the expansion becomes one grouped expression to whatever surrounds it. 3. Keep the body a **single expression** — never a sequence of statements. Applied to the worked example, the body becomes `( if (a) > (b) then (a) else (b) )` and the call site groups as `( ... ) * 2` whichever branch wins. Three honest limits. The discipline is a convention that nothing enforces, so one shorthand written in a hurry reopens the hole. Parentheses are an expression-level device, so they do nothing for a body that expands to more than one statement. And the diagnostics, when the paste does produce something ungrammatical, are reported where the failing characters are — inside text the author never typed. ## Why a tree-level rewrite does not have this class of bug A transformer that works on a parsed tree is handed the call as a node, with its arguments already parsed into nodes of their own, and returns a node. Grafting a node into the caller's tree cannot change how the caller's operators were grouped, because that grouping was decided by the parser before the transformer ran, and there is no second parse in which it could be re-decided. | | Text substitution | Tree rewrite | |---|---|---| | What it receives | characters at the call site | the call and its arguments as parsed nodes | | When grouping is decided | after substitution, by parsing the result | before the rewrite, by the parse that produced the nodes | | What it produces | a run of characters | one node, grafted whole | | Accidental precedence surprise | possible at both boundaries | does not arise | | Where a diagnostic points | into the expanded characters | wherever the transformer chooses to point it | The guarantee is precise and worth stating precisely: the *accidental* regrouping disappears. A transformer can still build a subtree that means the wrong thing — it simply cannot do so by having its output re-parsed in a context it did not anticipate.

  • Parenthesising every parameter use and the whole body — which expansion bug does that not fix?
    The grouping of statements. Parentheses are an expression-level device, so a body that expands to a sequence of statements still contributes only its first statement to a branch that takes a single statement. Closing that needs a block around the body, or a rewrite that returns a block node.
  • Why does a transformer that returns a parsed subtree not have the argument-boundary problem?
    Its argument arrives already parsed, as one node carrying its own internal grouping, and what the transformer returns is also one node. There is no second parse in which the caller's operators could be re-applied to the pieces, so the grouping the author wrote survives intact.
  • The same shorthand has been used correctly for months. What makes a new call site suddenly wrong?
    The call site's context, which is the half of the expansion the definition cannot see. The first use that puts the call next to an operator binding tighter than the body's outermost one regroups the result. Nothing about the shorthand changed; the surrounding text did.

It is the difference between handing someone a sealed box and dictating its contents into the middle of their sentence: what you dictate is read under their punctuation, not yours.

saying these in an interview costs you the question

  • Thinks the shorthand computes a value before the caller's expression is parsed
  • Believes a text-level shorthand behaves exactly like a function call
  • Assumes parenthesising the arguments alone makes the expansion safe
  • Expects the compiler to flag the regrouping as an error
  • Claims the wrong result appears for every input, so tests must catch it
open as a page

Why can a shorthand that expands to two statements leave only its first statement inside a conditional branch?

level: middleimportance: should knowfreq 46%

basics

~20 s

Because substitution inserts statements, not a block. In a grammar where a branch takes one statement unless delimiters group several, only the first expanded statement belongs to the branch and the rest becomes ordinary code after the conditional.

open as a page

What can a transformer that rewrites a parsed tree reject that a text-substituting shorthand cannot?

level: seniorimportance: should knowfreq 40%

basics

~20 s

A tree transformer is handed parsed nodes, so it can refuse a call whose arguments are the wrong number or the wrong kind of construct, and report that at the caller's position. A paste has only characters.

open as a page

As a lead, how would you decide whether a codebase may use text-level substitution when a tree-rewriting facility exists?

level: principalimportance: nice to knowfreq 24%

basics

~20 s

Decide on review cost, not power. Text-level substitution is acceptable only where the body is one fully parenthesised expression; anything contributing statements, or needing to refuse bad input, belongs to a tree rewrite or an ordinary function.

open as a page