Parsing & abstract syntax trees

The parser's job

Before JavaScript can run your code, it reads the text in steps. The scanner comes first. It cuts the text into tokens: small pieces such as a name, a number, or a + sign.

The parser comes next. It does three jobs with the tokens:

• It checks that the tokens follow JavaScript's grammar: the rules for how code may be written.
• It reports a SyntaxError when they don't.
• It builds a tree that shows which pieces belong together.

The engine then turns that tree into bytecode: simple instructions that it can run. Tools such as linters and formatters read a similar tree to check, tidy, or change your code.

This lesson uses ideas from earlier lessons:

• Code structure: statements and expressions.
• Other operators: the list of which operator goes first.
• Bundlers: there, Acorn (a parser written in JavaScript) found the import lines.
• Transpilers & polyfills: there, tools changed code by changing its tree.

It also touches linting, destructuring, arrow functions, and strict mode.

The table below lists four things that can appear between your text and the running code. Read each row from left to right: the name, what it is, an example, and who uses it.

Most JavaScript parsers are recursive descent parsers. That means:

• There is one function for each grammar rule. One function reads a statement; another reads an expression.
• The functions call each other. The statement function calls the expression function when it needs one.
• A function may call itself. That is the "recursive" part. It is how the parser handles things inside things, such as brackets inside brackets or a call inside a call.
• The parser starts at the biggest rule, the whole program, and works down to smaller rules. That is the "descent" part.

The table compares four ways of parsing that this lesson mentions. Read each row as: the name, how it works, and what it suits best.

Expressions need one more idea: precedence, which means which operator goes first. In a + b * c, the * goes first.

This lesson has its own small parser, called the mini parser. It gives each operator a number called its binding power. A bigger number means the operator holds the values beside it more tightly: + and - have 10, * and / have 20, and ** has 30.

The mini parser reads the value on the left. Then it keeps taking operators whose binding power is high enough. This way of parsing is called precedence climbing.

You may also hear of a Pratt parser. It is related, but it is not the same thing. A Pratt parser picks a separate small handler for each kind of token. The mini parser has just one loop for all operators like + and *, so "precedence climbing" is the right name for it.

1const input = "a + b * c(d)";2const tokens = tokenize(input);3let cursor = 0;4 5function parseExpression(minBP = 0) {6  let left = parsePostfix();7  while (isBinary(peek()) && bindingPower(peek()) >= minBP) {8    const operator = consume();9    const right = parseExpression(nextMinBP(operator));10    left = binary(left, operator, right);11  }12  return left;13}14 15function parsePostfix() {16  let expression = parsePrimary();17  while (peek() === "(" || peek() === ".") {18    expression = parseCallOrMember(expression);19  }20  return expression;21}22 23function parsePrimary() {24  return tokenToNode(consume());25}26 27function tokenize(source) {28  return source.match(/[A-Za-z_$][A-Za-z0-9_$]*|[0-9]+|[*][*]|[()+*/.,-]/g).concat("<eof>");29}30function peek() { return tokens[cursor]; }31function consume() { return tokens[cursor++]; }32function isBinary(token) { return ["+", "-", "*", "/", "**"].includes(token); }33function bindingPower(token) {34  return token === "+" || token === "-" ? 10 : token === "*" || token === "/" ? 20 : token === "**" ? 30 : -1;35}36function nextMinBP(operator) { return operator === "**" ? bindingPower(operator) : bindingPower(operator) + 1; }37function tokenToNode(token) { return /^[A-Za-z_$]/.test(token) ? { type: "Identifier", name: token } : { type: "Literal", value: Number(token), raw: token }; }38function parseCallOrMember(expression) {39  if (peek() === ".") return { type: "MemberExpression", object: expression, property: tokenToNode((consume(), consume())) };40  consume();41  const args = peek() === ")" ? [] : [parseExpression(0)];42  consume();43  return { type: "CallExpression", callee: expression, arguments: args };44}45function binary(left, operator, right) { return { type: "BinaryExpression", left, operator, right }; }46 47console.log(parseExpression(0).type);Run

Step through the code one line at a time. Like a real parser, it has three main functions:

• parseExpression (line 5) reads a whole expression, operators included.
• parsePostfix (line 15) reads a value and anything stuck right after it, such as a call (d) or a dot .name. "Postfix" means "comes after".
• parsePrimary (line 23) reads one simple token, such as a name or a number.

The recording comes from running the lesson's real parser on a + b * c(d).

1const input = "a + b * c(d)";2const tokens = tokenize(input);3let cursor = 0;4 5function parseExpression(minBP = 0) {6  let left = parsePostfix();7  while (isBinary(peek()) && bindingPower(peek()) >= minBP) {8    const operator = consume();9    const right = parseExpression(nextMinBP(operator));10    left = binary(left, operator, right);11  }12  return left;13}14 15function parsePostfix() {16  let expression = parsePrimary();17  while (peek() === "(" || peek() === ".") {18    expression = parseCallOrMember(expression);19  }20  return expression;21}22 23function parsePrimary() {24  return tokenToNode(consume());25}26 27function tokenize(source) {28  return source.match(/[A-Za-z_$][A-Za-z0-9_$]*|[0-9]+|[*][*]|[()+*/.,-]/g).concat("<eof>");29}30function peek() { return tokens[cursor]; }31function consume() { return tokens[cursor++]; }32function isBinary(token) { return ["+", "-", "*", "/", "**"].includes(token); }33function bindingPower(token) {34  return token === "+" || token === "-" ? 10 : token === "*" || token === "/" ? 20 : token === "**" ? 30 : -1;35}36function nextMinBP(operator) { return operator === "**" ? bindingPower(operator) : bindingPower(operator) + 1; }37function tokenToNode(token) { return /^[A-Za-z_$]/.test(token) ? { type: "Identifier", name: token } : { type: "Literal", value: Number(token), raw: token }; }38function parseCallOrMember(expression) {39  if (peek() === ".") return { type: "MemberExpression", object: expression, property: tokenToNode((consume(), consume())) };40  consume();41  const args = peek() === ")" ? [] : [parseExpression(0)];42  consume();43  return { type: "CallExpression", callee: expression, arguments: args };44}45function binary(left, operator, right) { return { type: "BinaryExpression", left, operator, right }; }46 47console.log(parseExpression(0).type);Run

The second replay parses config.get(user.name).theme. It shows that the calls and dots join up first, into one chain. Only after that do operators such as + or * get a turn. Calls and dots attach straight onto the value before them.

There are two kinds of syntax tree:

• A concrete syntax tree, also called a parse tree, follows the grammar rules exactly. It keeps every bracket, every comma, and every in-between step. That helps while parsing, but it is noisy for most tools.
• An abstract syntax tree (AST) keeps only the parts that carry meaning.

ESTree is a shared agreement about what a JavaScript AST should look like: the names of the nodes and the names of their fields. Many tools follow it. Acorn and Espree (two parsers), AST Explorer, ESLint rules, and many Babel-compatible tools give you ESTree nodes, or nodes very close to them.

The V8 engine, used in Chrome and Node.js, builds an AST too. V8's article about its scanner says it then turns that AST into bytecode for Ignition, V8's interpreter. But V8's own nodes are not ESTree nodes.

Each row below is one node type you will often see. The last column lists the fields that hold its parts.

The panel below parses the same line of code twice: once with the mini parser and once with Acorn. Pick a line and compare the two trees.

{
  "type": "Program",
  "body": [
    {
      "type": "ExpressionStatement",
      "expression": {
        "type": "BinaryExpression",
        "left": {
          "type": "Identifier",
          "name": "a"
        },
        "operator": "+",
        "right": {
          "type": "BinaryExpression",
          "left": {
            "type": "Identifier",
            "name": "b"
          },
          "operator": "*",
          "right": {
            "type": "CallExpression",
            "callee": {
              "type": "Identifier",
              "name": "c"
            },
            "arguments": [
              {
                "type": "Identifier",
                "name": "d"
              }
            ],
            "optional": false
          }
        }
      }
    }
  ],
  "sourceType": "script"
}

{
  "type": "Program",
  "body": [
    {
      "type": "ExpressionStatement",
      "expression": {
        "type": "BinaryExpression",
        "left": {
          "type": "Identifier",
          "name": "a"
        },
        "operator": "+",
        "right": {
          "type": "BinaryExpression",
          "left": {
            "type": "Identifier",
            "name": "b"
          },
          "operator": "*",
          "right": {
            "type": "CallExpression",
            "callee": {
              "type": "Identifier",
              "name": "c"
            },
            "arguments": [
              {
                "type": "Identifier",
                "name": "d"
              }
            ],
            "optional": false
          }
        }
      }
    }
  ],
  "sourceType": "script"
}

The operator lesson listed which operators go first. The parser turns that list into the shape of the tree. The deeper a node sits, the earlier it is worked out:

• * sits deeper than +.
• A dot, as in user.name, sits deeper than *.
• ** ("to the power of") groups from the right. This is called being right-associative. So 2 ** 3 ** 2 means 2 ** (3 ** 2).

1console.log(2 ** 3 ** 2);2 3try {4  new Function("return -2 ** 2;");5  console.log("parsed");6} catch (error) {7  console.log(error.name + ": " + error.message);8}9 10console.log(2 ** -2);11console.log((-2) ** 2);12console.log(-(2 ** 2));

Line 1 prints 512. JavaScript reads 2 ** 3 ** 2 as 2 ** (3 ** 2). That is 2 ** 9, which is 512.

Line 4 gives the string "return -2 ** 2;" to new Function. new Function turns a string into a function. It must parse the string first, and here the function is never called.

A unary operator works on one value, like the minus in -2. The grammar has a special rule: a unary operator may not sit right before **. So parsing fails, and line 7 prints the SyntaxError and its message.

Why the rule? Some people read -2 ** 2 as (-2) ** 2, which is 4. Others read it as -(2 ** 2), which is -4. JavaScript refuses to guess, so you write the brackets yourself.

Lines 10 to 12 show forms that work. A minus on the right side is fine, so 2 ** -2 prints 0.25. (-2) ** 2 prints 4, and -(2 ** 2) prints -4.

Most errors happen while code runs. Those are runtime errors. When one happens, the lines before it have already run.

The ECMAScript specification, the official rulebook for JavaScript, also lists early errors. An early error is found before any of the code runs. If a script has one, not a single line of that script runs. The same goes for a module, or a string passed to eval. This is not the engine guessing that code will fail later. The spec names each early error exactly.

The code below uses eval. It takes a string, then parses and runs it as code. Each string is parsed on its own, so you can see what happens to it.

1const early = [];2try {3  eval('early.push("before"); let item = 1; let item = 2; early.push("after");');4} catch (error) {5  early.push(error.name);6}7console.log(early.join(" -> "));8 9const runtime = [];10try {11  eval('runtime.push("before"); missingFunction(); runtime.push("after");');12} catch (error) {13  runtime.push(error.name);14}15console.log(runtime.join(" -> "));

Line 3: the first string declares let item twice. That is an early error. So the early.push("before") at the start of the string never runs. Line 7 prints only SyntaxError.

Line 11: the second string follows the grammar, so it starts running. It pushes "before". Then it fails at missingFunction(), a name that doesn't exist. Line 15 prints before -> ReferenceError.

Here are some common early errors to recognize. They are separate examples, so don't run them as one file.

1// Separate examples to read. Don't run them together.2let total = 1;3let total = 2;       // the same let name twice4 5return 1;            // return outside a function61 = 2;               // you can't assign to a number7 8"use strict";9010;                 // an old-style octal number in strict code

The next code checks six early errors, each in its own string:

• the same let name twice
• return outside a function
• assigning to something that can't hold a value, such as 1
• an old-style octal number such as 010 in strict mode
• two parameters with the same name in strict mode
• await outside an async function, in a normal script

Each eval fails before it runs anything, so every line prints SyntaxError.

1const cases = [2  ["duplicate let", 'let count; let count;'],3  ["return outside function", 'return 1;'],4  ["invalid assignment target", '1 = 2;'],5  ["strict octal literal", '"use strict"; 010;'],6  ["strict duplicate parameters", '"use strict"; function f(a, a) {}'],7  ["await outside async", 'await 1;'],8];9 10for (const [label, source] of cases) {11  try {12    eval(source);13    console.log(label + ": ran");14  } catch (error) {15    console.log(label + ": " + error.name);16  }17}

Sometimes the parser can't tell what some tokens mean until it sees a later token. Take (a, b):

• If no => follows, it is a comma expression in brackets. It works out a, then b, and gives back b.
• If => follows, the same tokens are the parameters of an arrow function.

The spec handles this with a cover grammar. That is a broad rule that "covers" both meanings for a while. When the later token arrives, the parser checks the tokens against the rules for the meaning that is now clear. It doesn't run any code, and it doesn't have to read the text twice.

Each row below shows a piece of code, what it ends up as, and what decides that.

1const samples = [2  ["parenthesized expression", "let a = 1, b = 2; (a, b);"],3  ["arrow parameters", "const fn = (a, b) => a + b;"],4  ["object assignment pattern", "let a; const b = { a: 2 }; ({ a } = b);"],5  ["object literal expression", "const value = ({ a: 1 });"],6];7 8for (const [label, source] of samples) {9  try {10    new Function(source);11    console.log(label + ": parses");12  } catch (error) {13    console.log(label + ": " + error.name);14  }15}

Lines 2 to 5 are fixed strings. Line 11 hands each one to new Function, which parses it without running it. If there is no error, line 12 prints parses. All four print parses.

Objects have the same problem. In ({ a } = b), the part that looks like an object is really a destructuring pattern. It takes b.a and stores it in a. In a normal object, { a = 1 } is not allowed. So the parser accepts the broad shape first. Then it applies the rules for whatever the shape turns out to be.

The fastest way to learn ASTs is to change some code and watch the tree change. AST Explorer is the usual website for this. You pick a parser, type some code, and see its tree.

With Acorn, Espree, or a Babel-style parser, these options matter most:

• ecmaVersion: which version of JavaScript to accept.
• sourceType: "script" or "module". Only a module may use import at the top level.
• locations: adds a line and column number to each node.
• ranges or tokens: add exact character positions, for tools that highlight or change code.

const total = prices
  .map((price) => price * tax)
  .reduce((sum, value) => sum + value, 0);
console.log(total);

Try these: delete a closing bracket ), add an import line, or click a CallExpression node. The playground parses your code with Acorn. It highlights the part of the text that each node came from. It never runs your code.

Tools use ASTs because they need to know what each piece of code is. A plain text search can't tell. For example:

• A linter should flag a real console.log() call, but not the string "console.log".
• A formatter must know what sits inside what before it decides where to break lines.
• A codemod, a script that changes code across many files, should rename a function call without touching comments.

Each row below names a tool and what it does with the AST.

The panel below uses acorn-walk, a helper that visits the nodes of an Acorn tree. It has two ways to walk:

• full walks the whole tree and calls your function on each node it visits. It skips the name after a dot, such as map in prices.map. So the code below counts 7 names, not 9.
• ancestor calls your function only for the node types you name, such as CallExpression. It also tells you the nodes above it.

1import { parse } from "acorn";2import { ancestor, full } from "acorn-walk";3 4const source = `const total = prices.map((price) => price * tax);5console.log(total);`;6const ast = parse(source, { ecmaVersion: 2024, locations: true });7 8let identifiers = 0;9full(ast, (node) => {10  if (node.type === "Identifier") identifiers += 1;11});12 13const consoleLogs = [];14ancestor(ast, {15  CallExpression(node) {16    if (17      node.callee.type === "MemberExpression" &&18      node.callee.object.type === "Identifier" &&19      node.callee.object.name === "console" &&20      node.callee.property.type === "Identifier" &&21      node.callee.property.name === "log"22    ) {23      consoleLogs.push(node.loc.start.line);24    }25  }26});27 28console.log(identifiers);29console.log(consoleLogs.join(","));

The bundlers lesson used Acorn in the same way to find import lines. The transpilers lesson used Acorn's positions to rewrite ??. Once code is a tree, a tool can make exact changes that a text search can't.

Common misconceptions

• "Grammar and syntax are the same word." Grammar is the set of rules. Syntax is the code you actually wrote, which the parser checks against those rules.
• "An AST holds every token." A parse tree keeps every grammar detail. An AST keeps a smaller tree with only the parts that carry meaning.
• "ESTree is what the engine runs." ESTree is a format for tools. Engines build their own private ASTs and turn them into bytecode or machine code.
• "An early error happens after the lines before it run." No. An early error stops every line of the script, module, or eval string from running.
• "Cover grammars mean the parser guesses while the code runs." No. It all happens while parsing. A later token decides what the broad shape must be. No code runs while it decides.

Each row below is a pair of similar words. Read across: how they differ, then a safe way to say it.

Key takeaways

• The parser reads tokens, checks them against the grammar, reports syntax errors and early errors, and builds a tree.
• A recursive descent parser has one function per grammar rule. This lesson's operator loop is called precedence climbing.
• ESTree is a shared AST format for tools. It is not V8's own AST.
• An early error stops every line of its script, module, or eval string from running.
• A cover grammar accepts a broad shape first. A later token decides what it must be, and the parser checks it then.
• ASTs power linters, formatters, code changers, bundlers, and clear syntax error messages.

Up next: Lazy parsing & preparsing. There you'll see how engines decide how much code to parse at startup, and how much to leave for later.