32. Recursive descent parsing

Two trees for one line

What is 1 + 2 * 3? You learned the answer at school: 7, because multiplication happens first. But the tokens alone don’t say that. Both of these trees fit them:

The program that reads tokens and builds the tree is the parser, and it has to pick the left tree every time. The rule it follows is called precedence.

A grammar with levels

Chapter 30’s grammar had one rule for every expression. To build in precedence, give each precedence level its own rule, loosest first, and let each rule build its operands from the next, tighter rule:

expression → equality
equality   → comparison
               ( EQ_OP comparison )*
comparison → term ( CMP_OP term )*
term       → factor ( ADD_OP factor )*
factor     → unary ( MUL_OP unary )*
unary      → ( "!" | "-" ) unary
           | primary
primary    → NUMBER | STRING | "true"
           | "false" | "nil"
           | "(" expression ")"

EQ_OP  → "==" | "!="
CMP_OP → "<" | "<=" | ">" | ">="
ADD_OP → "+" | "-"
MUL_OP → "*" | "/"

So term can only join finished factors. When it sees the + in 1 + 2 * 3, the 2 * 3 on its right is one factor, built as a unit. The last rule, primary, is the base case: a single literal, or a whole expression in brackets, which starts again from the loosest level. That is why brackets can override precedence.

One function per rule

Now the trick that gives this chapter its name. Write one function for each rule. Where a rule mentions another rule, call that function. Where it says *, write a loop. Here tokens are plain strings, like '1 + 2 * 3'.split(' '), and i is the index of the next one:

const at = (...ops) =>
  ops.includes(ts[i]);
const next = () => ts[i++];

function term() {
  let left = factor();
  while (at('+', '-')) {
    const op = next();
    const right = factor();
    left = bin(left, op, right);
  }
  return left;
}

bin makes a binary node, and factor is the same shape with * and /, calling unary. The last two rules are just as direct:

function unary() {
  if (at('!', '-')) {
    const op = next();
    const right = unary();
    return { kind: 'unary', op, right };
  }
  return primary();
}

function primary() {
  const t = next();
  if (t === '(') {
    const e = expression();
    if (next() !== ')') {
      throw new Error("Expect ')'");
    }
    return { kind: 'group', e };
  }
  return lit(Number(t)); // and true...
}

unary calls itself, so - - 1 and !!x work. Watch the functions call each other on 1 + 2 * 3:

Here is the whole parser, all six levels, with a tree printer:

function parse(ts) {
  let i = 0;
  const at = (...ops) =>
    ops.includes(ts[i]);
  const next = () => ts[i++];
  const bin = (left, op, right) => ({
    kind: 'binary', left, op, right,
  });

  function equality() {
    let left = comparison();
    while (at('==', '!=')) {
      const op = next();
      const right = comparison();
      left = bin(left, op, right);
    }
    return left;
  }
  function comparison() {
    let left = term();
    while (at('<', '<=', '>', '>=')) {
      const op = next();
      const right = term();
      left = bin(left, op, right);
    }
    return left;
  }
  function term() {
    let left = factor();
    while (at('+', '-')) {
      const op = next();
      const right = factor();
      left = bin(left, op, right);
    }
    return left;
  }
  function factor() {
    let left = unary();
    while (at('*', '/')) {
      const op = next();
      const right = unary();
      left = bin(left, op, right);
    }
    return left;
  }
  function unary() {
    if (at('!', '-')) {
      const op = next();
      const right = unary();
      return {
        kind: 'unary', op, right,
      };
    }
    return primary();
  }
  function primary() {
    const t = next();
    if (t === '(') {
      const e = equality();
      if (next() !== ')') {
        throw new Error("Expect ')'");
      }
      return { kind: 'group', e };
    }
    if (t === 'true') return lit(true);
    if (t === 'false') {
      return lit(false);
    }
    if (t === 'nil') return lit(null);
    if (/^[0-9]/.test(t)) {
      return lit(Number(t));
    }
    throw new Error('Expect expr');
  }
  const lit = (value) =>
    ({ kind: 'literal', value });

  const tree = equality();
  if (i < ts.length) {
    throw new Error('Extra ' + ts[i]);
  }
  return tree;
}

function show(e) {
  switch (e.kind) {
    case 'literal':
      return e.value === null
        ? 'nil' : String(e.value);
    case 'group':
      return `(group ${show(e.e)})`;
    case 'unary':
      return `(${e.op} ` +
        `${show(e.right)})`;
    case 'binary':
      return `(${e.op} ` +
        `${show(e.left)} ` +
        `${show(e.right)})`;
  }
}

const src = '1 + 2 * 3 == 7';
const tree = parse(src.split(' '));
console.log(show(tree));
console.log(show(parse(
  '1 - 2 - 3'.split(' '))));
console.log(show(parse(
  '- ( 1 + 2 ) * 3 < 4'.split(' '))));

// Try: '8 / 2 / 2', '! true == false'
// Try a mistake: '1 + * 2'

Which way does a chain lean?

Precedence doesn’t settle 1 - 2 - 3. Both operators are on the same level, and the two groupings give different answers:

The loop in term does this for free. After 1 - 2, left holds the node (- 1 2). The loop goes round again, sees the second -, and builds a new node with that whole subtraction on its left. Each pass wraps the tree so far, so the chain leans left.

Why not write the rule the way chapter 30 first did, term → term "-" factor? Turned into code, the first thing term() would do is call term(), with the same token still next. That call would do the same, forever, until the stack overflows. A rule whose first symbol is its own name can’t be coded directly in recursive descent, which is why the grammar uses * and the code uses a loop.

The companion’s parser

Drip’s statements are parsed in exactly this style, in companion/ts/src/parser.ts. Here is the rule for if, and its function (error messages shortened):

ifStmt → "if" "(" expression ")" statement
         ( "else" statement )?

function ifStatement(): Stmt {
  consume('(', "Expect '('...");
  const condition = expression();
  consume(')', "Expect ')'...");
  const then = statement();
  const otherwise = match('else')
    ? statement() : null;
  return { kind: 'if', condition,
           then, else: otherwise };
}

consume takes a token that must be there, or reports an error; match takes a token only if it is there, which is how ? becomes code. statement() may be another if, so the functions recurse just as the rules do.

For expressions, though, the companion does something different. It uses a Pratt parser (chapter 33), which replaces the six level functions with one loop and a table of binding powers. It builds the same trees: a differential test (chapter 15) that gives random expressions to both this chapter’s parser and the companion’s finds no differences.

Your turn

function parse(ts) {
  let i = 0;
  const at = (...ops) =>
    ops.includes(ts[i]);
  const next = () => ts[i++];
  const bin = (left, op, right) => ({
    kind: 'binary', left, op, right,
  });

  // term → factor (("+" | "-") factor)*
  function term() {
    // your code here
    return factor();
  }
  // factor → primary
  //          (("*" | "/") primary)*
  function factor() {
    // your code here
    return primary();
  }
  function primary() {
    const t = next();
    if (t === '(') {
      const e = term();
      next(); // the ')'
      return { kind: 'group', e };
    }
    return {
      kind: 'literal', value: Number(t),
    };
  }
  return term();
}

function show(e) {
  if (e.kind === 'literal') {
    return String(e.value);
  }
  if (e.kind === 'group') {
    return `(group ${show(e.e)})`;
  }
  return `(${e.op} ${show(e.left)} ` +
    `${show(e.right)})`;
}

const ts = '1 + 2 * 3'.split(' ');
console.log(show(parse(ts)));

function parse(ts) {
  let i = 0;
  const at = (...ops) =>
    ops.includes(ts[i]);
  const next = () => ts[i++];
  const bin = (left, op, right) => ({
    kind: 'binary', left, op, right,
  });

  // comparison → term
  //   (("<" | "<=" | ">" | ">=") term)*
  function comparison() {
    // your code here
    return term();
  }
  function term() {
    let left = factor();
    while (at('+', '-')) {
      const op = next();
      const right = factor();
      left = bin(left, op, right);
    }
    return left;
  }
  function factor() {
    let left = primary();
    while (at('*', '/')) {
      const op = next();
      const right = primary();
      left = bin(left, op, right);
    }
    return left;
  }
  function primary() {
    const t = next();
    if (t === '(') {
      const e = comparison();
      next(); // the ')'
      return { kind: 'group', e };
    }
    return {
      kind: 'literal', value: Number(t),
    };
  }
  return comparison();
}

function show(e) {
  if (e.kind === 'literal') {
    return String(e.value);
  }
  if (e.kind === 'group') {
    return `(group ${show(e.e)})`;
  }
  return `(${e.op} ${show(e.left)} ` +
    `${show(e.right)})`;
}


const ts = '1 + 2 < 4'.split(' ');
console.log(show(parse(ts)));

What you learned

• A parser turns tokens into a syntax tree.
• Precedence: one grammar rule per level, loosest first. Tighter operators end up deeper in the tree, so they happen first.
• Recursive descent: one function per rule; alternatives are ifs, * is a loop, nonterminals are calls. Brackets restart at the top.
• Associativity: the loop wraps the tree so far, so a - b - c leans left. Left recursion can’t be coded directly: it never stops.
• Drip’s statements use recursive descent; its expressions use Pratt parsing, which builds the same trees.