关于javascript:实现一个简易编译器

编译器在各种场合下都会有应用，从 webpack 到babel，到框架外部比方vue，都或多或少的应用到了编译，所以这次理解一下编译器的最根底的实现。

这次就把一个 lisp-like 函数调用形式转换成 JavaScript 的形式。

两种语言的函数调用形式比照如下：

	LISP	JavaScript
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 100 (substract 3 2))

也就是100 + (3 - 2)，那么开始吧。

个别的编译器分为以下几步：

Parsing – 将源代码文本解析成更为形象的表达方式，通常是 AST（Abstract Syntax Tree）– 形象语法树。
Transformation – 能够通过具体须要去变更，解决原始的 AST。
Code Generation – 从 AST 生成代码。

接下来就一步步开始。

这一步次要是对于源代码的解析，个别可再细分成 2 步：

Lexical Analysis（词法剖析）- 将源代码以单词为维度分成许多独立的片段。
Syntactic Analysis（语法分析）- 把独立的代码片段以树形构造串联起来，生成 AST。

这一步通常会用 tokenizer 表白，传入源代码，返回tokens – 我称之为单词数组。

对于咱们的例子来说, 拆分后大略会示意成上面的样子：

[{ type: 'paren', value: '('},
  {type: 'name', value: 'add'},
  {type: 'number', value: '100'},
  {type: 'paren', value: '('},
  {type: 'name', value: 'substract'},
  {type: 'number', value: '3'},
  {type: 'number', value: '2'},
  {type: 'paren', value: ')' },
  {type: 'paren', value: ')' }
]

这一步能够了解为以单个单词为维度拆分了一句句子，类比到中文就比方

我去餐厅吃饭

就能够被拆分为

我，去，餐厅，吃饭

这种以词性辨别的单词合集。

晓得了其意义之后就是代码实现了，具体如下：

function tokenizer(input) {
    // 单词数组
    const tokens = []

    // 设定一个指针
    let current = 0
    // 从 0 开始遍历源代码
    while (current < input.length) {let char = input[current]

        // 如果是空格则跳过
        const spaceRegExp = /\s/
        if (spaceRegExp.test(char)) {
            current++
            continue
        }

        // 如果是括号则退出后果中
        if (char === '(' || char === ')') {tokens.push({ type: 'paren', value: char})

            // 指针指向下一位，开始下次循环
            current++
            continue
        }

        // 如果是小写字母（这里暂且只反对小写字母）// 则累计遍历到最初一个小写字母再放入后果中
        const letterRegExp = /[a-z]/
        if (letterRegExp.test(char)) {
            let value = ''

            while (letterRegExp.test(char)) {
                value += char
                char = input[++current]
            }

            tokens.push({type: 'name', value})
            continue
        }

        // 如果是数字则累加遍历到最初一个数组放入后果中
        const numberRegExp = /[0-9]/
        if (numberRegExp.test(char)) {
            let value = ''

            while (numberRegExp.test(char)) {
                value += char
                char = input[++current]
            }

            tokens.push({type: 'number', value})
            continue
        }

        throw new Error('词法剖析失败，有不反对的单词类型')
    }

    return tokens
}

大抵的逻辑就是设定一个指针，通过适合的规定一直的一个个向后寻找符合条件的单词。

再接下来就是语法分析，把刚刚失去的单词们关联起来，把一整个语句生成一个树形构造，也就是形象语法树。

看上去会像这样：

{
  "type": "Program",
  "body": [
    {
      "type": "CallExpression",
      "name": "add",
      "params": [
        {
          "type": "NumberLiteral",
          "value": 100
        },
        {
          "type": "CallExpression",
          "name": "substract",
          "params": [
            {
              "type": "NumberLiteral",
              "value": 3
            },
            {
              "type": "NumberLiteral",
              "value": 2
            }
          ]
        }
      ]
    }
  ]
}

这一步就相当于把单词连成句子，用树形构造示意他们之间的关系。

比方函数就有类型，函数名，参数。这些实践上都能够自定义，依据每一种不同的语言的须要。

次要是代码的实现，因为每一个子节点都有可能是各种类型，所以用递归显著会更不便实现一些，具体代码如下。

function parser(tokens) {

    // 设定一个指针，从 0 开始
    let current = 0

    // 这里用递归更容易实现
    function parse() {let token = tokens[current]

         // 如果是数字则返回数字节点，指针指向下一个
        if (token.type === 'number') {
            current++
            return {
                type: 'NumberLiteral',
                value: +token.value,
            }
        }

        // 如果是左括号
        if (token.type === 'paren' && token.value === '(') {

            // 生成一个类型为调用表达式的节点
            const node = {
                type: 'CallExpression',
                name: '',
                params: [],}

            // 指向下一个 token，失常状况下肯定是 name 类型的
            token = tokens[++current]
            if (token.type !== 'name') {throw new Error('没有提供函数名')
            }

            node.name = token.value
            // 再指向下一个 token
            token = tokens[++current]

            // 只有不是右括号则始终退出参数中
            while (!(token.type === 'paren' && token.value === ')')) {node.params.push(parse())
                // 更新以后指针
                token = tokens[current]
            }

            // 跳过右括号
            current++

            return node
        }

        throw new Error('token 类型谬误')
    }

    const ast = {
        type: 'Program',
        body: [],}

    // 把所有的 token 生成的节点放入 body 中（如果是多行语句则会有多个对象）while (current < tokens.length) {ast.body.push(parse())
    }

    return ast
}

大抵的思路就是 parse 函数针对特定类型的值有特定的解决形式，而有那种须要依赖其余值的语法的时候（比方参数调用，参数可能是任何内容）就递归的调用，同时保护一个指针来确立地位。

事实上如果咱们的需要只是生成代码的话，通过下面失去的 AST 就能够间接进行下一步 Code Generation 了，但那样必须要针对咱们本人的树形构造生成对应的 JavaScript 代码，理论状况下两种语法可能是不同语言的，所以更好的是将咱们之前的 AST 转换成更规范的语法。

天经地义的，目前市面上也有比拟罕用的标准 estree，比方非常罕用的编译器 acorn 就是合乎这项规范的。（目前 webpack, rollup 都是基于他，@babel/parser 也是参考的他）具体各种生成后果能够在 https://astexplorer.net/ 尝试。

于是咱们接下来思考把咱们的 AST 变成合乎 estree 标准的 AST。

所以咱们必须要遍历所有节点，于是咱们针对每个节点都设定本人的处理函数，整体叫做visitor，大略是这样。

const visitor = {Program: function (node, parent) {// ...},
   NumberLiteral: function (node, parent) {// ...},
   // ...
}

对于每个函数须要的参数能够依据具体须要做考量，这里为了取得最简略的关系对应暂且传入以后节点和父节点。

另外因为咱们的需要比较简单，所以也不须要在意拜访工夫点，如果需要的话能够设定拜访开始和拜访完结之类的工夫点比方

const visitor = {
   Program: {enter () {// ...},
      exit () {// ...},
   }
   // ...

对于咱们这里就不须要了，接下来实现一下具体代码。

function traverser(ast, visitor) {
    // 拜访单个节点
    function traverseNode (node, parent) {
        // 执行以后拜访函数
        const method = visitor[node.type]
        method && method(node, parent)

        // 如果有子节点则遍历子节点
        switch(node.type) {
            case 'Program':
                traverseArray(node.body, node)
                break
            case 'CallExpression':
                traverseArray(node.params, node)
                break
            case 'NumberLiteral':
                break
            default:
                throw new Error('节点类型谬误')
        }
    }

    // 拜访数组节点
    function traverseArray(array, parent) {
        array.forEach(child => {traverseNode(child, parent)
        })
    }

    // 拜访 ast 根节点
    traverseNode(ast, null)
}

这个函数提供了 AST 以及 visitor，能够让咱们拜访到每一个节点，而对于每个节点的具体操作则要依据须要来，咱们这里是心愿把语法转换成合乎 estree 规范的语法，所以再实现一个转换函数。

function transform(ast) {
    const newAst = {
        type: 'Program',
        body: [],}

    // 这里设置一个属性指向新的 AST 上下文
    ast._context = newAst.body
    traverser(ast, {NumberLiteral(node, parent) {
            // 转换为 estree 规范的数字节点，放入父节点上下文
            parent._context.push({
                type: 'Literal',
                value: node.value,
            })
        },
        CallExpression(node, parent) {
            // estree 规范的调用节点构造
            let expression = {
                type: 'CallExpression',
                callee: {
                    type: 'Identifier',
                    name: node.name,
                },
                arguments: [],}

            // 把上下文设置为参数数组
            node._context = expression.arguments

            // 如果父节点不是调用表达式则表达式外层须要套一层，estree 规范
            if (parent.type !== 'CallExpression') {
                expression = {
                    type: 'ExpressionStatement',
                    expression,
                }
            }

            // 以后表达式放入父节点上下文中
            parent._context.push(expression)
        },
    })

    return newAst
}

这个函数的外部实现事实上是齐全依据须要来的，因为咱们须要这里转换格局所以生成了一个新的 AST，再判断节点，把对应节点转换过的新格局放入新的树中。

这样之后咱们失去的后果是这样：

{
  "type": "Program",
  "body": [
    {
      "type": "ExpressionStatement",
      "expression": {
        "type": "CallExpression",
        "callee": {
          "type": "Identifier",
          "name": "add"
        },
        "arguments": [
          {
            "type": "Literal",
            "value": 100
          },
          {
            "type": "CallExpression",
            "callee": {
              "type": "Identifier",
              "name": "substract"
            },
            "arguments": [
              {
                "type": "Literal",
                "value": 3
              },
              {
                "type": "Literal",
                "value": 2
              }
            ]
          }
        ]
      }
    }
  ]
}

目前这个树结构是合乎 estree 规范的，以至于咱们能够应用其余第三方库来操作这个树。比方 escodegen，能够通过 estree 生成代码，对下面这个树结构的执行后果是：

add(100, substract(3, 2));

尽管下面曾经能够用其余库实现了，不过咱们这里还是来理解一下通过 AST 生成代码的原理吧。大略的原理理论很简略，就是判断以后节点的类型对其以及其子节点递归的去生成代码。

function generateCode(node) {switch(node.type) {
        case 'Program':
            // 对 body 每一个节点生成代码用换行隔开
            return node.body.map(generateCode).join('\n')
        case 'Literal':
            // 字面量间接返回值
            return node.value
        case 'ExpressionStatement':
            // 表达式则返回表达式生成的代码，加上分号结尾
            return generateCode(node.expression) + ';'
        case 'CallExpression':    
            // 如果是函数调用，则把参数生成的代码通过逗号隔开
            return `${node.callee.name}(${node.arguments.map(generateCode).join(',')})`
        default:
            throw new Error('节点类型谬误')
    }
}

把下面几步加起来大略会是上面这样：

const tokens = tokenizer(code)
const ast = parser(tokens)
const newAst = transform(ast)
const result = generateCode(newAst)
console.log(result)
// => add(100, substract(3, 2));

那么这样就实现了。

这次介绍了编译器大抵的工作原理，在各种场景下应用时样子可能不太一样不过核心思想就是这么几步，之后面对各种理论状况踊跃的去改良吧！

本文参考了 the-super-tiny-compiler 这个我的项目的许多内容，举荐大家去学习。

the-super-tiny-compiler
相干代码
原文地址

关于javascript:实现一个简易编译器

前言

指标

思路

Parsing

Lexical Analysis

Syntactic Analysis

Transformation

Code Generation

总结

参考