The parser finds the stairs

The parser has found a staircase inside an arithmetic expression.

Make the grouping visible

The lexer handed it 1, +, 2, * and 3, all standing politely in a row. A row is not yet a calculation. The parser must decide which pieces belong together.

1 + 2 * 3

Add(
  Integer(1),
  Multiply(Integer(2), Integer(3))
)

These are sketch names for tree nodes, not Pooka’s internal constructor names. Their arrangement is the point. Multiplication sits inside addition’s right-hand side, so evaluating that subtree happens first.

Give operators their places

The grouping has an observable consequence:

main() {
  assert 1 + 2 * 3 == 7
  assert (1 + 2) * 3 == 9
}

A precedence-based expression parser gives operators different binding strengths. While reading the right-hand side of +, it allows * to gather its own operands. Parentheses can ask for a different grouping, and the parser must honour that request without keeping the parentheses as executable work.

Function calls and field access need their places in this arrangement too. A method call is not merely punctuation sprinkled on a name. It has a receiver and arguments that later phases must be able to inspect.

Find a safe place to resume

Then somebody forgets a closing bracket.

The parser has two jobs at that moment: explain what interrupted the construct, and find somewhere sensible to resume. Otherwise the rest of the file becomes a procession of errors caused by one missing character.

Recovery has to make progress. Returning an error without consuming anything can send the same token through the same unhappy function forever. I have considerable sympathy for the token, but nobody should spend their evening there.

A syntax tree is therefore more than a successful parse printed as a diagram. Its boundaries determine what can be checked, which locations can be highlighted, and how much useful work survives an incomplete file.

The arithmetic now has stairs. I am also putting a handrail on them.

— Peregrine Finch