Precedence and associativity determine which operations become children of others.
By the end: Read an abstract syntax tree and predict the structure of a small recursive-descent parser.
Structure changes meaning
The token list 2 + 3 * 4 does not itself say which operation happens first. Our grammar makes multiplication bind more tightly, so addition is the root and multiplication its right child. Parentheses in (2 + 3) * 4 change the root to multiplication. The results are fourteen and twenty.
An abstract syntax tree retains meaningful structure rather than every piece of spelling. Parentheses can disappear once their grouping is encoded by the tree. A concrete syntax tree or lossless syntax representation may retain punctuation and trivia for formatting and source tools.
Read the parent and child relationships
A binary syntax node records an operator and two ordered children. The left child supplies the left operand, and the right child supplies the right operand. A literal supplies a value without another arithmetic step. In 7 - 2 * 3, the subtraction node therefore needs a literal seven and a multiplication subtree. That subtree needs literals two and three. Reading the tree this way gives a dependency explanation for the result, rather than a remembered instruction to perform multiplication first.
Work upward through this example. The multiplication receives two and three and returns six. The subtraction then receives seven and six and returns one. Now put parentheses around 7 - 2. The multiplication becomes the root, and its left child is subtraction. That child returns five, which the root multiplies by three to obtain fifteen. Both sources contain the same literal values and the same binary operators. Their different parent and child relationships account for the different answers without changing any arithmetic rule.
Grouping changes the root
Original syntax trees. Positions are schematic, not time or numerical magnitude. Each line joins a parent operation to one operand.
The root is the operation that combines the whole expression, so it normally computes after its descendants. This does not mean that every node lower on the page executes before every higher node. SmallExpr evaluates the entire left subtree before the right subtree. A deep operation on the right can therefore execute after a shallower operation on the left. Tree edges show which results an operation needs. A language's evaluation rules supply the remaining ordering constraints between independent children of the same parent.
Distinguish grouping from source punctuation. In this implementation, reading an opening parenthesis starts another expression parse. After checking the closing parenthesis, the parser returns the enclosed node rather than constructing a special grouping node. Thus 7 and ((7)) have the same literal node kind and value. Their token streams differ, and the retained source positions refer to the literal itself. A formatter that must reproduce every original parenthesis would need more information than this abstract tree retains about the input text.
Source locations also do not replace structure. For (7 - 2) * 3, the subtraction's stored interval covers its operands and the operator between them, but not the surrounding parentheses. The multiplication's interval begins at the first child's stored start. Consequently this model does not promise that every node span includes all punctuation associated with its source phrase. For diagnostics, a compiler must define what its locations identify. For exact source rewriting, it must retain or recover punctuation and whitespace through an appropriate representation.
Node spans need not include grouping punctuation
Exact zero-based source offsets for (7 - 2) * 3. Each source cell is one ASCII character; bracket endpoints mark half-open node intervals. The AST root starts at 1, not at the opening parenthesis.
Try both versions of the seven example in the syntax view. Before entering the second source, sketch only the root and its two children. Predict which child must itself be an operation. Then compare your sketch with the displayed tree, without using a computed value as the acceptance criterion. The syntax view deliberately stops before binding and typing. You can correctly predict its tree even when a later stage would reject an operand. This separates evidence about grouping from evidence about whether execution is permitted.
Encode precedence in parser calls
Our parser reads an expression as a term followed by zero or more + or − and another term. A term reads primary expressions joined by *. A primary reads a literal, name, unary minus, or parenthesized expression. Calling the tighter level first makes it become a child of the looser operation.
Repeated operators are accumulated from left to right. Thus 8 − 3 − 1 becomes (8 − 3) − 1, yielding four. A right-associated subtraction tree would instead give six. Precedence chooses between operator levels; associativity chooses grouping within a level.
Follow the parser's unfinished work
Recursive descent stores unfinished parsing work in function calls. The expression function asks term for a complete operand at the tighter precedence level. Term asks primary for a starting operand and then consumes any following multiplication operators with their operands. Only after term returns does expression inspect addition or subtraction. This call arrangement explains why a multiplication becomes a child of addition. The parser does not first build an addition tree and then rotate multiplication into place through a separate precedence correction pass afterward.
Trace 2 + 3 * 4 with a cursor at the next unread token. The initial term returns literal two and leaves the cursor at plus. Expression consumes plus and asks for another term. That term starts with three, sees multiplication, consumes four, and returns a multiplication node. Only now can expression build the addition node. The cursor reaches the end marker after the right term completes. These are parsing events that construct nodes; none requires computing twelve or fourteen during the trace.
Construct nodes without calculating values
Completed parsing work
Next token
Structure returned or retained
Initial term
+
Literal 2
Consume +
3
Left operand remains literal 2
Right term begins
*
Literal 3 retained by term
Right term consumes * and 4
End
Multiplication with children 3 and 4
Expression combines operands
End
Addition with children 2 and the product
Exact parser sequence for 2 + 3 * 4. Rows are construction events, not arithmetic execution or measured time.
The repetition inside expression determines association. For 9 - 4 + 2, its first term is nine. After reading minus and the term four, the accumulated left tree represents 9 - 4. The following plus makes a new root whose left child is that entire accumulated tree and whose right child is two. This yields seven under the arithmetic rules. Giving addition and subtraction equal precedence does not say to group the addition first. The shared repetition makes both operators extend the accumulated left operand.
Compare this with 9 - (4 + 2). After minus, the right term begins with an opening parenthesis. Primary asks expression to parse the enclosed addition, then requires a closing parenthesis before returning its node. The outer subtraction receives that complete addition as its right child, so its result is three. Parentheses let a looser operator appear inside an operand handled at a tighter level. They do not change the precedence table for the rest of the source or introduce a new arithmetic operation.
Unary minus requires a different decision because it has only one child. In -2 * 3, primary consumes minus and recursively reads its child as another primary. That child is two, not the whole remaining product. Term then combines the resulting negation with three. In -(2 * 3), primary instead finds a parenthesized product as the negation's child. Both return negative six here, but their trees differ. Equal numerical results do not establish that the parser constructed the same structure or retained the same source locations.
Equal values can have different negation trees
Both expressions evaluate to −6, but their original ASTs differ. The label neg denotes unary minus. Schematic spacing shows structure only.
You can inspect association with 9 - 4 - 2 and 9 - (4 - 2). Predict five as the first intermediate subtraction for the unparenthesized source, followed by three as its final value. For the parenthesized source, predict two inside the right child and seven at the root. Draw the cursor positions after each complete term, not after each character. The lexer already grouped characters into tokens. This exercise tests the boundary between parser calls rather than your ability to scan decimal digits or recognize individual symbols.
Work through the mechanism
Inspect the parsed structure
Presets replace the whole source. Editing replaces the current calculation and resets any execution trace. Names: x = 4, y = 7, flag = true. Use ASCII - for subtraction and negation. Arithmetic is signed 32-bit wrapping; booleans are not numbers. See lesson 1 for the full grammar and editor bounds.
Abstract syntax tree
Parsing succeeded. Binding and type checking have not been used to accept this syntax tree.
Nodes are operations, literals, or names. Edges identify children; spacing has no numerical scale. The entered source is never passed to JavaScript eval or Function.
Source
Tree grouping
Value
2 + 3 * 4
2 + (3 * 4)
14
(2 + 3) * 4
(2 + 3) * 4
20
8 - 3 - 1
(8 - 3) - 1
4
The live diagram is the parsed structure, not a hand-selected answer for each preset.
Use the tree to compare representations
A tree is useful beyond drawing because its node kinds support different traversals. An evaluator returns values; a type checker returns types or a diagnostic; a bytecode emitter returns instructions. They can all follow the same child relationships while doing different work at each node. For x - y * 2, parsing identifies subtraction above multiplication without reading either binding. Checking later establishes that x and y are integers. Execution reads four and seven from the fixed environment and obtains negative ten.
Translate that tree into the teaching stack machine by visiting the left child, then the right child, then the operator. The emitted sequence is LOAD x, LOAD y, PUSH 2, MUL, SUB. After the first three instructions the stack, bottom first, contains four, seven, and two. Multiplication replaces seven and two with fourteen. Subtraction then replaces four and fourteen with negative ten. The instruction stream makes intermediate storage explicit, but the order of emitted operations comes from the tree together with SmallExpr's left-before-right evaluation rule.
Now compare (x - y) * 2. Its emission is LOAD x, LOAD y, SUB, PUSH 2, MUL. The first subtraction produces negative three, and multiplication produces negative six. Each version contains five abstract VM instructions. Equal instruction counts therefore do not establish equal behavior, and different results here do not indicate a slower implementation. A count describes this instruction vocabulary. A performance claim would also need an engine, workload, timing method, and control of conditions beyond the static shape of these two syntax trees.
Grouping changes when the stack combines operands
Completed instruction
x - y * 2: stack
(x - y) * 2: stack
1: LOAD x in both
[4]
[4]
2: LOAD y in both
[4, 7]
[4, 7]
3: PUSH 2 versus SUB
[4, 7, 2]
[−3]
4: MUL versus PUSH 2
[4, 14]
[−3, 2]
5: SUB versus MUL
[−10]
[−6]
Exact teaching VM trace with x = 4 and y = 7. Stacks are bottom first. Five abstract instructions in each column do not establish equal results or real performance.
A useful local translation argument starts with each subtree's contract. Code emitted for a literal or name pushes one value while preserving the stack entries beneath it. Assuming the two child translations satisfy that contract, a binary node's code first adds the left result and then the right result. Its arithmetic instruction consumes those two entries and pushes their combined result. The overall stack height increases by one. This reasoning explains why tree-shaped code generation can preserve expression meaning without executing the source during compilation.
The argument still depends on matching operation semantics. An integer multiplication in the tree and MUL in the VM must both use signed 32-bit wrapping. A translator using unbounded arithmetic in one route would not satisfy the argument at overflow boundaries. Likewise SUB must interpret the top stack entry as the right operand. Tests comparing tree and VM results provide concrete evidence for examples, while the subtree argument explains the general relationship under these assumptions. Neither licenses silently borrowing another language's coercion or overflow rules.
A local contract for binary-node translation
Translation segment
Stack height relative to entry
Proof obligation
Enter with a valid stack prefix
0
The prefix represents earlier work
Emit and run the left child
+1
Preserve prefix; push the left value
Emit and run the right child
+2
Preserve prefix and left value
Run the binary instruction
+1
Pop right, then left; apply matching arithmetic
Finish the subtree
+1
Exactly its value remains above the prefix
An inductive translation argument, not an execution benchmark. Height changes count stack entries; the contract assumes valid binding and typing and matching int32 operations.
Use the syntax view to compare x - y * 2 with its parenthesized variant, then write the two instruction lists on paper before consulting the execution lesson. Mark the instruction that first combines any operands. In one list it is MUL; in the other it is SUB. That point identifies where the source grouping first affects dynamic arithmetic. Both trees use only three leaves and fit the ordinary syntax display. The paper translation is an explanation of this implemented bytecode vocabulary, not a request for native machine code.
Parsing is not evaluation
A parser builds structure without needing the current value of x. A later interpreter can walk the tree, and a compiler can translate it into another form. This separation lets the same structure support checking, optimization, and diagnostics.
A parser must reject leftover tokens and malformed nesting rather than silently accept a valid prefix. An editor may recover after an error to show more diagnostics, but recovery needs explicit rules. The lab stops at its first error; it is not a production recovery parser.
Identify what parsing has established
Successful parsing establishes a complete grammatical structure within the lab's bounds. It does not establish that every name exists. For absent * 2, primary can construct a name node just as it constructs one for x. Binding later rejects absent because the fixed environment has no such entry. Similarly, flag * 2 has a grammatical multiplication tree but fails the integer operand rule. These distinctions matter when examining an editor that displays partial evidence. Seeing a plausible tree is not evidence that the whole compilation pipeline accepted the program.
A complete expression parser must also account for all tokens. For 2 3, expression can initially construct literal two, but the remaining number is not an allowed continuation. SmallExpr rejects that leftover token at offset two instead of returning a successful tree for the prefix. For 2 +, the parser has consumed an operator and needs a right operand when it encounters the end marker. The error is therefore an expected operand, not an unknown operator. Both failures concern grammar despite using individually supported lexical tokens.
Missing delimiters expose another unfinished obligation. In (2 + 3, the inner expression is complete, but primary still owes a closing parenthesis. The end marker at offset six cannot fulfill that obligation. In 2 + * 3, the multiplication symbol appears where primary must begin an operand, at offset four. An error location identifies where the implementation detected the contradiction with its grammar. It does not prove that the user's intended correction is uniquely determined. Removing the star and inserting an operand are different possible repairs.
Which parsing obligation remains unfinished?
Source
Detection offset
Unfulfilled obligation
2 3
2
No leftover token after a complete expression
2 +
3, end marker
A right operand after +
(2 + 3
6, end marker
A closing parenthesis
2 + * 3
4
A primary operand, not *
absent * 2
No parsing error
Later binding check finds no absent declaration
flag * 2
No parsing error
Later typing check rejects bool arithmetic
Exact SmallExpr detection points in zero-based string offsets. The syntax-only view does not run the later checks listed in the last two rows.
Some inputs instead encounter display limits. Eight leaves are allowed, but nine exceed the general tree bound even if their arithmetic grammar is ordinary. Parenthesis nesting and AST depth are different measures because grouping nodes disappear from this AST. Nested unary negations do remain nodes and therefore deepen the tree. These bounds protect the lesson's implementation and figures. They should not be described as general restrictions of recursive descent, or as a theorem that a larger expression has no valid parse in a more capable implementation.
Explore the distinction by entering 2 3, 2 +, and (2 + 3 separately in the syntax view. Predict which obligation fails before looking at the message. Then enter absent * 2 and flag * 2 there. Both should display trees because this view performs no acceptance check for binding or types. Compare the same inputs with the relevant later lesson when you want those checks. Changing views changes which responsibilities are demonstrated; it does not change the SmallExpr grammar or make boolean arithmetic valid.
Finally, test redundant grouping with ((x)). Predict one name node, not a chain of grouping nodes. Contrast that result with --x, which contains two actual negation nodes above the name. With x equal to four, evaluation would return four in both cases, but the second expression requests two operations before any transformation. A parser records those requested operations rather than removing them because their values happen to cancel. Simplifying a valid tree is a separate transformation with its own semantic obligations and implementation choices.
Original ASTs for ((x)) and --x. Both evaluate to 4 with x = 4, but only the right tree requests negations. Node placement is schematic.
Exercises
Change the root
Compare 2 + 3 * 4 with (2 + 3) * 4. Name each root operation and calculate both values.
Hint
Evaluate the operation represented by each child before the root.
Worked answer
Parentheses change which operation is the root.
Tree
Child result
Final result
Addition root
3 * 4 = 12
14
Multiplication root
2 + 3 = 5
20
The answer diagrams show the actual two structures.
The first root is +. Its right child computes 3 × 4 = 12, then addition gives fourteen. The second root is *. Its left child computes 2 + 3 = 5, then multiplication gives twenty. The same numbers and binary operators can produce different trees.
Left association
How does SmallExpr parse 8 - 3 - 1, and what would right association change?
Hint
The parser extends the left subtree each time it sees another subtraction.
Worked answer
Association
Grouping
Value
Left
(8 - 3) - 1
4
Right
8 - (3 - 1)
6
Equal precedence still needs an associativity rule.
Left association makes (8 − 3) − 1 = 4. Right association would make 8 − (3 − 1) = 6. Saying that all subtraction operators have equal precedence is insufficient to choose between these groupings.
Sources and further reading
The explanations, examples, and worked answers are complete without these optional links. The sources describe specific implementations and language contracts, not one universal compiler pipeline. SmallExpr and the later pseudocode models are constructed teaching examples. Source notes identify the selected material reviewed; this is not an exhaustive compiler survey, production conformance test, or independent specialist review.