CHAPTER 1(编译概述 Introduction to Compiling).ppt

30.05.2020,1,PrincipleofCompiler（编译原理）,30.05.2020,2,课程主要内容编译器（compiler）构造的原理、技术和实践：编译的基本理论，形式文法与形式语言编译器实现技术,课程介绍,30.05.2020,3,前导课程高级语言程序设计、离散数学、数据结构和汇编语言：C/PASCAL/FORTRAN/ALGOL数据结构汇编语言,课程介绍,30.05.2020,4,教材：Compiler:Principles,Techniques,andTools,教材,该书由三位世界著名的计算机科学家联合编写，是编译领域无可替代的经典著作，被誉为“龙书”。书中深入讨论了编译器设计的重要主题，在介绍编译器一般原理的同时，特别注重编译原理和技术的实际应用，并在最后给出了几个编译器的实例，此外，本书的每一章都提供了大量的习题和参考文献。本书一直被国外著名大学特别是美国的著名大学当作编译原理与技术课程的教材。,30.05.2020,5,Chapter1IntroductiontoCompiling,编译器概念（ConceptionofCompiler）编译的阶段（PhasesofCompiler）编译器的结构（FrameworkofCompiler）编译器的实现（ImplementationofCompiler）编译器的伙伴（CousinsofCompiler）,30.05.2020,6,1.1编译器概念,编译程序是现代计算机系统的基本组成部分：,操作系统,编译系统,裸机,计算机系统,30.05.2020,7,1.1编译器概念,从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言-sourcelanguage）书写的程序翻译成另一种语言（称作目标语言-targetlanguage）书写的等价的程序。,30.05.2020,8,1.1编译器概念,ACompiler,30.05.2020,9,1.1编译器概念,源语言和目标语言是多种多样的一般来说，源语言是面向人的高级语言，目标语言是面向机器的低级语言（机器语言）编译器执行的是一个等价变换，程序功能一样，执行结果一样要考虑时间与空间效率,30.05.2020,10,1.1编译器发展历史,1940s没有编译器，手写机器代码1950s初期第一个编译器诞生(G.M.Hopper)1950s晚期FORTRAN诞生,30.05.2020,11,30.05.2020,12,1960s,ALGOL60第一个具有形式文法的语言。语法制导编译器诞生(1961).PASCAL诞生(Wirth,1968).形式语言理论,30.05.2020,13,1970s以后,C语言诞生(1972).作为UNIX操作系统的一部分发布。BASIC诞生(1975).,30.05.2020,14,1.2编译的阶段,编译的分析-综合模型（Analysis-SynthesisModelofCompilation）分析：分析源程序，计算其基本属性，生成源程序的中间表示（intermediaterepresentation）综合：将源程序的中间表示转换为目标代码,30.05.2020,15,1.2编译的阶段,编译的逻辑过程词法分析（LexicalAnalysis）语法分析（SyntaxAnalysis）语义分析（SemanticAnalysis）中间代码生成（IntermediateCodeGeneration）代码优化（CodeOptimization）目标代码生成（CodeGeneration）,30.05.2020,16,1.2编译的阶段,词法分析（LexicalAnalysis）功能：从左至右读源程序（字符流），识别单词符号（又称记号token）源程序字符序列单词符号序列词法分析又称线性分析或扫描（LinearAnalysis，Scanning）,30.05.2020,17,例：position=initial+rate*60,单词类型单词值标识符1(id1)position算符(赋值)=标识符2(id2)initial算符(加)+标识符3(id3)rate算符(乘)*整数60,30.05.2020,18,1.2编译的阶段,语法分析（SyntaxAnalysis）功能：层次分析（HierarchicalAnalysis）依据：源程序的语法规则单词符号序列分析树（ParseTree）（或语法树-SyntaxTree）语法分析又称解析（Parsing）,30.05.2020,19,例：position=initial+rate*60,ParseTree,30.05.2020,20,例：position=initial+rate*60,*语法树是分析树的压缩表示,30.05.2020,21,1.2编译的阶段,语义分析（SemanticAnalysis）功能：语义检查，即验证语法结构合法的程序是否在语义上正确（程序的各个组成部分组合在一起是否有意义）。收集代码生成阶段需要的语义信息类型检查与类型转换分析树带语义（注释）的树,30.05.2020,22,例：position=initial+rate*60,=,+,60,*,position,initial,rate,inttoreal,30.05.2020,23,1.2编译的阶段,中间代码生成（IntermediateCodeGeneration）功能：生成源程序的中间表示。三地址代码（threeaddress-code）带语义（注释）的树中间代码,30.05.2020,24,例：position=initial+rate*60,中间代码：(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1),30.05.2020,25,1.2编译的阶段,代码优化（CodeOptimization）功能：对中间代码进行优化（提高时间与空间效率）,30.05.2020,26,例：position=initial+rate*60,代码优化：(1)(inttoreal，60-t1)(2)(*，id3t1t2)(3)(+，id2t2t3)(4)(:=，t3-id1)（1）(*，id360.0t1)（2）（+，id2t1id1),30.05.2020,27,1.2编译的阶段,代码生成（CodeGeneration）功能：生成目标代码机器代码（machinecode）、可重定位的机器代码（relocatablemachinecode）、汇编语言代码（assemblycode）,30.05.2020,28,例：position=initial+rate*60,(*,id360.0t1)(+,id2t1id1),movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1,目标代码生成,30.05.2020,29,1.2编译的阶段,符号表管理（Symbal-TableManagement）功能：管理分析过程中得到的源程序中的标识符的各种信息记录源程序中使用的标识符（identifier）收集每个标识符的各种属性（attribute）信息，包括类型（type）、作用域（scope）、存储分配（storageallocated）信息,30.05.2020,30,1.2编译的阶段,出错处理（ErrorDetectionandReporting）功能：检查错误的位置检查错误的性质（词法、语法、语义）错误恢复,30.05.2020,31,1.2编译的阶段,一个例子语句的完整编译过程见Fig.1-7,30.05.2020,32,1.3编译器的结构,编译器结构,30.05.2020,33,1.3编译器的结构,前端（Frontend）与后端（Backend）把编译程序分成前端和后端两部分前端：只依赖于源程序，独立于目标机器生成中间代码后端：依赖于目标机器，与源程序无关，只与中间语言有关从中间代码生成目标代码,30.05.2020,34,1.3编译器的结构,好处：提高开发编译器的效率取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）,30.05.2020,35,1.3编译器的结构,遍（Pass）对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示,30.05.2020,36,1.3编译器的结构,每一遍的输入是上一遍的输出，第一遍的输入是源程序正文，最后一遍的输出是目标代码遍数多：编译器结构清晰，但时间效率不高遍数少：编译速度快，但对机器的内存要求高,30.05.2020,37,1.4编译器的实现,世界上第一个编译程序是用什么语言书写的？用高级语言书写？没有编译器，如何编译？因此世界上第一个编译器只能是用机器语言开发的,30.05.2020,38,1.4编译器的实现,1、开发高级语言的编译器自展技术直接用目标机器上的机器语言书写源语言的编译程序工作量太大用目标机器上的机器语言书写源语言的一个子集的编译程序，然后再用这个子集作为书写语言，实现源语言的编译程序，这就是自展技术。,30.05.2020,39,1.4编译器的实现,2、用已有高级语言实现其它高级语言的编译程序:用语言L的编译器编译用L书写的另一高级语言的编译器例如，用C写PASCAL语言的编译器，然后编译,30.05.2020,40,1.4编译器的实现,编译器的构造工具词法分析器自动生成程序LEX,30.05.2020,41,1.4编译器的实现,编译器的构造工具语法分析器自动生成程序YACC,30.05.2020,42,1.5编译器的伙伴,一个语言处理系统Fig.1-5,30.05.2020,43,1.5编译