本文目录

[[toc]]

AST

使用场景

• 语法转换（ ES6 转 ES5 ）
• eslint （ 语法检查、自动修复 ）
• 格式化（ prettier ）
• 构建/解析（ webpack 、 loader ）

生成步骤

AST 主要包括 词法分析 与 语法分析 两个部分

为了方便理解，使用以下示例代码作为样例

var answer = 6 * 7

词法分析

词法分析通过 scanner 扫描代码，将代码分为不同的 token （词法单元），只关联每个 token 的类型，不会维护树结构，例如：

构建的 tokens 如下:

[
  {
    "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": ";"
  }
]

语法分析

语法分析就是将遍历得到的 tokens 列表，根据语法规则将 token 关联起来，形成一棵树形结构，这棵树就是 AST 。

所以 AST 表示的是源代码的语法结构，树上的每个节点表示的是源代码中的一种结构。

构建后的 AST 结构如下:

{
  "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"
}

简易的编译器

下面是一个简易的编译器实现，它可以将 Lisp 风格的函数调用转换为 C 风格的函数调用。

编译器的主要阶段

编译器通常分为三个主要阶段：

1. 解析（Parsing）：将原始代码转换为更抽象的代码表示
2. 转换（Transformation）：操作这个抽象表示，执行编译器想要的操作
3. 代码生成（Code Generation）：将转换后的代码表示转换为新代码

解析阶段

解析通常分为两个阶段：词法分析和语法分析。

词法分析（Lexical Analysis）

词法分析通过 tokenizer（词法分析器）将原始代码分割成称为 tokens（标记）的小对象。

例如，对于代码 (add 2 (subtract 4 2))，生成的 tokens 可能如下：

[
  { 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）

语法分析将 tokens 重新格式化为描述语法各部分及其相互关系的表示。这被称为中间表示或抽象语法树（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",
      }]
    }]
  }]
}

转换阶段

转换阶段接受上一步的 AST 并对其进行修改。它可以操作相同语言的 AST，或者将其转换为全新的语言。

遍历（Traversal）

为了遍历所有节点，我们需要能够深度优先地遍历 AST 中的每个节点。

访问者（Visitors）

访问者模式用于表示对对象结构元素的操作。我们创建一个具有接受不同节点类型方法的访问者对象：

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

当我们遍历 AST 时，每当"进入"匹配类型的节点时，我们都会调用访问者上的方法。

代码生成阶段

代码生成阶段接受转换后的 AST 并将其转换回代码字符串。代码生成器知道如何"打印" AST 的所有不同节点类型，并且它会递归调用自身来打印嵌套节点，直到所有内容都被打印成一个长代码字符串。

完整实现

下面是一个完整的简易编译器实现：

// 词法分析器
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;
    }

    // 处理字符串
    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;
}

// 解析器
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;
}

// 遍历器
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);
}

// 转换器
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;
}

// 代码生成器
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);
  }
}

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

  return output;
}

使用示例

// 输入: (add 2 (subtract 4 2))
// 输出: add(2, subtract(4, 2));

这个简易编译器展示了编译器的主要组成部分和工作原理，虽然它只处理了非常简单的语法，但包含了编译器设计的基本概念和流程。