《编译原理重点》由会员分享，可在线阅读，更多相关《编译原理重点（3页珍藏版）》请在金锄头文库上搜索。
1、1语言分类：论基础分为4类语言：强制式语言:基础是冯诺依曼模型涵数式语言；基础 是数学函数（函数运算）；逻辑式语言:基础是数理逻辑、谓词演算；对象式语言:基础是抽象 数据类型。按2语言的发展进程分类：第一代语言（机器语言）第二代语言（汇编语言） 第三代语言（高级语言:命令式、过程式）第四代语言（说明性语言、超高级语言）新一代 语言（函数式、逻辑式语言）3冯.诺依曼体系结构：三大特性：变量存储单元及名称由变量的概念代替。变量可以代 表一个或一组单元。赋值 存储（中间、最终的）计算结果。重复语句顺序执行，指令存 储在有限的存储器中，完成复杂计算时需要重复执行某些指令序列。4绑定（Binding）概
2、念：实体：程序的组成部分，如变量，表达式、程序单元等。属性：实 体具有的特性。绑定：实体与其各种属性建立起某种联系的过程称为绑定，实际上就是建立 了某种约束。描述符：描述实体属性的表格。若绑定在运行之前:即编译时）完成，且在运行 时不会改变，则称为静态绑定。若绑定在运行时完成，则称为动态绑定。5冯.诺依曼体系结构的特点：数据或指令以二进制形式存储；“存储程序”的工作方式；程 序顺序执行；存储器的内容可以被修改6虚拟机是由实际机器加软件实现的机器。若一台实际机器配置上C语言编译程序，对用户 来说，这台机器就是C语言的虚拟机7变量是对一个或若干个存储单元的抽象。一个存储单元至少一个字节。一个变量至
3、少占用 一个存储单元。赋值是对修改存储单元内容的抽象。8属性：变量的作用域：可以访问该变 量的程序范围。变量的生存期：存储单元绑定于一个变量的时间区间。变量的值：存储区单 元的内容。变量的类型：与变量相关联的值，以及对这些值进行的操作的抽象9程序单元是指程序执行过程中可独立调用的单元，编译时，一个源程序称为一个单元表示， 运行时，一个单元表示由一个代码段和一个活动记录组成此时称单元表示为单元实例。10.别名和副作用：引用环境中有两个变量绑定于同一数据对象，则称这些变量具有别名。 产生别名的两种情况:若过程参数传递方式是引用调用，那么形参和实参共享同一数据对象， 引起别名。当形参引用调用实参时，
4、它与全局变量表示同一数据对象，或者有重叠的数据对 象时，也会引起别名。对绑定的一个非局部变量进行修改时，将产生副作用。11数据类型的作用：实现了数据抽象，把程序员从机器的具体特征中解脱出来提高了编程 效率数据类型的分类12内部类型特点：反映基本硬件特性。优越性：基本表示的不可见性，基本位串对程序员 是不可见的；编译时能检查变量使用的正确性，能够进行静态类型检查；编译时可以确定无 二义的操作；精度控制，可以通过数据类型显式定义数据的精度13用户定义类型：1.笛卡尔积：n个集合A1，A2，An的笛卡儿积:A1xA2xxAn C 的结构2.有限映像：从定义域类型DT值的有限集合，到值域类型RT值的有
5、限集合的函 数（映射）称为有限映像。数组3.序列：任意多个数据项组成，数据项称为该序列的成分，且 类型相同。串、顺序文件4.递归：数据类型T包含属于同一类型T的成分。指针5.判定或： 一个选择对象结构的构造机制，规定在两个不同选择对象之间作出适当的选择。C的联合 6.幂集：类型T的元素所有子集的集合，称为幕集,T称为基类型。PASCAL的集合14用户定义类型显式命名的优点:可读性（选择名字）可修改性（不修改变量说明）可分 性（重复使用）一致性检查15用户定义类型与内部类型的异同:都建立某种基本表示的抽象.内部类型:对二进制位串 的抽象；用户定义类型:对内部类型和已定义的用户定义类型的数据作为基
6、本表示的抽象 每一类型都关联一组操作内部类型隐蔽了基本表示，不能对它的成分进行操作；而用户定 义类型具有更高级别的抽象，可以对其成分进行操作。16抽象数据类型:信息隐蔽；封装；继承在定义该类型的程序单元中，建立与表示有关的基 本操作;对使用该类型的程序单元而言，该类型的表示是隐蔽的。17类型检查：对数据的类型和使用的操作是否匹配的一致性检查18类型转换：隐式转换发生在下述的情况下：混合运算：级别低的类型向级别高的类型值 转换。将表达式的值赋给变量：表达式的值向变量类型的值转换。实参向函数形参传值：实 参的值向形参的值进行转换。函数返回值：返回值向函数返回类型的值进行转换。19类型等价：名字等价
7、，若两个变量具有相同的用户定义类型或内部类型名，则称他们具 有相容的类型。结构等价，若两个变量的类型具有相同的结构，则它们具有相容的类型，并 称两个变量结构等价。20语句级控制结构：顺序选择重复。单元级控制结构：规定程序单元之间控制流程的机制： 显示调用从属单元异常处理协同程序并发单元。21语言的定义：程序设计语言用来描述计算机处理数据时所执行算法的形式表示，由语法 和语义组成。文法的定义：文法是描述语言的语法结构的形式规则，必须准确易理解且描述 能力强。22语法描述的基本用途：表达语言设计者的意图和设计的目标，指导语言的设计者如何写 出一个正确的程序，指导语言的实现着如何编写一个语法检查程序
8、来识别所有合法的程序。 21.最右推倒是规范推倒，最左规约是规范规约。23句型：从文法的开始符推导出的任意符号串均是该文法的句型。只含终结符的句型是句 子。句子的集合是该文法的语言。24文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树，则称该文法是二义 的。25翻译:将一种语言编写的程序转换成完全等效的另一种语言编写的程序的过程称为翻译， 在计算机中，翻译由一个程序来实现，称为翻译程序。26编译程序：高级语言n低级语 言汇编程序：汇编语言n机器语言 宿主语言:编写编译程序的语言称为宿主语言宿主 机：运行翻译程序的机器自驻留：编译程序能生成可供其宿主机执行的机器代码交叉编译： 编译程序
9、生成的不是宿主机的机器代码，而是别的机器代码自编译；编译程序是用源语言写 的解释:不将源程序翻译成目标程序，而是一边分析，一边执行，这种翻译方法称为解释。 实现解释的程序，称为解释程序。优缺点1.特别适合于动态语言和交互式环境，便于人机对 话2.解释器边解释边执行，重复执行的程序需要重复翻译，比编译执行花费更多时间，执行 效率低；27编译步骤：1词法分析：分析输入字符串，根据词法规则识别出单词符号。2语法分析： 根据语法规则，将单词符号构成各类语法单位，进行语法检查，生成语法树。3.语义分析与 中间代码生成：根据语义规则，对语法正确的语法单位进行初步翻译，生成中间代码。4优化： 对中间代码进行
10、等价变换，提高代码的时空效率。5目标代码生成：根据优化后的中间代码 及有关信息，可生成较为有效的目标代码。28词法分析器是一个有限状态自动机，语法分析器是一个下推自动机。29词法分析的功能：从左到右逐个扫描源程序的字符串，按照词法规则，识别出单词符号 作为输出，对识别过程中发现的词法错误，输出有关的错误信息。30单词的种类：标识符保留字运算符常数界符31局部优化（基本块内优化）：1合并已知量：对于A：= OP B或A：=B OP C这样的语句， 变成A：=T； 2删除公共子表达式:A：=B+C*D，U：=V-C*D, U：=V-T； 3删除无用赋值:A：=B+D， A：=M+N，删除第一个式子
11、；4删除死代码：If条件为定值，删除不会执行的分支32循环优化：1代码外提：对于x：=op y若循环中y的值不变，0； 2强度削弱：j ：= c1 * i 土 c2变成j ：= j c1 * c ； 3删除循环变量：若j=10*i+5,判断条件为i10，则改为j105,删除与i有关的语句33参数传递的方式：传地址，传值，结果调用，传值得结果，传名，1345对形参的修改会 影响实参34活动记录的内容：返回地址，动态链接，静态链接，现场保护，参数个数，形式单元， 局部变量，临时变量。33.存储分配的方式：1静态分配：变量与存储区域的绑定关系在编译时便可建立，并完成存 储分配，例如，静态变量分配。2栈式分配：当一个程序单元被激活时，在栈顶分配其活动 记录；当程序单元退出时，在栈顶将其活动记录撤销，例如，半静态变量分配。3堆分配： 动态变量的首地址、长度、类型等在编译时无法确定，在执行过程中也可能改变，例如，C 中malloc分配的变量34静态作用域规则：这是一种最近嵌套规则，对非局部变量的引用，应是最近的嵌套外层 中说明的变量：(I)变量x在单元U1中被说明，则x的作用域局部于U1，或称x在U1中是 可见的(II)变量x在U1中没有被说明，则x的作用域是包围U1的说明了 x的最小外层单元 35动态作用域规则：这是一种最近活动规则：对非局部变量的引用，应是最近调用外层中 说明的变量
