《编译原理(1).ppt》由会员分享，可在线阅读，更多相关《编译原理(1).ppt（48页珍藏版）》请在三一文库上搜索。
1、编译原理,第一章 编译程序概论,一.编译程序,从功能上看，一个编译程序就是一个语言翻译程序。它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。 源语言通常是一个高级语言，如FORTRAN，C 或Pascal。 目标语言通常是一个低级语言,如汇编或机器语言。,编译程序,将一种语言书写的程序翻译成另一种语言的等价的程序。 编译程序的输入对象称为源程序。 编译程序的输出对象称为目标程序。,高级语言程序的处理过程,常用的翻译工具有3种,根据被翻译语言与执行方式的不同 1.汇编程序 用于特定计算机上的汇编语言的翻译程序。 2.编译程序 3.解释程序 对源程序进行翻译的程序
2、,编译程序与解释程序的区别,“解释程序”是这样的程序：它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。 “编译”的内涵是实现从源语言表示的算法向目标语言表示的算法的等价变换。,编译程序与解释程序的区别,解释方式,编译方式,编译阶段和运行阶段存储结构,编译时 运行时,名字表,目标代码缓冲区,编译用源程序中 间表示各种表格,目标代码区,数据区,源程序缓冲区,解释系统存储结构,解释执行, 不生成目标代码 能支持交互环境（同增量式编译系统） 优点：交互方便，节省空间。 缺点：效率低。因对源程序的循环语句部分要反复解释执行。 共同点：都需进行词法、语法、语义分析。,二.编译程
3、序概述,英译与编译的比较,1.识别出句子中的一个个单字 2.分析句子的语法结构 3.初步翻译句子的含意 4.译文修饰 5.写出最后译文,1.词法分析 2.语法分析 3.语义分析中间代码生成 4.优化 5.目标代码生成,1.词法分析,任务：扫描源程序，根据语言的词法规则，分解和识别出每个单词，并把单词翻译成相应的机内表示。 单词是语言中最小的语义单位 在词法分析阶段工作所依循的是语言的词法规则。描述词法规则的有效工具是正规式和有限自动机。,Pascal源程序片断,position := initial + rate * 60 词法分析后可能返回： 单词类型 单词值 标识符 position 算符
4、(赋值) := 标识符 initial 算符(加) + 标识符 rate 算符(乘) * 整数 60 界符(分号) ；,C源程序片断 int a; a = a + 2; 词法分析后可能返回: 单词类型 单词值 保留字 int 标识符 a 界符 ; 标识符 a 算符(赋值) = 标识符 a 算符(加) + 整数 2 界符 ；,2.语法分析,任务：根据语言的语法规则，把单词符号串分解成各语法单位。如“短语”、“句子”、 “子句”、“程序段”等。 通过语法分析，可以确定整个输入符号串是否构成一个语法正确的程序；对含有语法错误的程序，要进行相应的出错处理。 语法规则通常用“上下文无关文法描述”。,赋值
5、语句的语法分析,id1=id2+id3*10,依据的定义规则,:=“:=” :=“+” :=“* ” :=“(”“)” :=id :=n,3.语义分析,任务：审查源程序有无语义错误.如使用了没有声明的变量；或者给一个过程名赋值；或者调用函数时参数类型不合适或者参加运算的两个变量类型不匹配等 目的：保证标识符和常数的正确使用 通常使用“属性文法”描述语义规则,如下边的程序片段： int arr2,c; c = arr1 * 10 ; 其中的赋值语句是符合语法规则的，但是因为没有声明变量arr1，而存在语义错。,4.中间代码生成,“中间代码”是一种结构简单、含义明确的记号系统,这种记号系统可以设计
6、为多种多样的形式， 重要的设计原则为两点:一是容易生成；二是容易将它翻译成目标代码。 目的：为了最终能得到高效率的目标代码 任务：在语法分析和语义分析的基础上，根据语法成分的语义对其进行翻译。 常用的中间代码形式:(1)三元式(2)四元式(3)逆波兰式,sum = first+count*10,id1=id2+id3*10 四元式(运算符,运算对象1,运算对象2,结果),5.中间代码优化,任务：通过调整和改变中间代码中某些操作的次序，最终产生更加高效率的目标代码 优化所依循的原则是程序的等价变换规则 其方法有：公共子表达式的提取、循环优化、删除无用代码等。,t1 = b* c t1 = b*
7、c t2 = t1+ 0 t2 = t1 + t1 t3 = b* c a = t2 t4 = t2 + t3 a = t4,6.目标代码生成,任务：将中间代码优化之后的中间代码转换为等价的目标代码 目标代码依赖于具体计算机的硬件系统结构和指令系统,三.编译程序的结构,表格与表格管理,编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作 最重要的是“符号表”它用来登记源程序中出现的每一个名字以及名字的各种属性。如一个名字是常量名、变量名，还是过程名等；如果是变量名它的类型又是什么、所占内存是多大、地址是什么等。,类型、
8、作用域、分配存储信息,Const1 常量 值：35 Var1 变量 类型：实 层次：2,出错处理,一个编译程序不仅能对书写正确的程序进行编译，而且应能对出现在源程序中的错误进行处理。如果源程序有错，编译程序应设法发现错误，把有关错误报告给用户。这部分的工作是由专门的一组程序（叫做出错处理程序）完成的。,编译阶段的组合,常常把编译的过程分为前端(front end)和后端(back end) 前端的工作主要依赖于源语言而与目标机无关, 后端工作依赖于目标机而一般不依赖源语言 通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作, 即中间代码优化也可在前端做，也包括与前端每
9、个阶段相关的出错处理工作和符号表管理等工作。后端工作包括目标代码生成和目标代码优化，以及相关出错处理和符号表操作。,“遍”&“趟”,“遍“是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 一个编译过程可由一遍、两遍或多遍完成 每一遍扫视可完成上述一个阶段或多个阶段的工作 遍数多一点，整个编译程序的逻辑结构可能清晰些，但遍数多即意味着增加读写中间文件的次数，势必消耗较多时间，一般会比一遍的编译要慢,处理源程序的软件工具（编译技术的应用）,1.语言的结构化编辑器 2.语言程序的调试工具 3.程序格式化工具 4.语言程序测试工具 5.程序理解工具 6.高级语言之间的转换工具,1.语
10、言的结构化编辑器,结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能，而且还能像编译程序那样对源程序正文进行分析。因此，结构化编辑器能够执行一些对编制程序有用的附加的任务。 例如，它能够检查用户的输入是否正确，能够自动地提供关键字,当用户敲入if后，编辑器立即显示then并将这两个关键字之间必须出现的条件留给用户输入，并能检查begin或左括号与end或右括号是否相匹配等等。 商用产品很多如Turbo-Edit,Editplus和Ultraedit等等.很多集成开发环境中里也都包含这种类似的工具,如Jbuild.,2.语言程序的调试工具,调试是软件开发过程中一个重要环节，结构化编辑器只能
11、解决语法错误的问题，而对一个已通过编译的程序来说，需进一步了解的是程序执行的结果与编程人员的意图是否一致，程序的执行是否实现预计的算法和功能。 这种对算法的错误或程序没能反映算法的功能等错误就需用调试器来协助解决。有一种调试器允许用户使用源程序正文和它的符号来调试,即一行一行的跟踪程序,查看变量和数据结构的变化以进行调试工作.,3.程序格式化工具,程序格式化工具分析源程序并以使程序结构变得清晰可读的形式打印出来。例如，注释可以以一种专门的字形出现，且语句的嵌套层次结构可以用缩排方式（齿形结构）表示出来。,4.语言程序测试工具,语言程序测试工具有两种：静态分析器和动态测试器。 静态分析器是在不运
12、行程序的情况下对源程序进行静态地分析，以发现程序中潜在的错误或异常.它对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系。如某变量未被赋值就被引用，或定值后未被引用，或多余的源代码等一些编译程序的语法分析发现不了的错误。 动态测试工具也是首先对源程序进行分析，在分析基础上将用于记录和显示程序执行轨迹的语句或函数插入到源程序的适当位置，并用测试用例记录和显示程序运行时的实际路径,将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。,5.程序理解工具,对程序进行分析，确定模块间的调用关系，记录程序数据的静态属性和结构属性，并画出控制流程图，帮助用户理解程序。,6. 高级语言之间的转
13、换工具,由于计算机硬件的不断更新换代，更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好条件，然而一些已有的非常成熟的软件如何在新机器新语言情况下使用呢? 为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言转换成另一种高级语言，乃至汇编语言转换成高级语言的问题。 这种转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已。这与实现一个完整的编译程序相比工作量要少些。,知识结构,四.语法描述图,文法的EBNF表示, ：用左右尖括号括起来的中文字表示语法构造成分,或称语法单位,为非终结符 = ：该符号的左部由右部定义,可读作定义 为 | ：表
14、示或,为左部可由多个右部定义 ：花括号表示其内的语法成分可以重复。 ：方括号表示其内的成分为任选项 ( ) ：表示圆括号内的成分优先,EBNF描述文法的定义,=+|- =0|1|2|3|4|5|6|7|8|9 或更好的写法 =+|-|0 =1|2|3|4|5|6|7|8|9 =0|,程序=分程序 分程序=常量说明部分变量说明部分过程说明部分语句 常量说明部分=CONST常量定义 ，常量定义； 常量定义=标识符=无符号整数 无符号整数=数字数字 变量说明部分=VAR标识符，标识符； 标识符=字母字母|数字 过程说明部分=过程首部分程序；过程说明部分； 过程首部=PROCEDURE标识符； 语句=赋值语句|条件语句|当型循环语句|过程调用语句|读语句|写语句|复合语句|空,赋值语句=标识符=表达式 复合语句=BEGIN语句；语句END 条件=表达式关系运算符表达式|ODD表达式 表达式=+|-项加法运算符项 项=因子乘法运算符因子 因子=标识符|无符号整数|(表达式) 加法运算符=+|- 乘法运算符=*|/ 关系运算符=#|=|=|= 条件语句=IF条件THEN语句 过程调用语句=CALL标识符 当型循环语句=WHILE条件DO语句 字母=a|b|X|Y|Z 数字=0|1|2|8|9,