单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,编译原理实践及应用,编译原理实践及应用,-,中南大学 肖健宇,编译原理实践及应用-中南大学 肖健宇,20 十一月 2024,第,2,页,教材及主要参考资料,教材：编译原理实践及应用，,黄贤英，清华大学出版社,主要参考资料：,(1),编译原理，,陈火旺，国防工业出版社,(2),程序设计语言编译方法,，,肖军模，大连理工大学出版社,(3),编译原理，,张素琴，,吕映芝,，,清华大学出版社,(4),编译原理，,alfred V.Aho,等著，李建中等译，人民邮电出版社,08 十月 2023第2页教材及主要参考资料教材：编译原理实,20 十一月 2024,第,3,页,序 言,08 十月 2023第3页序 言,20 十一月 2024,第,4,页,C,语言程序,void main(),int x,y,z;,x=3;,y=2;,z=x+y;,什么是编译？,从程序员可以理解的,高级语言,程序,到机器可以理解的,机器语言,程序,的,自动翻译,过程。,08 十月 2023第4页C语言程序void main(),20 十一月 2024,第,5,页,汇编语言程序,mov ax,3,mov x,ax,mov ax,2,mov y,ax,mov ax,x,mov bx,y,add ax,bx,mov z,ax,.,300,302,304,306,308,内存地址,内存内容,单元名字,200H,3,x,：局部变量,201H,2,y,：局部变量,202H,5,z,：局部变量,机器码,08 十月 2023第5页汇编语言程序300内存地址内存,20 十一月 2024,第,6,页,为什么要学习编译原理？,1,、,有助于深刻理解和正确使用程序设计语言，加深对高级语言程序执行过程的理解,2,、有助于加深对整个计算机系统的理解。,3,、设计开发编译程序的软件技术同样可以用于其他软件的设计开发。,4,、随着微处理器技术的飞速发展，处理器性能在很大程度上取决于编译器的质量、编译技术成为计算机的核心技术，地位变得越来越重要。,08 十月 2023第6页为什么要学习编译原理？1、有助于深,20 十一月 2024,第,7,页,编译原理,课程在计算机科学中的重要地位,(1),学习编程最初是学习一门,高级语言,，,C,或,Pascal,，掌握编写一些简单程序的方法；,(2),学习,数据结构,，建立,“,算法,”,的概念，对编程有更深入的理解。遇到问题的时候，能够寻找相应的数据结构模型，设计适当的算法来解决问题；,(3),学习,汇编语言,，这门课程是我们真正深入了解计算机内部工作的第一门课程。通过学习了解汇编语言如何变为机器语言，如何对应于一条指令；,(4),计算机组成原理,课程的学习使我们了解到计算机的硬件组成，以及机器指令程序如何在计算机中运行的过程。,(5),编译原理,课程帮助我们了解高级语言程序转换成机器指令程序的过程。可以帮助我们更深刻地理解高级语言程序运行的内部机制。,08 十月 2023第7页编译原理课程在计算机科学中的重,20 十一月 2024,第,8,页,编译原理,课程在计算机科学中的地位,高级语言程序设计,离散数学,数据结构,编译原理,操作系统,系统软件,应用软件,软件工程,信息系统,电子商务,汇编语言,计算机组成原理,08 十月 2023第8页编译原理课程在计算机科学中的地,20 十一月 2024,第,9,页,学习本课程的目的和任务,加深对编程语言设计和实现的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用，提升自身的编程能力,掌握编译程序的基本结构，掌握常用的编译技术和方法，将编译原理的理论和方法应用于一般的软件设计中,培养团队协作能力,08 十月 2023第9页学习本课程的目的和任务加深对编程语,20 十一月 2024,第,10,页,本课程的特点,(1),本课程理论性很强，学习时需要很强的逻辑思维能力,(2),涉及的算法复杂，要深入地理解这些算法很困难,(3),编译原理课程各个部分之间的独立性很强，包括词法分析、语法分析、存储的组织与分配、中间语言、语法制导翻译、代码生成与优化这几大部分。词法分析、及语义分析是重点；其他部分相对来说知识性更强一些。,08 十月 2023第10页本课程的特点(1)本课程理论性,引 论,第一章,引 论第一章,20 十一月 2024,第,12,页,本章要求,主要内容,：,各种翻译程序的概念，编译过程和阶段划分，编译程序的组成和结构，编译程序的构造方法,重点掌握：,编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。,08 十月 2023第12页本章要求主要内容：各种翻译程序的,20 十一月 2024,第,13,页,问题：,1.,什么是编译程序？,2.,编译程序的工作过程是什么样的？,3.,编译程序的总体结构是什么样的？,4.,什么叫编译前端、编译后端？,5.,什么叫“遍”（,pass,）？,6.,编译程序有哪些生成方法？,08 十月 2023第13页问题：,20 十一月 2024,第,14,页,编译程序（,Compiler,）,将高级程序设计语言程序翻译成逻辑上等价的低级语言,(,汇编语言,机器语言,),程序的翻译程序。,功能,编译程序,源程序,目标程序,计算机运行,输入数据,结果,1.1,编译程序是什么,08 十月 2023第14页编译程序（Compiler）,20 十一月 2024,第,15,页,计算机中的语言层次和转换关系,08 十月 2023第15页计算机中的语言层次和转换关系,20 十一月 2024,第,16,页,解释程序,解释程序（,Interpreter,）,将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。,功能,解释程序,源程序,输入数据,结果,08 十月 2023第16页解释程序解释程序（Interpr,20 十一月 2024,第,17,页,编译程序的分类,诊断编译程序,优化编译程序,可变目标编译程序,交叉编译程序,08 十月 2023第17页编译程序的分类诊断编译程序,20 十一月 2024,第,18,页,与编译程序相关的程序,解释程序,(Interpreter),汇编程序,(assembler),连接程序,(linker),连接系统函数与系统资源,装入程序,(loader),重定位,(relocation),预处理器,(Preprocessor),编辑器,(editor),Debugger,Profiler,Project Manager,08 十月 2023第18页与编译程序相关的程序解释程序(I,20 十一月 2024,第,19,页,编译原理是讨论编译程序设计的基本理论、基本概念、基本方法,什么是编译原理,08 十月 2023第19页编译原理是讨论编译程序设计的基本,20 十一月 2024,第,20,页,1.2,编译过程概述,逻辑上分五个阶段：,词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。,每个阶段把源程序从一种表示变换成另一种表示。,词法,分析,语法分析,语义分析与中间代码生成,代码优化,目标代码生成,08 十月 2023第20页1.2 编译过程概述逻辑上分五,编译过程和英文翻译过程对比,把英文翻译为中文,识别出句子中的一个个单词；,分析句子的语法结构；,根据句子的含义进行初步翻译；,对译文进行修饰；,写出最后的译文。,词法分析,语法分析,中间代码产生,优化,目标代码产生,编译过程和英文翻译过程对比把英文翻译为中文 词法分析语法分析,20 十一月 2024,第,22,页,第一阶段：词法分析,任务,:,从左到右扫描源程序，识别出每个单词,附加任务：,a,、滤掉空格,b,、识别单词,单词符号是语言的基本组成成分,词法分析的工作主要依据语言的,词法规则,，描述词法规则的有效工具是,正规式和有限自动机,。,08 十月 2023第22页第一阶段：词法分析任务:从左到右,20 十一月 2024,第,23,页,begin,result:=5,B*C,B*C,end;,单词,类型,内部形式,begin,关键字,$begin,result,标识符,id,1,:=,界符,:=,5,常数,int,1,+,算符,+,B,标识符,id,1,*,算符,*,C,标识符,id,2,+,算符,+,B,标识符,id,2,*,算符,*,C,标识符,id,3,end,关键字,$end,;,界符,;,例,:,08 十月 2023第23页begin单词类型内部形式beg,20 十一月 2024,第,24,页,第二阶段：语法分析,任务,:,在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语,(,例：程序、语句、表达式,),。,确定整个输入串是否构成语法上正确的程序。,语法分析所依据的是语言的语法规则，表示语法规则的工具是上下文无关文法，用下推自动机实现。,08 十月 2023第24页第二阶段：语法分析任务:,20 十一月 2024,第,25,页,id1:=int1+id2*id3+id2*id3,例：识别符号串,id,1,:=int,1,+id,2,*id,3,+id,2,*id,3,（即,result:=5,B*C,B*C,）,是一个赋值语句。,08 十月 2023第25页id1:=int1+id2,20 十一月 2024,第,26,页,第三阶段：语义分析和中间代码生成,任务,：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译,(,翻译成中间代码,),。,静态语义审查,变量定义,类型匹配,类型转换,例：,C:=A*B(,检查,C,与、类型,),中间代码的翻译,中间代码有多种形式，如：,四元式,:(,运算符，运算对象,1,，运算对象,2,，结果,),08 十月 2023第26页第三阶段：语义分析和中间代码生成,20 十一月 2024,第,27,页,例：,对赋值语句：,id,1,:=int,1,+id,2,*id,3,+id,2,*id,3,1.,检查,result,、,C,是否定义类型,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,08 十月 2023第27页例：对赋值语句：id1:=in,20 十一月 2024,第,28,页,第四阶段：代码优化,任务,：对已产生的中间代码进行加工变换，使生成的目标代码更为高效,(,时间和空间,),。,优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。,代码的优化依据的是程序的等价变换规则。,08 十月 2023第28页第四阶段：代码优化任务：对已产,20 十一月 2024,第,29,页,序号,四元式,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,),例：,08 十月 2023第29页序号四元式1(*,id2,i,20 十一月 2024,第五阶段：目标代码的生成,任务,：把中间代码,(,或经优化的中间代码,),变换成,特定,机器上的低级语言代码。,依赖于机器的硬件系统结构和机器指令的含义,目标代码可以是：绝对指令代码、可重定位的指令代码、汇编指令代码,08 十月 2023第五阶段：目标代码的生成任务：把中间代码,20 十一月 2024,第,31,页,第,31,页,序号,四元式,1,(*,id,2,id,3,T1),2,(+,int,1,T1,T2),3,(+