Skip to content
he110
Back to blog

Compilation-Related Notes

An introduction to the uses and generation process of ASTs, demonstrated through a tiny compiler that converts Lisp-style function calls into C-style calls.

Updated

AST

Use Cases

  • Syntax transformation (ES6 to ES5)
  • eslint (syntax checking, auto-fixing)
  • Formatting (prettier)
  • Building/parsing (webpack, loaders)

Generation Steps

An AST mainly consists of two parts: lexical analysis and syntactic analysis.

To make this easier to understand, the following sample code is used as an example:

var answer = 6 * 7

Lexical Analysis

Lexical analysis scans the code through a scanner, splitting the code into different tokens (lexical units). It only associates the type of each token and does not maintain a tree structure. For example:

The resulting tokens are as follows:

[
  {
    "type": "Keyword",
    "value": "var"
  },
  {
    "type": "Identifier",
    "value": "answer"
  },
  {
    "type": "Punctuator",
    "value": "="
  },
  {
    "type": "Numeric",
    "value": "6"
  },
  {
    "type": "Punctuator",
    "value": "*"
  },
  {
    "type": "Numeric",
    "value": "7"
  },
  {
    "type": "Punctuator",
    "value": ";"
  }
]

Syntactic Analysis

Syntactic analysis takes the token list produced by traversal and associates the tokens according to grammatical rules, forming a tree structure. This tree is the AST.

So an AST represents the syntactic structure of the source code, and each node on the tree represents a construct in the source code.

The resulting AST structure is as follows:

{
  "type": "Program",
  "body": [
    {
      "type": "VariableDeclaration",
      "declarations": [
        {
          "type": "VariableDeclarator",
          "id": {
            "type": "Identifier",
            "name": "answer"
          },
          "init": {
            "type": "BinaryExpression",
            "operator": "*",
            "left": {
              "type": "Literal",
              "value": 6,
              "raw": "6"
            },
            "right": {
              "type": "Literal",
              "value": 7,
              "raw": "7"
            }
          }
        }
      ],
      "kind": "var"
    }
  ],
  "sourceType": "script"
}

A Tiny Compiler

Below is a tiny compiler implementation that can convert Lisp-style function calls into C-style function calls.

The Main Stages of a Compiler

Compilers are usually divided into three main stages:

  1. Parsing: converting the raw code into a more abstract representation of the code
  2. Transformation: manipulating this abstract representation, doing whatever the compiler wants to do
  3. Code Generation: converting the transformed representation of the code into new code

The Parsing Stage

Parsing is usually divided into two phases: lexical analysis and syntactic analysis.

Lexical Analysis

Lexical analysis splits the raw code into small objects called tokens through a tokenizer.

For example, for the code (add 2 (subtract 4 2)), the resulting tokens might be:

[
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'add'      },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'subtract' },
  { type: 'number', value: '4'        },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: ')'        },
  { type: 'paren',  value: ')'        },
]

Syntactic Analysis

Syntactic analysis reformats the tokens into a representation that describes each part of the syntax and their relationships. This is called an intermediate representation or abstract syntax tree (AST).

For the code above, the AST might be:

{
  "type": "Program",
  "body": [{
    "type": "CallExpression",
    "name": "add",
    "params": [{
      "type": "NumberLiteral",
      "value": "2",
    }, {
      "type": "CallExpression",
      "name": "subtract",
      "params": [{
        "type": "NumberLiteral",
        "value": "4",
      }, {
        "type": "NumberLiteral",
        "value": "2",
      }]
    }]
  }]
}

The Transformation Stage

The transformation stage takes the AST from the previous step and modifies it. It can manipulate an AST of the same language, or translate it into an entirely new language.

Traversal

To reach all nodes, we need to be able to traverse every node in the AST depth-first.

Visitors

The visitor pattern is used to represent operations on elements of an object structure. We create a visitor object with methods that accept different node types:

var visitor = {
  NumberLiteral: {
    enter(node, parent) {},
    exit(node, parent) {},
  },
  CallExpression: {
    enter(node, parent) {},
    exit(node, parent) {},
  },
};

When we traverse the AST, we call the methods on the visitor whenever we "enter" a node of a matching type.

The Code Generation Stage

The code generation stage takes the transformed AST and turns it back into a code string. The code generator knows how to "print" all the different node types of the AST, and it calls itself recursively to print nested nodes until everything is printed into one long string of code.

The Complete Implementation

Below is a complete tiny compiler implementation:

// The tokenizer
function tokenizer(input) {
  let current = 0;
  let tokens = [];

  while (current < input.length) {
    let char = input[current];

    // Handle parentheses
    if (char === '(') {
      tokens.push({
        type: 'paren',
        value: '(',
      });
      current++;
      continue;
    }

    if (char === ')') {
      tokens.push({
        type: 'paren',
        value: ')',
      });
      current++;
      continue;
    }

    // Handle whitespace
    let WHITESPACE = /\s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }

    // Handle numbers
    let NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {
      let value = '';
      while (NUMBERS.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({ type: 'number', value });
      continue;
    }

    // Handle strings
    if (char === '"') {
      let value = '';
      char = input[++current];
      while (char !== '"') {
        value += char;
        char = input[++current];
      }
      char = input[++current];
      tokens.push({ type: 'string', value });
      continue;
    }

    // Handle identifiers
    let LETTERS = /[a-z]/i;
    if (LETTERS.test(char)) {
      let value = '';
      while (LETTERS.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({ type: 'name', value });
      continue;
    }

    throw new TypeError('I dont know what this character is: ' + char);
  }

  return tokens;
}

// The parser
function parser(tokens) {
  let current = 0;

  function walk() {
    let token = tokens[current];

    if (token.type === 'number') {
      current++;
      return {
        type: 'NumberLiteral',
        value: token.value,
      };
    }

    if (token.type === 'string') {
      current++;
      return {
        type: 'StringLiteral',
        value: token.value,
      };
    }

    if (token.type === 'paren' && token.value === '(') {
      token = tokens[++current];
      let node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };
      token = tokens[++current];

      while (
        (token.type !== 'paren') ||
        (token.type === 'paren' && token.value !== ')')
      ) {
        node.params.push(walk());
        token = tokens[current];
      }

      current++;
      return node;
    }

    throw new TypeError(token.type);
  }

  let ast = {
    type: 'Program',
    body: [],
  };

  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

// The traverser
function traverser(ast, visitor) {
  function traverseArray(array, parent) {
    array.forEach(child => {
      traverseNode(child, parent);
    });
  }

  function traverseNode(node, parent) {
    let methods = visitor[node.type];

    if (methods && methods.enter) {
      methods.enter(node, parent);
    }

    switch (node.type) {
      case 'Program':
        traverseArray(node.body, node);
        break;
      case 'CallExpression':
        traverseArray(node.params, node);
        break;
      case 'NumberLiteral':
      case 'StringLiteral':
        break;
      default:
        throw new TypeError(node.type);
    }

    if (methods && methods.exit) {
      methods.exit(node, parent);
    }
  }

  traverseNode(ast, null);
}

// The transformer
function transformer(ast) {
  let newAst = {
    type: 'Program',
    body: [],
  };

  ast._context = newAst.body;

  traverser(ast, {
    NumberLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'NumberLiteral',
          value: node.value,
        });
      },
    },

    StringLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'StringLiteral',
          value: node.value,
        });
      },
    },

    CallExpression: {
      enter(node, parent) {
        let expression = {
          type: 'CallExpression',
          callee: {
            type: 'Identifier',
            name: node.name,
          },
          arguments: [],
        };

        node._context = expression.arguments;

        if (parent.type !== 'CallExpression') {
          expression = {
            type: 'ExpressionStatement',
            expression: expression,
          };
        }

        parent._context.push(expression);
      },
    }
  });

  return newAst;
}

// The code generator
function codeGenerator(node) {
  switch (node.type) {
    case 'Program':
      return node.body.map(codeGenerator)
        .join('\n');

    case 'ExpressionStatement':
      return (
        codeGenerator(node.expression) +
        ';'
      );

    case 'CallExpression':
      return (
        codeGenerator(node.callee) +
        '(' +
        node.arguments.map(codeGenerator)
          .join(', ') +
        ')'
      );

    case 'Identifier':
      return node.name;

    case 'NumberLiteral':
      return node.value;

    case 'StringLiteral':
      return '"' + node.value + '"';

    default:
      throw new TypeError(node.type);
  }
}

// The compiler
function compiler(input) {
  let tokens = tokenizer(input);
  let ast    = parser(tokens);
  let newAst = transformer(ast);
  let output = codeGenerator(newAst);

  return output;
}

Usage Example

// Input: (add 2 (subtract 4 2))
// Output: add(2, subtract(4, 2));

This tiny compiler demonstrates the main components and working principles of a compiler. Although it only handles very simple syntax, it contains the basic concepts and workflow of compiler design.