《编译概述》PPT课件.ppt

2019/5/16,1,Principle of Compiler （编译原理）,2019/5/16,2,课程主要内容 编译器（compiler）构造的原理、技术和实践： 编译的基本理论，形式文法与形式语言 编译器实现技术 编程实现一个小型语言的编译器,课程介绍,2019/5/16,3,前导课程 高级语言程序设计、离散数学、数据结构和汇编语言： C、PASCAL、FORTRAN、ALGOL 图论 各种数据结构及实现 汇编语言代码格式,课程介绍,2019/5/16,4,教材： Compiler: Principles, Techniques, and Tools,教材与参考书,该书由三位世界著名的计算机科学家联合编写，是编译领域无可替代的经典著作，被誉为“龙书”。书中深入讨论了编译器设计的重要主题，在介绍编译器一般原理的同时，特别注重编译原理和技术的实际应用，并在最后给出了几个编译器的实例，此外，本书的每一章都提供了大量的习题和参考文献。本书一直被国外著名大学特别是美国的著名大学当作编译原理与技术课程的教材。,2019/5/16,5,参考书： 陈火旺等，编译原理，电子工业出版社，2000 。 杜淑敏等，编译程序设计原理，北京大学出版社，1990.11。,教材与参考书,2019/5/16,6,Chapter1 Introduction to Compiling,编译器概念（Conception of Compiler ） 编译的阶段（Phases of Compiler ） 编译器的结构（Framework of Compiler ） 编译器的实现（Implementation of Compiler ） 编译器的伙伴（Cousins of Compiler ）,2019/5/16,7,1.1 编译器概念,编译程序是现代计算机系统的基本组成部分：,操作系统,编译系统,硬件,计算机系统,2019/5/16,8,1.1 编译器概念,从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言-source language）书写的程序翻译成另一种语言（称作目标语言-target language）书写的等价的程序。,2019/5/16,9,1.1 编译器概念,A Compiler,2019/5/16,10,1.1 编译器概念,源语言和目标语言是多种多样的 一般来说，源语言是面向人的高级语言，目标语言是面向机器的低级语言（机器语言） 编译器执行的是一个等价变换，程序功能一样，执行结果一样 要考虑时间与空间效率,2019/5/16,11,1.2 编译的阶段,编译的分析-综合模型 （Analysis-Synthesis Model of Compilation） 分析：分析源程序，计算其基本属性，生成源程序的中间表示（intermediate representation） 综合：将源程序的中间表示转换为目标代码,2019/5/16,12,1.2 编译的阶段,编译的逻辑过程 词法分析（Lexical Analysis） 语法分析（Syntax Analysis） 语义分析（Semantic Analysis） 中间代码生成（Intermediate Code Generation） 代码优化（Code Optimization） 目标代码生成（Code Generation）,2019/5/16,13,1.2 编译的阶段,词法分析（Lexical Analysis） 功能：从左至右读源程序（字符流），识别单词符号（又称记号token） 源程序字符序列 单词符号序列 词法分析又称线性分析或扫描（Linear Analysis，Scanning）,2019/5/16,14,例：position := initial + rate * 60,单词类型 单词值 标识符1(id1) position 算符(赋值) := 标识符2(id2) initial 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60,2019/5/16,15,1.2 编译的阶段,语法分析（Syntax Analysis） 功能：层次分析（Hierarchical Analysis） 依据：源程序的语法规则 （例：P 6-7） 单词符号序列 分析树（Parse Tree）（或语法树-Syntax Tree） 语法分析又称解析（Parsing）,2019/5/16,16,例：position := initial + rate * 60,Parse Tree,2019/5/16,17,例：position := initial + rate * 60,* 语法树是分析树的压缩表示,2019/5/16,18,1.2 编译的阶段,语义分析（Semantic Analysis） 功能：语义检查，即验证语法结构合法的程序是否在语义上正确（程序的各个组成部分组合在一起是否有意义）。 收集代码生成阶段需要的语义信息 类型检查与类型转换 分析树 带语义（注释）的树,2019/5/16,19,例：position := initial + rate * 60,:=,+,60,*,position,initial,rate,inttoreal,2019/5/16,20,1.2 编译的阶段,中间代码生成 （Intermediate Code Generation） 功能：生成源程序的中间表示。 三地址代码（three address-code） 带语义（注释）的树 中间代码,2019/5/16,21,例：position := initial + rate * 60,中间代码： (1) ( inttoreal, 60 - t1 ) (2) ( * , id3 t1 t2 ) (3) ( + , id2 t2 t3 ) (4) ( := , t3 - id1 ),2019/5/16,22,1.2 编译的阶段,代码优化（Code Optimization） 功能：对中间代码进行优化（提高时间与空间效率）,2019/5/16,23,例：position := initial + rate * 60,代码优化： (1) (inttoreal， 60 - t1 ) (2) ( * ， id3 t1 t2 ) (3) ( + ， id2 t2 t3 ) (4) ( := ， t3 - id1 ) （1） ( * ，id3 60.0 t1) （ 2）（ + ，id2 t1 id1),2019/5/16,24,1.2 编译的阶段,代码生成（Code Generation） 功能：生成目标代码 机器代码（machine code）、可重定位的机器代码（relocatable machine code ）、汇编语言代码（assembly code）,2019/5/16,25,例：position := initial + rate * 60,(* , id3 60.0 t1 ) (+ , id2 t1 id1 ),movf id3 , R2 mulf #60.0 , R2 movf id2 , R1 addf R2 , R1 movf R1 , id1,目标代码生成,2019/5/16,26,1.2 编译的阶段,符号表管理 （Symbal-Table Management） 功能：管理分析过程中得到的源程序中的标识符的各种信息 记录源程序中使用的标识符（identifier） 收集每个标识符的各种属性（attribute）信息，包括类型（type）、作用域（scope）、存储分配（storage allocated）信息,2019/5/16,27,1.2 编译的阶段,出错处理 （Error Detection and Reporting） 功能： 检查错误的位置 检查错误的性质（词法、语法、语义） 错误恢复,2019/5/16,28,1.2 编译的阶段,一个例子语句的完整编译过程 见 P 13,2019/5/16,29,1.3 编译器的结构,编译器结构,2019/5/16,30,1.3 编译器的结构,前端（Front end）与后端（Back end） 把编译程序分成前端和后端两部分,前端：只依赖于源程序，独立于目标机器 生成中间代码,后端：依赖于目标机器，与源程序无关，只与中间语言有关 从中间代码生成目标代码,2019/5/16,31,1.3 编译器的结构,好处：提高开发编译器的效率 取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器 不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）,2019/5/16,32,1.3 编译器的结构,遍（Pass） 对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示,2019/5/16,33,1.3 编译器的结构,每一遍的输入是上一遍的输出，第一遍的输入是源程序正文，最后一遍的输出是目标代码 遍数多：编译器结构清晰，但时间效率不高 遍数少：编译速度快，但对机器的内存要求高,2019/5/16,34,1.4 编译器的实现,世界上第一个编译程序是用什么语言书写的？,用高级语言书写？ 没有编译器，如何编译？ 因此世界上第一个编译器只能是用机器语言开发的,2019/5/16,35,1.4 编译器的实现,1、开发高级语言的编译器 自展技术,直接用目标机器上的机器语言书写源语言的编译程序工作量太大 用目标机器上的机器语言书写源语言的一个子集的编译程序，然后再用这个子集作为书写语言，实现源语言的编译程序，这就是自展技术。,2019/5/16,36,1.4 编译器的实现,2、用已有高级语言实现其它高级语言的编译程序,用语言 L 的编译器编译用 L 书写的另一高级语言的编译器 例如，用 C 写 PASCAL 语言的编译器，然后编译,2019/5/16,37,1.4 编译器的实现,编译器的构造工具 词法分析器自动生成程序 LEX,2019/5/16,38,1.4 编译器的实现,编译器的构造工具 语法分析器自动生成程序 YACC,2019/5/16,39,1.5 编译器的伙伴,一个语言处理系统 P 5 Fig.1.3,Source Program,Pre-Processor,Compiler,Assembler,Loader Link/Editor,Executable,Library, relocatable object files,2019/5/16,40