【编译原理】第一讲：绪论【笔记】

第一讲：绪论

特别声明：以下内容，源自 大学慕课 《编译原理》哈尔滨工业大学 陈鄞，文章经个人整理所得，仅供学习交流

(一) 什么是编译

(1) 基本概念

先说几个必备的概念

A：机器语言

机器语言是机器能直接识别的程序语言或指令代码，勿需经过翻译，每一操作码在计算机内部都有相应的电路来完成它，或指不经翻译即可为机器直接理解和接受的程序语言或指令代码。机器语言使用绝对地址和绝对操作码。不同的计算机都有各自的机器语言，即指令系统。从使用的角度看，机器语言是最低级的语言。 —— 百度百科

个人理解：

• 从表面形式来看，机器语言就是一堆1和0组成的代码，也就是用二进制代码表达指令，但更确切一点来说，机器语言是由高低电位构成的，指定高电位为1，低电位为0，而我们对电路进行一定的设计后，电路中高低电位的输入输出正好与2进制状态相符，所以我们也就看到了 1、0的那种表现形式
• 计算机能直接理解机器语言，不需要经过任何处理（因为1、0 和其实体电路结构是相关的）
• 如下图中 C706 0000 0002（16进制）C706 代表操作码，0000 0002 代表操作数 代表赋值语句 X = 2
• 补充：为了简化二进制，照顾人的易读性所以用十六进制来表示（0~9和a~f），机器可不能直接识别十六进制数，计算机内部的一切信息的存取以及传输还都是以二进制形式进行的

疑问：实际情况下，我们直接用二进制进行描述一些程序等是非常麻烦的，那为什么不直接转换成容易理解的十进制呢？然后运行的时候再转为二进制呢？而出现了八进制或者十六进制这样的概念

答案：首先直接使用二进制当然是比较麻烦的，枯燥，且很长很长，所以转换成一些更高的进制，就可以大幅度缩小长度，而十进制描述虽然符合人的行为习惯，容易被人接受，但是直接与计算机结构关联却有一些不太合适，而八进制或者十六进制分别是 2^3 以及 2^4 这一点使得，进制之间的转换会比较容易，同时8位二进制数为一个字节，而两位十六进制刚好可以表示一个字节，例如，F1 对应二进制为 11110001，同样可以看到，每一位十六进制数，也转换成了四位二进制数

B：汇编语言

汇编语言（assembly language）是一种用于电子计算机、微处理器、微控制器或其他可编程器件的低级语言，亦称为符号语言。在汇编语言中，用助记符代替机器指令的操作码，用地址符号或标号代替指令或操作数的地址。在不同的设备中，汇编语言对应着不同的机器语言指令集，通过汇编过程转换成机器指令。特定的汇编语言和特定的机器语言指令集是一一对应的，不同平台之间不可直接移植。[1] —— 百度百科

简单概括：低级，不具有移植性，能直接访问计算机硬件，效率高，占用资源少，同时使用助记符（Memoni）代替操作码，用地址符号（Symbol）或标号（Label）代替地址码。如上图的MOV X,2 同样代表赋值语句 X = 2

C：高级语言

高级编程语言（High-level programming language）是高度封装了的编程语言，与低级语言相对。它是以人类的日常语言为基础的一种编程语言，使用一般人易于接受的文字来表示，有较高的可读性，以方便对电脑认知较浅的人亦可以大概明白其内容。 —— 维基百科

这没什么好说的，就日常编程所做的，x = 2

Em 铺垫好像是长了点哈

从上图可知，内容经过编译这个过程以后，从高级转换到低级的形式（从人乐意看的内容转换成机器乐意看的内容）

编译的定义：将高级语言（源语言）翻译成汇编语言或机器语言（目标语言）的过程

(2) 编译器在语言处理系统中的位置

前面我们说了编译的一个基本概念，而为了建立可执行的目标程序，除了编译器外，我们还需要一些其他的程序进行配合，下图就是一个语言处理的基本过程，注意留意编译器所处的位置

简单介绍一下流程中的内容

A：预处理器（Preprocessor）

• 一个源程序可能分成几个模块存放在不同的文件里，将这些源程序汇集在一起的任务，这时候就需要预处理器把存储在不同文件中的源程序聚合在一起
• 把称为宏的缩写语句转换为原始语句

B：编译器（Compiler）

• 将高级语言翻译成汇编语言或机器语言

C：汇编器（Assembler）

• 将汇编语言翻译成可重定位的机器语言
• 若在编译器阶段已经直接将高级语言翻译成机器语言，则可以省略汇编器
• 可重定位（Relocatable）/ 可再装配：数据在内存存放的起始位置 L 不是固定的，起始位置 + 相对地址 = 绝对地址

D：加载器（Loader）

• 修改可重定位地址
• 将修改后的指令和数据放到内存中适当的位置

E：链接器（Linker）

• 将多个可重定位的机器代码文件（包括库文件）连接到一起
• 解决外部内存地址问题

(二) 编译系统结构

(1) 结构概述

A：前端（fornt end）

与源语言相关，字符流——词法分析器——词法单元流——语法分析器——语法树——语义分析器——语法树——中间代码生成器

B：后端（back end）

与目标语言相关，中间表示形式 ——机器无关代码优化器——中间表示形式——目标代码生成器——目标机器语言——机器相关代码优化器——目标机器语言

上述字体加粗的为后端部分

(三) 词法分析概述

(1) 基本概念

从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型，将识别出的单词转换成统一的机内表示——此法单元（token）形式

token：<种别码，属性值>

(2) 例题一

种别码本身应该是一个整数，为了上例中为了直观，使用了宏定义的形式

• WHILE：表示 while ，关键字，一词一码
• IDN（identify）：表示标识符，第一个分量全为IDN，第二个分量为其字面值以互相区分
• NE（not equal）：表示不等，运算符，一词一码或一型一码
• CONST：表示常量，一型一码
• SLP、SRP、LP、RP：分别表示左右小括号以及左右花括号，界限符， 一词一码
• INC：表示 自增 ++ 运算符，一词一码或一型一码
• SEMI：表示 分号 ；界限符，一词一码

(四) 语法分析概述

(1) 基本概念

语法分析器(parser)从词法分析器输出的token序列中识别出各类短语，并依据这些规则所体现出的语言构造的层次性，用各记号的第一元建成一种树形的中间表示

(2) 例题一：赋值语句的分析树

从下往上看，一个标识符 rete * 一个数字60 组成了一个新的表达式，而它又 + 另一个标识符 initial 组成了一个更大的表达式，接着通过 = 与标识符 postion 组成了最终的赋值语句

(3) 例题二：变量声明语句的分析树

D：declaration（声明）

T：type（类型 ）

IDS：identifiers sequence（标识符序列）

文法在图片中有提到，即 ① 声明 = 类型 + 标识符序列 + ; ② 类型 = int 或 real 或 char 或bool ③ 一个标识符 id 本身 可以构成一个标识符序列，一个标识符序列 + , + 标识符 id 可以构成一个更大的标识符序列

这样一看这个图就很直观了

(五) 语义分析概述

(1) 收集标识符的属性信息

A：种属（Kind）

简单变量、符合变量（数组、记录 …）、过程、…

B：类型（Type）

整型、实型、字符型、布尔型、指针型、…

C：存储位置、长度

一个例子就明白了：

例如，创建一个实型数组x ，所以其相对地址为 0 ，其含有 8个元素，同时假设一个实型变量占用 8 个字节，这个数组占据了0-63的地址 ，所以下一个 整型变量 i 只能从 64 开始，而假设一个整型变量占用 4 个字节，j 就需要从64 + 4，68开始

D：值

E：作用域

F：参数和返回值信息

参数个数、参数类型、参数传递方式、返回值类型

总结：符号表

这些收集到的标记符属性信息，都会被存放到一个叫做符号表的数据结构中，其中有着例如 TYPE、KIND 等多种属性，同时符号表通常带有一个字符串表如下图

NAME = 标识符在字符串表中的起始位置 + 长度

(2) 语义检查

• 变量或过程未经声明就使用
• 变量或过程名重复声明
• 运算分量类型不匹配
• 操作符与操作数之间的类型不匹配
• 数组下标不是整数
• 对非数组变量使用数组访问操作符
• 对非过程名使用过程调用操作符
• 过程调用的参数类型或数目不匹配
• 函数返回类型有误

(六) 中间代码生成

中间代码生成：经过语法分析和语义分析后，许多编译器为源程序产生更低级的显示中间表示，可以理解为一种抽象的程序

(1) 常用的中间表示形式

三地址码 (Three-address Code) （在这里进行简单介绍）

• 三地址码由类似于汇编语言的指令序列组成，
• 每个指令最多有三个操作数(operand)

语法结构树/语法树 (Syntax Trees)（后面详细讲，这里不涉及）

(2) 常用的三地址指令

• x = y op z ：op 是一个二元运算符，y 和 z 是两个运算分量的地址，x 是运算结果的存放地址
• x = op y：op 在这里是一个一元运算符，因此只有两个操作数 x y
• x = y ：也只有两个操作数
• if x relop y goto n ：如果 x 和 y 满足 relop 关系，就跳转到 n 对应的指令
• goto n：直接跳转到 n 对应的指令
• param x：将 x 设置为参数
• call p,n：p 是过程的名字，n 是过程的个数
• return：跳转到地址 x 对应的指令
• x = y[i]：y 表示数组的名字，即基地址，i 是数组元素的偏移地址，不是下标
• x[i] = y：将一个变量的值赋值给数组元素
• 最后三个：与指针相关的指令

(3) 三地址指令的表示

• 四元式 (Quadruples)（下面提一下这个）
• (op, y, z, x)
• 三元式 (Triples)
• 间接三元式 (Indirect triples)

(4) 中间代码生成的例子

说明一下，右边，冒号左边的数字代表指令的编号，例子中从100取到112，j 代表 jump

如何看这个程序做了什么呢，例如第一行：100:(j<,a,b,102) 就是说，当 a < b 的时候 跳转到 102 指令，若不满足就继续执行 101 指令，找这种方式，对应着代码看，这个例子是非常直观的

(七) 目标代码生成

• 目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言
• 目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器

(八) 机器无关/有关优化器

代码优化

• 为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些，或者二者兼顾

(九) 整点题目练练手

① 编译是对( ) 【正确答案：C】

• A：机器语言的执行
• B：汇编语言的翻译
• C：高级语言的翻译
• D：高级语言程序的解释执行

② 用高级语言编写的程序经编译后产生的程序叫( ) 【正确答案：B】

• A：源程序
• B：目标程序
• C：连接程序
• D：解释程序

③ ( )不是编译程序的组成部分 【正确答案：C】

• A：词法分析程序
• B：代码生成程序
• C：设备管理程序
• D：语法分析程序

④ 源程序是句子的集合，( )可以较好地反映句子的结构 【正确答案：B】

• A：线性表
• B：树
• C：完全图
• D：堆栈

⑤ 编译程序是一种( ) 【正确答案：B】

• A：汇编程序
• B：翻译程序
• C：解释程序
• D：目标程序

⑥ 按逻辑上划分，编译程序第三步工作是( ) 【正确答案：A】

• A：语义分析
• B：词法分析
• C：语法分析
• D：代码生成

⑦ 编译程序中语法分析器接收以( )为单位的输入 【正确答案：A】

• A：单词
• B：表达式
• C：产生式
• D：句子

⑧ 编译过程中，语法分析器的任务就是( ) 【正确答案：B】

• A：分析单词是怎样构成的
• B：分析单词串是如何构成语句和声明的
• C：分析语句和声明是如何构成程序的
• D：分析程序的结构

⑨ 语法分析时所依据的是( ) 【正确答案：A】

• A：语法规则
• B：词法规则
• C：语义规则
• D：等价变换规则

总结

绪论部分的知识比较少，主要是对编译原理的基本知识进行了一定的总结概括，以及一些基本知识的入门，让我们对编译有一个初步的概念，更加详细的课程在后面的章节，后面再更新，最近在忙着写一些东西，可能更新文章会慢一些，希望大家见谅，再次感谢大家的支持，谢谢！！！