92. Parsing real JavaScript

A bigger language

Drip’s grammar fits on a page. JavaScript’s specification is hundreds of pages long^[5], and it grows every year. Writing a complete JavaScript parser is a project in itself, and it isn’t the project Viscosity is about. What Viscosity needs is a syntax tree it can lower to VIR.

ESTree

ESTree began as the documented output of the parser built into Firefox’s SpiderMonkey engine, and caught on as the common format for tools that work on JavaScript source^[2]. Every node is a plain object whose type field says which kind of node it is, a discriminated union, as chapter 14 showed^[1]. Here is the real tree acorn builds for p.x += p.vx;, without its positions and optional flags:

ExpressionStatement
  expression: AssignmentExpression
    operator: "+="
    left: MemberExpression
      object: Identifier "p"
      property: Identifier "x"
      computed: false
    right: MemberExpression
      object: Identifier "p"
      property: Identifier "vx"
      computed: false

computed: false is how ESTree tells p.x from p[x]. Each node also has start and end offsets into the source, and, when asked for, a loc with line numbers. Those offsets are what VIR’s source references point at, and what emit replaces.

The acorn adapter

By default the JavaScript plugin uses acorn, a small, fast parser written in JavaScript that returns ESTree^[3]. Inside lower, trimmed:

const js = opts.typescript
  ? stripTypes(source) : source;
const program = acorn.parse(js, {
  ecmaVersion: 'latest',
  sourceType: 'module',
  locations: true,
  onComment: (_b, value, _s, _e,
      start, end) =>
    comments.push({ value,
      line: end?.line ?? start?.line }),
});

Three jobs hide in those lines. TypeScript is first turned into JavaScript by sucrase, which removes types and leaves everything else alone^[4]. locations: true asks for line numbers, for explain. And onComment collects comments, which acorn reports through that callback rather than in the tree, and // @viscosity soa lives in one. After parsing, the plugin matches each annotation to the declaration on the next line.

A parser you can read

The rest of the plugin only depends on ESTree: estree.ts describes “the small slice of ESTree types the front-end touches”. So any parser that produces that slice, with offsets and lines, can replace acorn. jsPlugin({ parser: 'mini' }), or --parser mini on the command line, selects the book’s own: mini-parser.ts, 448 lines. Statements are recursive descent, as in Drip, one case per keyword:

case 'if': {
  p++; expect('(');
  const test = expression();
  expect(')');
  const consequent = statement();
  const alternate =
    eat('else') ? statement() : null;
  return node('IfStatement', t,
    { test, consequent, alternate });
}

Expressions use Pratt parsing with a table of binding powers. Here is part of the table, and the loop at the heart of binary, trimmed:

const BIN = { '??': 1, '||': 2,
  '&&': 3, '+': 10, '-': 10,
  '*': 11, '/': 11, '**': 12, … };

let left = unary();
for (;;) {
  const op = peek().value;
  const bp = BIN[op];
  if (bp === undefined || bp <= minBp)
    break;
  p++;
  // ** is right-associative
  const right = binary(
    op === '**' ? bp - 1 : bp);
  left = node('BinaryExpression', t,
    { operator: op, left, right });
}

(The real loop also makes &&, || and ?? into LogicalExpressions, and handles in.) Step through it:

const BIN = { '+': 10, '-': 10,
  '*': 11, '/': 11, '**': 12 };

function parse(src) {
  const ts = src.split(' ');
  let p = 0;
  function binary(minBp) {
    let left = ts[p++];
    for (;;) {
      const op = ts[p];
      const bp = BIN[op];
      if (bp === undefined ||
          bp <= minBp) break;
      p++;
      const right = binary(
        op === '**' ? bp - 1 : bp);
      left = '(' + left + ' ' + op +
        ' ' + right + ')';
    }
    return left;
  }
  return binary(0);
}

console.log(parse('1 - 2 * 3'));
console.log(parse('1 - 2 - 3'));
console.log(parse('2 ** 3 ** 2'));

Small, and honest about it

The mini parser covers what numeric, data-heavy code uses: declarations, functions and arrows, loops including for-of, objects, arrays, calls, members and every operator. Outside that, it stops instead of guessing:

let y = a?.b;
→ optional chaining is not supported
  by the mini parser at line 1 near '?.'

How do you know it is right on what it does accept? Chapter 88’s answer: compare. mini-parser.test.ts compiles every program in the differential corpus (36 files) and the five end-to-end benchmark programs with both parsers, and requires the compiled code and the explanation to be byte-identical. The trees themselves needn’t be: the mini parser writes operator before left, and gives every node a loc with column 0 and no end, details the plugin never reads. What matters is that the plugin can’t tell them apart.

Your turn

function parseLet(src) {
  const ts = src.match(/\d+|\w+|\S/g);
  let p = 0;
  const peek = () => ts[p];
  const next = () => ts[p++];
  // your code here
}

console.log(parseLet('let x = 1;'));

function parseExpr(src) {
  // your code here
}

What you learned

• ESTree is the shared tree format for JavaScript: objects tagged by type, with start/end offsets and loc lines.
• The acorn adapter calls acorn with the options Viscosity needs, collects comments for @viscosity annotations, and strips TypeScript first with sucrase.
• The hand-written mini parser uses recursive descent for statements and Pratt binding powers for expressions, and produces the same ESTree slice.
• Everything after parsing depends only on ESTree, so the parser is pluggable. A differential test checks that both parsers give byte-identical compiler output.