编译原理 13007
2024-03-29 01:06:05 0 举报AI智能生成
编译原理 13007 是一个关于编译原理的课程，旨在深入研究计算机科学中的编译技术。课程涵盖了编译器设计、词法分析、语法分析、语义分析、代码生成、优化技术等方面。学生将学习如何将高级编程语言转换为机器语言，并深入了解编译器的内部工作原理。通过本课程，学生将具备设计和实现编译器的基础知识，为未来的计算机科学研究或相关领域工作奠定基础。
作者其他创作
大纲/内容
确定中间代码的形式
表示高级语言的语义
确定翻译方法
解决三个问题
声明语句
可执行语句
高级语言的语句有两类
便于进行与机器无关的代码优化工作
使编译程序改变目标机更容易
使编译程序的结构在逻辑上更为简单、明确
生成中间代码的好处有
1、中间代码生成概述
如果遇到操作数，则将操作数入栈；
如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作 数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈；
遍历完成后，栈内只有一个元素，该元素即为逆波兰表达式的值
操作
tokens = [\"10\
输入
22
输出
该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
解释
1、逆波兰式
x = y op z 将y和z的运算结果存放到x中
x =op z 此时op是单目运算符，对z进行指定操作，结果存放到x中
x = y 将y的值赋给x
无条件转移 goto L
条件转移 if x rop y goto L 此时rop是关系运算符，如x和y满足关系，则跳转
常用的三地址代码有
（op，arg1，arg2）
将 a=b*c+b*d用三元形式
记录结构
三元式
（op，arg1，arg2，result）
op为运算符；result存放运算结果；arg为运算对象，如果为空，则使用空格，留出位置
t1 = b*c
t2 = b*d
t3 =t1+t2
a = t3
写成三地址码的赋值语句形式
写成四元形式
将 a=b*c+b*d用四元式形式
四元式
2、三地址代码
5+1*12
3、抽象语法树
a:b*(-c)+b*(-c)
4、有向无环图表示
2、中间代码
1、属性文法
综合属性用于自下而上传递信息，继承属性用于自上而下传递信息。
说明表达式3*5+4#的求值过程
计算
综合属性
终结符只有综合属性；非终结符有综合属性，也可以有继承属性。
c语言中标识符的属性文法定义
继承属性
2、属性
构造语法树，在语法树的各结点处按语义规则进行属性计算。
3、属性的计算顺序
翻译模式
S-属性文法的自下而上的翻译
L-属性文法的自上而下的翻译
4、语法制导翻译的实现方法
3、属性文法和语法制导的翻译
<常量声明>->const<常量类型><常量声明表>
常量声明语句
<变量声明>-><变量类型><变量声明表>
变量声明语句
<函数声明>-><函数类型><标识符>
函数声明语句
1、声明语句的语义处理
所有表达式都是赋值表达式
有算术表达式、布尔表达式等
2、表达式的翻译
布尔表达式的基本概念
布尔量的语义处理
布尔表达式的优化
布尔表达式的语义处理
3、布尔表达式的翻译
if语句的翻译
do...while语句的翻译
for语句的翻译
4、控制语句的翻译
函数定义
函数调用过程
函数调用的翻译
5、函数定义及函数调用的翻译
4、常见语句的语法制导的翻译
带类型的简单变量声明、常量声明
各种表达式：算术表达式、布尔表达式、关系表达式、赋值表达式
简单赋值语句
各种控制语句
函数声明、函数定义和函数调用
Sample语言的语法成分包括
5、中间代码生成器的设计
第五章 中间代码生成
代码区一般位于存储器的低端，该区域所有代码的逻辑地址都可以计算出来，所有函数或过 程的入口地址都是已知的。
代码区线性存放目标指令序列，当前执行的指令位置由指针IP指示，如果IP指向程序的第一 条指令，程序便开始执行，以后每执行一条，IP+1，遇到跳转指令，则将转移地址赋给IP
代码区
程序的某些数据对象的大小是已知的，可以静态分配到固定位置，如全局变量、静态数据
静态数据区
动态数据区可用栈和堆的方式组织，栈用于分配符合后进先出原则的数据，堆用于其他数据
栈和堆被放在剩余地址空间的两端，栈向较低地址方向增长，堆向较高地址方向增长
有的语言可以显示分配和回收数据对象占用的空间，如C的malloc()和free()
有的语言可以检测出无用的数据元素看做垃圾，进行自动回收
动态数据区
1、程序执行时存储器的划分
为了管理一个函数在一次执行中所需的全部信息 ，将它们放在一块连续的存储区中，称为活动记 录
局部变量和常数、临时变量、形式参数、 返回地址、保护区
2、活动记录
3、局部数据布局
1、存储组织
又称为子程序或过程
1、源程序中的函数
2、函数执行时的活动
3、名字的作用域
把实参地址传递给形参
每个形参都有一个相应单元，称为形式单元，用来存放实参地址
如果实参是常数或表达式，先将值计算出来，然后存放到临时地址
值地址
得结果，每个形参对应两个单元，一个存放实参地址，一个存放实参的值
传值，是一种最简单的参数传递
传名，是一种替换规则
4、参数的传递
函数的定义
名字的申明
申明的作用域
静态概念
函数的活动
名字的绑定
绑定的生命期
动态概念
5、名字的绑定
2、函数调用
数据对象大小和在内存中位置必须已知
一个过程的所有活动使用同一个局部名字绑定，所以不允许递归
数据结构不能动态建立
局限性
1、静态存储分配
定义函数的活动记录首地址BP和活动记录栈顶SP
向各连接数据单元填入实际内容
计算可变数组占用空间
在函数调用前
2、栈式存储分配
定长块管理
最先匹配法
最佳匹配法
最差匹配法
分配策略
变长块管理
实现
3、堆式存储分配
3、存储分配策略
对象分配
参数传递和返回值
此时u原来的引用会丢失，如果这是原来引用的最后一个引用，那么会出现垃圾
引用赋值
过程返回
集合操作
1、可达性
回收一个对象可能对其他对象的计数器-1，当回收计数为零的对象时，很难回收产生 循环指向的数据结构对象
开销比较大，引用计数器需要频繁修改
缺陷
垃圾能够被及时回收，空间使用相对低
以增量方式完成，运算分布在程序运行整个过程
优势
2、引用计数回收器
Free 保存已知的空闲对象，表示可以被分配
Unscanned 保存已经确定可达但还未被扫描的对象
Reached 表明该对象并未确定是否可达
Scanned 表示该对象已经被扫描
状态
3、标记-清扫回收器
空间一分为二
4、复制回收器
4、垃圾回收机制
通过CPU的三个寄存器IP/BP和SP来实现对程序执行过程的控制。 IP指向要执行的指令，BP和SP是基址寄存器和栈指针。BP指向栈底，SP指向栈顶。
1、内存的划分及程序执行的总体情况
2、案例： 程序运行时内存的变化
5、C语言编译程序运行时存储实例
第六章 运行时存储组织
目的：节省时间和空间
与机器无关的优化--对中间代码进行
依赖于机器的优化--对目标代码进行
按阶段分
局部优化:(基本块)
循环优化:对循环中的代码进行优化
全局优化:大范围的优化
程序范围分
等价原则：不改变运行结果
有效原则：优化后时间更短，占用空间更少
合算原则：应用较低的代价取得较好的优化效果
优化的原则
1、代码优化的地位
是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其 第一个语句，出口是其最后一个语句
基本块
首先确定入口语句
划分基本块的算法
快速排序程序
2、基本块的概念及流图
1、代码优化概述
删除公共子表达式
删除无用赋值
合并已知量
对临时变量 改名
对语句变换位置
代数变换等
基本块内可以进行的优化
1、删除公共子表达式
2、复写传播
3、删除无用代码
强度削弱
代数变换
4、代数恒等变换
5、基本块的DAG表示及优化
2、局部优化
循环的查找算法
回边
1、循环的定义
2、循环外提
3、强度削弱
4、删除归纳变量
3、循环优化
第七章代码优化
中间代码：后缀式，三地址代码，四元式
符号表中的项：名字，类型，嵌套深度，偏移量
目标代码：绝对机器代码，可重定位代码，汇编
各种代码的形式
要充分发挥目标机器的能力：充分利用目标机器的资源
指令地址的决定
指令选择
寄存器分配
计算次序选择
存储管理
代码生成器固有的问题
机器描述
可移植的代码生成器
偏移量
作用域
决定中间代码中名字所代表的数据对象的运行地址
可能在动态时刻作为调试信息存在
符号表信息
代码生成的很多技术是可以用于不同的中间代码
代码生成前，中间代码记录了足够详细的程序信息
中间代码
代码生成器的输入
可以放在内存中固定地方，并立即执行
小程序、需要迅速编译和执行
绝对机器语言
程序可以分为多个目标模块，分别编译
需要连接装配器将一组可重定位模块一起装入执行
需要额外的开销，但灵活：可分别编译子程序和从目标模块中调用其它先前编译好的程序模块
如果目标机器不能自动处理重定位，则编译器必须提供显式的重定位信息给装配程序
可重定位的机器语言
代码生成的过程容易
避免了重复汇编器的工作
汇编语言
代码生成器的输出：目标程序
把程序中的名字映射到运行时的目标对象的地址是由前端和代码生成器共同完成的 语言中过程的语义决定了运行时刻名字如何与存储空间相联系
记录了名字在过程数据区的相对地址
所需要的存储空间
对名字的引用通过符号表
运行时活动记录的分配和释放作为过程调用和返回序列的一部分
运行时活动记录的管理
存储管理分静态、栈式和堆式存储分配
通过一个计数器决定每个指令的地址
i出现在j之前，目标地址是i对应的三地址代码的第一条指令地址
如果i小于j
i出现在j之后，目标地址此时不可知，可以利用回填的技术解决
如果i大于j
标号的处理：j: goto i /*j是当前语句的号码*/
目标机器指令系统的性质决定了指令选择的难易程度
指令系统的一致性和完整性是重要因素
指令的速度和机器的特点是另一些重要的因素
代码的质量取决于它的执行速度和长度
寄存器分配：为程序的某一点选择驻留在寄存器中的一组变量
寄存器指派：挑出变量将要驻留的具体寄存器
寄存器使用的两个子问题
计算执行的次序会影响目标代码的效率
选择最佳次序是一个NP完全问题
正确的代码：最重要的目标
易于实现、调试和维护
代码生成器的目的
流信息
依赖信息
代码生成需要多方面的信息
代码生成的途径
1、概述
1、80x86体系结构
标志寄存器
2、80x86中的寄存器
数据传送指令（MOV）
算术逻辑运算指令（ADD，SUB，MUL，DIV，AND，OR，CMP等）
控制转移指令（无条件跳转、条件跳转、函数调用和返回）
三类指令
3、80x86指令系统介绍
2、目标机及指令系统简介
3、一个简单的代码生成器
尽可能留
尽可能用
及时腾空
考虑三个方面
计算变量的引用信息和活跃信息
算法
1、引用信息和活跃信息
寄存器的分配和指派
原则
生成存数指令
2、寄存器描述和地址描述
3、基本块的代码生成
4、基本块的代码生成器
5、从DAG生成目标代码
1、目标代码生成器的结构
2、汇编指令的选择
3、构成完整的汇编语言程序
6、代码优化及目标代码生成器的设计
第八章目标代码生成
40-50年代：机器语言
60年代：C语言
70年代：C++，VB等
90年代：Java，PHP，JavaScript等
1、程序设计语言的发展
2、翻译程序大家族
编译方式
解释方式
3、高级语言的运行方式
工作结果上，编译是源程序的某机器语言，而解释是源程序的执行结果。
执行次数上，编译可以执行多次，解释只能执行一次。
通用性上，很多脚本语言都是解释执行的。
处理时间上，编译时源程序和数据是不同时间，解释是同时。
执行速度上，编译更快。
区别
1、程序设计语言及翻译程序
预处理器执行删除注释、宏扩展、文件包含。这 些命令在编译过程的第一步执行。
预处理
编译器可以提高程序的性能，并将中间文件转换 为汇编文件。
编译
汇编程序有助于将汇编文件转换为包含机器代码 的对象文件。
汇编
链接器用于将库文件与对象文件链接。这是编译 中生成可执行文件的最后一步。
链接
1、高级语言编译流程
gcc
静态链接，就是在装载之前，就完成所有的符号引用的一种链接方式。
静态链接
动态链接，就是将对符号的重定位推迟到程序运行时才进行。
动态链接
2、高级语言编译实例
2、编译系统
1、编译过程概述
2、编译程序的结构
3、编译阶段的组合
3、编译过程和编译程序的结构
用机器语言或汇编语言编写
用高级语言编写（普遍使用）
自编译方式，先构造一个小的编译程序，再进一步构造较大的编译程序
用编译工具自动生成部分程序
移植，同种语言的编译程序在不同机器之间移植
构造编译程序的方法
源语言、目标语言、编译方法与工具
4、编译程序的构造方法
合法句子的集合
语法描述单词的正确顺序，而语义帮助描述符号和事物之间的关系。
语法是指神奇的正确性，语义是指提供句子的正确含义。
句法研究句子的结构，而语义学研究其背后的定义和意识形态。
句法在语言上使句子成为句子，而语义通常是通过使用关于内容的已知知识来使用的。
句法正确的句子不一定有意义，而有意义的句子必须句法正确。
语法和语义的区别
1、高级语言的构成成分
2、程序的结构
3、Sample语言规范
4、符合Sample语言规范的源程序举例
5、认识Sample语言
编译程序的发展
语言的结构化编辑器
程序的格式化工具
语言程序的调试工具
语言程序的测试工具
程序理解工具
各种软件工具的开发
深刻理解和正确使用程序设计语言
加深对整个计算机系统的理解
设计开发编译程序的软件技术同样可以用于其他软件的设计开发
编译技术的地位变得越来越重要
知道我们编写的代码是如何被计算机识别并执行的
为什么要学习编译原理及其构造技术
6、编译程序的发展及编译技术的应用
第一章 编译概述
词法分析，是分析源程序中的字符流能否构成正确的单词
词法分析独立执行
语法分析为核心，词法分析为子程序
词法分析设计
扫描源程序
识别单词，输出单词及其种别码
过滤掉源程序中的注释、空格、回车换行等
调用出错处理程序
词法分析的主要工作
1、词法分析概述
如 while，if，int 等
关键字
如变量名、函数名、类或对象名等
标识符
分为算术运算符（+、-、*、/、%）、逻辑运算符（!、&&、||）和关系运算 符（<、>、<=、>=、==、!=）。
运算符
如逗号，分号，花括号，注释符号等
界符
十进制，以数字1-9开头，后跟0-9组成的字符串
八进制，以数字1-9开头，后跟0-7组成的字符串
十六进制，以0x或0X开头，后跟0-9 a-f或A-F组成的字符串
整型常量
如100，'text'，TRUE 等
常量
1、单词的分类
关键字、界符和运算符，一般采用一字一种；
标识符一般统归一种；
常数按类型分种；
种别码设计的基本原则
单词的输出为二元形式
2、单词的种别码
2、高级语言中的单词
有限个结点，称为状态。
结点间用带箭头的弧线连接，称为边。
边上标记的符号，表示从一个状态转换为另一个状态的输入字符。
开始状态，又称初态，用双箭头 => 标识
接受状态，又称终态，至少有一个
构成
1、状态转换图
初始时位于初态，输入指针指向输入缓冲区开始。
读入一个字符，状态发生转换，寻找与之匹配的边
指针不断后移，状态不断改变，直到终态
过程
2、单词识别程序
3、超前搜索技术和双界符的识别
4、数值型常量的识别与状态转换图的合并
3、单词的识别
4、词法分析器的设计
一个高级语言程序能够使用的全体字符构成的集合称为字母表。
字母表
字母表上的符号串是指由该字母表中的符号构成的有穷序列，又称为字。
字
1、符号和符号串
2、集合的运算及语言的定义
优先顺序从大到小为：* > ·> |
交换律：U|V＝V|U
结合律：U|(V|W)＝(U|V)|W
结合律：(UV)W=U(VW)
分配律：U(V|W) = UV|UW
分配律： (V|W)U = VU|WU
零一律：εU=U
零一律：Uε=U
运算规律
3、正则表达式
确定的有穷自动机->DFA
不确定的有穷自动机->NFA
4、有穷自动机
DFA任何状态之间都没有ε 转换
DFA对任何状态s 和任何输入符号a，最多只有一条标记为a的边离开s
DFA的初态唯一，NFA的初态为一集合
5、正则表达式与有穷自动机的等价性
5、正则表达式与有穷自动机
1、Lex概述
声明
翻译规则和辅助程序
用 %%分开
2、Lex源文件的书写
读取Lex的源程序，对每个正则表达式分别生成对应的不确定的有穷自动机
将这些NFA合并为一个NFA M
将该NFA确定化，最小化为DFA D
写出该DFA的分析控制程序
如果出现二义性，遵循最长匹配原则和优先匹配原则
3、Lex的工作原理
4、Lex使用中的一些注意事项
5、使用Lex自动生成词法分析器
6、词法分析器的自动生成工具
非法字符错误
拼写错误
注释、字符常数、字符串常数不闭合
错误的“与”“或”运算
变量声明有重复
词法分析的常见错误
7、词法分析中的错误处理
第二章 词法分析
1、语法分析概述
文法是描述语言的语法结构的形式规则（即语法规则），这些规则必须准确且可理解
文法的形式化定义为：文法G是一个四元组，G=（Vn，Vt，P，S），其中Vn是非终结符集 ，Vt是终结符集，S是开始符号，P是产生式集合
第一条产生式的左部是开始符号
在产生式中，用大写字母表示非终结符；小写字母表示终结符；小写希腊字母（如α 、β）代表任意的文法字符串。
如果S是文法G的开始符号，也可以将文法G写成G[S]
有时为了书写简洁，常把相同左部的多个产生式用|进行缩写。
约定
1、文法的定义
从文法的开始符号出发，反复连续使用所有可能的产生式，将一个符号串中的非终结符 用某个产生式右部进行替换和展开，直到全部为终结符为止，这个过程就称为推导
如果在推导过程中，每一步都是替换符号串中最左边的非终结符，这样的推导称为最左 推导
如果在推导过程中，每一步都是替换符号串中最右边的非终结符，这样的推导称为最右 推导
2、推导
如果文法G1与文法G2产生的语言相同，即L(G1) = L(G2)，则称文法G1与文法G2是等价 的
3、文法产生的语言
语法树就是用一棵树来表示一个句型的推导过程，有时也称为语法分析树。
4、语法树
如果一个文法存在某个句型对应两棵或两棵以上不同的语法树，则称为这个文法为二义 文法
要使用一些附加的规则来消除二义性
文法的二义性不能代表语言一定是二义的，只有当产生的一个语言的所有的文法都是二 义的，这个语言才是二义的。因为可以用无二义的文法代替二义的文法
5、二义文法
利用运算符之间的优先级和结合性来消除算术表达式文法的二义性
左结合性
6、消除二义性
7、Sample语言文法描述
2、上下文无关文法
试探与回溯
直接左递归
间接左递归
左递归
消除文法的直接左递归
消除文法中的间接左递归
1、自上而下分析方法中的问题探究
检查是否含有左递归
如果没有左递归，则计算其First集，判别其First集是否相交，即是否有回溯
文法的判别方法
2、LL(1)文法
分析程序由一组函数组成。每个函数对应于文法的一个非终结符号。
每一个函数的功能是：判断选择该非终结符的哪个候选式，并按该候选式的要求处理 完输入符号串。
实现思想
3、递归下降分析方法
分析过程
实现方式
4、预测分析方法
3、自上而下的语法分析
基本思想
“移进-归约”分析方法
1、自下而上分析方法概述
a<b a的优先级低于b
ab a的优先级等于b
a>b a的优先级高于b
任何两个相邻终结符号a和b之间的优先关系有三种
2、算符优先分析
3、LR分析法
4、自下而上的语法分析
1、YACC概述
定义部分
规则部分
第三部分
2、YACC源文件的格式
文法规则的单引号中的任何字符都表示它本身。
在定义部分用YACC的记号声明（%token开始）来声明符号记号
YACC文法规则中的记号有两种
3、YACC的翻译规则
main的定义
main调用yyparse
调用yylex
4、YACC的辅助程序
5、语法分析器的自动生成工具YACC
发现错误为主，校正错误为辅
错误局部化
准确报告，应尽早给出错误发生的位置
错误处理原则
应急模式的恢复
短语层次的错误恢复
添加错误产生式
错误恢复策略
1、语法分析中的错误处理的一般原则
把Follow(A)中的所有符号放入非终结符A的同步符号集
加入相应语句开头的关键字
把First集中的符号也加入到同步集合中
如果某个非终结符有ε产生式，就可以将ε作为默认情况
一般方法
在推导过程中当前输入符号和文法推导的符号不相匹配
在递归过程中调用形成死循环
递归下降分析程序中的错误处理方式
2、自上而下语法分析的错误处理
若在栈顶终结符与下一个输入符号之间不存在任何优先关系
若找到某一“素短语”，但不存在任一产生式，其右部为此素短语
算符优先分析中的错误检测
LR分析中的错误检测
YACC中的错误处理
3、自下而上语法分析的错误处理
6、语法分析中的错误处理
第三章 语法分析
语义不能离开语法独立存在
语义远比语法复杂
同一语言结构可包含多种含义，不同语言结构可表示相同含义
语法与语义之间没有明确的界限
语义和语法区别
一致性检查（数据类型是否一致、操作是否合法）
越界检查（数组维数是否正确、下标是否越界）
语义检查
说明语句的翻译（相关信息登记到符号表中）
执行语句的翻译（生成等价的中间代码）
语义处理
语义分析的任务
静态语义是指在编译阶段能够检查的语义，比如标识符未定义，类型不匹配等。
静态语义
动态语义是指在目标程序运行阶段能够检查的语义，比如除数为0，无效指针，数组下标越界等
动态语义
对结构上正确的源程序进行上下文有关性质的审查，审查源程序是否有无语 义错误，为代码生成阶段收集类型信息。
主要功能包括建立符号表，进行静态语义检查，发现语义错误。
1、语义分析概述
1、程序的语义
2、函数的语义
3、各种名字的声明和使用的语义
4、各种语句的语义
5、表达式的语义
2、Sample语言的语义描述
收集符号信息
进行语义的合法性检查
功能
常量的符号表至少要保存入口、常量名、常量类型、值等几项
常量表
变量的符号表则需要入口、变量名、变量长度、变量类型、值、地址等
变量表
函数表可以使用数组或hash表存储
函数表等等
包含
1、符号表概述
在程序运行期间一直存在，需要单独分配空间，是存放在数据段中的
全局变量
分配在栈空间，随着程序块运行结束而结束
局部变量
每进入一个局部化区，记录本层符号表的首地址
遇到声明性标识符时，构造其语义，查本层的符号表，检查是否有重名，有则出错。否则就 把语义字填到符号表里
遇到使用性出现，查符号表，如果查到则读取其语义字，否则出现语义错误
退出一个局部化区，作废本层的符号表。
使用花括号对{} 表示进入一个新的作用域
作用域允许嵌套，作用域内声明的变量在作用域外不可见
对于嵌套作用域，外部作用域声明的变量在内部作用域可见
内部作用域声明的变量可以覆盖外部作用域声明的同名变量
作用域的特点
2、符号表的组织方式
插入操作
查找操作
3、符号表的操作
3、符号表管理技术
相关名字检查
类型检查
控制流检查
一致性检查
1、静态语义检查概述
变量未声明就使用、变量重定义
函数未声明就定义和调用、函数重定义、函数声明与定义不匹配、函数调用与声明不匹配、 函数和变量重名等
数组长度必须是正整数、数组名不能和变量名、函数名同名
有些语言要求程序中循环或程序块的名字必须同时出现在开头或结尾
强类型语言
2、声明与定义语义检查
函数调用时实参和形参的类型不匹配，参数个数不相等
有void返回值的函数不能参与表达式运算
如果操作符作用于不相容的操作数，需要报告出错信息
数组下标运算错误
赋值表达式中，左边只能是变量、数组下标或指针等
赋值表达式的类型不匹配
3、表达式语义检查
break语句必须在循环和switch语句内使用
continue语句必须在循环语句内使用
return语句必须在函数中使用
4、语句语义检查
4、静态语义检查
第四章 语义分析
编译原理 13007
收藏
收藏
0 条评论
回复 删除
下一页
