第1章-引论(2学时)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,学习任务和学习方法,学习任务,掌握编译的理论基础和形式化系统,了解编译的全部过程和具体实现方法（实验）,学习方法,认真听课，理解基本概念、基本原理和基本算法。,弄懂例题，独立完成课后作业。,认真总结每章的要点，在理解的基础上记忆。,理论结合实践，认真独立地完成实验。,成绩考核方法,（1）平时成绩 30,40%,课堂点名,if(,旷课次数/点名次数 30%,),取消考试资格,或,交一份由辅导员+班主任两人签字的允许考试证明;,平时作业,上机实验,（2）考试成绩 70,60%,第1章 引论,1.1 什么是编译程序,1.2 编译过程和编译程序的结构,1.2.1,编译过程,1.2.2 编译程序结构,1.2.3 编译阶段的组合,1.3 解释程序和一些软件工具,1.3.1,解释程序,1.3.2,处理源程序的软件工具,1.4 程序设计语言范型,程序设计语言,低级语言,特定的计算机系统所固有的语言,即：机器语言、汇编语言,特点：执行效率高、编制效率低,高级语言,与自然语言比较接近的语言,如：,过程式语言：C,Pascal,Fortran,ADA,对象式语言：Java,C+等,函数式语言：LISP,逻辑式语言：Prolog,特点：执行效率低、编制效率高,1.1,什么是编译程序,一、编译程序（又称“编译器”）,是语言的翻译器,功能：高级语言的,源程序,低级语言的,目标程序,重要性：使编程者不必考虑与机器有关的细节,本课程主要研究：顺序过程式语言的编译原理和技术,源程序,预处理程序,源程序,编译程序,汇编程序,装配/连接程序,目标汇编程序,可再装配的机器代码,绝对机器代码,将机器代码与一些库文件连接,汇集分散的源程序、宏展开、,二、高级语言程序的处理过程,三、编译程序的分类,一趟编译,多趟编译,具有调试、优化功能的编译,都使用相同的基本编译技术！,1,、20世纪50年代早期：将计算公式翻译成机器码,2、20世纪50年代中期：出现了FORTRAN等一批高级语言,（也就出现了相应的编译程序）,3,、20世纪50年代后期：出现了编译程序的编译程序,（即编译程序的,自动生成工具,，如：LEX、YACC）,4,、20世纪60年代：用,自展技术,构造编译程序,（用,被编译语言,书写其,自身的编译程序,，1971年PASCAL的成功）,5,、,并行,技术与并行语言的发展：,发展方向,并行语言的并行编译,自动并行编译技术（将串行程序转换成并行程序）,四、编译程序的历史和发展,1.2,编译过程和编译程序的结构,一、编译过程,表 格 管 理,词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成,出 错 处 理,源程序,目标程序,1,词法分析,任务：,从左到右读入源程序的每个字符，对构成源程序的字符流进行扫描和分解，从而识别出一个个,单词,（也叫,单词符号,或,符号,）。,单词,是具有独立意义的,最小语法单位,。,如：,标识符,、,保留字,（关键字或基本字）、,算符,、,界符,、,常数,等。,例.某源程序片断如下：,begin,var sum,first,count:real;,sum:=first+count*10,end.,保留字,begin,保留字,var,标识符,sum,逗号,标识符,first,逗号,标识符,count,冒号:,保留字,real,分号;,标识符,sum,赋值号:=,标识符,first,加号+,标识符,count,乘号*,整数10,保留字,end,界符.,2,语法分析,任务：,依据语言的,语法规则,，确定源程序的输入串是否构成一个语法上正确的程序。,最终将单词序列分解成各类,语法短语,（也叫,语法单位,），如,“,程序,”,、,“,语句,”,、,“,表达式,”,等。,语法,：由程序语言基本符号组成,程序中各个语法成分,的一组规则。,一般语法规则,：由单词符号构成语法成分的规则；,词法规则,：由基本符号构成的符号书写规则。,举例：,id1:=id2+id3*10,的语法树,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,id1,sum,id2first,id3count,10,id1:=id2+id3*10,的语法树的另一种形式,:=,id1,+,id2,*,id3,10,程序结构的递归表示,表达式的表示：,1,）任何,标识符,是表达式。,2,）任何,常数,（整常数、实常数）是表达式。,3,）若表达式1和表达式2都是表达式，那么,表达式1+表达式2,表达式1*表达式2,（表达式1）,都是表达式。,语句的表示：,1,）,标识符:=表达式,是语句,2,）,while(,表达式),do,语句,是语句,3,）,if(,表达式),then,语句,else,语句,是语句,3,语义分析,任务：审查源程序有无,语义错误,，为代码生成阶段,收集类型信息,。,主要功能：类型检查、报语义错误、类型转换等,语义,：是程序设计语言中按语法规则构成的各个语法成分的意义。,静态语义,：,编译时刻,即可确定的语法成分含义。,动态语义,：,运行时刻,才能确定的语法成分含义。,:=,id1,+,id2,*,id3,10,inttoreal,real first,count,sum,sum:=first+count*10,举例：类型检查和转换,4,中间代码生成,任务：,在语法和语义分析之后，将源程序变成一种,“,内部表示形式,”,。,中间代码,：一种结构简单、含义明确的记号系统。,特征：,1,）结构简单、含义明确,2）复杂性介于源语言和机器语言之间,3）容易生成；,4）容易将它翻译成目标代码。,四元式,：,（运算符，运算对象1，运算对象2，结果）,四元式：,（运算符，运算对象1，运算对象2，结果）,举例：源程序 sum:=first+count*10,生成的四元式可以是：,(inttoreal,10,-,t1 ),(*,id3,t1,t2 ),(+,id2,t2,t3 ),(:=,t3,-,id1),:=,id1,+,id2,*,id3,10,inttoreal,5,代码优化,任务：,对中间代码进行变换或改造，使之更为高效（时间、空间）。,(inttoreal,10,-,t1 ),(*,id3,t1,t2 ),(+,id2,t2,t3 ),(:=,t3,-,id1),(*,id3,10.0,t2 ),(+,id2,t2,id1),(*id310.0t1 ),(+id2t1id1),6,目标代码生成,任务,：,把中间代码变换成特定机器上的绝对指令代码或可重定位的,机器指令代码,或,汇编指令代码,。,特点,：,1,）与硬件系统结构和指令含义有关，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。,2）高级语言,低级语言转换是,基于语义,的等价变换，不是结构上的变换。,(*id310.0t1 ),(+id2t1id1),sum:=first+count*10,MOVFid3,R,2,MULF#10.0,R,2,MOVFid2,R,1,ADDFR,1,R,2,MOVR,1,id1,表格管理,任务：,用于保存源程序的各种信息。因为上述各阶段工作均需要查找、更新、构造表格。,出错处理,任务：,报告源程序中错误的性质、地点，将错误所造成的影响限制在尽可能小的范围。有些编译程序还可以自动纠错。,一个程序是正确的，包括两层含义：,1）,书写正确,（合乎语法规则）,2）,含义正确,（合乎语义规则）,说明,多数实用的编译程序都采用以上几个阶段的工作过程。,有些编译程序没有“中间代码生成”和“代码优化”。,二、编译程序的结构,表 格 管 理,程 序,词法分析,程序,语法分析,程序,语义分析,程序,中间代码生成,程序,代码优化,程序,目标代码生成,程序,出 错 处 理,程 序,源程序,目标程序,三、编译阶段的组合,前端,：,主要依赖于源语言而与目标机器无关的编译阶段。如：词法分析、语法分析、语义分析、中间代码生成、部分代码优化、与前端有关的出错处理工作和表格管理工作。,后端,：,依赖于目标机而一般不依赖于源语言，只与中间代码有关的编译阶段。如：,目标代码生成,，以及相关出错处理和表格处理。,遍,（,趟,）：,对,源程序,或其等价的,中间语言程序,从头到尾扫视并完成规定任务的过程。每一遍扫视可完成编译的一个阶段或多个阶段工作。,多遍编译：占内存少，逻辑结构清晰，耗时长,一遍编译：占内存多，逻辑结构不清晰，耗时短,1.3,解释程序和一些软件工具,一、解释程序,接受高级语言程序，并立即运行这个源程序。,例如：BASIC语言解释程序，LISP解释程序，SQL解释程序，Java语言中的BYTECODE解释程序,解释程序,源程序,输入数据,结果,编译程序,高级语言程序,（源程序）,低级语言程序,（目标程序）,解释程序,源程序,结果,输入数据,运行程序,输入数据,结果,编译与解释的根本区别：,是否生成目标代码,。,二、解释程序与编译程序的比较,三、解释程序的优、缺点,优点：可移植性较好。,缺点：（1）速度慢,（2）空间开销大,有些语言既有编译程序，又有解释程序。如java,四、处理源程序的软件工具,1,语言的结构化编辑器,正文编辑、修改,对源程序正文进行分析（检查用户输入是否正确、自动提供关键字、检查括号的匹配情况）,2,语言程序的调试工具,了解程序执行的结果与编程人员的意图是否一致,允许用户一行一行跟踪程序，查看变量值的变化,3,程序格式化工具,分析源程序，并使程序结构变得清晰可读（如缩排）,四、处理源程序的软件工具,4,语言程序测试工具,静态分析器：不运行源程序，就可以发现其中潜藏的错误或异常。,动态分析器：对源程序进行分析，把记录和显示程序执行轨迹的语句或函数插入源程序，将运行结果与期望结果进行比较和分析。,5,程序理解工具,对程序进行分析，确定模块间的调用关系，并画出控制流程图。,6,高级语言之间的转换工具,将一种高级语言程序转换成另一种高级语言程序,1.4,程序设计语言范型,一、强制式语言（过程式语言、命令式语言）,由一系列的语句组成，每个语句的执行引起若干存储单元中值的改变。,如：C，Fortran，Pascal,二、函数式语言（应用式语言）,从前面已有的函数出发构造出更复杂的函数。,Function n(,Function 2(Function 1(data),),如：ML，LISP,1.4,程序设计语言范型,三、基于规则的语言（基于逻辑的语言）,检查一定的使能条件，当它满足时，则执行适当的动作。,条件,动作,如：PROLOG,四、面向对象语言,提供抽象数据类型，支持封装性、继承性和多态性。,如：Ada，C+，Java,练习,1,、程序语言一般分为,（1）,和,（2）,两大类。其中,（3）,与人类自然语言比较接近，,（4）,又称为面向机器的语言。,A 高级语言,B 专用程序语言,C 低级语言,D 通用程序语言,A C A C,练习,2、面向机器的语言是指,（1）,，其特点是,（2）,。,（1）A.用于解决机器硬件设计问题的语言,B.特定计算机系统所固有的语言,C.各种计算机系统都通用的语言,D.只能在一台计算机上使用的语言,（2）A.程序执行效率低，编写效率低，可读性差,B.程序执行效率低，编写效率高，可读性强,C.程序执行效率高，编写效率高，可读性强,D.程序执行效率高，编写效率低，可读性差,B D,练习,3、编译程序是将,（1）,翻译成,（2）,；汇编程序是将,（3）,翻译成,（4）,。,A.汇编语言程序,B.高级语言程序,C.机器语言程序,D.汇编语言程序 或 机器语言程序,E.汇编语言程序 或 高级语言程序,B D A C,练习,4、编译程序的工作过程可以划分为,（1）,等六个阶段，同时还伴有,（2）,和,（3）,。,（1）词法分析、语法分析、语义分析、中间代码生成、代码优化、目