编译原理及编译程序构造

编译原理及编译程序构造翟玉庆[e-mail]主要参考资料：1、编译原理及编译程序构造，秦振松，东南大学出版社2、编译原理，陈火旺，国防工业出版社3、编译原理及实践，KennethC.Louden，冯博琴译，机械工业出版社主要参考资料为什么要设置编译原理课程？1、加深对程序内部执行过程的理解2、为了进一步编好程序为什么要设置编译原理课程？如何讲解编译原理？程序语言语法语义语用语言高级语言汇编语言机器语言人机器翻译编译反编译翻译：口译编译：笔译如何讲解编译原理？1、引论2、基础知识：文法3、词法分析理论模型——正规文法与有限自动机实现——词法分析程序4、语法分析理论模型：自上而下分析——下推自动机自下而上分析——优先分析和LR分析实现——递归下降分析法、YACC5、中间代码生成语法制导翻译6、运行时数据区的管理：静态存储管理、栈式存储管理、堆式存储管理7、中间代码优化：局部优化、循环优化、全局优化8、目标代码生成本课程基本框架第一章引论一、程序设计语言•程序设计语言–高级语言–汇编语言–机器语言•在计算机上如何执行一个高级语言程序？–把高级语言程序翻译成机器语言程序–运行所得的机器语言程序求得计算结果第一章引论二、程序设计语言的转换与编译•翻译–在不改变语义的条件下，把某种语言的源程序转换成另一种语言程序——目标语言程序。•解释–接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。第一章引论二、程序设计语言的转换与编译•解释–以源程序作为输入，不产生目标程序，一边解释一边执行。–优点：直观易懂，结构简单，易于实现人机对话–缺点：效率低第一章引论二、程序设计语言的转换与编译•编译–由高级语言转换为低级语言,然后对编译出来的目标程序进行运行计算第一章引论二、程序设计语言的转换与编译•编译的转换过程–两阶段转换：编译——运行源程序编译程序目标代码编译时初始数据运行子程序目标代码计算结果运行时第一章引论二、程序设计语言的转换与编译•编译的转换过程–三个阶段的转换：编译——汇编——运行源程序编译程序汇编语言编译时目标代码汇编程序汇编时初始数据运行子程序目标代码计算结果运行时第一章引论三、编译程序•编译程序的工作–从输入源程序开始到输出目标程序为止的整个过程。可分为五个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成–注：也可加入语义分析。词法分析器语法分析器语义分析器中间代码生成优化目标代码生成源程序目标代码表格管理出错处理第一章引论三、编译程序1.词法分析•任务–输入源程序，对构成源程序的字符串进行扫描和分解，依照词法规则，识别出一个个的单词，并转化为机器易于使用的内码形式。•单词–是高级语言中有实在意义的最小语法单位，它由字符构成。•注：1)一般内码可用二元式（类号、内码）表示。对于标识符与常数是由用户任意使用的，数目无限，解决办法是给标识符分配一个类号，不同的标识符用它的符号表入口地址（或变量地址）来区分，将这些地址当作内码给出。2)描述词法规则的有效工具是正规式和有限自动机第一章引论三、编译程序1.词法分析第一章引论三、编译程序2.语法分析•任务：1）组词成句——在词法分析的基础上，根据语言的语法规则或文法，把单词符号组成各类的语法单位，如：短语、子句、语句、过程、程序。2）通过语法分解，确定整个输入串是否构成语法上正确的句子、程序等。•语法规则的表示：BNFWord::={}•注：语法分析对说明语句的处理是要填符号表，而对一般语句处理规则是构造语法树。•语法分析方法：推导（derive)和归约(reduce)–推导：从文法的开始符号开始，按照语法规则，每次选择某规则右部的一个候选式取代左部，直至识别了语句或者找到错误为止。其过程可用语法树描述–归约：按照语法规则，每次选择某规则左部取代右部的一个候选式–注：语法＝词法规则＋语法规则第一章引论三、编译程序2.语法分析•语法树AabV=ETT*FFFCxE+TVV50第一章引论三、编译程序3.中间代码生成•任务在语法分析正确的基础上，按照相应语义规则，产生介于源代码和目标代码之间的一种代码。注：这种中间代码不依赖于机器，但又便于产生依赖于机器的目标代码。•两阶段工作–对每种语法范畴进行静态语义检查–若语义正确，就进行中间代码的翻译•中间代码形式–四元式、三元式、逆波兰式–注：1）中间代码是为后续的优化和目标代码生成提供方便，因此中间代码的选择往往与所采用的优化技术和计算机硬件结构有关。2）用得最广的是四元式。第一章引论三、编译程序4.优化•任务对产生的中间代码进行加工变换，以期在最后阶段能产生更为高效（省时间、省空间）的目标代码•依据原则：程序的等价变换规则•主要优化内容删除公共子表达式、合并已知量、删除无用赋值语句、循环优化等第一章引论三、编译程序5.目标代码生成•任务：把中间代码程序转化成具体机器的指令序列•注：转换过程需涉及具体机器的指令系统以及寄存器分配等硬件功能。第一章引论三、编译程序6.表格与表格管理•表格作用：–用于记录源程序的各种信息以及编译过程中的各种状况，以便后续阶段使用。•与编译前三阶段有关的表格有：–符号表、常数表、标号表、分程序入口表、中间代码表等。–注：在编译过程中，随着源程序的不断被改造，编译的各阶段常常需要不同的表格，编译过程的绝大多数时间是花在查表、造表和更新表格的事务上。在大多数的编译程序中，表格专门由表格管理程序来处理。•符号表：用来登记源程序中的常量名、变量名、数组名、过程名等的性质、定义和引用状况。NAMEINFORMATIONm整型、变量地址n整型、变量地址k整型、变量地址值14常数表登记各类常量(直接量)值(登记标号的定义与引用)注：标号表可与符号表合并NAMEINFORMATION………….10四元式序号4标号表•入口名表：登记过程的层号，分程序符号表的入口(指分程序结构的语言)等NAMEINFORMATION………….INCWAP二目子程序、四元式序号1中间代码表：记录四元式序列的表序号OPARG1ARG2RESULT（1）＝Im（2）=jn（3）=1k（4）J100k(9)（5）+m10m（6）+n10n（7）+k1k（8）j(4)（9）return第一章引论三、编译程序7.出错处理•任务如果源程序有错误，编译程序应设法发现错误，并报告给用户。注：查错无形式化的办法解决。•完成：由专门的出错处理程序来完成•错误类型:–语法错误:在词法分析和语法分析阶段检测出来。–语义错误：一般在语义分析阶段检测。第一章引论三、编译程序8.遍•遍：指对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标代码的过程。–注：遍与阶段的含义毫无关系。•多遍扫描的好处–节省内存空间，提高目标代码质量，使编译的逻辑结构清晰。•多遍扫描的缺点–编译时间较长。–注：在内存许可情况下，还是遍数尽可能少些为好。语法分析扫描器语义子程序源程序目标代码编译程序一遍扫描（以语法分析为中心）第一章引论四、编译程序生成•1.直接用机器语言编写编译程序•2.用汇编语言编写编译程序–注：编译程序核心部分常用汇编语言编写•3.用高级语言编写编译程序–注：这是普遍采用的方法•4.自编译•5.编译工具:LEX(词法分析)与YACC(用于自动产生LALR分析表)•6.移植（同种语言的编译程序在不同类型的机器之间移植）第一章引论五、编译程序构造•在某机器上为某种语言构造编译程序要掌握：–源语言–目标语言–编译方法第一章引论六、编译原理的学习•注意各章节之间的关联•注意理论联系实际，多实践–实验安排：4次实验，实验内容见附录