Follow

Follow
What is AST?

What is AST?

Manuel Spigolon's photo
Manuel Spigolon
ยทJan 9, 2023ยท

6 min read

Table of contents

  • Abstract Syntax Tree
  • How to generate a JavaScript AST
  • Summary

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.

Abstract Syntax Tree

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.
The 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.

function foo() {
  ~ this is not javascript code! ~
}

Running node index.js will throw the error:

  ~ 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:

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

hello('foo')

The following AST can represent it:

AST tree view

{
  "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, comment, share, and follow me on Twitter @ManuEomm!

ย 
Share this