31. Syntax trees

A flat line of tokens

The scanner turns -2 * (3 + 4) into a flat row of tokens:

-  2  *  (  3  +  4  )

But that is not how you read it. You see a multiplication, whose left side is “minus 2”, and whose right side is a whole addition. The meaning is nested, one operation inside another. Before Drip can run this, it needs that nesting written down somewhere. The natural shape is a tree, like the ones you walked in chapter 9.

Which tree?

When you derived a sentence in chapter 30, every rule you used replaced one nonterminal with its parts. Draw each replacement as a node with children, and you get a tree of the whole derivation, called a parse tree. It is faithful but cluttered: it has a node for every rule and every token, including the ;.

Nodes as a discriminated union

You built a tree type like this in chapter 14. Drip’s is the same idea, with more kinds. Here are the first few, from companion/ts/src/ast.ts:

type Expr =
  | { kind: 'literal';
      value: number | string
           | boolean | null }
  | { kind: 'grouping'; expression: Expr }
  | { kind: 'unary';
      operator: Token; right: Expr }
  | { kind: 'binary'; left: Expr;
      operator: Token; right: Expr }
  | { kind: 'variable'; name: Token };
  // ...and seven more kinds

Every node is a plain object with a kind tag. Checking e.kind narrows e to one variant, so the checker knows a binary node has a left. Operators and names are kept as whole tokens, not just strings, so that a later error message can say which line they came from.

A literal’s value is what the scanner put in the token’s literal field: a number or a string. The keywords true, false and nil become literals too, holding true, false and null.

There is one kind that isn’t strictly needed: grouping, for brackets. The tree’s shape already says that 3 + 4 happens first. Drip keeps the node anyway, so a printed tree shows where the brackets were.

const lit = (value) =>
  ({ kind: 'literal', value });
const bin = (left, op, right) => ({
  kind: 'binary', left,
  operator: { lexeme: op }, right,
});

// 1 + 2 * 3, as the parser will
// build it: * is deeper, so it
// happens first.
const e = bin(lit(1), '+',
  bin(lit(2), '*', lit(3)));

console.log(e.kind);
console.log(e.left.value);
console.log(e.right.operator.lexeme);
console.log(e.right.right.value);

// Try: build (1 + 2) * 3 instead.

Expressions and statements

Drip has two families of node. An expression produces a value: 1 + 2, x, "hi". A statement does something: prints, declares a variable, loops. Statements get their own union:

type Stmt =
  | { kind: 'expression'; expression: Expr }
  | { kind: 'print'; expression: Expr }
  | { kind: 'let'; name: Token;
      initializer: Expr | null }
  | { kind: 'block'; statements: Stmt[] }
  | { kind: 'if'; condition: Expr;
      then: Stmt; else: Stmt | null }
  // ...while, function, return, class

Statements contain expressions (a print holds the expression to print), and some contain other statements (a block holds a list). A whole Drip program parses to an array of statements, Stmt[].

Printing a tree

A tree is hard to look at in the console. JSON.stringify works, but 1 + 2 alone is about 150 characters of braces. So Drip comes with a tree printer that writes each node as brackets, the operator first:

function printExpr(e: Expr): string {
  switch (e.kind) {
    case 'literal':
      return e.value === null
        ? 'nil' : String(e.value);
    case 'grouping':
      return '(group ' +
        printExpr(e.expression) + ')';
    case 'binary':
      return '(' + e.operator.lexeme +
        ' ' + printExpr(e.left) +
        ' ' + printExpr(e.right) + ')';
    // ...a case for every kind
  }
}

(A switch jumps to the case whose value equals e.kind.) The real printExpr in ast.ts has a case for all twelve kinds, and no default. Add a thirteenth kind without a case, and tsc reports that the function can end without returning a string: an exhaustiveness check for free.

function printExpr(e) {
  switch (e.kind) {
    case 'literal':
      return String(e.value);
    case 'grouping':
      return '(group ' +
        printExpr(e.expression) + ')';
    case 'unary':
      return '(' + e.operator.lexeme +
        ' ' + printExpr(e.right) + ')';
    case 'binary':
      return '(' + e.operator.lexeme +
        ' ' + printExpr(e.left) +
        ' ' + printExpr(e.right) + ')';
  }
}

The printer isn’t meant to reproduce the source. "hi" + name prints as (+ hi name), without quotes. Its job is to make a tree’s shape easy to compare with what you expected, which is exactly what a parser test needs:

test('* binds tighter than +', () => {
  expect(show('1 + 2 * 3'))
    .toBe('(+ 1 (* 2 3))');
});

Here show would scan, parse and print. That test is one line of expected text instead of a nest of objects.

Your turn

function printExpr(e) {
  // your code here
}

// -2 * (3 + 4)
const lit = (value) =>
  ({ kind: 'literal', value });
const op = (lexeme) => ({ lexeme });
const t = {
  kind: 'binary', operator: op('*'),
  left: {
    kind: 'unary', operator: op('-'),
    right: lit(2),
  },
  right: {
    kind: 'grouping',
    expression: {
      kind: 'binary', operator: op('+'),
      left: lit(3), right: lit(4),
    },
  },
};
console.log(printExpr(t));

function evaluate(e) {
  // your code here
}

const t = {
  kind: 'binary',
  operator: { lexeme: '*' },
  left: { kind: 'literal', value: 6 },
  right: { kind: 'literal', value: 7 },
};
console.log(evaluate(t));

What you learned

• An AST stores a program as nested nodes, keeping what affects its meaning and dropping punctuation and helper rules.
• Each AST node is a kind plus its children. Drip’s Expr and Stmt are discriminated unions tagged by kind.
• Expressions produce values; statements do things. A program is an array of statements.
• A tree printer writes each node as (operator children...), making a tree easy to check and to test.

Next: the parser that builds these trees from tokens.