编译原理第1章

《编译原理第1章》由会员分享，可在线阅读，更多相关《编译原理第1章（38页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理,程序设计语言,第一章 引论,1.1,什么叫编译程序,1.2,编译过程概述,1.3,编译程序的结构,1.4,编译程序与程序设计环境（略）,1.5,编译程序的生成,1.,什么是编译程序？,1.1,什么叫编译程序,翻译程序,：一种语言程序,-,-,另一种语言程序,源语言,目标语言,编译程序,：高级语言程序,-,-,低级语言程序,汇编程序,：汇编语言程序,-,-,机器语言程序,解释程序,：源语言程序,-,-,边解释边执行,（,1,）编译方式：先编译后执行。,（,2,）解释方式：,以源程序作为输入，但,不产

2、生目标代码,，而,是,边解释边执行,源程序本身。,2.,“,高级语言程序,”,的执行方式,1.1,什么叫编译程序,编译和解释的主要区别：,是否产生目标代码！,b:=3;,a:=b+3;,write a;,编译程序,解释程序,MOV#3.0 R1,MOV R1 b,MOV b R2,ADD R1 R2,MOV R1 a,直接将,6,输出显示,3.,“,编译程序”在计算机系统中的位置较接近于“硬件”,1.1,什么叫编译程序,4.,发展,20,世纪,50,年代 第一个编译程序,FORTRAN,编译程序,目前：编译原理与技术得到迅速发展，现已形成一套比较成熟的系统化的理论与方法，并开发出了一些好的编译

3、程序的实现语言、环境与工具。,当时普遍认为设计和实现编译程序是一件十分困难、令人生畏的事情,1.1,什么叫编译程序,编译技术是计算机科学中发展最迅速、最成熟的一个重要分支，集中体现了计算机科学发展的重要成果与精华。,通过本课程的学习，一方面要理解、掌握编译系统的结构、工作流程以及编译程序各组成部分的设计原理和实现技术，获得分析、设计、实现和维护编译系统的初步能力；另一面，通过学习编译的理论和方法，提高对程序设计语言、操作系统、计算机原理和体系结构等课程知识的综合理解。,1.2,编译过程概述,The elephant ate an banana.,什么是语言？,for K:=1 to 100 d

4、o,begin,M:=I+10*K;,N:=J+10*K,end,一,.,类比自然语言翻译和编译过程,英汉 编译的工作过程,1),识别单词,词法分析,2),分析句子语法结构,语法分析,3),根据句子含义初步翻译,语义分析与中间代码产生,4),修饰译文,优化,5),写出最后译文,目标代码生成,1.2,编译过程概述,1.,词法分析,for K:=1 to 100 do,begin,M:=I+10*K;,N:=J+10*K,end,基本字,for,标识符,K,赋值号,:=,常数,1,基本字,to,常数,100,基本字,do,基本字,begin,.,.,1.2,编译过程概述,词法分析,规则：,规则描述

5、工具：,任务：,依循词法规则,.,正规式和有限自动机（,FA,）,.,输入源程序,，对构成源程序的字符串进行扫描和分解，,识别出一个个的单词符号,，如基本字、标识符、常数、算符、界符等。,1.2,编译过程概述,2.,语法分析,for K:=1 to 100 do,begin,M:=I+10*K;,N:=J+10*K,end,规则：,规则描述工具：,任务：,依循语法规则,.,上下文无关文法,.,在词法分析的基础上，根据语言的语法规则，对单词符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的,“,程序,”,。,1.2,编译过程概述,3.,语义分析和中间代码产生,规则：,规则

6、描述工具：,任务：,语义规则,属性文法,两部分工作：,1.,对每种语法范畴进行,静态语义检查,;,2.,若语义正确，则进行,中间代码翻译,.,对语法分析器识别出的各类语法单位，分析其含义并进行初步翻译（产生,中间代码,）。,中间代码：一种独立于具体硬件的记号系统，更接近于机器代码,1.2,编译过程概述,for K:=1 to 100 do,begin,M:=I+10*K;,N:=J+10*K,end,；,K:=1,L,1,:if 100K goto L,2,T,1,:=10*K,M:=I+T,1,T,2,:=10*K,N:=J+T,2,K:=K+1,goto L,1,L,2,:,语义分析后产生

7、的中间代码：,三地址代码,具体实现：,三元式，四元式，间接三元式,1.2,编译过程概述,K:=1,L,1,:if 100K goto L,2,T,1,:=10*K,M:=I+T,1,T,2,:=10*K,N:=J+T,2,K:=K+1,goto L,1,L,2,:,序号,OP,ARG1,ARG2,RESULT,(1),(2),(3),(4),(5),(6),(7),(8),(9),:=,j,*,+,*,+,+,j,1,100,10,I,10,J,K,K,K,T,1,K,T,2,1,K,(9),T,1,M,T,2,N,K,(2),四元式序列：,1.2,编译过程概述,任务：,对中间代码进行加工变换

8、，以期在最后阶段,能产生出更为,高效（省时间和空间）,的目标,代码。,4.,优化,包括：公共子表达式的提取、循环优化、删除无用代码等,1.2,编译过程概述,序号,OP,ARG1,ARG2,RESULT,(1),(2),(3),(4),(5),(6),(7),(8),(9),:=,j,*,+,*,+,+,j,1,100,10,I,10,J,K,K,K,T,1,K,T,2,1,K,(9),T,1,M,T,2,N,K,(2),序号,OP,ARG1,ARG2,RESULT,(1),(2),(3),(4),(5),(6),(7),(8),(9),:=,:=,:=,j,+,+,+,j,I,I,1,100,

9、M,N,K,K,10,10,1,M,N,K,(9),M,N,K,(2),优化前,优化后,1.2,编译过程概述,任务：,把中间代码变换成,特定机器上,的低级语言代码，,实现最后的翻译。,5.,目标代码生成,绝对指令代码,/,可重定位的指令代码,/,汇编指令代码,有赖于硬件系统结构和机器指令含义,1.2,编译过程概述,1.3,编译程序的结构,一,.,编译程序总框图,1.,表格管理,编译各阶段都要涉及到构造、查找或 更新有关表格,。,表格的作用：,登记源程序的,各类信息,和编译,各阶段的进展状况,。,符号表：,用来登记源程序中出现的每个,名字,以及,名字的各种属性,。,举例：,名字,变量名,/,常量

10、名,/,过程名,？,变量名,类型？,/,内存？,/,地址？,1.3,编译程序的结构,2.,出错处理,每一阶段都可能检测出错误，绝大多 数错误可在前三阶段检测出来,.,任务：,设法发现错误，并把有关错误信息报告给用户,.,语法错误,：源程序中不符合语法,/,词法规则的错误。,词法,/,语法分析时检测,语义错误,：源程序中不符合语义规则的错误。,语义分析,/,运行时检测出来,1.3,编译程序的结构,二,.,遍,1.,编译过程的划分：,上述划分的五个阶段仅仅是,逻辑功能,上的一种划分,2.,遍（,Pass,）,对源程序或源程序的中间结果,从头到尾,扫描一次，并作有关的加工处理，生成,新的,中间结果或

11、目标程序。,具体实现时，受各方面（如源语言、设计要求等）限制，往往组织成若干遍,1.3,编译程序的结构,3.,注意：,既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍,例如：,词法分析,+,语法分析,一遍,语法分析,+,语义分析与中间代码产生,一遍,优化,若干遍,单遍代码不太有效。,根据系统资源的状况、运行目标的要求等，可以将一个编译程序设计形成多遍扫描的形式，在每一遍扫描中完成不同的任务。,1.3,编译程序的结构,当一遍中包含若干阶段时，各阶段的工作是穿插进行的,。,例如：,识别出一个语法单位时,语法分析器,词法分析器,语义分析和中间代码产生器,识别语法结构需要下一个单词时,单

12、词符号,1.3,编译程序的结构,三,.,编译前端与后端,1,、前端：,由与源语言,有关,但与目标机,无关,的那些部分组成,包括,词法分析、语法分析、语义分析与中间代码,产生、部分代码优化工作,2,、后端：,包括编译程序中与目标机,有关,的那些部分，如与,目标机有关的代码优化和目标代码生成等。,不依赖于源语言而仅仅,依赖于中间语言,1.3,编译程序的结构,1.5,编译程序的生成,一,.,设计目标,目标程序小，执行速度快,编译程序小，执行速度快,诊断能力强，可靠性强,可移植性，可扩充性,如何实现编译器？,直接用可运行,的代码编制,太费力！,1.5,编译程序的生成,以汇编语言和机器语言为工具,优点,

13、:,可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。,缺点,:,程序难读、难写、易出错、难维护、生产的效率低。,五,.,编译程序生成,高级语言书写,优点,:,程序易读、易理解、容易维护、生产的效率高。,缺点,:,难以充分发挥计算机的系统功能，生成的程序效率低。,1.5,编译程序的生成,2,、问题,（,1,）历史上第一个高级语言的编译程序是怎样构造的？,-,自编译技术（自展技术）,（,2,）已有,A,机器上的,L1,语言（如：,C,语言）的编译程序，如何构造,A,机器上的,L2,语言（如：,PASCAL,语言）的编译程序？,（,3,）已有,A,机器上的,L,语言的编译程序，如何构

14、造,B,机器上的,L,语言的编译程序？,-,交叉编译,/,移植,ST,I,源语言,编译程序实现语言,目标语言,一般采用基于,T,形图的方式：,表现语言翻译的,T,形图,1.5,编译程序的生成,高级语言书写,利用已有的某种语言的编译程序实现另一语言的编译程序。,L1,语言,A,代码,P1:,A,代码,L2,语言,A,代码,P2:,L1,语言,L2,语言,A,代码,P2:,A,代码,同一台机器,不同的语言,1.5,编译程序的生成,移植方法,把一种机器上的编译程序移植到另一种机器上。,L,语言,A,代码,P1:,A,代码,L,语言,B,代码,P2:,L,语言,L,语言,B,代码,P2:,A,代码,L

15、,语言,B,代码,P2:,L,语言,L,语言,B,代码,P2:,B,代码,同一种语言不同的机器,1.5,编译程序的生成,L,1,+L,2,+.+L,n,L,1,+L,2,自展技术,L,1,1.5,编译程序的生成,编译程序自动产生,编译程序,-,编译程序，编译程序书写系统,LEX,词法分析程序产生器,YACC,语法分析程序产生器,编译程序,自动产生器,L,语言的语法描述,语义描述,目标语言,或机器描述,L,语言的,编译程序,1.5,编译程序的生成,1.5,编译程序的生成,三,.,如何学习构造编译程序,要在某一台机器上为某种语言构造一个编译程序，必须掌握以下内容：,源语言,：,对被编译的源语言，要深刻理解其结构（语法）和,含义（语义）。,目标语言,：,假定目标语言是机器语言，那么，就必须搞清硬,件的系统结构和,OS,的功能。,编译方法,：,把一种语言程序翻译为另一种语言程序的方法很,多，但必须准确的掌握一、二。,关于学习编译原理,意义,:,学习编译程序构造原理，技术,更好地理解高级语言,编译的原理和方法有助于构造一些实用的工具,第,1,章 总结,1.,编译程序的概念,2.,编译过程（掌握）,3.,基本概念：遍，编译前端,/,后端（掌握）,4.T,型图（了解）,