编译原理复习提纲

程序设计语言与编译复习提纲 语言部分

第一章

? 变量及其属性

变量是对一个(或若干个)存储单元的抽象，赋值语句则是修改存储单元内容的抽象。

变量除名字外,具有四个属性:作用域（Scope）、生存期(Lifetime)、值(Value)和类型(Type)。 ? 虚拟机的概念

虚拟机是由软件实现的机器。 ? 程序单元及单元实例

程序执行过程中的独立调用单元；如子程序、分程序、过程等

运行时，单元表示由一个代码段和一个活动记录组成，称为单元实例。 第二章

? 数据类型的作用 1.实现了数据抽象

2.使程序员从机器的具体特征中解脱出来

3.提高了编程效率

? 数据聚合的几种方式 笛卡尔积、有限映像、序列、递归、判定或、幂集 ? 动态数组

动态数组是指在声明时没有确定数组大小的数组

? 抽象数据类型的条件

在实现该类型的程序单元中,建立与表示有关的基本操作;

对使用该类型的程序单元来说,该类型的表示是隐蔽的。 ? 类型检查及分类

对数据对象的类型和使用的操作是否匹配的一致性检查称为类型检查

类型检查分为静态检查（static

checking）和动态检查（dynamic checking）;

静态检查使程序更正确更有效 动态检查使编程方便,但影响了可读性,且降低了执行效率 ? 何谓类型等价

若T1和T2是两个类型，且T1的任何值都可以赋予T2类型的变量，T1类型的实参可以对应类型T2的形参，反之亦然，则称T1和T2是相容的，或等价的

名字等价：两个变量的类型名相同 结构等价：两个变量的类型具有相同的结构。

? 内情向量及内容

任何对数组元素的访问都编译成通过动态描述符的间接地址，动态描述符通常成为内情向量。 第三章

? 语句级控制结构

顺序（sequencing）、选择（selection）、重复（repetition） ? 单元级控制结构

规定程序单元之间控制流程的机制。有显式调用、异常处理、协同程序和并发单元。

? 异常处理的主要问题

1）异常如何说明，它的作用域是什么？

2）异常如何发生（或如何发信号）？

3）发出异常信号时，如何控制要执行的单元（异常处理程序）？ 4）发出异常时，如何绑定相应的异常处理程序？

5）处理异常之后，控制流程转向何处？

? 选择/循环结构的不确定实例 ? 副作用

对非局部环境的修改 ? 别名

在单元激活期间,两个变量表示(共享)同一数据对象

第四章

? 语言的定义

用来描述计算机所执行的算法的形式表示

由两个部分组成：

? 语法:用以构造程序及其成分的一组规则的集合

? 生成的观点 ? 识别的观点

? 语义:用以规定语法正确的程序或其成分的含义的一组规则的集合

? 文法的定义

文法G定义成一个四元式： G=(VT,VN,S,P) ? 文法的分类 0、1、2、3型文法

? 语法描述的基本用途

用于产生和识别一个正确的程序 ? 抽象机的结构

指令指针ip和存储器，存储器分为代码区和数据区 ? 推导

如果α1?α2 …?αn ，则称记为α1 推导出αn，记为α1?αn ? 句型

如果S?α，α?V*，则α为G的一个句型 ? 句子

如果S?α，α?VT*，则α为G的一个句子 ? 语言

文法G的所有句子的集合称为G产生的语言，记为L（G) ? 语法树

语法树（或推导树）是一棵用来表示一个句型的推导过程的树 ? 设计语言的准则

可写性、可读性、可靠性

编译部分

第七章

? 编译等概念

将高级语言程序翻译成低级语言程序称为编译

? 词法分析器的功能

从左到右逐个字符扫描源程序的字符流，分析出一个个单词符号，把由字符串表示的源程序转换成由符号串组成的串，供语法分析器使用；并对识别过程中发现的错误，输出有关信息 ? 状态转换图

是一张有限方向图，是设计词法分析器的有效工具；它由结点和有向边构成

? 左递归的消除

? FIRST集、FOLLOW集、预测

分析表的构造

? 短语、直接短语、句柄、素短

语

? FIRSTVT集、LASTVT集、优

先关系表的构造

? LR(0)项目集规范族、LR(0)分析

表的构造、SLR(1)分析表的构造 第十一章

? 何谓语法制导翻译

在语法分析过程中，根据每个产生式对应的语义子程序（语义动作）进行翻译（生成中间代码）的方法称为语法制导翻译

? 根据语义子程序进行翻译 ? 简单语句的翻译方案 第十二章

? 优化的措施、会进行简单的优

化

? 不同阶段的优化

① 源程序阶段的优化：考虑数据

结构和算法

② 编译优化——中间代码优化和

目标代码优化

③ 中间代码优化——局部优化和

全局优化

? 基本块的划分

找出入口语句和出口语句，然后使用划分基本块的算法：

? 求出四元式序列中的各个入口语句；

? 对每一个入口语句构造一个基本块；

? 删除未被纳入任何基本块的语句；

? 循环的查找

若n?d是流图G=(N,E,ｎ0)的一条回边，M是流图中有通路到达n而该通路不经过d的结点集,则集合LOOP={n,d}∪M组成了G的一个子图, 称为由回边n?d组成的循环。

? 代码生成的简单方法

给定语句p: x:=y op z，其中p是语句所在的位置，这个语句一般由两条指令实现： MOV y, Ri OP Ri, z

? 寄存器的分配原则、

? 为x分配寄存器，要考虑如下三种情况：

① y本身占有寄存器Ri，且y在p点后不再被引用 op Ri, z； ② 有空余的可用寄存器Ri，将Ri分配给x,生成前述两条指令； ③ 寄存器均被占用：保存副本，选择一个——最好选择占用Ri的变量在主存中已有副本的；或者在p点后该变量不再被引用的；或者在离p点最远处才被引用的寄存器，然后生成前述两条指令。 第十三章

? 活动记录的内容 一个活动记录（Activation Record）是一个程序单元的数据空间

临时变量 局部变量 形式单元 参数个数 现场保护 静态链接 动态链接 返回地址

? 静态分配的条件

1.不允许过程的递归调用； 2.无动态数组和动态类型； 3.程序无嵌套层次结构；

? 仅含半静态变量的栈式分配

（条件、过程调用语句的翻译、返回语句的翻译）

1.只允许过程的递归调用；

2.每个变量的长度静态可确定； 3.每个程序单元的整个活动记录的长度可静态确定；

? 数据参数传递的几种方法 传值、传值得结果、传地址