教案编译原理-chap

：参考资料等编著，电子工业1、编译原理，主要参考资料：1、程序设计语言编译原理，陈火旺编著，国防工业2、Compilers:Principles,Techniques,and

Tools。By:Alfred

V.Aho,Ravi

Sethi,Jeffrey

D.Ullman，人民邮电1、加深对程序 执行过程的理解2、为了进一步编好程序为什么要设置编译原理课程？本课程基本框架1、引论2、基础知识：文法3、词法分析理论模型——正规文法与有限自实现——词法分析程序4、语法分析理论模型：自上而下分析——下推自自下而上分析——优先分析和LR分析实现——递归下降分析法、YACC5、中间代码生成语法制导翻译6、符号表的组织与管理7、运行时数据区的管理：静态 管理、栈式 管理、堆式 管理8、中间代码优化：局部优化、循环优化、窥孔优化9、目标代码生成第一章

编译概述1.1翻译程序与编译程序程序设计语言–高级语言–汇编语言–机器语言在计算机上如何执行一个高级语言程序？–把高级语言程序翻译成机器语言程序–运行所得的机器语言程序求得计算结果翻译–在不改变语义的条件下，把某种语言的源程序转换成另一种语言程序——目标语言程序。解释–接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。第一章

编译概述1.1翻译程序与编译程序解释–以源程序作为输入，不产生目标程序，一边解释一边执行。–优点：直观易懂，结构简单，易于实现人机–缺点：效率低第一章

编译概述1.1翻译程序与编译程序编译–由高级语言转换为低级语言,然后对编译出来的目标程序进行运行计算编译与解释的区别：解释器是源程序的一个执行系统，而编译程序是源程序的一个转换系统；解释程序的工作结果是源程序的执行结果，而编译程序的工作结果是得到等价于源程序的某中目标机程序。第一章

编译概述1.1翻译程序与编译程序基于编译的高级语言源程序的执行过程

–两阶段：编译——运行源程序编译程序目标代码编译时初始数据目运标行代子码程序计算结果运行时第一章

编译概述1.1翻译程序与编译程序基于编译的高级语言源程序的执行过程–三个阶段的转换：编译——汇编——运行源程序编译程序程汇序编语言目标编译阶段程机序器语言目标汇编程序汇编阶段计算结果运行阶段初始数据运行系统第一章 编译概述1.1翻译程序与编译程序第一章

编译概述1.2

编译过程和编译程序的基本结构编译过程–从输入源程序开始到输出目标程序为止的整个过程。可分为五个阶段：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成源程序词法分析器语法分析器生及语成中义间分代析码器代码优化目标代码生成目标程序出错处理第一章 编译概述1.2编译过程和编译程序的基本结构编译程序的基本结构表格管理第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构1.词法分析任务–输入源程序，对构成源程序的字符串进行扫描和分解，依照词则，识别出一个个的单词，并转化为机器易于使用的内码形式。单词–是高级语言中有实在意义的最小语法单位，它由字符构成。词

则–定义了单词符号的形成规则Void

jisuan(){inty,c,d;float

x,a,b;x=a+b*50;y=c+)d*(x+b;}第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构词法分析识别右边程序中的单词基本字：Void

,int,

float标识符：a,

b,c,d,

x,y,jisuan整常数：50运算符:：+,-,*,=界限符：{};,()第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构•1.转词换法内分容析–对基本字、运算符、界限符的转换–标识符的转换–常数的转换第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构词法分析注：1)一般内码可用二元式（类号、内码）表示。对于标识符与常数是由用户任意使用的，数目无限，解决办法是给标识符分配一个类号，不同的标识符用它的符号表 地址（或变量地址）来区分，将这些地址当作内码给出。2)描述词 则的有效工具是正规式和有限自定单词如何构成短语、–语言的规则，又称为文语句、过程和程序2）语法检查——通过语法分解，确定整个输入串是否构成语法上正确的句子、程序等。语则的表示：BNF如<Word>::={}，A::=a|b|cB注：语法分析对说明语句的处理是要填符号表，而对一般语句处理规则是构造语法树。第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构2.语法分析任务：1）组词成句——在词法分析的基础上，根据语言的语

则或文法，把单词符号组成各类的语法单位，如：短语、子句、语句、过程、程序。第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构2.语法分析例：赋值语句的语

则•A::=V=E•E::=T|E+T•T::=F|T*F•F::=V|(E)|C•V::=标识符•C::=常数第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构2.语法分析语法分析方法：推导（derive)和归约(reduce)–推导：从文法的开始符号开始，按照语则，每次选择某规则右部的一个候选式取代左部，直至识别了语句或者找到错误为止。其过程可用语法树描述。–推导可分为：最左推导、最右推导–归约：按照语

则，每次选择某规则左部取代右部的一个候选式–规约可分为：最右归约、最左归约–注：语法＝词 则＋语

则第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构3.语义分析及中间代码生成任务在语法分析正确的基础上，按照相应语义规则，产生介于源代码和目标代码之间的一种代码。注：这种中间代码不依赖于机器，但又便于产生依赖于机器的目标代码。两阶段工作–对每种语法范畴进行静态语义检查–若语义正确，就进行中间代码的翻译中间代码形式–四元式、三元式、逆波兰式–注：1）中间代码是为后续的优化和目标代码生成提供方便，因此中间代码的选择往往与所采用的优化技术和计算机硬件结构有关。2）用得最广的是四元式。第一章 编译概述1.2

编译过程和编译程序的基本结构编译程序功能结构4.代码优化任务对产生的中间代码进行加工变换，以期在最后阶段能产生更为高效（省时间、省空间）的目标代码依据原则：程序的等价变换规则主要优化内容删除公共子表达式、合并已知量、删除无用赋值语句、循环优化等第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构5.目标代码生成任务：把中间代码程序转化成具体机器的指令序列注：转换过程需涉及具体机器的指令系统以及寄存器分配等硬件功能。第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构6.表格与表格管理表格作用：–用于记录源程序的各种信息以及编译过程中的各种状况，以便后续阶段使用。与编译前三阶段有关的表格有：–符号表、常数表、标号表、分程序表、中间代码表等。–注：在编译过程中，随着源程序的不断被改造，编译的各阶段常常需要不同的表格，编译过程的绝大多数时间是花在查表、造表和更新表格的事务上。在大多数的编译程序中，表格专门由表格管理程序来处理。NAMEINFORMATIONm整型、变量地址n整型、变量地址k整型、变量地址第一章 编译概述1.2

编译过程和编译程序的基本结构编译程序功能结构6.表格与表格管理符号表：用来登记源程序中的常量名、变量名、数组名、过程名等的性质、定义和 状况。值14常数表登记各类常量(直接量)值注：标号表可与符号表合并(登记标号的定义与

)NAMEINFORMATION………….10四元式序号4标号表第一章 编译概述1.2

编译过程和编译程序的基本结构编译程序功能结构6.表格与表格管理NAMEINFORMATION………….INCWAP二目子程序、四元式序号1第一章 编译概述1.2

编译过程和编译程序的基本结构编译程序功能结构6.表格与表格管理

名表：登记过程的层号，分程序符号表的 (指分程序结构的语言)等6.表格与表格管理中间代码表：记录四元式序列的表序号OPARG1ARG2RESULT（1）＝Im（2）=jn（3）=1k（4）J<100k(9)（5）+m10m（6）+n10n（7）+k1k（8）j(4)（9）return第一章 编译概述1.2编译过程和编译程序的基本结构编译程序功能结构7.出错处理任务如果源程序有错误，编译程序应设法发现错误，并报告给用户。注：查错无形式化的办法解决。完成：由专门的出错处理程序来完成错误类型:–语法错误:在词法分析和语法分析阶段检测出来。–语义错误：一般在语义分析阶段检测。第一章 编译概述1.2

编译过程和编译程序的基本结构编译程序功能结构8.遍产生背景一个具体的编译器体系结构可能按功能结构方式组织起来，也可能是按别的方式组织起来。

“别的方式”从形式上看就是分遍的问题；按遍数可把编译器分为一遍的和多遍的。第一章 编译概述1.2

编译过程和编译程序的基本结构编译程序功能结构8.遍遍：指对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标代码的过程。–注：遍与前述阶段的含义毫无关系。第一章 编译概述1.2

编译过程和编译程序的基本结构编译程序功能结构8.遍一遍扫描的好处–避免重复性工作，编译速度快。一遍扫描的缺点–发生语法或语义错误时，前面所作的工作可能要半途而废。–不便于分工，不便于优化，算法不清晰。第一章 编译概述1.2

编译过程和编译程序的基本结构编译程序功能结构8.遍多遍扫描的好处–节省内存空间，提高目标代码质量，使编译的逻辑结构清晰，算法清晰。多遍扫描的缺点–编译时间较长。–注：在内存 情况下，还是遍数尽可能少些为好。语法分析扫描器语义子程序源程序目标代码编译程序一遍扫描（以语法分析为中心）第一章 编译概述1.3编译程序的生成方法目前已有方法：1.直接用机器语言编写编译程序2.用汇编语言编写编译程序–注：编译程序 部分常用汇编语言编写3.用高级语言编写编译程序–注：这是普遍采用的方法4.自编译5.编译工具:LEX(词法分析)与YACC(用于自动产生

LALR分析表)6.移植（同种语言的编译程序在不同类型的机器之间移植）在某机器上为