Yao

V1

2022/12/18阅读:19主题:红绯

编译原理

知乎上有一种说法是「编译器、图形学、操作系统是程序员的三大浪漫」。

计算机很笨,它只认识 0 和 1,也只会运行最简单的机器指令,而我们平时写的代码大多都属于高级语言。高级语言编写的指令要想在计算机上执行,需要将高级语言转换成计算机识别的机器语言。编译器就是将高级语言转换成机器语言的一款软件。

一个完整的编译器将源码编译成目标机器指令主要包含以下几个步骤。

词法分析

词法分析从左到右扫描源程序的字符,识别出每个单词,并组成词素(源代码中的一个字符串,比如一个变量名,一个运算符,都会被识别为一个词素。)。对于每个词素,词法分析会把它解析成一个词法单元。这个词法单元被称为 Token。Token 的形式一般为

〈token-name, attribute-value〉
  • token-name: 单词的类别

程序中的单词大体可以分成五类:

  • attribute-value: 指向符号表中关于这个词法单元的条目。符号表条目的信息会被语义分析和代码生成步骤使用

什么是符号表?

编译器的重要功能之一是记录源程序中使用的变量的名字,并收集和每个名字的各种属性有关的信息。这些属性可以提供一个名字的存储分配、类型、作用域等信息。对于过程名字,这些信息还包括:它的参数数量和类型、每个参数的传递方法及返回类型。

符号表数据结构为每个变量名字创建了一个记录条目。记录的字段就是名字的各个属性。这个数据结构应该允许编译器迅速查找到每个名字的记录,并向记录中快速存放和获取记录中的数据。

比如,对于赋值语句position = initial + 2 * 60

position是一个词素,被映射成词法单元<id, 1>,其中 id 是表示标识符(identifier)的抽象符号,而 1 指向符号表中 position 对应的条目。

赋值符号=是一个词素,被映射成词法单元<=>,因为这个词法单元不需要属性值,所以省略了第二个分量。

整条语句被词法分析后的结果可以表示为
<id, 1> <=> <id, 2> <+> <2> <*> <60>

语法分析

语法分析对词法分析中扫描的 Token 进行分析,并产生语法树,这棵树被称为 AST 抽象语法树。整个分析过程采用的是上下文无关语法(Context-free Grammar)。

简单来说,语法分析生成的树是以表达式为节点的树。

比如,对于赋值语句position = initial + 2 * 60,经过语法分析后生成的数

语义分析

语义分析利用前面生成的语法树和符号表来检查源程序是否符合语言定义。同时收集类型信息,以便在代码生成过程中使用。

语义分析的一个重要作用就是类型检查,编译器检查每一个运算符是否具有合法的运算分量。另外对于某些语言允许自动类型转换,编译器需要根据自动类型转换规则,对数据类型进行转换。

语义分析结束以后,整个语法树的表达式都被标识了类型,如果有些类型需要做隐式转换的,在分析完后会在语法书树上插入相应的转换节点。

比如position = initial + 2 * 60 经过语义分析后

语义分析同时还会对更新符号表里的符号类型。

中间语言生成

在经过语义分析后。大多数的编译器不会直接生成目标代码,一般会生成一个抽象于平台的中间语言(Intermediate Representation,简称 IR ),该中间语言与机器无关。

先生成中间代码一方面可以增加编译器的模块化、可移植性和可扩展性。中间代码既独立于任何高级语言,也独立于任何目标机器架构,这样可以开发出适应广泛高级语言的编译器。

另一方面,也可以做一些与机器无关的优化操作。

中间语言有很多种,在不同的编译器中可能也会有不同的表达形式。常用的方式有三地址码、P-代码等。

拿三地址码来举例,基本的三地址码是这样的x = y op z,表示将变量y和z操作后赋值给x,op既可以是算术运算也可以是其他的操作。 position = initial + 2 * 60 被三地址成三地址码

t1 = 2 * 60
t2 = initial + t1
position  = t2

中间代码优化

中间代码优化的主要是做一些于底层机器无关的优化,比如消除死代码,函数内联优化,for 循环展开等优化。这一步输入的是中间代码IR,输出的也是中间代码IR。

position = initial + 2 * 60 被翻译成中间语言后,t1 = 2 * 60 是可以在生成目标代码之前计算出来的,t2 = initial + t1 中的t1也是可以直接被替换成值的。 经过优化后的中间代码

t2 = initial + 120
position  = t2

目标代码生成

目标代码生成的工作是将中间代码转换成目标机器代码,这个过程十分依赖目标机器,因为不同的机器有着不同的字长、寄存器、数据类型等等,需要生成不同的机器代码。

现在编译器有着异常复杂的机构,因为现代高级语言本身非常的复杂,像C++编译器,至今也没有一个编译器能够完整的支持C++标准所规定的所有语言特性。 那么作为一个高级语言的使用者,为什么要学习编译原理呢?这里引用《三体》中的一段话结束。

成吉思汗的骑兵,攻击速度与二十世纪的装甲部队相当;北宋的床弩,射程达一千五百米,与二十世纪的狙击步枪差不多;但这些仍不过是古代的骑兵与弓弩而已,不可能与现代力量抗衡。基础理论决定一切,未来史学派清楚地看到了这一点。而你们,却被回光返照的低级技术蒙住了眼睛。

分类:

后端

标签:

后端

作者介绍

Yao
V1