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

谭光志 2020-11-10 15:10:47
javascript 实战 原理 编译 入门


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

例如 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
依次类推,接下来的顺序为 mulExpressionterm1(integerConstant)、+(op)、mulExpressionterm2(integerConstant)、*(op)、mulExpressionterm3(integerConstant)。

如下图所示:

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

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 上,有兴趣的话可以看看。

参考资料

版权声明
本文为[谭光志]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000037786459

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云