编译原理实践及应用第1章编译原理概述

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,编译原理实践及应用,主讲人：董明刚,03 十一月 2024,第,2,页,教材及主要参考资料,教材,：编译原理实践及应用，,黄贤英，清华大学出版社,主要参考资料：,编译原理，,陈火旺，国防工业出版社,编译原理,(,原书第,2,版,)(,龙书,),，,ALFRED V.AHO etc,著，赵建华 郑滔等译，机械工业出版社,2008.12,程序设计语言编译方法,，,肖军模，大连理工大学出版社,编译原理，,张素琴，,吕映芝,，,清华大学出版社,更多教材及参考资料参见,编译原理精品课程网站,。,C,语言程序,void main(),int x,y,z;,x=3;,y=2;,z=x+y;,内存地址,内存内容,单元名字,200H,3,x,：局部变量,202H,2,y,：局部变量,204H,5,z,：局部变量,300H,3A03,302H,3AE1,304H,3A02,306H,3AE2,308H,DA6C,.,3A71,汇编语言程序,mov ax,3,mov x,ax,mov bx,2,mov y,bx,add ax,bx,mov z,ax,.,序言,在内存中：,数据区,代码区,？,编译原理概述,第一章,03 十一月 2024,第,5,页,本章要求,主要内容,：,各种翻译程序的概念，编译过程和阶段划分，编译程序的组成和结构，编译程序的构造方法,重点掌握：,编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。,03 十一月 2024,第,6,页,1.1,程序设计语言与翻译程序,机器语言,(machine language),C7 06 0000 0002,汇编语言,(assembler language),MOV X,2,高级语言,(high-level language),X=2,为什么要使用编译程序？,03 十一月 2024,第,7,页,机器语言,(machine language),C7 06 0000 0002,汇编语言,(assembler language),MOV X,2,高级语言,(high-level language),X=2,为什么要使用编译程序？,03 十一月 2024,第,8,页,计算机中的语言层次和翻译程序,03 十一月 2024,第,9,页,什么叫翻译程序,翻译程序,：,能够将某种语言写的程序转换成另一种语言的程序，而且后者与前者在逻辑上是,等价,的。,编译程序,：,将高级程序设计语言程序翻译成逻辑上等价的低级语言,(,汇编语言,机器语言,),程序的翻译程序。,解释程序,：,将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。,03 十一月 2024,第,10,页,高,级,语,言,语言处理程序,操作系统,汇编语言,翻译程序所处的层次,计算机硬件,C,编译程序,C,语,言,Basic,解释程序,Basic,语言,Fortran,编译程序,Fortran,语言,.,.,.,.,.,.,.,.,.,.,.,.,03 十一月 2024,第,11,页,编译程序,编译程序,源程序,目标程序,计算机运行,输入数据,结果,解释程序,解释程序,源程序,输入数据,结果,03 十一月 2024,第,12,页,对编译程序的一些说明,编译程序实质上是一个,翻译程序,，要注意,等价,变换,本课程的,任务,就是讲解在这个转换过程中所涉及到的一些理论和方法，最后，使用这些理论和方法，自己编写一个小的编译器,转换是一个总体的功能，要抓住总体结构，逐层细分，写编译器时要体现软件工程中,软件设计的原则,，自顶向下，逐层分解。,编译器要完成的转换任务相当复杂，实现编译器时必须,分步骤分阶段,实现。分阶段实现的好处是能够,简化程序的设计,，当然也可以不分阶段实现。,03 十一月 2024,第,13,页,编译程序的分类,诊断编译程序,优化编译程序,可变目标编译程序,交叉编译程序,03 十一月 2024,第,14,页,编译器的伙伴,编辑器,(editor),预处理器,(Preprocessor),将源程序汇集到一起，宏展开等,汇编程序,(assembler),连接程序,(linker),连接系统函数与系统资源,装入程序,(loader),重定位,(relocation),Debugger,Profiler,Project Manager,03 十一月 2024,第,15,页,编译原理是讨论编译程序设计的基本理论、基本概念、基本方法,什么是编译原理,03 十一月 2024,第,16,页,1.2,编译过程概述,1,、,逻辑上分五个阶段：,词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成,每个阶段把源程序从一种表示变换成另一种表示,词法,分析,语法分析,语义分析与中间代码生成,代码优化,目标代码生成,03 十一月 2024,第,17,页,按照词法分析、语法分析、语义分析等这种方式来划分阶段的原因是：每个阶段的复杂程度不同，所依据的,理论基础不同,，实现时采用的,方法也不同,。主要是方便理解和实现。,划分阶段的依据是什么？每个阶段所实现的,功能相对独立,。,用一个例子说明各阶段的功能,03 十一月 2024,第,18,页,/*,一个,PASCAL,语言的源程序*,/,program test;,/*this is an example,computing an area*/,var area,length,width:integer;,begin,length:=5;width:=5;,area:=5,length*width,length*width,end.,03 十一月 2024,第,19,页,第一阶段：词法分析,任务,:,从左到右扫描源程序，识别出每个单词,附加任务：,a,、滤掉空格,b,、去掉注释,单词符号是语言的基本组成成分,词法分析的工作主要依据语言中单词的构成规则,单词的种类：,（,1,）标识符,（,2,）关键字（,char,、,int,、,if,、,else,、,while,、,for,等）,（,3,）运算符（即运算符号,+,、*、,/,、,&,等）,（,4,）界符（常见的有 ；，：（）等）,（,5,）常数,03 十一月 2024,第,20,页,begin,area:=5,length*width,length*width,end;,单词,类型,内部形式,begin,关键字,$begin,area,标识符,id,1,:=,界符,:=,5,常数,int,1,+,算符,+,length,标识符,id,1,*,算符,*,width,标识符,id,2,+,算符,+,length,标识符,id,2,*,算符,*,width,标识符,id,3,end,关键字,$end,;,界符,;,例,:,03 十一月 2024,第,21,页,第二阶段：语法分析,任务,:,在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语,(,例：程序、语句、表达式,),。,确定整个输入串是否构成语法上正确的程序。,根据规则判定：,赋值语句：,标识符,:,表达式,表达式：,标识符、常数是表达式,表达式的运算也是表达式,例：识别符号串,id,1,:=int,1,+id,2,*id,3,+id,2,*id,3,是一个赋值语句（,area:=5,length*width,length*width,）,而,int,1,+id,2,*id,3,+id,2,*id,3,是一个表达式,（,5,length*width,length*width,）,03 十一月 2024,第,22,页,语法分析所依据的是语言的语法规则,id1:=int1+id2*id3+id2*id3,03 十一月 2024,第,23,页,第三阶段：语义分析和中间代码生成,任务,：对语法分析所识别出的各类语法短语分析其含义，进行初步的翻译,(,翻译成中间代码,),。,静态语义审查,变量定义,类型匹配,类型转换,例：,C:=A*B(,检查,C,与、类型,),中间代码的翻译,中间代码有多种形式，如：,四元式,:(,运算符，运算对象,1,，运算对象,2,，结果,),03 十一月 2024,第,24,页,例：,对赋值语句：,id,1,:=int,1,+id,2,*id,3,+id,2,*id,3,1.,检查,area,、,length,、,width,是否定义、类型,2.,生成中间代码,(,运算符，运算对象,1,，运算对象,2,，结果,),(*,id,2,id,3,T1),(+,int,1,T1,T2),(*,id,2,id,3,T3),(+,T2,T3,T4),(:=,T4,_,id,1,),id,1,:=int,1,+id,2,*id,3,+id,2,*id,3,03 十一月 2024,第,25,页,第四阶段：代码优化,任务,：对已产生的中间代码进行加工变换，使生成的目标代码更为高效,(,时间和空间,),。,优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。,代码的优化依据的是程序的等价变换规则。,序号,四元式,1,(*,id,2,id,3,T1),2,(+,int,1,T1,T2),3,(*,id,2,id,3,T3),4,(+,T2,T3,T4),5,(:=,T4,_,id,1,),序号,四元式,1,(*,id,2,id,3,T1),2,(+,int,1,T1,T2),3,(+,T2,T1,id,1,),03 十一月 2024,第,26,页,第五阶段：目标代码的生成,任务,：把中间代码,(,或经优化的中间代码,),变换成,特定,机器上的低级语言代码。,依赖于机器的硬件系统结构和机器指令的含义,目标代码可以是：绝对指令代码、可重定位的指令代码、汇编指令代码,序号,四元式,1,(*,id,2,id,3,T1),2,(+,int,1,T1,T2),3,(+,T2,T1,id,1,),（,1,）,mov AX,id,2,（,2,）,mul AX,id,3,（,3,）,mov BX,AX,（,4,）,add AX,int,1,（,5,）,add AX,BX,（,6,）,mov id,1,AX,03 十一月 2024,第,27,页,1.2,编译程序的结构,由左图可以看出，词法分析是实现编译器的基础，语法分析是实现编译器的关键。,因此按照这个顺序来实现编译器,每一步的实现都依赖于一定的理论基础。,数学，尤其是离散数学是程序设计方法学的理论基础,03 十一月 2024,第,28,页,编译阶段的组合,几个概念,遍：,对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。,编译前端,：,主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化,编译后端,：,指与目标机器有关的部分。如与机器有关的优化、目标代码生成,03 十一月 2024,第,29,页,编译阶段的组合,03 十一月 2024,第,30,页,为什么生成中间代码,03 十一月 2024,第,31,页,编译程序中的主要数据结构,(,续,),Token,表,符号表,常数表,错误信息,语法树,中间代码表,临时文件,目标代码表,03 十一月 2024,第,32,页,(1)Token,表,当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。,(2),语法树（,syntax tree,）,如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。,编译程序中的主要数据结构介绍,: