修订版编译原理版.pptx

单击编辑母版标题样式,#,编译原理,Compilers Principles,Techniques and Tools,王中卿,苏州大学 计算机科学与技术学院,1,编译原理,主讲：周国栋、段湘煜、王中卿,2,（自然语言处理实验室）,Principles,Techniques and Tools,（,2,nd,Edition,）,中文版（赵建华、郑滔、戴新宇译）,机械工业出版社，,2009.1,ISBN 978-7-111-25121-7.,6,编译原理,评分,平时成绩：,15%,期中考试：,15%,期末考试：,70%,考点分布,概述：第一章至第二章,10%,重点：第三章至第五章,60%,简述：第六章至第七章,20%,其他：,10%,7,第一章 引论,8,第一章：引论,翻译器的不同形式,编译器、解释器、混合编译器,典型编译器结构,编译系统,程序设计语言发展历程,9,1.1,语言处理器（,1.1,）,翻译器,能够完成从一种语言到另一种语言变换的软件,源语言,目标语言,翻译器,10,1.1,语言处理器,翻译器,11,编译器,解释器,混合编译器,编程语言排行榜,TIOBE Index for February 2018,12,1.1,语言处理器,一个语言处理系统：图,1.5,预处理器,编译器,汇编器,连接器,/,加载器,13,1.1,语言处理器,编译器,编译器是一种翻译器,特点：目标语言比源语言低级,编程语言,传统程序设计语言：,Pascal,、,C+,、,Java,专用语言：,Lisp,、,Prolog,、,LaTeX,编程语言,机器语言,编译器,14,1.1,语言处理器,编译器,编译器是一种翻译器,特点：目标语言比源语言低级,机器语言（操作：寄存器,BX,的内容送到,AX,中,),机器指令,1000100111011000,汇编指令,movax,bx,编程语言,机器语言,编译器,15,1.1,语言处理器,编译器,编译器是一种翻译器,特点：目标语言比源语言低级,编程语言,机器语言,编译器,16,1.2,编译器结构（,1.2,）,分析部分,前端：源程序,-,中间表示,综合部分,后端：中间表示,-,目标程序,17,1.2,编译器结构,一个编译器的各个步骤 图,1.6,编译器的工作可以分成若干阶段，每个阶段把源程序从一种表示变换成另一种表示。,符号表管理器,出错管理器,18,1.2,编译器结构,一个编译器的各个步骤,实例：图,1.7,一个赋值语句的翻译,19,1.2,编译器结构,前端,20,后端,1.2,编译器结构,编译器的前端与后端,前端：只依赖于源语言,后端：编译器中依赖于目标机器的部分，一般独立于源语言，而与中间语言有关。,前端,+,后端：组合,取一个编译器前端，重写它的后端以产生同一源语言在另一机器上的编译器,把几种不同的语言编译成同一种中间语言，让不同的前端使用同一后端，从而得到一台机器上的几个编译器,编译的几个阶段常用一趟,/,遍（,pass,）扫描来实现，一趟,/,遍扫描包括读一个输入文件和写一个输出文件。,21,1.2,编译器结构,词法分析,逐个读构成源程序的字符，把它们组成词法单元,(,token,),流,。,实例：,position=initial+rate*60,（）标识符（,position,）,（）赋值号（,:=,）,（）标识符（,initial,）,（）加号（）,（）标识符（,rate,）,（）乘号（）,（）数（,60,）,22,1.2,编译器结构,词法分析,逐个读构成源程序的字符，把它们组成词法单元,(,token,),流,。,实例：,编译器的词法分析也叫做线性分析或扫描。,词法分析,23,position=initial+rate*60,1.2,编译器结构,语法分析,把词法记号流依照语言的语法结构按层次分组，以形成语法短语。,实例：,position=initial+rate*60,的语法分析树,24,1.2,编译器结构,语法分析,表达式、语句等程序层次结构通常由递归的规则表示,实例：表达式,任何一个标识符都是表达式；,任何一个数都是表达式；,如果,和,都是表达式，那么,、,、（,）、（,2,）也都是表达式。,25,1.2,编译器结构,语法分析,表达式、语句等程序层次结构通常由递归的规则表示,实例：语句,如果,identifier,是标识符，,expression,是表达式，那么,identifier:=expression,是语句。,如果,expression,是表达式，,statement,是语句，那么,while(expression)do statement,if(expression)then statement,也都是语句。,26,1.2,编译器结构,语法分析,把词法记号流依照语言的语法结构按层次分组，以形成语法短语。,实例：,position=initial+rate*60,的语法树,27,1.2,编译器结构,语义分析,检查程序的语义正确性，以保证程序各部分能有意义地结合在一起，为后面代码生成阶段收集类型信息。,类型转换,类型检查,语法制导翻译,real,型,28,1.2,编译器结构,中间代码生成,中间代码位于高级编程语言和机器语言（目标程序）之间,后缀表示,:9+5-2,95+2-,抽象语法树,:,三地址码,29,1.2,编译器结构,代码优化,改进代码，以产生执行较快的机器代码。,30,1.2,编译器结构,目标代码生成,生成可重定位的机器代码或汇编码,为源程序所用的每个变量选择存储单元，并且把中间代码翻译成等价的机器指令序列。,关键问题是寄存器分配。,31,1.2,编译器结构,符号表管理,编译器的一项重要工作是记录源程序中使用的标识符，并收集每个标识符的各种属性。,这些属性提供标识符的存储分配、类型和作用域信息。,如果是过程标识符，还有参数的个数和类型、参数传递方式和返回值类型。,符号表是为每个标识符保存一个记录的数据结构，记录的域是标识符的属性。,该数据结构允许我们迅速地找到一个标识符的记录，在此记录中存储和读取数据。,32,1.2,编译器结构,符号表管理,实例 语句,position=initial+rate*60,词法分析器发现源程序的标识符时，把该标识符填入符号表。但是，词法分析期间不能确定一个标识符的属性。,例如：,其余的阶段把标识符的信息填入符号表，然后以不同的方式使用这些信息,33,1.2,编译器结构,出错管理,每个阶段都可能发现源程序的错误。发现错误后，该阶段必须处理此错误，使得编译可以继续进行，以便进一步发现源程序的其他错误。,词法分析：当前被扫描的字符串不能形成语言的词法记号。,语法分析：记号流违反语言的语法规则。,语义分析：编译器试图找出语法正确但对所含的操作来说是无意义的结构，如相加的两个标识符，其一是数组名，另一个是过程名。,34,1.3,编译系统,除了编译器外，还需要一些其他工具的帮助，才能得到可执行的目标程序，这些工具包括预处理器、汇编器和连接器等,C,语言的编译系统,Java,语言的编译系统,35,1.3,编译系统,C,语言的编译系统,一个语言处理系统：图,1.5,设有两个文件,main.c,swap.c,gccvo swap main.c swap.c,-v,可以输出该编译系统各步骤执行的命令和执行结果,-o,指示生成的可执行文件的名字,36,1.3,编译系统,C,语言的编译系统,预处理器,实现文件包含,#include,实现宏展开,#define pi 3.1415926,条件编译,#if,、,#ifdef,37,1.3,编译系统,C,语言的编译系统,汇编器：对输入进行两遍扫描,第一遍，汇编器扫描输入，将表示存储单元的所有标识符都存入符号表，并分配地址。,第二遍，汇编器再次扫描输入，把每个操作码翻译成机器语言中代表那个操作的位串，并把代表存储单元的每个标识符翻译成符号表中为这个标识符分配的地址。,gcc S main.c,as,o main.o main.s,38,1.3,编译系统,C,语言的编译系统,连接器：收集、组织程序所需的不同代码和数据,静态连接器：将多个可重定位目标文件组成一个可执行目标文件（也可以组成一个可重定位目标文件）,动态连接器：支持在内存中的可执行程序在执行时与共享目标文件进行动态的连接。,39,1.3,编译系统,Java,语言的编译系统,一般的高级语言程序如果要在不同的平台上运行，至少需要编译成不同的目标代码。,Java,虚拟机技术是实现,Java,平台无关性特点的关键。,Java,虚拟机语言（简称,JVML,）,JVML,程序只需要与虚拟机交互，不需要关心底层的硬件和操作系统。,40,1.3,编译系统,Java,语言的编译系统,41,1.4,程序设计语言发展历程（,1.3,）,程序设计语言发展历程,机器语言（第一代）：,20,世纪,40,年代,汇编语言（第二代）：,20,世纪,50,年代早期,高级语言：,20,世纪,50,年代晚期,+,通用（第三代）：,Fortran,、,Cobol,、,C,、,C+,、,C#,、,Java,专用（第四代）：,SQL,、,Postscript,逻辑（第五代）：,Prolog,、,LISP,42,1.4,程序设计语言发展历程,C,语言的产生,The Development of the C Language,：,C history Written by Dennis Ritchie,BCPL,B,语言,New B,语言,C,语言,Ken Thompson,(left)with,Dennis Ritchie,DEC PDP-7,as used for initial work on C and Unix,43,1.4,程序设计语言发展历程,第一届（,1966,年）图灵奖得主：,Alan J,Perlis,贡献领域：高级程序设计技巧，编译器构造,44,1.4,程序设计语言发展历程,1983,年图灵奖得主：,Ken Thompson,Dennis Ritchie,贡献领域：,C,语言和,Unix,操作系统,45,1.4,程序设计语言发展历程,2006,年图灵奖得主：,Frances E.Allen,贡献领域：优化编译器,46,1.4,程序设计语言发展历程,编译性语言、解释性语言和脚本语言,高级语言翻译成机器语言，计算机才能执行高级语言编写的程序。,翻译有两种方式,编译：一次性编译成机器语言文件，不用重新编译，效率高,解释：每个语句都是执行的时候才翻译，每执行一次就翻译一次，效率比较低,脚本语言,一种解释性语言：,JavaScript,，,ASP,PHP,PERL,Java,语言,既要编译，又要解释；编译只有一次，程序执行时解释执行；通过编译器，把,java,程序翻译成一种中间代码,字节码，然后通过,JVM,解释成相应平台的语言。,47,1.4,程序设计语言发展历程,主流编译理论会议,PLDI,（,ACM Symposium on Programming Language Design and Implementation,，编程语言设计与实现）,POPL,（,ACM Symposium on Principles of Programming Languages,，编程语言原理）,PPoPP,（,ACM Symposium on Principles and Practice of Parallel Programming,，并行编程原理与实践）,OOPSLA,（,ACM Conference on Object-Oriented Programming Systems,Languages and Applications,，面向对象的编程系统、语言和应用）,48,第一章：总结,自然语言处理,vs,编译原理,词法分析,49,第一章：总结,自然语言处理,vs,编译原理,语法分析,50,第一章：总结,第一章总结（,1.7,）,51,作业,给定一个后缀表示，比如,95+2-,求输出结果,C+,实现,52,重点,什么是编译器？,编译器，解释器的区别？,一个语言处理系统由哪些部分组成？,编译器的前端分析由哪些部分构成？,编译器的后端分析由哪些部分构成？,什么是词法分析？,什么是语法分析？,什么是标识符，表达式，语句？,中间代码有哪三种表达方式？,什么是符号表？,什么是出错管理？,53,