Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

编译原理

一、基础知识

1. 编译器在语言处理中的位置

语言分类：机器语言 – 汇编语言 – 高级语言

汇编语言、高级语言都需要翻译成机器语言后才能给计算机使用。

机器语言：计算机能够直接立即的语言，完全是01串构成，eg：C706 0000 0002。难读难写

汇编语言：引入助记符，更加直观，eg：MOV X, 2。需要依赖特定的机器，且需要记忆相关指令，对于非计算机专业人员使用受限制，而且编写效率很低，简单的功能也需要很多指令才能实现

高级语言：类似于数学定义或者自然语言的简洁形式，eg：x = 2。编写效率高，不依赖特定机器，更接近人的表达习惯。

高级语言 –编译–> 汇编语言 –汇编–> 机器语言

高级语言 –编译–> 机器语言

编译器在语言处理中的位置：

如图是源程序变成目标程序的整个步骤：

先经过预处理器：源程序 –> 经过预处理器的源程序

预处理器就是负责将存放在不同文件中的源程序聚合在一起，eg：c语言中的 include，在这一步就会将 include 的文件导进来

将被成为宏的缩写语句转换为原始语句，eg:c语言中的#define NUM 2，会在这一步将所有的宏定义全部转换为具体的值，即所有涉及 NUM 的位置都被替换成 2。
经过编译器：预处理的源程序 –> 汇编语言程序
经过汇编器：汇编语言程序 –> 可重定位的机器代码

可重定位就是，在内存中存放的起始位置L是不固定的，相应的代码中的所有地址都是相对位置（相对于L）
经过加载器/链接器：可重定位的机器代码 –> 目标机器代码

加载器能够修改可重定位的地址，将修改后的指令和数据存放到内存中的适当位置——获得了绝对地址

链接器能够将多个可重定位的机器代码文件连接到一起（针对大型软件来说）；也可以解决外部内存地址问题，一个文件引用了另外一个文件的数据，这个数据的地址对于本文件来说就是外部内存地址，而这个需要链接器来处理。

2. 编译器的结构

主要由几个阶段（phrase）构成：词法分析、语法分析、语义分析、中间代码生成、目标代码生成、代码优化

词法分析：类似于分析每个单词的词性

语法分析：根据语法，去获得每个单词在句子中的类型，是主、谓、宾、定、状、补中哪个类型

语义分析：获得该语句的含义

如下图：上面大块就是分析部分/前端，是与源语言相关，下面大块就是综合部分/后端，与目标语言相关；中间表示是独立的，起到一个桥梁作用

（代码看成是字符流，所有的数据和变量、关键字都是字符构成的）

3. 词法分析

词法分析的主要任务：从左向右逐行扫描源程序的字符，识别出各个单词，确定单词类型。将识别出的单词转换成统一的机内表示——词法单元形式：

token: <种别码, 属性值>

不同的单词类型，有不同的编码，如下图显示：

有一词一码：每个单词对应不同的种别码，eg: while——是关键字，对应一个种别码 WHILE；

也有多词一码：不同的单词对应同一个种别码，eg: num——是变量名，对应一个种别码 var， temp——是变量名，对应同一个种别码 var；

一型一码：一种类型的单词对应同一个种别码，eg：100——是整型常量，对应一个种别码 CONST，1——也是整型常量，对应同一个种别码 CONST。

如下图：举例：

4. 语法分析

是从词法分析器输出的token序列中，识别出各类短语，并构造语法分析树（parse tree）

语法分析树描述了句子的语法结构。

如下图，是一个赋值语句经过词法分析器后输出的结果。

然后将其构造成了一个棵语法分析树：

语法分析概述：

例如一个声明语句的文法是：

如下图：解释就是：一个声明语句（define）由类型（type）+标识符序列（identifications）。

其中类型可以是int or real or char or bool，而标识符序列可以由标识符本身 or 标识符序列与逗号（涉及到了递归定义）

举例：

int a, b, c;

5. 语义分析

语义分析的主要任务：

收集标识符的属性信息
- 标识符的种属（kind）：标识符是简单变量 or 复合变量（数组、记录等）or 过程….
- 类型（type）：标识符是整型、实型、字符型、布尔型、指针型
- 存储的位置（location）：存储的位置、长度
- 值（value）
- 作用域
- 参数和返回值信息：参数个数、参数类型、参数传递方式、返回值类型
  
  最后构成了如下的表：符号表+字符串表（字符串表用来存放该标识符的名字，对应符号表中name存放的是标识符在字符串表中的位置）
  
  每个标识符都会对应一条记录，每个字段都代表着标识符的一个属性
  
  （字符串表的作用是：由于标识符名字不定长，所以为了统一，且这样方便查找）
语义检查
- 变量或者过程未经声明就使用
- 变量或者过程名重复声明
- 运算分量类型不匹配：看是否需要强转 or 无法相加
- 操作符与操作数之间的类型不匹配
  - 数组下标不是整数
  - 非数组变量使用数组访问操作符
  - 非过程名使用过程调用操作符（过程：函数）
  - 过程调用的参数类型或数目不匹配
  - 函数返回类型有误
6. 中间代码生成和编译器后端
中间表示形式：三地址码/语法结构树（syntax tree）——语法分析树（parse tree）是不同的

三地址码：类似于汇编语言的指令序列构成，每个指令最多有3个操作数

常用的三地址指令：

地址可以表示为：源程序中的名字（通过符号表可以直接搜到地址）、常量、编译器生成的临时变量

三地址指针的表示：
- 四元式：(op, y, z, x)——操作符，操作数1，操作数2，结果
- 三元式
- 间接三元式
目标代码生成：根据获得的中间表示形式作为输入，并映射到目标语言；还有一个任务就是为成程序中使用的变量合理分配寄存器。

代码优化：是为了改进代码所作的等价程序变换，使得运行的更快一些、占用空间更少一些

一个是对中间表示形式的优化——机器无关代码优化器；一个是对目标语言的优化——机器相关代码优化器

二、语言及其文法

1. 字母表

注意：字母表是一个有穷符号集合，而符号可以是各种类型的

字母表的运算：

$\varepsilon$表示空串里面没有一个符号

（黄色句子的理解：n次幂，就说明该字母表自身乘了n次，那么该集合中的每个元素都有n长度，那么该集合也就是由很多个n长度的符号串构成的集合）ps：如果字母表的元素个数为m，那么n次幂的集合有$m^n$个元素

正闭包就是包含了字母表1~n次幂的集合的并集，所以里面的每个元素长度都是正数

串的概念：在$\sum^*$上的定义是字母表中符号的一个有穷序列

串的长度：$|s|$ 就是指串中的符号个数 eg: $|aab| = 3$

2. 文法定义

语言的基本符号：未用尖括号括起来的部分，在单词的文法中就是指字母；在句子的文法中就是指单词

语法成分：尖括号括起来的部分，在单词的文法中就是指<动词>、<名词>、<形容词>等

文法的形式化定义：

一个四元组构成了文法

终结符集合：——基本符号，即从终结符不能再推导出其他的符号了（就是句子文法中的单词就是终结符集合）

非终结符集合：——语法成分

（由于可以从该语法成分中推导出更多的成分，所以称为非终结符）

终结符和非终结符的区别和关系：

两者不相交、并集就构成就构成了文法符号集

产生式集合：即用来产生串的式子，就是告知如何能产生一个串

举例：

开始符号：句子中的最大语法成分

举例：

产生式的简写：——有相同左边的产生式可以写在同一行中，中间用竖线相隔

符号约定：

终结符约定：

非终结符约定：

其他规定：

总结：

3. 语言的定义

问题引出：前面定义了一个句子的文法，那么有了文法（语言规则），如何判定一个词串是否是满足该文法的句子

推导

总结就是：产生式的右部推导出产生式的左部

形象的描述就是：$a_0$经过n步推导出$a_n$

$n=1$时，即$a_0 \Rightarrow a_1$——为一步推导

$n=0$时，即$a_0 \Rightarrow a_0$——没有推导
规约

总结为：用产生式的左部来规约产生式的右部

举例：

所以，如何判断一个字符串是满足规定文法的句子：
- 从句子推导：即从句子的文法推导出字符串——从生成语言的角度
- 从句子规约：即从字符串推导到文法——从识别语言的角度
=> 都是根据规则推出的

句子和句型

注意区别：句型可以包含终结符，也可以包含非终结符，也可能是空串

从开始符号（文法中最大的语法成分）经过若干步变成了终结符号串，那么就变成了句子，所以句子，意味着不包含非终结符的句型

举例：

4. 语言的形式化定义

问题：

是无穷多个

所以文法能够解决，无穷语言的有穷定义

问题：

如下图的文法，描述了什么内容？

D是数字，L是字母，T是字母、数字、数字字母构成的字符串，所以S是单个字母或者首字母+字母数字串——标识符的构成文法

5. 语言上的运算

语言是一个集合，那么就可以进行一定的计算

那么标识符也可以如下表示：

6. 文法的分类

Chomsky文法分类体系

0型文法（Type-0 Grammar）

没有任何限制，只需要$\alpha$至少包含一个非终结符
1型文法

$\alpha$至少要包含一个非终结符，且产生式的左侧字符的个数不能比右侧的多

称为上下文有关文法，因为只有当非终结符的上下文为$\alpha_1,\alpha_2$是，才能进行替换

证明：上下文有关语法的产生式右部不存在空串$\varepsilon$

假设右侧为$\varepsilon$，即右侧为空，那么左侧也为空。而又要求了左侧至少包含一个非终结符，所以与前提相悖，命题得证
2型文法

$\alpha$至少要包含一个非终结符，且产生式的左侧字符的个数不能比右侧的多，且左侧都是非终结符

语言：

举例：

标识符的文法——也是一个上下文呢无关文法
3型文法

即在P的所有产生式中：固定一种模式：

右线性文法：终结符号串+非终结符号串 or 终结符号串

左线性文法：非终结符号串+终结符号串 or 终结符号串

语言：

举例：都是标识符的文法

左线性文法：

$S \rightarrow La|Lb|Lc|Ld|L0|L1|L2|L3|L4$

$L \rightarrow La|Lb|Lc|Ld|L0|L1|L2|L3|L4$

$L \rightarrow a|b|c|d$

四种文法之间的关系