メインコンテンツへ移動
黯羽軽揚毎日少しずつ

the-super-tiny-compiler ソースコード解析

無料2018-09-03#JS#compiler in JavaScript#JS写编译器#编译原理JavaScript#抽象语法树

200 行ほどの JS で書かれた「麻雀型」コンパイラ

一.目標

コンパイラを実装することで、シンプルな式変換をサポートし、Lisp スタイルの関数呼び出しを C スタイルに変換します。例えば：

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

つまり (add 2 2) を入力し、add(2, 2) を出力することを要求します

二.設計

コンパイル作業を 3 つの部分に分割します：

  • 解析：コード文字列を抽象表現に変換

  • 変換：抽象表現を望む形に修正

  • コード生成：変換済みの抽象表現を新しいコード文字列に変換

ここでの解析には字句解析と構文解析が含まれ、字句解析器がコード文字列を一連の字句ユニット（token）に変換し、その後構文解析器が構文構造（構文成分及其びその関係を含む）を記述できる中間表現形式（Intermediate Representation）または抽象構文木（Abstract Syntax Tree）を生成します

構造から見ると、字句ユニットは独立した構文成分（数値、ラベル、句読点、演算子など）を記述する小オブジェクトのグループで、抽象構文木（略称 AST）は深いネストされたオブジェクトで、処理しやすく構文構造情報を携えています。例えば：

// 代码字符串
(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: ')'        },
]
// 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',
      }]
    }]
  }]
}

変換段階では AST を修正します。つまり上記で生成されたツリー構造を traverse し、ノードレベルの操作（ノードの追加/削除/変更）と属性レベルの操作（属性の追加/削除/変更）を行います。もちろん、新しいツリーを作成することもできます

実装上は、深さ優先 traverse でよく、特別なことはありません。ノードごとに処理するのは少し面白いです：

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

ノードを訪問する操作を visitor 層として取り出し、traverse 過程中に字句ユニットタイプに対応する enter/exit メソッドを呼び出すだけで、これはちょっとしたテクニックです

AST を修正した後、最後のコード生成環節に進み、traverse して収集し、AST をコード文字列に戻します

三.実装

字句解析

// 接受代码字符串 input
function tokenizer(input) {
  // 当前正在处理的字符索引
  let current = 0;
  // 输出结果集合，存放词法单元
  let tokens = [];

  // 遍历字符串，挑出词法单元
  while (current < input.length) {
    let char = input[current];

    // 匹配左括号、右括号
    if (char === '(') {
      tokens.push({
        type: 'paren',
        value: '(',
      });
      current++;

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

      continue;
    }

    // 跳过空白字符
    let WHITESPACE = /\s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }

    // 匹配数值
    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;
    }

    // 匹配形如"abc"的字符串
    if (char === '"') {
      let value = '';

      // 吃掉左双引号
      char = input[++current];
      // 收集两个双引号之间的所有内容，作为字符串值
      while (char !== '"') {
        value += char;
        char = input[++current];
      }
      // 吃掉右边双引号
      char = input[++current];
      tokens.push({ type: 'string', value });

      continue;
    }

    // 匹配函数名，要求只含大小写字母
    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;
}

コード文字列を traverse し、各語素を拆分し、字句ユニットの形式にパッケージします

構文解析

function parser(tokens) {
  // 当前正在处理的 token 索引
  let current = 0;

  // 递归遍历（因为函数调用允许嵌套），把 token 转成 AST 节点
  function walk() {
    let token = tokens[current];

    // 数值
    if (token.type === 'number') {
      current++;

      // 生成一个 AST 节点，表示数值字面量
      return {
        type: 'NumberLiteral',
        value: token.value,
      };
    }

    // 字符串
    if (token.type === 'string') {
      current++;

      return {
        type: 'StringLiteral',
        value: token.value,
      };
    }

    // 函数调用
    if (
      token.type === 'paren' &&
      token.value === '('
    ) {
      // 丢掉左括号，取下一个 token 作为函数名
      token = tokens[++current];

      let node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

      // 看下一个 token
      token = tokens[++current];

      // 右括号之前的所有 token 解析完都是参数
      while (
        (token.type !== 'paren') ||
        (token.type === 'paren' && token.value !== ')')
      ) {
        node.params.push(walk());
        token = tokens[current];
      }
      // 吃掉右括号
      current++;

      return node;
    }

    // 无法识别的 token，报错
    throw new TypeError(token.type);
  }

  // AST 的根节点
  let ast = {
    type: 'Program',
    body: [],
  };
  // 填充 ast.body，允许多条语句，所以放循环里
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

関数呼び出しのネストに対応するため、再帰を使用して token シーケンスを traverse します

traverse

function traverser(ast, visitor) {
  // 遍历 AST 节点数组
  function traverseArray(array, parent) {
    array.forEach(child => {
      traverseNode(child, parent);
    });
  }

  function traverseNode(node, parent) {
    // 从 visitor 取出对应的一组方法
    let methods = visitor[node.type];
    // 通知 visitor 我们正在访问 node
    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;

      // 无法识别的 AST 节点，报错
      default:
        throw new TypeError(node.type);
    }

    // 通知 visitor 我们要离开 node 了
    if (methods && methods.exit) {
      methods.exit(node, parent);
    }
  }

  // 开始遍历
  traverseNode(ast, null);
}

AST 構造を再帰 traverse し、traverse 過程中に visitor に通知します。アスペクト のような感じです

変換

// 输入 Lisp AST，输出 C AST
function transformer(ast) {
  // 新 AST 的根节点
  let newAst = {
    type: 'Program',
    body: [],
  };

  // 偷懒以简单粗暴的方式维持新旧 AST 的联系，方便在遍历过程中操作新 AST
  ast._context = newAst.body;

  // 创建 vistor，开始遍历
  traverser(ast, {
    // 数值和字符串，直接原样插入新 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) {
        // 创建不同的 AST 节点
        let expression = {
          type: 'CallExpression',
          callee: {
            type: 'Identifier',
            name: node.name,
          },
          arguments: [],
        };

        // 函数调用可以有孩子，建立节点对应关系，供子节点使用
        node._context = expression.arguments;

        // 顶层函数调用算是语句，包装成特殊的 AST 节点
        if (parent.type !== 'CallExpression') {
          expression = {
            type: 'ExpressionStatement',
            expression: expression,
          };
        }

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

  return newAst;
}

traverse（traverser）と修正（visitor）操作が 2 層に分離されているため、旧 AST ノードを traverse する同時に、対応する新 AST 親ノードを明確に知るのはあまり容易ではありません。ここで簡単粗暴 な方式を採用し、直接新しい _context 属性を追加することで旧 AST ノードの親ノードに操作対象の新 AST ノード参照を持たせます。使えますが、旧 AST を汚染します

コード生成

// 递归遍历新 AST，输出代码字符串
function codeGenerator(node) {
  switch (node.type) {
    // 根节点，把 body 里的所有内容都生成一遍，按行输出
    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 + '"';

    // 无法识别的新 AST 节点，报错
    default:
      throw new TypeError(node.type);
  }
}

AST を再びコ��ド文字列に戻し、セミコロンを追加すべきものはセミコロンを追加し、括弧を追加すべきものは括弧を追加します……

フロー連結

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

  return output;
}

上記のすべての環節を連結し、シンプルなコンパイラを構成します。確かに 200 行ほどの样子です。试玩一下：

const input  = '(add 2 (subtract 4 2))';
let output = compiler(input);
// add(2, subtract(4, 2));
console.log(output);

四.最適化

2 つの最適化ポイント：

  • 字句解析：文字ごとにマッチするのは冗長で、効率が許容できる場合、正規表現の方が明確

  • 変換：新しい AST を生成する方式は汚く、旧 AST を汚染します。追加のデータ構造を通じて新旧 AST の連絡を記録し、旧 AST に影響を与えるのを回避できます

より明確な字句解析

例えば各語素に対応する正規表現：

const REGEX = {
  PAREN: /^\(|^\)/,
  WHITESPACE: /^\s+/,
  NUMBERS: /^\d+/,
  STRING: /^"([^"]+)?"/,
  NAME: /^[a-z]+/i
};

while (rest.length > 0) {
  let type, value;
  // 匹配结果，本次匹配消费掉的串长度
  let matched, span;

  // 匹配左括号、右括号
  if (matched = rest.match(REGEX.PAREN)) {
    type = 'paren';
  }
  //...匹配其它词素

  value = value || matched[0];
  tokens.push({type, value});
  rest = rest.slice(span || matched[0].length);
}

比較明確になりました。拡張性を向上したい場合、語素関連の type, value, span をさらに構成化 できます：

// 词素相关配置
const lexemes = [
  {
    regex: /^\(|^\)/,
    type: 'paren',
    value: 0,
    span: 0
  }, {
    regex: /^\d+/,
    type: 'number',
    value: 0,
    span: 0
  }, {
    regex: /^"([^"]+)?"/,
    type: 'string',
    value: 1,
    span: 0
  }, {
    regex: /^[a-z]+/i,
    type: 'name',
    value: 0,
    span: 0
  }
];

然后以统一的方式处理这些词素：

while (rest.length > 0) {
  // 跳过空白字符
  if (matched = rest.match(/^\s+/)) {
    rest = rest.slice(matched[0].length);
    continue;
  }

  lexemes.forEach(({regex, type : t, value: v, span: s}) => {
    if (matched) return;
    if (matched = rest.match(regex)) {
      type = t;
      value = matched[v];
      span = matched[s].length;
    }
  });

  if (matched) {
    tokens.push({type, value});
    rest = rest.slice(span);
  }
  else {
    // 无法识别的字符，报错
    throw new TypeError('Unexpected character: ' + rest);
  }
}

よりクリーンな変換

新しいツリーを生成するには 2 つのことを行う必要があります：

  1. ノードマッピング

  2. ツリー構造の作成

ノードマッピングは簡単ですが、新しいノードをどこに掛けるかが問題 です。visitor と transformer は実装上は独立した 2 層なので、新旧 2 つのツリーの連絡を手動で記録する必要があります。例えば上記変換部分ソースコード中の：

// 偷懒以简单粗暴的方式维持新旧 AST 的联系，方便在遍历过程中操作新 AST
ast._context = newAst.body;
// 函数调用可以有孩子，建立节点对应关系，供子节点使用
node._context = expression.arguments;

これで現在訪問中の旧ノードに対応する新ノードを新ツリーのどの位置に掛けるべきかが分かります。例えば：

// 旧树中父节点身上挂着对应新树节点的孩子数组，把新节点填进去
parent._context.push({
  type: 'NumberLiteral',
  value: node.value,
});

しかしこの実装は汚いです（传入された旧ツリー ast を汚染します）。より合理的な做法は非侵入的な方式で新ツリー中の現在アクティブなノードコンテナを記録することで、関数呼び出しはネストを許可するため、スタック構造を使用して記録する必要があります：

// 用额外的数据结构维持新旧 AST 的联系
let stack = [newAst.body];
function peak() {
  return stack[stack.length - 1];
}

旧ツリーを再帰 traverse する過程中にこの連絡を維持します：

// 函数调用
CallExpression: {
  enter(node, parent) {
    // 取出活跃的新树节点容器
    let newASTHost = peak();

    // 创建新树节点
    let expression = {
      type: 'CallExpression',
      callee: {
        type: 'Identifier',
        name: node.name,
      },
      arguments: [],
    };

    // 函数调用可以有孩子，建立节点对应关系，供子节点使用
    stack.push(expression.arguments);

    // 填充新树结构
    newASTHost.push(expression);
  },
  leave(node, parent) {
    // 参数收集结束，回到上一层
    stack.pop();
  }
}

これで旧ツリーを汚染することはなくなり、コストもそれほど高くありません（追加のデータ構造 stack 1 つ）

五.ソースコード

Github アドレス：https://github.com/ayqy/the-super-tiny-compiler

P.S.詳細な注釈付きの原版および最適化後の実装を含みます

参考資料

コメント

コメントはまだありません

コメントを書く