程序语言理论与实现: 编译技术概论
课程介绍与编译技术概论
这个课程使用rescript
进行学习, 主要的学习目标就是实现一个编程语言. 为什么要使用rescript
去学习, 主要是因为rescript
是元语言, 也是ocaml的一种方言; 这个语言并不是一种js类型加强 (例如typescript), 而是选取了一个js的子集进行重写改造, 有着优秀的语法设计并且可以编译出经过性能优化的js代码. 可以说, 它和ts属于2个赛道, 但是做的事情都是一样的, 即在开发中帮助程序员消除js的各种陷阱&添加类型.
为什么要学习编译器和解释器?
- 有意义, 用自己的编程语言去写东西是一个很快乐的事情
- 我们熟悉的编程软件, 比如js, 尽管可能需要了解js的全貌很难, 但是我们可以尝试去了解一个语言的最小实现, 对于学习语言底层会有更帮助一些; 其次我们可以了解每种语言的抽象机制, 即cost, 每个语言都有自己的擅长领域, 比如有些语言号称
zero runtime cost
, 但是它相对在编译中就会产生大量的cost, 比如js就是典型的需要在runtime中有大量cost的语言, 那么我们学习不同的抽象机制, 在遇到js相关疑难杂症, 会更容易我们调试, 比如经典的闭包内存泄漏等等… - 尝试写一些dsl, 比如vue的sfc就是典型的dsl (或者sql), 通过编译技术将模板编译为可供render的数据结构
- 提升个人品味 (装逼)
编译管道
- 从一个字符串
- 到抽象语法树
- 经过类型检查到类型抽象语法树
- 得到多层的IR (中间表示)
- 线性化之后得到一个更低层次的IR
- 代码生成得到机器码
在大家的印象中, 编译器的后端部分都比较重, 反而前端比较“简单”, 其实对于现代语言, 反而前端/中端更重要, 要做更多创新和类型检查, 反而后端变得可以重用了, 压力也很小, 因为可以用LLVM去处理IR, 生成的代码也很高效, 而且容易扩展
后端不“重”指的是现代大多数场景, 如果对于一些计算密集或者神经网络加速的, 会对后端要求比较高
区别几个重要概念
- 编译, 离线的, 在程序运行之前称之为(预)编译时
- (解释)运行, 在线的, 每个程序最终都会有运行时. 包括c/c++, 只不过是在cpu执行的
- 转译器, 从a到b, 它们之前是很相似的, 一般称之为转译
词法解析/语法解析 (前端部分 )
我们从一个简单的文本内容开始, 通过解析会得到一个抽象语法树, 这个是大致的流程; 在这个流程中, 会把文本内容拆解成一个又一个token
, 然后会将一个个token再解析为一个语法句子( 比如空白字符, 注释等等…), 然后就得到了一个抽象语法树.
语法对于语义影响很有限, 但是语法对于用户体验影响很大, 本质上我们只要确定了抽象语法树, 语法的设计只要符合规则即可
语义分析/解析
语义分析是在语法解析之后的步骤, 它依赖于ast, 目的很明确: 确定代码含义; 并且为每个语法带来更多的标注工作, 比如类型检查, 作用域, 在语义分析的步骤中, 可能会导致一些常见的错误
- 类型不正确
- 使用了未定义的变量
在导致一些错误之后, 也会给这个ast添加更多有用的信息, 为下一步处理做准备.
在这里需要提到一个专业名词叫做: type soundness
,指的就是类型系统中的一个性质, 表达了代码中如果存在类型, 那么在运行时就会严格按照类型运行, 不会出现任何错误, 实现了type soundness的语言也很多, 比如ocaml/rescript
我作为一个java黑, java一直以来都有争议说java是type safe, 但是它不属于type sound, 因为如果类型不一样, 它会直接抛出错误, 但是就算再差也比js好.
针对语言的优化
- 模块
- 面向对象
- 模式匹配
- class
- 其他优化
- 多层/单层的IR转译
线性的优化
cpu是一个流水线的架构, 只能理解线性的东西, 所以我们要有一个线性的IR, 这一层主要就是做IR优化, 比如
- 常数折叠
- 常数传播
- …等等编译器优化技术
针对每个平台进行代码生成
首先每个平台的ISA(指令集架构)
都不一样, 那么这里最重要的一个优化点就是寄存器分配
,这样做的目的很简单, 就是将我们常用到的变量都从栈上划分到寄存器上, 这样可以更快的执行, 可以更多的利用计算机资源.
因为寄存器在cpu之上, 由cpu直接控制, 所以比内存通信快, 但是它比内存容量要小, 所以要在程序的不同的地方进行寄存器共享, 这就需要编译器在编译期间进行寄存器分配
我们一般讲栈式虚拟机的时候, 是要把变量放在栈上的, 但是由于栈上的数据访问速度要低于寄存器, 所以我们需要把存储数据放到寄存器中即栈分配到寄存器分配, 这也是我们语言的一个优化; 对于编译器而言, 我们做了寄存器分配, 由于可以安全无冲突的共享数据, 也是编译性能的一个优化.
寄存器分配完成之后, 会做一些指令的调度, 针对不同机器相关优化, 比如说经典的后端优化技术peephole
它通过检查一小段指令序列来查找可以优化的机会, 达到更好的执行效率以及减少代码
之前提到过, 在绝大部分场景下, 编译器的后端技术其实并不需要太多的优化, 除非是神经网络涉及一些计算, 在我们熟知的go语言这一类的编译器, 其实后端并没做太多优化, 因为只要保证语言语义足够静态, 在编写编译器的时候, 又尽可能的用上优化手段, 其实都大差不差.
抽象语法 & 具体语法的区别
现在的编程语言解析过程中都不会牵扯到语义, 抽象语法可以一对多的反射到不同的具体语法的.
抽象语法指的是语言的理论结构, 指的是语句的形式和意义结构, 而具体语法就是我们实际编写的语法. 总之抽象语法是建立在语言基本规则之上, 是一种理论, 而具体语法只是一种用法和实现
比如说git就是内核实现了一套抽象语法, 有很多图形界面工具就实现了一个具体用法, 实际上操作的还是git的抽象语法