フロントエンドエンジニアをやっています。
26歳です。頑張るから読んでほしい。

はじめてのコンパイラ

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

具体的には、 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つの主要な段階に分類されます。

  1. 構文解析は生のコードを受け取り、それをコードのより抽象的な表現に変換します。
  2. 変換はこの抽象表現を受け取り、コンパイラーが望んでいることを何でもするように操作します。
  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: ')'        },
]

数字や文字は1文字ではなく(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'
        }]
      }]
    }
  }]
};

Code Generation(コード生成)

5-code-generator.js

新しいastを元に構文作成。

.mapで新しい配列を作成。.joinで配列の中身を連結させて文字列にしています。

"add(2, subtract(4, 2));"

実際にブラウザで動かしてみた

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

- コード

まとめ

実際に簡単な例のコンパイラをコードリーディングをしてみることで、コンパイルの仕組みを理解することができました。

ESlintとかBabelだったり、pug→htmlの変換も同じような流れなのかなと、思ったり...!

今度はRubyでつくるRubyも読んでみたいなあと思っています。