Skip to content

What is an Abstract Syntax Tree?

Editor's note:  This is a cross-post written by Senior Software Developer, Manuel Spigolon. Manuel has his own blog at  backend.cafe where you can subscribe for updates and find more great posts. Some of the links in the article point to Manuel’s personal GitHub account.

Abstract Syntax Tree

You may have seen the term "AST" in multiple contexts without digging into what it actually means. It is a common term in compiler theory, and it is also used in the context of static analysis. In this post, we will see what an AST is, and we will focus on how it is a key part of the JavaScript language and ecosystem.

The AST acronym stands for  Abstract Syntax Tree . It is a tree data structure representing any structured text file, so every standardized syntax can be represented through an AST.

Since the AST is "abstract", it does not have a standard representation, because every language may have its own specific dictionary. However, the common concept shared across all the ASTs, is the tree representation where the first node describes the document/program's entry point.

Generally, the first step to run a piece of software is to parse the source code and build an AST. This operation is called  parsing  and is performed by the  parser  component.

???? Source ➞ ⚙️ Parser ➞ ???? AST

If the parser is unable to parse the source code, it will throw an error. The source code is invalid and the AST cannot be generated.

How the AST is used

The AST is generated to process source code files, but it can be generated from any text file such as Markdown, JSON, or even a GraphQL Document.

When the parser builds a valid AST, the following step is the  transform :

???? Source ➞ ⚙️ Parser ➞ ???? AST ➞ ⚙️ Transform ➞ ???? AST (Transformed)

The AST is manipulated and transformed during this phase to generate a new AST.

Some examples of transformations are:

  • the babel tool that transforms the AST to generate a new AST that is compatible with the target environment
  • source code minification, where the AST is transformed to remove unnecessary characters and to reduce the file size
  • code formatting tools, where the AST is transformed to add/remove spaces and new lines to improve the code readability

Finally, the new AST is then passed to the  compiler :

???? Source ➞ ⚙️ Parser ➞ ???? AST ➞ ⚙️ Transform ➞ ???? AST (Transformed) ➞ ⚙️ Compiler ➞ ???? Output

The compiler generates output such as:

  • bytecode to be executed
  • a new source code file derived from the original source code
  • some console output such as a warning or an error or suggestions

All the tools we use in our daily work are based on the AST and are used to improve developer experience. Code completion, refactoring, linting and formatting are all powered by the source code tree representation! This is how our IDE and powerful editors implement extraordinary features!

How to generate a JavaScript AST

Let's focus on the  Node.js  runtime and see how the AST is built. JavaScript is a dynamic language, but the first step for every high-level programming language is to parse the source code and build an AST. Without completing this step, our code will never be executed.

In fact, if you try to run a JS file that contains invalid JavaScript code, the runtime will throw a Syntax error even if the function is never called.

text 
~ this is not javascript code! ~
         ^^

SyntaxError: Unexpected identifier

Under the hood, Node.js relies on the  Google V8 engine  to parse the source code and build the AST. The tree representation is then passed to the  Ignition interpreter  that builds the final bytecode.

The AST generated by V8 is not accessible from the JavaScript code, but it is possible to generate an AST from JavaScript using one of the many available libraries:

For example, the following code:

js 
function hello(name) {
  console.log('Hello ' + name)
}

hello('foo')

The following AST can represent it:

json 
{
  "type": "Program",
  "start": 0,
  "end": 70,
  "body": [
    {
      "type": "FunctionDeclaration",
      "start": 0,
      "end": 56,
      "id": {
        "type": "Identifier",
        "start": 9,
        "end": 14,
        "name": "hello"
      },
      "expression": false,
      "generator": false,
      "async": false,
      "params": [
        {
          "type": "Identifier",
          "start": 16,
          "end": 20,
          "name": "name"
        }
      ],
      "body": {
        "type": "BlockStatement",
        "start": 22,
        "end": 56,
        "body": [
          {
            "type": "ExpressionStatement",
            "start": 26,
            "end": 54,
            "expression": {
              "type": "CallExpression",
              "start": 26,
              "end": 54,
              "callee": {
                "type": "MemberExpression",
                "start": 26,
                "end": 37,
                "object": {
                  "type": "Identifier",
                  "start": 26,
                  "end": 33,
                  "name": "console"
                },
                "property": {
                  "type": "Identifier",
                  "start": 34,
                  "end": 37,
                  "name": "log"
                },
                "computed": false,
                "optional": false
              },
              "arguments": [
                {
                  "type": "BinaryExpression",
                  "start": 38,
                  "end": 53,
                  "left": {
                    "type": "Literal",
                    "start": 38,
                    "end": 46,
                    "value": "Hello ",
                    "raw": "'Hello '"
                  },
                  "operator": "+",
                  "right": {
                    "type": "Identifier",
                    "start": 49,
                    "end": 53,
                    "name": "name"
                  }
                }
              ],
              "optional": false
            }
          }
        ]
      }
    },
    {
      "type": "ExpressionStatement",
      "start": 58,
      "end": 70,
      "expression": {
        "type": "CallExpression",
        "start": 58,
        "end": 70,
        "callee": {
          "type": "Identifier",
          "start": 58,
          "end": 63,
          "name": "hello"
        },
        "arguments": [
          {
            "type": "Literal",
            "start": 64,
            "end": 69,
            "value": "foo",
            "raw": "'foo'"
          }
        ],
        "optional": false
      }
    }
  ],
  "sourceType": "module"
}

The AST standard initiative

In the initial section, we said that the AST is not standardized. Moreover, the AST generated by v8 is a tuned and optimized AST  designed for its engine, so it is a  tailor-made AST .

As mentioned before, many libraries can generate an AST from a JavaScript source code. At this point, the  ESTree  community organization defines an (unofficial) standard for JavaScript ASTs.

However, there is a  nice story  behind the JavaScript AST baseline structure:

“Once upon a time, an unsuspecting Mozilla engineer created an API in Firefox that exposed the SpiderMonkey engine's JavaScript parser as a JavaScript API. Said engineer documented the format it produced, and this format caught on as a lingua franca for tools that manipulate JavaScript source code.”

The specification maintained by the ESTree community follows the  ECMAScript standard  and its naming conventions.

Resources

A handy tool to explore the AST is  AST Explorer .

You can copy-paste the source code and see the AST generated by the selected parser.

“ℹ️ Navigate the AST I find it very useful to explore the AST generated by a GraphQL schema when I need to implement a mercurius plugin!”

Of course, an  awesome list ????  of AST-related projects exists!

Summary

I hope this AST post was helpful to understand how the AST is used in the JavaScript ecosystem.

Now you should see your IDE and the  eslint  tool with different eyes! There was no magic, just a tree data structure!

If you are willing to build an  eslint  or  graphql  plugin, the information in this post will help you to start your journey!

If you enjoyed this article please share and follow me on Twitter @ManuEomm !

Insight, imagination and expertly engineered solutions to accelerate and sustain progress.

Contact