《编译原理恐龙书》PPT课件.ppt

编译原理,2019/6/13计算机学院,辛明影,2,自我介绍,姓名：辛明影 电话： 86413213 教研室：计算机软件基础 办公室：综合楼513 ,助课教师：洪晓鹏，综合楼614 单丽丽，新技术楼608,2019/6/13计算机学院,辛明影,3,开课目的及应用前景：,介绍设计与构造程序设计语言编译程序的原理与方法,源程序,编译程序,目标程序,连接,可执行程序,预备知识：,形式语言与自动机、,两门以上的高级程序设计语言,汇编语言,数据结构等,How?,2019/6/13计算机学院,辛明影,4,内容简介：,第一章：编译器的基本结构,第二章：高级语言及其语法描述,第三章：词法分析器,第四章：语法分析技术,第五章：语法制导翻译的主要概念及中间代码,第六章：程序运行时的存贮分配问题,第七章：代码优化,第八章：目标代码生成,2019/6/13计算机学院,辛明影,5,教学设计：,(1)自顶向下，逐步求精的方法 (2)问题驱动 (3)将课程设计成一个应用平台 (4)用实验拓广课堂教学 (5)精讲多练 (6)承前启后,教学目标：,2019/6/13计算机学院,辛明影,6,第一章 绪论,编译器就是一个程序，它读入用某种语言编写的源程序，并翻译成一个与之等价的另一种语言编写的源程序。,编译器,源程序,目标程序,错误信息,Fortran、Pascal、Java、 C ,另一种程序设计语言、,汇编语言、机器语言,1.1什么叫编译程序,2019/6/13计算机学院,辛明影,7,1.2 编译过程概述,编译程序的工作，从输入源程序开始，到输出目标程序结束，与自然语言之间的翻译有很多相似之处。,一段英文翻译成中文， 需经下列步骤：,识别出句子中的单词,分析句子的语法结构,根据句子的含义进行初步分析,对译文进行修饰,写出最后的译文,编译程序,词法分析,代码优化,语法分析,语义分析及中间代码生成,目标代码生成,构成编译程序各个阶段,I am a experienced teacher.,2019/6/13计算机学院,辛明影,8,编译器的各个阶段：,编译器是分 阶段执行的。,每个阶段将源程序从一种表示转换成另一种表示,源程序,词法分析器,错 误 处 理 器,符 号 管 理 表,语法分析器,语义分析器,中间代码生成器,代码优化器,代码生成器,编译的各个阶段,2019/6/13计算机学院,辛明影,9,各分析阶段,随着编译器各个阶段的进展，源程序的内部表示不断地发生变化。,以 a=b+c *d 为例,1。词法分析,读入源程序,完成的任务：,识别出单词：,a、=、b、+、c 、 *、 d,并用记号方式表示识别出的单词,关键字、标识符、常数、算符和界符,例：25表示a、b、c、d；36：；2：；31：*,记号表示逻辑上相关的字符序列，常用整数来表示,上述单词表示为：,(25,a),(36,_),(25,b),(32,_),(25,c),(31,_),(25,d),2019/6/13计算机学院,辛明影,10,语法分析,在词法分析的基础上，根据语言的语法规则，把单词符号串组成各类语法单位.,具体的说，语法分析是在单词流的基础上建立一个层次结构-建立语法树,赋值语句,标识符,=,表达式,a,表达式,标识符,b,+,表达式,表达式,*,标识符,c,表达式,标识符,d,2019/6/13计算机学院,辛明影,11,语义分析阶段,语义分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作信息及类型信息,=,+,a,b,*,c,d,temp1=c*d,temp2=b+temp1,temp1,temp2,a=temp2,2019/6/13计算机学院,辛明影,12,中间代码生成阶段,本阶段将产生源程序的一个显式中间表示,这种中间表示可以看成是某种抽象的程序，通常是与平台无关的,其重要性质：1.易于产生 2.易于翻译成目标程序,下面是用三地址码和四元式表示的例子：,temp1=c*d temp2=b+temp1 a=temp2,（* , c , d , tempt1) (+ , b, tempt1 , tempt2) (= , tempt2 , , a),2019/6/13计算机学院,辛明影,13,代码优化阶段,试图改进中间代码，以产生执行速度较快的机器代码,对上面中间代码进行优化处理后，产生如下的代码：,temp1=c*d a=b+temp1,temp1=c*d temp2=b+temp1 a=temp2,2019/6/13计算机学院,辛明影,14,代码生成阶段,生成可重定位的机器代码或汇编代码,Movf R2，c Mult R2,d Movf R1,b Addf R2,R1 Movf a,R2,2019/6/13计算机学院,辛明影,15,1.3符号表管理,int a,b; float e,f char ch1,ch2;,为什么要先说明?,定义了变量的类型，也就规定了变量在内存中的存放形式，在其上所能进行的运算,解决符号地址到存贮地址上的映射,2019/6/13计算机学院,辛明影,16,编译器的一个基本功能是记录源程序中使用的标识符,并将它们记载到符号表中。,符号表是一个数据结构。,每个标识符在符号表中都有一条记录,名字,记号,类型,种属,addr,id1(25),id2(25),b,a,例：int a,b;,int,简变,0,4,并收集与每个标识符相关的各种属性信息，,int,简变,2019/6/13计算机学院,辛明影,17,符号表的接口：,符号表的作用就是存放字符串或词素,当一个字符串或词素被保存时，与之相对应的记号也被保存,符号表上的操作：,Insert(s,t):将符号串s和记号t插入符号 表，返回相应表项的指针,Lookup(s):在符号表中查找字符串s，查找成功返回相应指针，否则返回0,2019/6/13计算机学院,辛明影,18,关键字的处理,通常情况下，将关键字存在符号表中，作为符号表的初值。,当词法分析程序识别出一个标识符s后，用lookup(s)查找符号表，如果是关键字，返回相应的记号；如果是变量名，返回记号id,2019/6/13计算机学院,辛明影,19,符号表的实现,固定长标识符：采用前面的结构,不定长标识符：使用单独的数组lexemes,i f eos i n t eos p o s i t i o n eos i n i t i a l eos,If(12),Int(13),Id1(25),Id2(25),存放标识符的字符串,符号表中存放标识符在lexemes的起始位置和相应记号,2019/6/13计算机学院,辛明影,20,1.4编译各阶段的分组,一、前端和后端,前端包括词法分析、词法分析、语义分析，以及相关的错误处理和符号表的建立,前端依赖于源程序并在很大程度上独立于目标机器。,2019/6/13计算机学院,辛明影,21,后端主要包括代码优化、代码生成和相关错误处理。,后端依赖于目标机器。,后端处理对象是由前端产生的结果，即中间代码,前端生成与平台无关的字节码,后端是由与平台有关的解释器对所生成的字节码文件进行解释执行,Java语言的编译采用的是前端后端方式。,2019/6/13计算机学院,辛明影,22,二、编译的遍,编译的若干阶段通常是以一遍来实现的，每遍读一次输入文件、产生一个输出文件。,2019/6/13计算机学院,辛明影,23,在编译的各个阶段都会发现源程序中的错误，,1.5错误检测与报告,为了使编译器能继续运行，以检测出源程序中 更多的错误，在检测到错误后，必须以合适的方式进行错误处理。,error,第二章 高级语言 及其语法描述,2019/6/13计算机学院,辛明影,25,内容简介：,本章概述程序设计语言的结构,2.1 程序语言的定义,任何语言实现的基础是语言定义。,语言的定义决定了该语言,具有什么样的语言功能、,什么样的数据结构、,什么样的程序结构、,以及具体的使用形式等细节问题。,和主要的共同特征，,并介绍程序设计语言主要语句的文法描述与形式定义。,2019/6/13计算机学院,辛明影,26,对于编译程序设计者来说：语言定义就是具体实现的理论依据。,对于语言用户来说：语言定义就是一本用户手册。,2.1.1语法,语言的语法是指这样一组规则，用它可产生一个程序。,规则： 词法规则 语法规则,2019/6/13计算机学院,辛明影,27,词法规则是指单词符号的形成规则,字母表就是一个有穷字符集。,C语言的字母表为： =a-z 、 AZ 、 09 、(、) 、 、 、 、.、! 、 、+ 、- 、* 、 / 、 ,C语言的标识符的构成规则：,字母、下划线打头的字母、数字和下划线构成的符号串。如：a1、ave 、_day,一 .词法规则,2019/6/13计算机学院,辛明影,28,上述的定义是用文字来描述的，当设计编译程序时，就要把它用形式的方式描述出来，就要用到形式语言。,各类型的常数、,标识符、,基本字、,算符和界符等,正规式和有穷自动机是描述词法结构和进行词法分析的有效工具,在现今多数程序设计语言中，单词符号一般包括：,2019/6/13计算机学院,辛明影,29,C语言的标识符的文法和自动机描述：,例：C语言标识符的文法描述 L（G）=w/w为字母或-打头的字母数字串,解：P:I aB I -B I a B aB B dB Ba B d,识别L（G）的自动机,I,B,T,a,-,a,d,其它,2019/6/13计算机学院,辛明影,30,S,A,C,D,F,E,B,7,d,d,d,d,d,d,d,e,e,+,T,*,例：C语言实常数的文法描述,文法：S dA A dA A eD A .B B dC C dC C eD D -E D +E D dF E dF F dF F d,其它,其它,其它,1000,3.14,10e+3 3.14e-5,12e5 0.1e24,2019/6/13计算机学院,辛明影,31,二.语法规则,语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则,一般的程序设计语言的语法单位有：,表达式 、,语句 、,分程序 、,函数 、,过程和程序等,下推自动机理论和上下文无关文法是我们讨论语法分析的理论基础,2019/6/13计算机学院,辛明影,32,表达式： EE+T EE-T ET TT*F TT/F TF F(E) F id,主要语句的形式描述：,2019/6/13计算机学院,辛明影,33,布尔表达式： B B or B B B and B B not B B(E） B id relop id B true B false,2019/6/13计算机学院,辛明影,34,赋值、分支、循环语句： S id=E S if B then S S if B then S else S S while B do S S L L L ;S L S,2019/6/13计算机学院,辛明影,35,调用语句： Scall id(Elist) Elist Elist,E Elist E|,2019/6/13计算机学院,辛明影,36,类型说明和过程说明语句： P D D D;D D id:T Did（Elist） D ; S T int T float,2019/6/13计算机学院,辛明影,37,数组说明语句： L idElist Elist Elist,E Elist E,2019/6/13计算机学院,辛明影,38,2.1.2 语义,例：a=b+c*d,例do 999 I=1,10,对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义，这就是语义问题,对于编译程序来说，只有了解程序的语义，才知道应把它翻译成什么样的目标指令代码,2019/6/13计算机学院,辛明影,39,2.2 构造基础,2.2.1 程序结构简介,一个高级语言程序通常由若干子程序段（过程、函数等）组成，,许多语言还引入了类、程序包等更高级的结构,2019/6/13计算机学院,辛明影,40,FORTRAN,一个FORTRAN 程序由一个主程序和若干个辅助程序段组成,PROGRAM MAIN . END SUBROUTINE SUB1 . .END FUNCTION FUN1 . END,它的定义是并列的,2019/6/13计算机学院,辛明影,41,FORTRAN 的构成特点：,同一名字在不同的程序段中一般都代表不同的对象，也就是说代表不同的存贮单元,PROGRAM MAIN .integer x END SUBROUTINE SUB1 Integer x .END,Integer x,X,X=9999,100,Integer x,9999,X=100,X,PROGRAM MAIN . END SUBROUTINE SUB1 .END,一个名字对应多个对象,2019/6/13计算机学院,辛明影,42,但是不同程序段里的同名公用块却代表同一个存贮区域,PROGRAM MAIN . Common a,b END SUBROUTINE SUB1 common x,y .END,PROGRAM MAIN . END SUBROUTINE SUB1 . END,Common a,b,a,b,A=100 B=50,100,50,Common x,y,x,y,Y=x+100,200,共享存贮单元,多个名字对应一个对象,2019/6/13计算机学院,辛明影,43,二。Pascal,Pascal 允许子程序嵌套定义,Program main 说明部分 Begin 可执行部分 end,Pascal的 程序结构,Program main Begin end,Procedure P1 Begin end,Procedure P11 Begin end,Procedure P2 Begin end,也允许并列定义,2019/6/13计算机学院,辛明影,44,关于名字的作用域的规定：,标识符X的任意一次出现（除去说明语句中）都意味着对某个说明语句中说明的这个变量X的引用,此时，说明语句同标识符X应共处一个最小程序中，即：,P1中说明的X只在P1中有效,P11是P1的内层子程序，P11中没有再对X作新的说明，则在P11中对X的引用，实际上引用的就是P1中说明的X，,即内部过程可以引用外部过程中定义的量,2019/6/13计算机学院,辛明影,45,三.java,Java语言是一种面向对象的高级语言，它很重要的方面是类和继承的概念，同时支持多态性和动态绑定等特性,Class car Int color_num; Int door_num; Int speed; . Void push_break() Void add_oil() ,Class benz extends car Double price; Void ABS( ) ,2019/6/13计算机学院,辛明影,46,一个类把有关的数据及其操作封装在一起构成一个抽象数据类型,一个子类继承其父类的所有数据和方法，并且可以加入自己新的定义,在java中，变量和方法的定义之前可以加上public、private、pretected等修饰词，,以限制其它类的对象对于这些变量和方法的使用,2019/6/13计算机学院,辛明影,47,2.2.2 构造基础,程序设计语言的数据对象：,数据、,函数、,过程,常用能反映其本质的、有助于记忆的名字来表示,一.名字,特性：,一个名字对应一个对象,，普通变量,多个名字对应一个对象,一个名字对应多个对象,，common, 数组、重载、 局部变量、 重写、,2019/6/13计算机学院,辛明影,48,每个对象可以看做是一个存贮单元，,可能是一个字，也可能是多个字,名字具有属性，,通常由说明语句给出,一个名字的属性，包括：类型和作用域,类型决定了它有什么样的值，,作用域规定了值的存在范围,值在计算机内的表示，,以及对它能施加什么样的运算,2019/6/13计算机学院,辛明影,49,二.数据类型,1.初等数据类型,数值数据：整形、实型、双精度等，可施行算术运算,逻辑数据：可施行逻辑运算,字符数据：,指针类型：,2019/6/13计算机学院,辛明影,50,三。数据结构,1。数组,从逻辑上讲，一个数组是由同类型数据所组成的n 维矩形结构,一个数组所需的存贮空间大小在编译时就已知道的，则称此数组是一个确定的数组；否则称为可变数组,设int Al1u1,l2u2 lnun 为n维数组 各维的长度：di=ui-li+1 (1in),2019/6/13计算机学院,辛明影,51,任一数组元素Ai1,i2, in的地址为： D=a+(i1-l1) d2d3 dn +(i2-l2) d2 d2 dn + (in-1-ln-1) dn + (in-ln),整理后C= ( (l1 d2 +l2) d3+ l3) d4+ + ln-1) dn+ ln,C是数组计算中不变的部分,2019/6/13计算机学院,辛明影,52,变量部分：v= ( (i1 d2 +i2) d3+ i3) d4+ + in-1) dn+ in,任一数组元素Ai1,i2, in的地址: addr=a-c+v,2019/6/13计算机学院,辛明影,53,在编译时，当遇到说明时，必须把数组的有关信息记录在一个“内情向量”之中，用于数组元素的地址计算。,数组的内情向量包括：,维数，各维的上、下限，首地址及数组的类型,ln,un,dn,l2,l1,un,un,d1,d2,N维数,C常数,T类型,A首地址,2019/6/13计算机学院,辛明影,54,对于确定数组来说，内情向量可登记在符号表中；,对于可变数组，内情向量的信息在编译时无法全部知道，只有到运行阶段才能全部确定下来，存贮分配也要等到运行时方能进行,2019/6/13计算机学院,辛明影,55,2.记录（结构）,从逻辑上讲，记录是由已知的数据组合起来的一种结构,Struct student char name20; boolean partmember; int age; stu;,2019/6/13计算机学院,辛明影,56,记录结构最简单的存贮方式是连续存放,上述的变量stu共占7个字，共28个字节,S Stu.partmember Stu.age,3.字符串、表格和队列,k K+1 . K+20 . K+24 .,. .,2019/6/13计算机学院,辛明影,57,四.抽象数据类型,一个抽象数据类型包括：,这种类型对象的封装,作用于这些数据对象的抽象运算的集合,数据对象的一个集合,C+、Java语言通过类对抽象类型提供支持,2019/6/13计算机学院,辛明影,58,五.语句与控制结构,1.表达式,要解决的问题：,优先级,结合率,2.语句,语句可分为：,说明语句：,可执行语句：,定义各种不同数据类型的变量和运算,描述语句的动作,执行语句分为：赋值、控制和I/O语句,2019/6/13计算机学院,辛明影,59,赋值句,A=B,左值,右值,名字的左值指它所代表的存贮单元地址,名字的右值指该 单元的内容,2019/6/13计算机学院,辛明影,60,控制语句,无条件转移语句：Goto lable,条件语句：If B then S If B then S else S,循环语句：While B do S Repeat S until B For I=e1 to e2 step e3,过程调用语句：Call P(x1, x2,.xn),返回语句：Return(E),2019/6/13计算机学院,辛明影,61,说明语句,说明语句用于定义名字的性质。,编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。,许多说明语句不产生目标代码,但有的说明语句，如过程说明和可变数组说明，则要产生相应的目标代码,2019/6/13计算机学院,辛明影,62,简单句和复合句,简单句是指不包含其它语句成分的基本句。赋值、goto语句等,复合句则指那些句中有句的语句,If (x=0) then x=1 x=1;y=2;goto l1;,2019/6/13计算机学院,辛明影,63,program reference（input，output）； var a，b ： integer； procedure swap（x，y： integer）； var temp： integer； begin temp :x； x ：y； y ：temp end; begin a：1; b：2; swap(a，b); writeln( a=，a， b= , b ） end.,2.2.3 参数传递,结果是什么？,2019/6/13计算机学院,辛明影,64,1 传值调用,实在参数和形式参数结合的方法： 传值调用（call-by-value） 引用调用（call-by-reference） 复制恢复（copy-restore） 传名调用（call-by-name）,2019/6/13计算机学院,辛明影,65,子程序为每一个形参开辟一个存贮单元，用于存放 相应实参的值。,子程序执行时，每当访问形参时，就直接访问形参单元。,实参：,形参：,传值调用可以实现如下：,主调过程计算实在参数，并把它们的右- 值放入到形式参数的存储空间中。,2019/6/13计算机学院,辛明影,66,使用传值的方法，调用swap（a,b）等价于下面几步： x：= a y：= b temp：= x x：= y y：= temp,2019/6/13计算机学院,辛明影,67,2 引用调用（传地址） 把实在参数的地址传递给相应的形式参数, 在目标代码中，在被调用过程中对形式参数的一次引用就成为对传递给被调用过程的指针的一个间接引用。,Reference,a b x y,1 2,swap,a b,temp,2019/6/13计算机学院,辛明影,68,子程序为每个形参开辟一个单元，用于存放相应实参的地址，,执行时，子程序间址方式访问这些形参单元,当实参为表达式或常数时，则存放它们值的临时单元。,实参：,地址,形参：,Temp:=x; x:=y; y:=temp;,temp:=a; a:= b; b:=temp;,2019/6/13计算机学院,辛明影,69,3 复制恢复（传值结果） 实现： 1. 当控制流入到被调用过程之前，把实在参数 的右-值和左-值传递到被调用过程中； 2. 当控制返回时，把形式参数的现行右-值复制回到相应的实在参数的左-值中。,2019/6/13计算机学院,辛明影,70,子程序为每个形参分配两个存贮单元B1和B2，B1用于存放实参地址，B2用于存放实参值。,执行时，对B2单元使用直接访问形式；返回前，按B1中的地址把B2中的内容存入主调程序的实参单元中。,实参：,地址,形参：,B1,B2,B1,2019/6/13计算机学院,辛明影,71,在主调程序中设置计算实参地址和右值的形实替换子程序THUNK,子程序中为相应实参开辟一个形式单元，用于存放该实参的THUNK子程序的入口地址。,执行时，每当要对形参进行访问时，就调用THUNK子程序，以获得相应实参地址或值,4 传名调用,对形参的访问是发生在实参单元上的,2019/6/13计算机学院,辛明影,72,例：有程序段： procedure p(x,y,z) begin y=y+1; z=z+x; end,Begin a=2; b=3; c=4; P(a,b,c); print a,b,c; end,2019/6/13计算机学院,辛明影,73,传值：,a,b,c,实参,形参,x,y,z,2,3,4,P(a,b,c);,2,3,4,y=y+1;,输出：2 3 4,4,6,Z=z+x;,A=2 B=3 C=4,2019/6/13计算机学院,辛明影,74,传地址：,a,b,c,实参,形参,x,y,z,2,3,4,P(a,b,c);,&a,&b,&c,y=y+1; y=y+1,输出：2 4 6,4,6,Z=z+x; z=z+x,2019/6/13计算机学院,辛明影,75,传值结果：,a,b,c,实参,形参,XB1 B2,YB1 B2,ZB1 B2,2,3,4,&a,&b,y=y+1;,输出：2 4 6,Z=z+x;,&c,按B1返回B2 的值,4,6,2,3,4,4,6,2019/6/13计算机学院,辛明影,76,传名：,a,b,c,实参,形参,x,y,z,2,3,4,P(a,b,c);,&thunk,&thunk,&thunk,y=y+1; JSR Thunk Yb,输出：2 4 6,4,6,Z=z+x; jsr Thunk Z c,x a,2019/6/13计算机学院,辛明影,77,例：有程序段： procedure p(x,y,z) begin y=y+1; z=z+x; end,Begin a=2; b=3; P(a+b,a,a); print a end,2019/6/13计算机学院,辛明影,78,传值：,a,b,a+b,实参,形参,x,y,z,2,3,P(a+b,a,a);,5,2,2,y=y+1;,输出：2,3,7,Z=z+x;,A=2 B=3,5,2019/6/13计算机学院,辛明影,79,传地址：,a,b,a+b,实参,形参,x,y,z,2,3,5,P(a+b,a,a);,&a+b,&a,&a,y=y+1; y=y+1,输出：8,3,Z=z+x; z=z+x,8,2019/6/13计算机学院,辛明影,80,传名：,a,b,实参,形参,x,y,z,2,3,P(a+b,a,a);,&thunk,&thunk,&thunk,y=y+1; JSR Thunk Ya,输出：9,3,9,Z=z+x; jsr Thunk Z a,x a+b,第三章 词法分析,2019/6/13计算机学院,辛明影,82,编译器的各个阶段：,编译器是分 阶段执行的。,每个阶段将源程序从一种表示转换成另一种表示,源程序,词法分析器,错 误 处 理 器,符 号 管 理 表,语法分析器,语义分析器,中间代码生成器,代码优化器,代码生成器,编译的各个阶段,2019/6/13计算机学院,辛明影,83,3 . 2 词法分析器的手工构造： 用DFA 能识别,3 . 3词法分析程序自动构造工具LEX简介,3. 1 词法分析程序的设计：,2019/6/13计算机学院,辛明影,84,=,8,0,;,0,1,3,4,2,5,6,e,n,i,L,字母,字母,字母,字母,数字,数字,数字,=,=,；,；,0,1,2,4,5,6,3,L,i,n,e,=,8,0,;, id(25) , Line, =( 36), , num(27), 80, ;(45), ,数字,字母,字母,1,1,=,=,0,0,0,3,;,;,1,输入,输出,有穷控制器,单词的词类和属性 （词类符号， 单词的属性）,2019/6/13计算机学院,辛明影,85,3.1 词法分析程序的设计,二、 扫描器的任务,一、词法分析程序的功能 源程序 单词序列,词法分析器,1、组织源程序的输入,2、识别单词，转换成机内表示形式,3、删除注释行、空格及无用符号,4、查填符号表,5、检查词法错误,2019/6/13计算机学院,辛明影,86,if ij then i:0 else j:=1,词法分析,if I J Then I 0 else j = 1,2019/6/13计算机学院,辛明影,87,三、词类和属性,2标识符：用来表示各种名字,3字面常数：256，3 .14，true,abc,4 运算符：如，、*、/ 等等,5分界符：如逗号，分号，冒号等,程序语言单词的分类： 1关键字(保留字或基本字)：while, if,2019/6/13计算机学院,辛明影,88,界符和运算符:,词法分析器的输出： （词类编码，单词自身的属性值）,关键字可分成一类，也可以一个关键字分成一类。,常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。,所有的标识符分为一类。,词类编码原则:,一字一码。,一类型一码。,一类一码。,一符一码。,2019/6/13计算机学院,辛明影,89,表3.1 单词词类编码,2019/6/13计算机学院,辛明影,90,对于关键字、界符、运算符来说，它们的词类编码就可以表示其完整的信息，,而对于标识符，词类编码所反映的信息不够充分，标识符的具体特性还要通过单词自身的属性进行互相区分。,标识符的单词自身的属性常用其在符号表中的入口指针来表示,故对于这类单词，其单词自身的属性值通常为空,2019/6/13计算机学院,辛明影,91,对于常数， 其单词自身的属性常用其在常数表中的入口指针来表示,2019/6/13计算机学院,辛明影,92,以语句子a=b+c*d 为例，假设按表3.1为单词编码，词法分析后的结果为：,Token字,符号表,a = b + c * d,a 25,b 25,c 25,d 25,2019/6/13计算机学院,辛明影,93,四、 词法分析的设计形式 （1）设计成一个独立程序，完成词法分析的任务，结果以文件的形式组织，做为语法分析的输入,源程序,词法 分析,符号表,TOKEN字,错误信息,2019/6/13计算机学院,辛明影,94,词法 分析,语法分析,语义分析和 中间代码生成,源程序,中间代码,符 号 表 管 理,错 误 的 诊 查 处 理,（2）作为语法分析和语义分析的子程序,2019/6/13计算机学院,辛明影,95,五、词法分析程序的设计框图,SCANNER,OUTPUT,sort,字母,RECOGID,数字,RECOGDIG,/,HANDLCOM,RECOGDEC,界符,RECOGSTR,LOOKUP,2019/6/13计算机学院,辛明影,96,32 词法分析器的手工构造,为了构造词法分析器，要研究构词法，每种词类的结构模式以及识别它的数学模型有穷自动机。 32 1确定的有限自动机（DFA） 32 2构造识别单词的DFA 32 3 编写词法分析程序,2019/6/13计算机学院,辛明影,97,SCANNER,OUTPUT,sort,字母,RECOGID,数字,RECOGDIG,/,HANDLCOM,RECOGDEC,界符,RECOGSTR,LOOKUP,2019/6/13计算机学院,辛明影,98,一、 手工构造识别单词的DFA m 根椐DFA识别单词的定义，在研究给定程序语言单词结构的基础上，能直接构造出识别它的DFA m。例如：对于C语言,整数：非空数字串。,无符号实数（用d表示数字）:,(a) dd.d dE(+- ) dd,ddE(+- ) dd,(c) dd.d d,0.1e+14,12e-4,3.141592,(d) dddd,1000,2019/6/13计算机学院,辛明影,99,I,B,T,T,a,-,a,d,其它,例：C语言的标识符,标识符：字母开始的字母数字串。,2019/6/13计算机学院,辛明影,100,例：C语言实常数的文法描述,0,1,2,3,4,5,6,7,d,d,d,E,d,E,d,-,+,d,d,1000,3.1415,12e-4,0.1e+14,.,2019/6/13计算机学院,辛明影,101,在识别标识符的过程中，首先要拼写出来，并和保留字区别开来；识别出的标识符要填入符号表中,二、 编写词法分析程序,根据画出的状态转换图（识别单词的）构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；,在识别常数的过程中，要把它转换成机器表示以作为属性值，记录到常数表中。,词法分析程序的控制程序模拟状态转换图的状态转换。,2019/6/13计算机学院,辛明影,102,program SCANNER; Begin initiate符号表,字符串表,行,列计数器; Open 源文件,TOKEN文件,打印机文件; Repeat FIRSTCH(CH); if CH!=EOL then call SORT(CH) else RDLINE; until CH=EOF; 把符号表,字符串表做成文件; close源文件,TOKEN文件; call OUTPUTR;,模块0： 扫描器主控,2019/6/13计算机学院,辛明影,103,单词分类模块(SORT)输入： CH内含单词首符； procedure SORT(CH); case CH of 字母: 字母: call RECOGID(CH,TOKEN); /: call HANDLECOM(CH,TOKEN); 数字: call RECOGDIG(CH,TOKEN); call RECOGSTR(CH,TOKEN); otherwise call RECOGDEL(CH,TOKEN); end case; write TOKEN into TOKEN文件; Return ,2019/6/13计算机学院,辛明影,104,procedure RECOGID(CH,TOKEN); WORD:= ; WORD:=WORD|CH; Repeat call GETCH(CH); if CH是字母或数字 then WORD:=WORD|CH; until CH!=字母或数字; if CH是非法字符 then call PRINTERR(非法字符) else 列计数-1; if WORD 是关键字 then TOKEN:=(关键字种别码,_) else call LOOPUP(WORD,标识符,ENTRY) TOKEN:=(标识符种别码,ENTRY); Return ;,识别标识符； 输入：CH中含标识符的首字母； 输出：TOKEN(二元式形式);,2019/6/13计算机学院,辛明影,105,procedure HANDLECOM(TOKEN); call GETCH(CH); if CH!=* then 列计数-1; TOKEN=(/的识别码,_); return ; TOKEN=-1; GETCH(CH); while 列计数=行长-1 do CH1:=CH; call GETCH(CH); if CH1=* and CH=/ then TOKEN:= ; if TOKEN!= then call PRINTERR(注解未完); TOKEN:= ; return ,处理注解(HANDLECOM); 输入：/;进入该模块之前已扫描了一个字符/ 输出：/的TOKEN字或空TOKEN字;,2019/6/13计算机学院,辛明影,106,识别界限符(RECOGDEL) 输入：CH内含单界限符； 输出：各种界符的TOKEN字; procedure RECOGDEL(CH,TOKEN); case CH of +: TOKEN:=(+的种别码,_); ): TOKEN:=()的种别码,_); then TOKEN:=(的种别码,_) else 列计数-1;TOKEN:=(的种别码,_) endcase; return ,2019/6/13计算机学院,辛明影,107,3.3词法分析程序的自动构造工具LEX简介 一.原理 单词的结构用正规式描述 正规式 NFA DFA min DFA,LEX 编译器,LEX 源程序 lex.1,Lex.yy.c,二.用LEX建立词法分析程序的过程,2019/6/13计算机学院,辛明影,108,C 编译器,Lex.yy.c,a.out,a.out,输入流,单词序列,三.lex源程序 lex源程序由三部分组成,2019/6/13计算机学院,辛明影,109,声明 % 翻译规则 % 辅助过程,2019/6/13计算机学院,辛明影,110,声明包括变量，符号常量和正规定义式。 翻译规则的形式为： p1 动作1 p2 动作2 p n 动作n,2019/6/13计算机学院,辛明影,111,每个pi是正规定义式的名子，每个动作i是正规定义式pi识别某类单词时，词法分析器应执行动作的程序段。用C书写。,标识符 字母(字母|数字)* % 标识符 入口地址=LOOKUP(); % LOOKUP(),2019/6/13计算机学院,辛明影,112,辅助过程是动作需要的，这些过程用C书写，可以分别编译.例：LOOKUP(),第四章 语法分析,该讲语法分析了！ 这可是很重要的章节,2019/6/13计算机学院,辛明影,114,主要内容：,本章将重点介绍典型的语法分析方法及相关的概念和实现技术,语法分析分为：,自上而下:,自下而上：,递归下降分析法,LL（1）预测分析法,推导,算符优先分析法,LR分析法,归约,从根向叶的方向建立分析树,从叶向根的方向建立分析树,2019/6/13计算机学院,辛明影,115,4.1语法分析器的功能,词法分析器,语法分析器,语义分析,符号表,源程序,单词符号,语法树,中间表示,完成的任务：, 对词法分析器产生的单词符号进行处理，输出分析树,与单词相关的信息记录到符号表中,类型检查,错误处理,4.1.1 语法分析器任务,2019/6/13计算机学院,辛明影,116,4.1.2 相关约定,一.符号的使用约定,1. 终结符,.字母表中比较靠前的小写字,如a,b,c,. 操作符，如+、-等,. 标点符号，如括号、逗号等,. 数字0、1、。9,. 黑体串，如if 、id等,2019/6/13计算机学院,辛明影,117,2.下列符号是非终结符,.字母表中比较靠前的大写字,如A、B、C,.字母S，常用来表示开始符号,. 小写斜体名字，如expr、stmt,2019/6/13计算机学院,辛明影,118,3.字母表中比较靠后的大写字母，如X、Y、Z等，用来表示文法符号，也就是说，可以是终结符，也可以是非终结符,4.字母表中比较靠后的小写字母，如u、vz等，表示终结符的串联,5.小写希腊字母、等表示 文法符号的串，所以一个产生式可写作：,A ,2019/6/13计算机学院,辛明影,119,4.2自顶向下分析法,4.2.1 使用的技术、存在的问题及解决方法,2019/6/13计算机学院,辛明影,120,一、 推导,推导：就是用产生式的右部的串来代 替左部的非终结符,事实上推导给出了自顶向下构成分析树过程的精确描述,例：有描述算术表达式的文法G,字符串id+id*id 是该文法的句子，其推导过程如下：,E E+E| E*E|（E）|-E|id,2019/6/13计算机学院,辛明影,121,E,几个约定：,=E+T,=E+T*F,=E+T*id,=E+F*id,=E+id*id,E=-E E推导出-E,= 一步或多步推导,= 零步或多步推导,*,+,=T+id*id,=F+id*id,=id+id*id,2019/6/13计算机学院,辛明影,122,最左推导：每一步都坚持替换当前句型中 最左非终结符的推导,最右推导：每一步都坚持替换当前句型中 最右非终结符的推导，也称为 规范推导,+ 句子：S =w 称终结符串w是文法G句子,+ 句型：S = 称是文法G的句型,+ 语言：L（G）=w/S =w ,2019/6/13计算机学院,辛明影,123,二、语法树,语法描绘了如何从文法的开始符号推导出一个句子的过程,语法树可以看成是推导的图形表示，但它不能显示出替代的顺序,前面句子id+id*id推导过程所对应的分析树如下：,2019/6/13计算机学院,辛明影,124,E E + T T T * F F F id id id,2019/6/13计算机学院,辛明影,125,4.如杲A是某个内结点的非终结符标记，A1， A2， An是该结点从左到右排列的所有子结点的标记，则A A1 A2 An是一个产生式,3.每个内结点由一个非终结符标记,1.树根标记为开始符号,2.每个叶结点由终结符或者标记,语法具有如下特性的树：,2019/6/13计算机学院,辛明影,126,语法树的叶结点从左到右的排列，刚好是这个文法所产生的语言的一个句子,一个文法生成的语言就是它的某个分析树所生成的句子的集合,为给定的终结符串（句子）构造一棵分析树的过程称为这个串（句子）的语法分析（parsing),2019/6/13计算机学院,辛明影,1