BabylonでJavaScript AST事始め #JavaScript

最新JS本発売中ですが、サンプルコードにtypoがあったりして修正中です。

それはさておき、JavaScriptの特徴としてはASTでエコシステムが発達しきっている点があるかなと思っています。他の言語でもコンパイラの内部ではASTとか使われているはずですが、大抵は内部的な物だったり、公開されてても一部の特殊なツールでしか使われない感じです。JSでは、ASTのデファクトスタンダードが存在してて、ASTをホゲるツールも多種多様です。ということでAST触ってみようと思います。

間違いとかあったらツッコミなどいただけると幸いです。

babylon を使ってみる

babylonはみんな大好きbabelのAST parserです。ぱっと探した感じデファクトのようですね。

$ npm i babylon -S

使い方はとても簡単です。

const babylon = require('babylon')

const ast = babylon('1 + 2 * (3 + 4)')
console.log(ast)

帰ってくるASTは、Node型で構成されたツリーです。Node型自体は実質ただのプロパティ保持用のクラスで、特にメソッドをもっているわけでもないようです。これのいいところは、演算子の優先順位などはすべて処理したあとのものになっているところです。

さて、プロパティとしてはどれにも含まれるのが、type, start, end, locなどです。typeはそのNodeがどういう意味のノードなのかです。start, end, loc はコード場の位置情報です。

子Nodeのたどり方

{
  "type": "File",
  "program": <Node>,
  "comments": []
}

一番トップのNodeはこんな感じです。Fileの場合はprogramが子Nodeです。

{
  "type": "Program",
  "sourceType": "script",
  "body": [<Node>, ....]
}

次のNodeはProgramですが、コイツの子Nodeはさっきと違ってbodyです。しかもさっきと違って、bodyはNodeの配列です。つまりtypeごとに子Nodeをたどるやり方が異なるのです。なんでこういう仕様にしたのかがとても謎ではありますが、まぁしゃーないのです。

ASTのアウトラインを見てみる

const replacer = (key, value) => {
    if (!key) {
        return value
    }
    if (/^[0-9]+$/.test(key)) {
        return value
    }
    return (['type', 'program', 'body', 'expression','left', 'right']).indexOf(key) === -1 ? undefined : value
}
console.log(JSON.stringify(ast, replacer, '  '))

JSON.stringify(ast)によってアウトラインを見たいのですが余計なプロパティが多いので、replacer関数を使って、必要なものだけ取り出します。replacer関数わりと仕様が謎なんですが、とりあえずこんな感じのコードでいけるようです。

{
  "type": "File",
  "program": {
    "type": "Program",
    "body": [
      {
        "type": "ExpressionStatement",
        "expression": {
          "type": "BinaryExpression",
          "left": {
            "type": "NumericLiteral"
          },
          "right": {
            "type": "BinaryExpression",
            "left": {
              "type": "NumericLiteral"
            },
            "right": {
              "type": "BinaryExpression",
              "left": {
                "type": "NumericLiteral"
              },
              "right": {
                "type": "NumericLiteral"
              }
            }
          }
        }
      }
    ]
  }
}

追記: replacerを汎用化する (Node型を判定する)

const isNode = obj => {
    if (typeof obj !== 'object') {
        return false
    }

    if (Array.isArray(obj)) {
        return obj.find(v => isNode(v)) !== undefined
    }

    while (obj && 'constructor' in obj) {
        if (obj.constructor.name === 'Node') {
            return true
        }
        obj = Object.getPrototypeOf(obj)
    }
    return false
}

const replacer = (key, value) => {
    if (!key || key === 'type' || isNode(value)) {
        return value
    }

    return undefined
}

isNodeですが、Node型がBabylonではexportされていないのでinstanceofで判定することはできません。とりあえずconstructor.nameが'Node'かどうかを見ています。Nodeをextendsしてる場合も見越して、先祖を追いかけるコードにしています (いらないかも)。

こっちのコードであれば、いちいちtypeを見て、どのプロパティがNodeを保持してるか決め打ちしなくても済みます。

astを使って計算機を作る

二項演算子の計算機は、さっき説明したアウトラインに出てきたtypeを処理するだけで可能なので、簡単に計算機を作ってみましょう。今回は用途を単純にしているので、例えばFile Nodeは単にprogramの中を処理して、Program Nodeはbodyの配列を処理するという感じに決め打ちできます。

ツリー構造を処理する場合の常套手段は再帰関数です。ASTを処理するためのwalker(あるいはtraverser)などの関数がよく作られてると思いますが、ここでもそれを作ってみましょう。もっとも、walkers[node.type]を再帰呼び出しするという単純なものです。walkersは、Nodeのtypeに応じた関数一覧です。

const walker = (node, warkers) => {
    if (!(node.type in walkers)) {
        throw new Error('対応してないtype', node.type)
    }

    return walkers[node.type](node)
}

BinaryExpressionは、left と right を operator で計算するというものです。left, right が子Nodeで、今回の場合だと BinaryExpressionかNumericLiteralが入ります。再帰的に処理してたどり着く末端(ふつうのツリー構造だとLeaf Nodeとか言われるよね…)がNumericLiteralです。こいつはとりあえずvalueを返すだけで大丈夫です。

const walkers = {
    'File': node => walker(node.program),
    'Program': node => {
        node.body.forEach(value => console.log(walker(value)))
        return null
    },
    'ExpressionStatement': node => walker(node.expression),
    'BinaryExpression': node => {
        const left = walker(node.left)
        const right = walker(node.right)
        switch (node.operator) {
            case '+': return left + right
            case '*': return left * right
            case '-': return left - right
            case '/': return left / right
            case '%': return left % right
            default: throw new Error('対応してない二項演算子')
        }
    },
    'NumericLiteral': node => node.value
}

完成版は gist に置いてます。

宣伝

技術書典3では、カジュアルなAST本を出す予定です！カジュアルです！皆さんカジュアルに見に来てください！