编译原理实战入门：用 JavaScript 写一个简单的四则运算编译器（修订版）

[woai3c]

编译器是一个程序，作用是将一门语言翻译成另一门语言。

例如 babel 就是一个编译器，它将 es6 版本的 js 翻译成 es5 版本的 js。从这个角度来看，将英语翻译成中文的翻译软件也属于编译器。

一般的程序，CPU 是无法直接执行的，因为 CPU 只能识别机器指令。所以要想执行一个程序，首先要将高级语言编写的程序翻译为汇编代码（Java 还多了一个步骤，将高级语言翻译成字节码），再将汇编代码翻译为机器指令，这样 CPU 才能识别并执行。

由于汇编语言和机器语言一一对应，并且汇编语言更具有可读性。所以计算机原理的教材在讲解机器指令时一般会用汇编语言来代替机器语言讲解。

本文所要写的四则运算编译器需要将 1 + 1 这样的四则运算表达式翻译成机器指令并执行。具体过程请看示例：

// CPU 无法识别
10 + 5

// 翻译成汇编语言
push 10
push 5
add

// 最后翻译为机器指令，汇编代码和机器指令一一对应
// 机器指令由 1 和 0 组成，以下指令非真实指令，只做演示用
0011101001010101
1101010011100101
0010100111100001

四则运算编译器，虽然说功能很简单，只能编译四则运算表达式。但是编译原理的前端部分几乎都有涉及：词法分析、语法分析。另外还有编译原理后端部分的代码生成。不管是简单的、复杂的编译器，编译步骤是差不多的，只是复杂的编译器实现上会更困难。

可能有人会问，学会编译原理有什么好处？

我认为对编译过程内部原理的掌握将会使你成为更好的高级程序员。另外在这引用一下知乎网友-随心所往的回答，更加具体：

1. 可以更加容易的理解在一个语言种哪些写法是等价的，哪些是有差异的
2. 可以更加客观的比较不同语言的差异
3. 更不容易被某个特定语言的宣扬者忽悠
4. 学习新的语言是效率也会更高
5. 其实从语言a转换到语言b是一个通用的需求，学好编译原理处理此类需求时会更加游刃有余

好了，下面让我们看一下如何写一个四则运算编译器。

词法分析

程序其实就是保存在文本文件中的一系列字符，词法分析的作用是将这一系列字符按照某种规则分解成一个个字元（token，也称为终结符），忽略空格和注释。

示例：

// 程序代码
10 + 5 + 6

// 词法分析后得到的 token
10
+
5
+
6

终结符

终结符就是语言中用到的基本元素,它不能再被分解。

四则运算中的终结符包括符号和整数常量（暂不支持一元操作符和浮点运算）。

1. 符号：+ - * / ( )
2. 整数常量：12、1000、111...

词法分析代码实现

function lexicalAnalysis(expression) {
    const symbol = ['(', ')', '+', '-', '*', '/']
    const re = /\d/
    const tokens = []
    const chars = expression.trim().split('')
    let token = ''
    chars.forEach(c => {
        if (re.test(c)) {
            token += c
        } else if (c == ' ' && token) {
            tokens.push(token)
            token = ''
        } else if (symbol.includes(c)) {
            if (token) {
                tokens.push(token)
                token = ''
            } 

            tokens.push(c)
        }
    })

    if (token) {
        tokens.push(token)
    }

    return tokens
}

console.log(lexicalAnalysis('100    +   23   +    34 * 10 / 2')) 
// ["100", "+", "23", "+", "34", "*", "10", "/", "2"]

四则运算的语法规则（语法规则是分层的）

1. x*， 表示 x 出现零次或多次
2. x | y， 表示 x 或 y 将出现
3. ( ) 圆括号，用于语言构词的分组

以下规则从左往右看，表示左边的表达式还能继续往下细分成右边的表达式，一直细分到不可再分为止。

• expression: addExpression
• addExpression: mulExpression (op mulExpression)*
• mulExpression: term (op term)*
• term: '(' expression ')' | integerConstant
• op: + - * /

addExpression 对应 + - 表达式，mulExpression 对应 * / 表达式。

如果你看不太懂以上的规则，那就先放下，继续往下看。看看怎么用代码实现语法分析。

语法分析

对输入的文本按照语法规则进行分析并确定其语法结构的一种过程，称为语法分析。

一般语法分析的输出为抽象语法树（AST）或语法分析树（parse tree）。但由于四则运算比较简单，所以这里采取的方案是即时地进行代码生成和错误报告，这样就不需要在内存中保存整个程序结构。

先来看看怎么分析一个四则运算表达式 1 + 2 * 3。

首先匹配的是 expression，由于目前 expression 往下分只有一种可能，即 addExpression，所以分解为 addExpression。
依次类推，接下来的顺序为 mulExpression、term、1（integerConstant）、+（op）、mulExpression、term、2（integerConstant）、*（op）、mulExpression、term、3（integerConstant）。

如下图所示：

这里可能会有人有疑问，为什么一个表达式搞得这么复杂，expression 下面有 addExpression，addExpression 下面还有 mulExpression。
其实这里是为了考虑运算符优先级而设的，mulExpr 比 addExpr 表达式运算级要高。

1 + 2 * 3
compileExpression
   | compileAddExpr
   |  | compileMultExpr
   |  |  | compileTerm
   |  |  |  |_ matches integerConstant		push 1
   |  |  |_
   |  | matches '+'
   |  | compileMultExpr
   |  |  | compileTerm
   |  |  |  |_ matches integerConstant		push 2
   |  |  | matches '*'
   |  |  | compileTerm
   |  |  |  |_ matches integerConstant		push 3
   |  |  |_ compileOp('*')                      *
   |  |_ compileOp('+')                         +
   |_

有很多算法可用来构建语法分析树，这里只讲两种算法。

递归下降分析法

递归下降分析法，也称为自顶向下分析法。按照语法规则一步步递归地分析 token 流，如果遇到非终结符，则继续往下分析，直到终结符为止。

LL(0)分析法

递归下降分析法是简单高效的算法，LL(0)在此基础上多了一个步骤，当第一个 token 不足以确定元素类型时，对下一个字元采取“提前查看”，有可能会解决这种不确定性。

以上是对这两种算法的简介，具体实现请看下方的代码实现。

表达式代码生成

我们通常用的四则运算表达式是中缀表达式，但是对于计算机来说中缀表达式不便于计算。所以在代码生成阶段，要将中缀表达式转换为后缀表达式。

后缀表达式

后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。

示例：

中缀表达式： 5 + 5 转换为后缀表达式：5 5 +，然后再根据后缀表达式生成代码。

// 5 + 5 转换为 5 5 + 再生成代码
push 5
push 5
add

代码实现

编译原理的理论知识像天书，经常让人看得云里雾里，但真正动手做起来，你会发现，其实还挺简单的。

如果上面的理论知识看不太懂，没关系，先看代码实现，然后再和理论知识结合起来看。

注意：这里需要引入刚才的词法分析代码。

// 汇编代码生成器
function AssemblyWriter() {
    this.output = ''
}

AssemblyWriter.prototype = {
    writePush(digit) {
        this.output += `push ${digit}\r\n`
    },

    writeOP(op) {
        this.output += op + '\r\n'
    },

    //输出汇编代码
    outputStr() {
        return this.output
    }
}

// 语法分析器
function Parser(tokens, writer) {
    this.writer = writer
    this.tokens = tokens
    // tokens 数组索引
    this.i = -1
    this.opMap1 = {
        '+': 'add',
        '-': 'sub',
    }

    this.opMap2 = {
        '/': 'div',
        '*': 'mul'
    }

    this.init()
}

Parser.prototype = {
    init() {
        this.compileExpression()
    },

    compileExpression() {
        this.compileAddExpr()
    },

    compileAddExpr() {
        this.compileMultExpr()
        while (true) {
            this.getNextToken()
            if (this.opMap1[this.token]) {
                let op = this.opMap1[this.token]
                this.compileMultExpr()
                this.writer.writeOP(op)
            } else {
                // 没有匹配上相应的操作符 这里为没有匹配上 + - 
                // 将 token 索引后退一位
                this.i--
                break
            }
        }
    },

    compileMultExpr() {
        this.compileTerm()
        while (true) {
            this.getNextToken()
            if (this.opMap2[this.token]) {
                let op = this.opMap2[this.token]
                this.compileTerm()
                this.writer.writeOP(op)
            } else {
                // 没有匹配上相应的操作符 这里为没有匹配上 * / 
                // 将 token 索引后退一位
                this.i--
                break
            }
        }
    },

    compileTerm() {
        this.getNextToken()
        if (this.token == '(') {
            this.compileExpression()
            this.getNextToken()
            if (this.token != ')') {
                throw '缺少右括号：)'
            }
        } else if (/^\d+$/.test(this.token)) {
            this.writer.writePush(this.token)
        } else {
            throw '错误的 token：第 ' + (this.i + 1) + ' 个 token (' + this.token + ')'
        }
    },

    getNextToken() {
        this.token = this.tokens[++this.i]
    },

    getInstructions() {
        return this.writer.outputStr()
    }
}

const tokens = lexicalAnalysis('100+10*10')
const writer = new AssemblyWriter()
const parser = new Parser(tokens, writer)
const instructions = parser.getInstructions()
console.log(instructions) // 输出生成的汇编代码
/*
push 100
push 10
push 10
mul
add
*/

模拟执行

现在来模拟一下 CPU 执行机器指令的情况，由于汇编代码和机器指令一一对应，所以我们可以创建一个直接执行汇编代码的模拟器。
在创建模拟器前，先来讲解一下相关指令的操作。

栈

在内存中，栈的特点是只能在同一端进行插入和删除的操作，即只有 push 和 pop 两种操作。

push

push 指令的作用是将一个操作数推入栈中。

pop

pop 指令的作用是将一个操作数弹出栈。

add

add 指令的作用是执行两次 pop 操作，弹出两个操作数 a 和 b，然后执行 a + b，再将结果 push 到栈中。

sub

sub 指令的作用是执行两次 pop 操作，弹出两个操作数 a 和 b，然后执行 a - b，再将结果 push 到栈中。

mul

mul 指令的作用是执行两次 pop 操作，弹出两个操作数 a 和 b，然后执行 a * b，再将结果 push 到栈中。

div

sub 指令的作用是执行两次 pop 操作，弹出两个操作数 a 和 b，然后执行 a / b，再将结果 push 到栈中。

四则运算的所有指令已经讲解完毕了，是不是觉得很简单？

代码实现

注意：需要引入词法分析和语法分析的代码

function CpuEmulator(instructions) {
    this.ins = instructions.split('\r\n')
    this.memory = []
    this.re = /^(push)\s\w+/
    this.execute()
}

CpuEmulator.prototype = {
    execute() {
        this.ins.forEach(i => {
            switch (i) {
                case 'add':
                    this.add()
                    break
                case 'sub':
                    this.sub()
                    break
                case 'mul':
                    this.mul()
                    break
                case 'div':
                    this.div()
                    break                
                default:
                    if (this.re.test(i)) {
                        this.push(i.split(' ')[1])
                    }
            }
        })
    },

    add() {
        const b = this.pop()
        const a = this.pop()
        this.memory.push(a + b)
    },

    sub() {
        const b = this.pop()
        const a = this.pop()
        this.memory.push(a - b)
    },

    mul() {
        const b = this.pop()
        const a = this.pop()
        this.memory.push(a * b)
    },

    div() {
        const b = this.pop()
        const a = this.pop()
        // 不支持浮点运算，所以在这要取整
        this.memory.push(Math.floor(a / b))
    },

    push(x) {
        this.memory.push(parseInt(x))
    },

    pop() {
        return this.memory.pop()
    },

    getResult() {
        return this.memory[0]
    }
}

const tokens = lexicalAnalysis('(100+  10)*  10-100/  10      +8*  (4+2)')
const writer = new AssemblyWriter()
const parser = new Parser(tokens, writer)
const instructions = parser.getInstructions()
const emulator = new CpuEmulator(instructions)
console.log(emulator.getResult()) // 1138

一个简单的四则运算编译器已经实现了。我们再来写一个测试函数跑一跑，看看运行结果是否和我们期待的一样：

function assert(expression, result) {
    const tokens = lexicalAnalysis(expression)
    const writer = new AssemblyWriter()
    const parser = new Parser(tokens, writer)
    const instructions = parser.getInstructions()
    const emulator = new CpuEmulator(instructions)
    return emulator.getResult() == result
}

console.log(assert('1 + 2 + 3', 6)) // true
console.log(assert('1 + 2 * 3', 7)) // true
console.log(assert('10 / 2 * 3', 15)) // true
console.log(assert('(10 + 10) / 2', 10)) // true

测试全部正确。另外附上完整的源码，建议没看懂的同学再看多两遍。

更上一层楼

对于工业级编译器来说，这个四则运算编译器属于玩具中的玩具。但是人不可能一口吃成个胖子，所以学习编译原理最好采取循序渐进的方式去学习。下面来介绍一个高级一点的编译器，这个编译器可以编译一个 Jack 语言（类 Java 语言），它的语法大概是这样的：

class Generate {
    field String str;
    static String str1;
    constructor Generate new(String s) {
        let str = s;
        return this;
    }

    method String getString() {
        return str;
    }
}

class Main {
    function void main() {
        var Generate str;
        let str = Generate.new("this is a test");
        do Output.printString(str.getString());
        return;
    }
}

上面代码的输出结果为：this is a test。

想不想实现这样的一个编译器？

这个编译器出自一本书《计算机系统要素》，它从第 6 章开始，一直到第 11 章讲解了汇编编译器（将汇编语言转换为机器语言）、VM 编译器（将类似于字节码的 VM 语言翻译成汇编语言）、Jack 语言编译器（将高级语言 Jack 翻译成 VM 语言）。每一章都有详细的知识点讲解和实验，只要你一步一步跟着做实验，就能最终实现这样的一个编译器。

如果编译器写完了，最后机器语言在哪执行呢？

这本书已经为你考虑好了，它从第 1 章到第 5 章，一共五章的内容。教你从逻辑门开始，逐步组建出算术逻辑单元 ALU、CPU、内存，最终搭建出一个现代计算机。然后让你用编译器编译出来的程序运行在这台计算机之上。

另外，这本书的第 12 章会教你写操作系统的各种库函数，例如 Math 库（包含各种数学运算）、Keyboard 库（按下键盘是怎么输出到屏幕上的）、内存管理等等。

想看一看全书共 12 章的实验做完之后是怎么样的吗？我这里提供几张这台模拟计算机运行程序的 DEMO GIF，供大家参考参考。

这几张图中的右上角是“计算机”的屏幕，其他部分是“计算机”的堆栈区和指令区。

这本书的所有实验我都已经做完了（每天花 3 小时，两个月就能做完），答案放在我的 github 上，有兴趣的话可以看看。

参考资料

• 《计算机系统要素》