はじめてのコンパイラ

ブラウザの仕組みを勉強したのですが、言語処理系の部分やコンパイルの仕組みが気になったので、コンパイルの仕組みを調べてみました。

具体的には、 the-super-tiny-compilerのコードリーディング、写経を行い実際にブラウザで動かしてみて、コンパイルの仕組みを調べてみました。

- 実際にブラウザで動かしてみる。

- コード

今回の記事は

なぜthe-super-tiny-compiler?
コンパイラの仕組み
the-super-tiny-compilerのコードリーディング

について書いています。

the-super-tiny-compilerとは？

JavaScriptで書かれたコンパイラの主要部分が非常に単純化された例。

なぜthe-super-tiny-compilerを読む？

コンパイラは身の回りにたくさんあるし、多くのツールはコンパイラのコンセプトを取り入れているのでthe-super-tiny-compilerを読むことで良い経験になるかなあと思いました。

どんなものを作る？

Lispのような関数呼び出しをCのような関数呼び出しにコンパイルするものを作成します。

LISP-style	C-style
(add 2 (subtract 4 2))	add(2, subtract(4, 2))

Stages of a Compiler

ほとんどのコンパイラは、解析、変換、およびコード生成の3つの主要な段階に分類されます。

構文解析は生のコードを受け取り、それをコードのより抽象的な表現に変換します。
変換はこの抽象表現を受け取り、コンパイラーが望んでいることを何でもするように操作します。
コード生成はコードの変換された表現を受け取り、それを新しいコードに変えます。

Parsing（解析）

構文解析は通常、2つのフェーズに分けられます。

字句解析
構文解析

字句解析(Lexical Analysis)

生のコードを受け取り、それをトークナイザー（またはレクサー）と呼ばれるものによってトークンと呼ばれるものに分割する。

トークンは、孤立した構文の一部を表す小さな小さなオブジェクトの配列

(add 2 (subtract 4 2))

↓

トークン

[
  { 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: ')'        },
]

構文解析

トークンを受け取り、抽象構文木（ abstract syntax tree、AST）を作成します。（構文の各部分およびそれらの相互関係を記述する表現に再フォーマットしている。）

抽象構文木（AST）

{
  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',
      }]
    }]
  }]
}

Transformation(変換)

ASTを受け取り、変更を加えることができます。 ASTを同じ言語で操作することも、まったく新しい言語に翻訳することもできます。

Traversal(通過、横断する)

{
  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'
      }]
    }]
  }]
}

↓　以下のように通過します

Program - ASTのトップレベルから開始
CallExpression（add） - プログラム本体の最初の要素に移動する
NumberLiteral（2） - CallExpressionのパラメータの最初の要素への移動
CallExpression（減算） - CallExpressionのパラメータの2番目の要素に移動する
NumberLiteral（4） - CallExpressionのパラメータの最初の要素への移動
NumberLiteral（2） - CallExpressionのパラメータの2番目の要素への移動

Visitors

ツリーの各ノードにアクセスするには？

"visitor"オブジェクトを作成

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

ASTを通過するときに、一致するタイプのノードに「入る」たびに、このvisitorメソッドを呼び出します。ノードと親ノードへの参照も渡します。

→ Program (enter)
- → CallExpression (enter)
  - → NumberLiteral (enter)
  - ← NumberLiteral (exit)
  - → CallExpression (enter)
    - → NumberLiteral (enter)
    - ← NumberLiteral (exit)
    - → NumberLiteral (enter)
    - ← NumberLiteral (exit)
  - ← CallExpression (exit)
- ← CallExpression (exit)
← Program (exit)

"exit"で呼ぶ可能性があるので最終的には

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

Code Generation(コード生成)

コードを新たに作成します。

これで完成です！

the-super-tiny-compilerのコードリーディング

Parsing(解析)

1-tokenizer.js

(add 2 (subtract 4 2)) をトークンにします。

↓

[
  { 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: ')'        },
]

数字や文字は１文字ではなく（123 456）の場合などが考えられるので以下の処理をします。

//数値が続く限り
      while (NUMBERS.test(char)) {
        value += char;
        char = input[++current];
      }

2-parser.js

1-tokenizer.jsでできたトークンをastにします。

[
  { 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: ')'        },
]

↓

ast = {
  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'
      }]
    }]
  }]
};

walkという再帰関数でループしています。

Transformation(変換)

3-traverser.js

nodeにアクセスできるようにします。 astの配列を順番に見ていき、enterメソッド、exitメソッドがある場合は呼び出します。

function traverseArray(array, parent) {
    array.forEach(child => {
      traverseNode(child, parent);
    });
  }

4-transformer.js

3-traverser.jsを使って新しいastを作成します。

ast = {
  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'
      }]
    }]
  }]
};

↓

newAst = 
{
  type: 'Program',
  body: [{
    type: 'ExpressionStatement',
    expression: {
      type: 'CallExpression',
      callee: {
        type: 'Identifier',
        name: 'add'
      },
      arguments: [{
        type: 'NumberLiteral',
        value: '2'
      }, {
        type: 'CallExpression',
        callee: {
          type: 'Identifier',
          name: 'subtract'
         },
        arguments: [{
          type: 'NumberLiteral',
          value: '4'
        }, {
          type: 'NumberLiteral',
          value: '2'
        }]
      }]
    }
  }]
};