如何实现一个简易编译器

本篇文章的内容是设计一个新语法，并实现能够解析该语法的编译器，将新语法编译成javascript的标准语法，使之能够正常运行在生产环境中。读完这篇文章，再结合自身的实践，大家就能知道该如何写一个小型编译器了。如果对源码感兴趣，请移步这里进行查看。

OK，总结一下接下来要做的事情：

语法设计
编译器的实现
结语

语法设计

我们做的第一件事就是设计我们的语法规范,由于我们的新语法是在javascript的规范上进行的扩充，所以，有些语法我们要沿用ECMA的规范。在设计我们的新语法之前，先来看下面这段代码。

var a, b, c = 5
a = b = c

显而易见，这段代码的作用是定义三个变量，并为它们赋初始值为5。
但我觉得上面的写法啰嗦，我想像下面这样书写代码，并实现同样的赋值操作。

var a b c = 5

简洁吗？不够简洁？
OK，我们再看下面两段代码，这次我们不再随意以a,b,c的方式命名变量，而是将变量命名语义化。

// javascript语法
var baseSalary, graduateSalary, doctorSalary = 1000
baseSalary = graduateSalary = doctorSalary
// 新语法
var baseSalary graduateSalary doctorSalary = 1000

可以看到，我们将变量命名语义化之后，后者的代码量减少了很多。但不要高兴的太早哦。因为ECMA规范中并没有这种语法，假如这样书写，非但达不到想要的效果，浏览器或者nodejs引擎会报语法错误。

如果你受不了第一种啰嗦的赋值语法，又特别想用第二种语法，怎么办呢？是的，我们可以实现一个编译器，将第二种语法编译成第一种语法。

在继续讲述之前，为了方便书写，姑且将第二种语法命名为qi语法，qi语法就是我们要实现的语法。

至此，我们的语法设计就结束了。

编译器的实现

在开始实现我们的编译器之前，我们首先得明确编译器长什么样子，由哪几部分构成，工作原理是怎样的。只有了解了这些，我们才知道该如何下手。

为了简单起见，我们对qi语法进行如下约束：
1.qi语法只能通过var或者let方式进行赋值。
2.qi语法不能使用ES6的解构赋值。
3.qi语法只能为变量赋予数字，字符串，null，bool四种基本类型值。即=号右侧只能跟数字、字符串、null、true或者false，不能跟表达式、对象、数组等复杂类型。

做了如上三个约束条件，我们就可以简化编译器的实现了。注意：仅仅是简化，我不会忽略这当中的每一个过程。

本质上来说，编译器其实也是一个程序，这个程序能够将一种语言（源代码）翻译成另一种语言（目标代码），类似于现实生活中的翻译员。如下图所示

本文源代码就是符合我们前面设计好的语法规范的代码，目标代码是javascript标准代码。

如何下手

OK，我们接下来要实现一个能够将qi语法翻译为javascript语法的程序，但，从何处着手编码呢？在实际编码之前，我们再花点时间了解一下编译器的内部构造与工作原理，我们可以把编译器看成一个黑盒，从一端输入源代码，另一端输出目标代码。

一个完整的编译器包含如下过程
1.词法分析
2.语法分析
3.语义分析
4.生成中间代码
5.编译优化
6.生成目标代码

为了便于理解，本文所讲的编译器不包含4（生成中间代码）和5（编译优化）的步骤。

首先源代码经过词法分析器（tokenizer）分析，输出线性结构的token单词流。
token经过语法分析器（parser）分析，输出符合qi语法规范的AST（抽象语法树）。
将AST传入语法树遍历器（transformer）输出符合javascript规范的AST。
将生成的符合javascript规范的AST传入代码生成器（generator）构造目标代码。

至此，整个编译流程就结束了。具体流程如下图所示。

为了简单起见，我用下面这段代码作为贯穿全文的示例代码进行分析。

// qi语法
var a b c = 100

本文实现的编译器，要能够把上面这段代码，翻译成如下代码。

// javascript语法
var a, b, c = 100
a = b = c

另外，还需要声明一点，qi语法的规则也是要遵循javascript语法规范的，我只是在javascript现有语法的基础上衍生一种新的语法。明确了这一点，后续的词法分析和语法分析程序就容易编写了。

词法分析

编译器的第一个阶段就是词法分析，词法分析的作用是将源代码翻译成token集合。源代码实质上是一个字符序列，字符本身粒度太小，直接拿来进行语法分析，复杂度较高。所以我们先分割出一个词法分析器，将字符序列转换成单词集合。拿上面的源代码来说，如果以字符为粒度进行展开，其形式如下：

['v', 'a', 'r', ' ', 'a', ',' ,' ', 'b', ' ', 'c', ' ', '=', ' ', '1', '0', '0']

这种结构我们很难提取出有价值的信息，而我们的词法分析器，则是将上面的字符序列，变成下面的单词序列。

['var', ' ', 'a', ' ', 'b', ' ', 'c', ' ', '=',' ', '100']

很显然，单词序列的可读性更高，我们甚至能够很容易地读出这段代码的意思。

javascript词法规范中包含、保留字、操作符、字面量（字符串，数字，null，bool等）、变量标识符等诸多单词类型，所以我们的词法分析器还应该分析出单词类型。

前面我对qi语法的赋值类型做了一些约束，并且规定qi语法的词法完全遵循javascript的规范，所以qi语法的词法类型有以下几种

标识符，IDENTIFIER
关键词，KEYWORD
bool字面量，BOOLEAN_LITERAL
null字面量，NULL_LITERAL
数字字面量，NUMBER_LITERAL
字符字面量，STRING_LITERAL
操作符，PUNCTUATOR
换行符，BR
程序结束，EOF

OK，明确了单词类型，我们就可以定义有限自动状态机了，如下：

const tokenType = {
  IDENTIFIER: 1,
  KEYWORD: 2,
  EOF: 3,
  NULL_LITERAL: 4,
  BOOLEAN_LITERAL: 5,
  PUNCTUATOR: 6,
  NUMBER_LITERAL: 7,
  BR: 8,
  STRING_LITERAL: 9
}
module.exports = tokenType

需要注意的是，我们增加换行符的目的，是为了减少变量定义语句的二义性。看下面这段代码，假设我们不增加换行符。

var a b
c = 100

token集合为[ ‘var’, ‘a’, ‘b’, ‘c’, ‘=’, ‘100’ ]

var a b c = 100

token集合为[ ‘var’, ‘a’, ‘b’, ‘c’, ‘=’, ‘100’ ]

可以看到这两段代码的token集合是一模一样的，但是这两段代码的实际语义却是完全不一样的。
为了能够采用自顶向下的LL（1）的语法分析方式，我们引入换行符BR来消除二义性。

明确了单词类型，我们就可以着手写代码了，词法分析过程不是很复杂，利用前面定义的有限自动状态机即可，所以我不打算贴上全部代码，仅取主要方法讲解一下，如果想看具体实现，点击这里词法分析器

function getNextToken(){
  let cp, token
  if(pos > len){
    return {
      type: Type.EOF
    }
  }
  cp = source[pos]
  // 判断是否属于标识符的开始字符，若是，就先进行标识符的扫描
  if(isIdStart(cp)) {
    token = scanId()
    return token
  }
  // 判断是否是操作符，若是，进行操作符的扫描
  if(cp === '(' || cp === ')' || cp === ';' || cp ===',') {
    token = scanPuntuator()
    return token
  }
  // 判断是否是单双引号，若是，进行字符串的扫描
  if(cp === '"'|| cp === '\'') {
    token = scanStringLiteral()
    return token
  }
  // 判断是否是点号，若是，先判断接下来的字符是否属于数字，若是，则进行数字扫描，如若不是，进行操作符的扫描
  if(cp === ".") {
    if(isDecimalDigit(source[pos + 1])) {
      return scanNumberLiteral()
    }
    return scanPuntuator()
  }
  // 判断当前字符是否是数字，若是，进行数字的扫描。
  if(isDecimalDigit(cp)) {
    return scanNumberLiteral()
  }
  // 以上情况都不符合，进行操作符的扫描
  return scanPuntuator()
}

上面这段代码经过词法分析器分析之后，得到下面这种线性结构的数据。

至此，我们的词法分析阶段结束，开始下一步的语法分析。

语法分析

经过词法分析，我们得到了可读性较高的token集合，接下来开始语法分析，语法分析阶段主要做两件事：

语义分析

我们在语法树构建过程的同时，会对源程序进行语义分析，由于我们的语法比较简单，仅仅是变量定义，不会涉及变量类型检测，所以语义分析仅仅是简单的单词类型检测。
生成抽象语法树（AST）

先来看一下我们要生成的语法树是什么样子的

OK，大家对抽象语法树有了大概的认识，我们开始写代码，写代码之前，要搞清楚如何进行语法分析。由此，需要引出文法这一概念。文法是什么？文法其实是描述语言的一种工具。比如我们的赋值语句：

var a = 1

怎么定义我们赋值语句的形式呢？如果用大白话来说，我可以这样解释赋值语句：赋值语句最左边是var，然后跟一个变量a，再跟等号，最后跟一个表达式。但这样解释太啰嗦了，我需要用一组符号来表示

S->abcE；E->f

S 对应 赋值语句

a 对应关键词var

b 对应变量a

c 对应操作符=

E 对应表达式

f 对应数字1

这种用符号来表示语言的形式就叫产生式，S->abcE代表S的产生式，E->f代表E的产生式，其中小写字母代表终结符，大写字母代表非终结符。当我们为式子中某个非终结符挑选一个产生式，并用这个产生式的右侧部分代替这个非终结符在式子中的位置，那么这个过程，我们叫非终结符的展开。当某个式子能够按照文法完全展开，那么我们可以说这个式子符合该文法的定义，是正确的文法。

语法分析的过程就是根据文法定义，不停的去寻找产生式，直到找到一个匹配源代码的展开方案，如果找不到，说明我们的源代码是有语法错误的。
明白了文法的定义形式，我们为qi语法定义如下的文法：

S -> aV

变量定义语句 -> var 变量定义，
V -> DF

变量定义 -> 变量跟随变量定义
F -> ξ

跟随变量定义 -> 空
F -> ,V

跟随变量定义 -> , 变量定义
D -> IE

变量 -> 多变量表达式
I -> iI

多变量 -> 单变量多变量
I -> ξ

多变量 -> 空
E->ξ

表达式 -> 空
E->t

表达式 -> = 数字字面量 | 布尔字面量 | 字符串字面量 | null

注：终结符有三类，a代表关键词var或者let，i代表变量名，t代表字面量

如图

文法定义好了，我们拿一个式子展开一下，验证一下该式是否符合该文法。

var a b c = 10
展开上式
代入1式，得S->var V
代入2式，得S->var DF
带入5式，得S->var IEF
代入6式，得S->var a IEF
代入6式，得S->var a b IEF
代入6式，得S->var a b cIEF
代入7式，得S->var a b c EF
代入9式，得S->var a b c = 10 F
代入3式，得S->var a b c = 10

展开成功，该语句是符合我们连等语法的赋值语句。

再来个复杂一些的：

var  a b c = 10, d e = 11
代入1式，得S->var V
代入2式，得S->var DF
代入5式，得S->var IEF
代入6式，得S->var a IEF
代入6式，得S->var a b IEF
代入6式，得S->var a b cIEF
代入7式，得S->var a b c EF
代入9式，得S->var a b c=10 F
代入4式，得S->var a b c=10, V
代入2式，得S->var a b c = 10, DF
代入5式，得S->var a b c = 10, IEF
代入6式，得S->var a b c = 10, d IEF
代入6式，得S->var a b c = 10, d e IEF
代入7式，得S->var a b c = 10, d e EF
代入9式，得S->var a b c = 10, d e = 11 F
代入3式，得S->var a b c = 10, d e = 11
展开成功

文法定义好了，接下来我们开始编写语法分析器。其实语法分析就是寻找式子展开方案的过程，并根据文法中的产生式构建抽象语法树。语法分析的关键点搞定之后，我们就可以进行编码了。碍于篇幅有限，我只贴上生成语法树的递归函数。详细代码参见语法分析器

function parseEqualVariableDeclaration(re) {
    let node, equalNode, id_list
    current_token = token_list[pos++]
    //遍历token集合
    while(current_token.type === Type.IDENTIFIER) {
        node = new Node()
        node.type = Syntax.Identifier
        node.value = current_token.value
        !id_list && (id_list = [])
        id_list.push(node)
        current_token = token_list[pos++]
    }
    if(!id_list) {
        return
    }
    //如果每一个定义语句多于一个变量的话，则视为Syntax.EqualVariableDeclaration
    if(id_list.length > 1) {
        equalNode = new Node()
        equalNode.type = Syntax.EqualVariableDeclaration
        equalNode.body = id_list
        re.push(equalNode)
    } else if (id_list.length === 1) {
        re.push(node)
    }
    //判断是否存在跟随变量，如果存在的话，递归解析
    if(current_token && current_token.value === ',') {
      if(equalNode){
        equalNode.init = undefined
      } else {
        id_list.forEach(function(n){
          n.init = undefined
        })
      }
      parseEqualVariableDeclaration(re)
    }
    let init = ''
    //判断是否有赋值过程
    if(current_token && current_token.value === '=') {
        current_token = token_list[pos++]
        // 若有赋值过程，则值类型必须在基础类型范围之内
        if (current_token.type === Type.STRING_LITERAL || current_token.type === Type.NUMBER_LITERAL || current_token.type == Type.BOOLEAN_LITERAL || current_token.type == Type.NULL_LITERAL) {
            if(current_token.type === Type.STRING_LITERAL) {
              init = '"' + current_token.value + '"'
            } else {
              init = current_token.value
            }
            current_token = token_list[pos++]
        } else if (current_token.type === Syntax.BR) {
            current_token = token_list[pos++]
        } else {
            throw new Error("语法分析错误")
        }
        if(equalNode) {
          equalNode.init = init
        } else {
          node.init = init
        }
    }
    //判断赋值语句后是否存在跟随变量，如果有，则递归解析
    if(current_token && current_token.value === ',') {
        parseEqualVariableDeclaration(re)
    }
}

语法分析结束后，我们能得到下面的语法树。

{
    "type": "Program",
    "body": [{
        "type": "VariableDeclaration",
        "body": [{
            "type": "EqualVariableDeclaration",
            "body": [{
                "type": "Identifier",
                "value": "a"
            }, {
                "type": "Identifier",
                "value": "b"
            }, {
                "type": "Identifier",
                "value": "c"
            }],
            "init": 100
        }],
        "kind": "var"
    }]
}

语法树遍历器

经过语法分析，我们得到了qi语言的语法树，正常情况下我们可以根据语法树，生成最终代码了，但我想再增加一个语法树遍历器transformer，通过它，我可以将qi语法的AST转换成任何我想要的语言的AST，这样我可以为这些语言扩充qi语法，而不仅仅是为javascript。
语法树遍历器的实现比较简单，我只需要对qi语法的AST树采用深度优先遍历即可，具体代码参见语法树遍历器

OK，说下我的期望，我想将qi语法的语法树转变成如下树形结构。

{
    "type": "Program",
    "body": [{
        "type": "VariableDeclaration",
        "body": [{
            "type": "Identifier",
            "value": "a"
        }, {
            "type": "Identifier",
            "value": "b"
        }, {
            "type": "Identifier",
            "value": "c"
        }],
        "kind": "var"
    }, {
        "type": "AssignmentExpression",
        "body": [{
            "type": "AssignmentEqual",
            "body": [{
                "type": "Identifier",
                "value": "a"
            }, {
                "type": "Identifier",
                "value": "b"
            }, {
                "type": "Identifier",
                "value": "c"
            }],
            "value": 100
        }]
    }]
}

经过AST转换之后，我得到了包含一个变量定义语句和一个赋值表达式语句的树形结构，这种结构在生成目标代码阶段更容易分析。

目标代码生成

经过语法树遍历器我们得到了更利于生成代码的树形结构，这样我们就可以构造目标代码了。构造过程分为两个阶段

1. 生成变量定义代码

{
    "type": "VariableDeclaration",
    "body": [{
        "type": "Identifier",
        "value": "a"
    }, {
        "type": "Identifier",
        "value": "b"
    }, {
        "type": "Identifier",
        "value": "c"
    }],
    "kind": "var"
}

上面的树形结构对应代码

var a, b, c

2. 生成变量赋值代码

{
    "type": "AssignmentExpression",
    "body": [{
        "type": "AssignmentEqual",
        "body": [{
            "type": "Identifier",
            "value": "a"
        }, {
            "type": "Identifier",
            "value": "b"
        }, {
            "type": "Identifier",
            "value": "c"
        }],
        "value": 100
    }]
}

上面树形结构对应代码为

a = b = c = 100

可以看出，转换后的AST可以让我们很容易的生成目标代码，逻辑比较简单，这里不做过多着墨，详细代码参见代码生成器

结语

至此，我们的编译器就介绍完了，希望本文能够帮助大家消除编译器的困惑。本文的所有源码托管在github上。另外，针对该库我编写了一个webpack-loader,assign-loader，感兴趣的同学可以去试用下。

lucefer

details is the key to success