编译原理课件（完整）

1、1编译原理一 什么是编译程序？2 计算机经过几十年的开展， 在程序设计语言方面,已经从低级语言开展到高级语言;然而,计算机内部的本质只能识别 0 , 1 代码序列机器语言,而对高级语言甚至符号语言仍然一窍不通。 因此用高级语言编写的程序,必须先翻译为机器语言，才能被计算机理解执行。第一个完成这种翻译任务的编译程序为FORTRAN编译程序,是上世纪五十年代设计的. 第一章 引论第一节、编译程序概述3定义:设源语言为L1,目标语言为L2, 翻译程序是一个程序,它能将L1转换为逻辑上等价的L2。 假设 L1 为高级语言，L2 为低级语言或机器语言，称这种 翻译程序为编译程序。 假设 L1 为低级语言

2、，L2 为机器语言，称这种翻译程序为 汇编程序。 解释程序是指逐条翻译 L1的语句，并立即执行翻译出的 目标代码序列。 编译原理 就是介绍编译程序的一般规律及设计方法的一门课程。高级语言程序机器语言程序翻译为4二 编译过程概述 编译程序从接受源程序到输出目标代码的整个过程，可逻辑的分为 5 个阶段，词 法 分 析语 法 分 析 中间代码生成 代 码 优 化 目标代码生成 1 词法分析：把源程序作为字符串进行扫描 ，根据单词词法，识别出所有单词，过滤无用符，并检查是否为合法的单词。 单词一般分为如下几种： 根本字，标识符，常数，算符，界符 5例如： if n=1 then f:=1 else f

3、:=n*f(n); 该程序经过语法分析,得到如下单词序列:ifn=1thenf:=1 elsef:=n*f(n);过滤掉回车换行,空格,注释等62) 语法分析: 根据语言的语法规那么,从单词符号串中识别出各种语法单位 ,进行句子分析,并检查整个输入字串是否为合法的程序; 重要的语法单位有: 程序,子程序,语句,短语,表达式等例如: program add;var a,b:real;begin read(a,b);write (a+b);end.7程序首部说明段执行部program程序名及参数var说明语句add变量名表变量类型a,brealbegin多语句endread(a,b)write(a

4、+b)83) 中间代码生成:根据语义规那么,把各种语法单位翻译成中间代码序列. 中间代码有三种: 四元式,三元式,逆波兰式. 中间代码的特点:结构简单,语义明确,易于理解及优化. 四元式可表示为: (操作符,操作数1,操作数2,结果)例如: 语句 Z:=(x+0.4)*Y/W; 翻译后得到右面 的四元式序列: 四元式序列(+ , x, 0.4, T1)(* , T1, Y, T2)(/ , T2, w, T3)(:= , T3, , Z)从例如可看出:每条四元式只进行一次最根本的操作.94) 代码优化：对产生的中间代码序列进行加工变换，使变换后的代码更为高效 时间，空间上。 优化主要有： 循环

5、优化，公共表达式提取，强度削弱等。5) 目标代码生成：把中间代码程序翻译为机器指令或汇编指令程序。 这一局部的处理，与计算机硬件及操作系统密切相关。 如存放器数目，机器指令功能及指令条数；操作系统的 BIOS，内存管理，文件管理等。三 编译程序的结构 编译程序可以划分为如下几个根本模块：10词法分析器语法分析器中间代码生成中间代码优化目标代码生成源程序单词符号语法单位四元式四元式目标程序 表格管理 错误处理编译程序总框11表格管理:对各种表格进行管理,包括表格的构造、查找、修改、 删除、插入 等； 编译程序中，表格的种类较多，最主要的有如下几种： 符号表，常量表，标号表，子程序名表，四元式表等

6、。 表格由假设干结构相同的表格项组成，表格项由二元式表示：项名 信息表格项表格项名 1 信息项名 2 信息项名 n 信息12四 设计编译程序 编译程序的设计方式可以分为两类：方式人工设计自动生成低级语言高级语言自动生成扫描器自动生成分析器自动生成编译程序13第二节、高级语言概述一 什么是程序设计语言 程序设计语言是一符号系统，由语法和语义两方面所定义。语法：是一组规那么，规定了语言的形式结构，包括单词结构， 句子结构，程序结构等。 语法=词法规那么+句法规那么 词法规那么：规定了形成单词的规那么；如常数，标识符， 根本字，算符等。 句法规那么：规定了由单词构造更大语法单位的规那么； 如表达式，

7、短语，语句，程序等。14语义：也是一组规那么，规定了各语法单位确实切含义。 例如：A=B，可解释为：A赋值为B；C语言 也可以解释为 ：A等于B P语言 这完全由语义规那么所确定。二 数据类型 各种语言都提供了一些最根本的数据类型,称为初等数据类型，这些数据类型的特征是数据的单一性；还提供了由初等数据类型构造复杂结构类型的手段。1初等数据类型数值类型：整数，实数可进行算术运算和比较运算；逻辑类型：可进行逻辑运算；字符类型：可进行比较远算及字符串操作；指针类型：指向另一变量的地址。152）结构类型-数组 数组是由同一类型数据所组成的多维结构，数组元素是多维空间的一个点，代表了一个存储空间。数组的

8、存储，是通过按行或按列方式，把每个数组元素存放在一个连续的存储空间中。设数组类型为 A:arrayL1 .u1,L2 . u2,.Ln . un of elemtype, 数组元素为 Ai1,i2,.in, di=ui -Li+1则该元素的地址可按如下公式计算: addr= a + (i1 - L1)*d2d3d4.dn + (i2 - L2)* d3d4.dn + (in-1 - Ln-1)* dn + (in - Ln ) *elemlength16addr=a -c +v c = ( L1 )*d2d3d4.dn + ( L2 )* d3d4.dn + ( Ln-1)* dn + ( L

9、n ) *elemlength = (.(L1d2+L2)d3+L3)d4+L4).) dn + Ln *elemlengthv = (.(i1d2+i2)d3+i3)d4+i4).) dn + in *elemlength C是常量,在编译时可以计算出;V是可变部分,只能在程序运行时才能计算出。 从上可知：计算数组元素地址涉及到如下几个因素： a c L1.Ln d1.dn elemlength i1.in 17 这些因素中,在编译时能确定的局部,用一个数组内情向量表来记录, 以便计算数组元素地址使用。换句话说：当编译程序扫描到数组说明语句时，就把数组的各确定局部登记到内情向量表中。 内情向

10、量表组织如下：L1 u1 d1 L2 u2 d2 Ln un dn a c n elemlength 183）结构类型- 记录 是由多种类型的数据组合起来的一种数据结构。Pascal 语言中，可如下定义一种记录类型type = record :; :; :; end; 域名即记录分量,域的类型可以是简单数据类型,也可以是已经定义过的数据类型。 可采用分量顺序方式,分配记录的地址空间。由于每个域类型及空间大小都可能不同,因此,只能通过表映射方式计算各个域在记录中的地址。19记录分量表：域名 相对位移 域类型name1 offset1 type1name2 offset2 type2 namen

11、offsetn typen因此，name i 在记录中的地址为：addr=a+offset ia 为记录的第一个分量的地址；20三 表达式 表达式是由算符和运算量组成,可递规定义如下: 1 变量,常量,函数为表达式 E; 2 若 E1,E2为表达式,则: E1 op E2, op E, (E) 为表达式。 算符间存在如下优先顺序： 乘幂（*） 负号 （） 乘除（* /） 加减（+ -） 关系符（ = = 类型定义段 type = set of ; = array of ; = record end;222 变量说明段var :;:;:;3 函数及过程定义 function (参数说明):; ;

12、 procedure (参数说明) ; ;4 赋值句 := ; 左边变量取其地址,右边表达式取其值.235 分支语句 if then else ; case of :; : else : end; goto ;246 循环控制语句 while do ; for := to do ; repeat ;. until 7 子程序调用 函数调用一般出现在表达式中,形式如下: (实际参数) 过程调用一般作为语句,形式如下: (实际参数);258 输入输出语句 read(); write();9 简单句和复合句 简单句是指不包含其它语句的根本语句, 复合句是指句中有句.例如: V:=E,goto L ,

13、read(a,b) 等都是简单句; if B then S else S, while B do S 等都是复合句.26五 子程序参数传递 当调用一个子程序时,首先应将所需的数据传递给子程序,传递方式主要有三种: 传值,传地址,传名 设有如下函数: function distence(x1,y1,x2,y2):real; begin distence:=sqrt(x2-x1)*2+(y2-y1)*2) end; x1,y1,x2,y2 称为形式参数 设主程序调用如下: d=distence(a1,b1,a2,b2); a1,b1,a2,b2 称为实际参数.271传值 调用程序把实际参数的值传递

14、到形式参数的空间中.1145x1y1x2y21145a1b1a2b2主程序空间子程序空间这种方式,子程序一般不改变实际参数的值.282传地址 调用程序把实际参数的地址传递到形式参数的空间中. addr(a1) addr(b1) addr(a2) addr(b2)x1y1x2y21145a1b1a2b2主程序空间子程序空间 这种方式,子程序间接访问主程序实际参数的值,改变了实际参数的值.293传名 传名是一种宏替换,直接在调用处产生一个子程序副本,并且用实际参数名替代形式参数名. 设主程序调用如下: d:=distence(a1,b1,a2,b2);相当于在此处产生一段程序: d:=sqrt(a

15、2-a1)*2+(b2-b1)*2);30六 存储分配 程序运行时,必须分配相应的存储空间. 这些空间包括:变量空间,常量空间,临时空间,连接单元 等.有的空间在编译时就能确定其大小,而有的空间必须在程序运行时才能确定.根据这一特性,把空间分配分为两种: 静态存储分配 动态存储分配1 静态存储分配 假设在编译时能完全确定程序所需空间大小,并能确定每个数据项的地址,就可在编译时分配所需空间,这种分配方法称为静态存储分配. 假设一个语言无递归调用,无可变数据项,那么可静态地确定各数据项的空间大小和地址. Fortran语言满足这种定义.312 动态存储分配 是指在程序运行时才能确定存储空间和地址的

16、一种分配方法.适用于允许递归和可变数据项的语言,如pascal 和 c 语言. 一般采用堆栈动态地分配空间, 当调用子程序时,就在堆栈中为该子程序分配所需空间;而子程序运行结束后,就释放该子程序空间.子程序空间编译时可确定(活动记录)运行时可确定(可变空间)活动记录连接数据形式参数局部变量数组内情向量表临时变量等活动记录可变空间堆栈子程序 S 32第二章 词法分析内容提要:状态转换图正规式与有限制动机词法分析器的自动生成词法分析器源程序单词序列34第一节 状态转换图一 单词分类及表示 编译中,把高级语言的单词分为五类: 标识符,根本字,常数,运算符,界符 根本字,运算符,界符都是有限可枚举的;

17、而标识符,常数可认为是无限的. 简单起见,单词可表示为如下二元组: (单词分类号,单词自身值); 或者为: (单词种别码,单词自身值); 标识符,常数 各为一个种别码,而由于根本字,运算符,界符的有限性,可以设计为一字一个种别码.35例如:单词 单词种别码分类号 标识符1 1常数 2 2if 3 3then4 3end90 3,91 4;92 4=151 5+152 5保留字界符运算符36二 词法分析器的设计1 源程序的预处理子程序 源程序中,存在许多编辑用的符号,它们对程序逻辑功能无任何影响. 例如:回车,换行,多余空白符,注释行等.在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单

18、.源程序输入缓冲区预处理子程序扫描缓冲区2扫描缓冲区1 缓冲区分为两局部,每个长度为256字节,这样单词的总长度可到达256字节.预处理子程序把处理好的字符串轮流放入两个缓冲区中,供词法分析程序使用.372 词法分析程序 词法分析程序又称为词法分析器或扫描器.可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用词法分析子程序返回一个单词.这里,作为子程序介绍. 词法分析器的结构:源程序输入缓冲区预处理子程序扫描缓冲区2扫描缓冲区1词法分析子程序调用返回一单词数据383 词法规那么的表示-状态转换图定义:状态转换图是一有向图,由有限个结点及有向边连接而成; 每个结点称

19、为状态;状态图有一个初态,多个终态;每条边上 有相应的字符. 状态转换图用于表示单词结构,从状态转换图的初态到终态间,每条路径上字符的连接,就构成了该状态图的合法单词.例如: 012初态终态字母字母数字其它*1标识符的状态图表示:星号表示单词尾部多跟一个字符,应该去掉.39012初态终态数字数字其它*2整数的状态图表示:016初态终态数字数字其它*3实数的状态图表示:23456数字数字 数字E+或 数字E其它数字404 单词的识别 状态图即可以表示单词规那么,同时也可以用于识别单词. 设有一字符串S = s1s2.sn, 假设状态图中存在一初态到终态的路径,且路径上字符的连接为: s1s2.s

20、n, 称 S 可被状态图识别.例如: S=var1012初态终态var1其它* 保存字由于满足标识符定义,因此可以跟标识符用同样的状态图表示与识别,只需增加一个保存字表,当识别出一个标识符时,通过查保存字表来区别保存字及普通标识符.因此 var1 是一个合法的标识符.415 一个简单例如 构造一个简单语言所有单词的状态转换图.该语言的单词种类如下表所示:单词符号 种别码 助记符 内码值 DIMIFDOSTOPEND标识符正常数=+*,()1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR

21、$RPAR( 1 , )( 2 , )( 3 , )( 4 , )( 5 , )( 6 , 串值)( 7 , 数值)( 8 , )( 9 , )( 10, )( 11, )( 12, )( 13, )( 14, )420 1 2初态终态字母字母数字其它*空白 3 4 终态数字数字非数字* 5 = 6 + 7* 9 8*非 * *10,11(12)13其它436 状态转换图的程序实现 为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序:1) CHAR 字符变量2) TOKEN 单词字符串3) GETCHAR 读一个字符到 CHAR 中4) GETBC 读一个非

22、空白字符到CHAR 中5) CONCAT 把CHAR 中字符连接到TOKEN 之后6) LETTER 判断CHAR 中字符是否为字母7) DIGIT 判断CHAR 中字符是否为数字8) RESERVE 用TOKEN中的字符串查找保存字表,并返回保存 字种别码,假设返回零,那么非保存字9) RETRACT 把CHAR 中字符回送到缓冲区44 下面分析状态图的结构特点.每个状态图都由三种结构构成: 分支结构 循环结构 终结点1分支结构程序设计 i i2i1 inc1c2cnstate i:GETCHAR; CASE CHAR OF c1 :CONCAT；state i1: . c2 :CONCAT

23、；state i2: . cn :CONCAT；state in: . ELSE ERROR END;452循环结构程序设计 i j C其它state i:GETCHAR; WHILE CHAR=C DO CONCAT;GETCHAR; RETRACT；state j: . 3终结点程序设计 一般对应一条返回语句: return( c,val); c 为种别码, val 为单词值. 带 * 号的终结点,必须用RETRACT 退还多余字符 下面程序为简单例如语言的实现:46TYPE WORDTYPE=RECORD C：INTEGER； VAL：CHAR； END；FUNCTION RETURN_

24、WORD( ):WORDTYPE; STATE0: TOKEN:=;GETCHAR;GETBC; CASE CHAR OF A.Z: CONCAT; STATE1:GETCHAR; WHILE (LETTER OR DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE2: C:=RESERVE; IF C=0 THEN RETURN($ID,TOKEN) ELSE RETURN(C,_ ) 47 0. 9: CONCAT; STATE3:GETCHAR; WHILE ( DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE4: RETUR

25、N($INT,TOKEN ); =: STATE5:RETURN($ASSIGN,_ ); +: STATE6:RETURN($PLUS,_ ); *: STATE7:GETCHAR; STATE9: IF CHAR=* THEN RETURN($POWER,_ ); STATE8: RETRACT; RETURN($STAR,_ ); , : STATE10:RETURN($COMMA,_ ); ( : STATE11:RETURN($LPAR,_ ); ) : STATE12:RETURN($RPAR,_ ); ELSE STATE13: ERROR 这节介绍词法规那么的形式表示(正规式)

26、,从正规式向有限自动机的转化.正规式有限自动机词法分析器控制程序自动生成器转化合成第二节 正规式与有限自动机49一 根本概念 定义 1 字与字集 假设: 是一有穷字符集,它的每个元素称为一个字符; 字- 上的一个字,是由 中的字符所构成的一个有穷序列;空串-不包含任何元素的序列称为空串,记为;闭包*- 上所有可能的字的全体; 空字集-不含任何字的集合称为空字集;记为 = ; 例如: =a,b 那么 *=,a,b,aa,ab,ba,bb. 注意: , , 三者间的关系定义 2 连接运算 设 U,V * 那么 UV= | U, V 一般 UVVU Vn =VV.V 称为 V 的 n 次积50例如:

27、 设 U=a,aa, V=b 那么UV=ab,aab VU=ba,baa定义 3 V的闭包 设 V 为字集,且 V0= 令 V*=V0V1 V2 . V+= V* - 称V* 为V的闭包 称V+ 为V的正那么闭包 注意: * 与 V* 的区别.51 二 正规式与正规集 *是一个无穷集,在程序语言中,我们只研究满足词法规那么(正规式)的单词集(正规集).定义 1 正规式与正规集的递归定义 : 1) , 是 上的正规式, 所表示的正规集为 , ; 2) 假设 a ,那么 a 为正规式, 所表示的正规集为 a; 3) 设U,V 为 上的正规式, 所表示的正规集为 L(U),L(V); 那么 U|V为

28、 上的正规式, 所表示的正规集为 L(U) L(V); UV为 上的正规式, 所表示的正规集为 L(U) L(V); V* 为 上的正规式, 所表示的正规集为 L(V)* ; 4) 仅当有限次使用上述三步骤而定义的表达式,才是 上的正规式 , 而这些正规式所表示的字集才是上的正规集.52例如: 令=A.Z,0.9 那么整数的正规式为: (0|1|2.|9)(0|1|2.|9) * 所表示的正规集为所有整数; 标识符的正规式为:(A|B|.Z)(A|B|.Z| 0|1|.|9) * 所表示的正规集为所有标识符定义 2 假设两个正规式 U,V 所表示的正规集相同,即 L(V)=L(U), 那么称两

29、个正规式等价,记为 U=V.正规式的运算: 设 U V W 为正规式, 那么满足以下关系: 1) U|V=V|U 2) U|(V|W)=(U|V)|W 3) U(VW)=(UV)W 4) U(V|W)=UV|UW (U|V)W=UW|VW 5) U=U =U53三 确定有限自动机 一个确定有限自动机(DFA M)是一个五元式: DFA M=(S, , f,s0,Z) 其中 S 是一有限集,每个元素称为一个状态; 是一个有穷字母表,每个元素为一字符; f 是一个单值映射函数,f(si,a)=sj ( si , sj S, a ); 其含义为:在状态 si ,输入字符 a 时,将转换到下一状态sj

30、. 称sj为 si的后继状态. s0 S, 是唯一的初态; Z S ,是终态集. 一个DFAM可用状态转换矩阵或状态图表示54例如: DFAM=( 0,1,2,3, a,b, f, 0, 3) 其中f为: f(0,a)=1 f(1,a)=3 f(2,a)=1 f(3,a)=3 f(0,b)=2 f(1,b)=2 f(2,b)=3 f(3,b)=3状态转换矩阵可表示为: 状态图可表示为:ab012132213333状态字 符013初态终态2abbaaabb55四 非确定有限自动机 一个非确定有限自动机(NFA M)是一个五元式: NFA M=(S, , f,S0,Z) 其中 S 是一有限集,每个

31、元素称为一个状态; 是一个由穷字母表,每个元素为一字符; f 是一个多值映射函数,f(si,)=s i1 , s i2 ,. s ik ( si , si1 ,. , s ik S, *); 其含义为:在状态 si ,输入字串 时,将转换到下一状态集: s i1 , s i2 ,. s ik S0 S, 是初态集; Z S ,是终态集. 一个NFAM也可用状态图表示,此时每条边用字串表示.56例如:01初态终态2aabba,ba,ba,b终态DFAM 是 NFAM 的特例.定义: 状态图中,从初态到终态任一路径上的字串连接,称为该状态图可识别的单词,可识别单词的全体记为:L(M). 假设L(M

32、)= L(M),称M 与M等价. 57五 正规式与有限自动机的等价性 前面,介绍了正规式,DFAM,NFAM, 下面讨论这三个概念间的关系.定理1 : 对任意正规式V,存在一个NFAM ,使得L(V)=L(NFAM);证明: (1)构造一个拓广转换图 显然,该转换图能识别的 单词集为:L(V)XYV58(2) 进行如下等价变换,直到转换图的每条边上的标志为上的 字符. ijV1V2ijV1kV2aijV1 | V2iV1jV2bijV*ijkcV 等价变换后的转换图M 符合 NFAM的定义,显然有 L(V)=L(M).该定理说明,从正规式可逐步构造一个NFAM.59定义:设 S 是一个状态集,

33、 _CLOSURE(S)定义如下: a) 假设 s S,那么 s _CLOSURE(S); b) 假设 s S,那么 从 s 出发经过任意条 边所能到达的状态 s 都属于 _CLOSURE(S). 状态集_CLOSURE(S)称为 S 的_ 闭包.定理2: 对任意NFAM,存在一个DFAM ,使得L(DFAM)=L(NFAM);证明: (1) 对 NFAM 进行等价变换,使得变换后的转换图NFAM中 仅含边和 上的字符边; (2) 用状态转换矩阵M 表示NFAM;60其中, I0 为初态集的_ 闭包.Ii a = _ CLOSURE f(si 1 , a) f(si 2 , a) f(sik

34、, a) si 1 , si 2 ,. sik Ii (3) 将M 中的状态集换名, si = Ii 得到一新的状态转换矩阵 M , M 满足 DFAM 的定义.Iabc.I0I1Ii Ii a Ii b Ii cInM61证毕.推论: 对任意正规式V,存在一个DFAM ,使得L(DFAM)= L(V).Sabc.s0s1si si a si b si csnM62例如: 设正规式为 ( a|b) *(aa|bb)(a|b) *,求与之等价的DFAM. (1) 由定理 1 的证明方法,可如下构造NFAMXY( a|b) *(aa|bb)(a|b) *等价变换得到:513264aaaabbbbN

35、FAMXY(2) 用状态转换矩阵M 表示NFAM;63Iabx,5,1 5,1,3 5,1,45,1,3 5,1,3,2,6,y 5,1,45,1,4 5,1,3 5,1,4,2,6,y5,1,3,2,6,y 5,1,3,2,6,y 5,1,4,6,y5,1,4,2,6,y 5,1,3,6,y 5,1,4,2,6,y5,1,4,6,y 5,1,3,6,y 5,1,4,2,6,y5,1,3,6,y 5,1,3,2,6,y 5,1,4,6,yM(3) 将M 中的状态集换名, si = Ii 得到一新的状态转换矩阵 M注意: M 与 M等价.64Sabs0 s1 s2s1 s3 s2s2 s1 s4

36、 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5MM满足确定有限自动机的定义,状态图表示如下: s0s1s3s5s6s4abbs2aaaaaabbbbb65 第三节 词法分析器的 自动生成原理及LEX语言正规式确定自动机状态转换矩阵词法分析器控制程序自动生成器转化合成一 自动生成原理66二 LEX 语言 LEX 语言用正规式描述单词的词法规那么,并通过LEX编译,自动生成词法扫描器.LEX语言源程序LEX编译词法分析器 LEX语言源程序由两部分组成:正规式辅助定义式识别规则671 辅助定义式 辅助定义式是如下形式的 LEX 语句D1 R1D2 R2Dn Rn Ri为正规

37、式, Di为简名. 规定Ri中只能出现上的字符及之前已定义过的D1. Di -1 .例如:Letter A|B|.|Z|a|b|.|zDigit 0|1|2.|9Iden Letter(Letter| Digit)*682 识别规那么Unsignedint Digit( Digit)*Sign +| - | signedint Sign Unsignedint P1 A1P2 A2Pm Am Pi为正规式, 规定Pi中只能出现上的字符及D1. Dn ;P1. Pm 代表了某种高级语言的所有词形. Ai为一段程序代码,指出当识别出满足规那么Pi的单词时,扫描器应采取的动作.693 LEX编译的工

38、作原理 LEX编译对源程序进行处理, 产生一个词法分析器.主要有三个步骤: 1 对每条识别规那么Pi ,构造一个非确定有限自动机 Mi , 设一 初态X ,用边连接每个Mi的初态,构成一个总的NFAM; M1 M2 Mm x P1 P2Pm NFAM702根据定理 3 ,把 NFAM 确定化,得到一确定有限自动机 DFAM 的状态转换矩阵;3产生一个控制程序.输出如下所示的词法分析器:状态转换矩阵控制程序 控制程序用于扫描输入字符串,控制状态的转移;(对任何 转换矩阵,其控制程序是一样的)当识别出某词形Pi后,执行Ai. (返回种别码及值)词法分析器 71 本章习题1) 构造如下正规式相应的D

39、FA 11(0|1)*1012) 构造一个DFA,它接受=0,1上所有满足如下 条件的字符串: 每个1后都有0直接根在后边;根 据DFA的状态图,编写一个识别程序. 72第三章 语法分析 内容提要:上下文无关文法算符优先分析法递归下降分析法 语法分析的任务: 把单词符号作为根本单位,分析程序是否为 合法的程序.74第一节 上下文无关文法 上下文无关文法是这样一种文法: 它定义的语法单位,独立于该语法单位可能出现的环境,不必考虑上下文关系. 自然语言不是上下文无关文法; 程序语言是上下文无关文法;1. 上下文无关文法定义 上下文无关文法 G 是一个四元式: G =(VT,VN,S,P) 75VT

40、 : 是一个非空有限单词集,每个元素称为终结符号.VN: 是一个非空有限集,每个元素为非终结符号,代表了一 种语法单位. 且 VT VN=. 例如:表达式,短语,语句等S: 是一个非终结符号,称为开始符号,S VN. S 是文法 G 的最高层次的语法单位. 在程序语言中, S代表了程序这一语法概念.P: 是一个非空有限集,每个元素称为一条产生式;一条产 生式定义了一个非终结符.产生式形式如下: Pi i (Pi VN , i (VT VN ) * ) 称Pi定义为i . 762 文法的几点约定 a) 若 Pi i1 Pi i2 Pi ik则简写为: Pi i1|i2|. |ikb) 用英文大写

41、字母串代表非终结符; 英文小写字母串代表终结符; 希腊字母 等代表由VT,VN组成的符号串; 即: , (VT VN) * .c) 一个文法,可以仅用开始符号及产生式代替.例如:表达式的文法可以定义如下: E E+E|E-E|E*E|E/E|(E)|i E 为文法的开始符号, + - * / ( ) 为终结符.773 文法 G 与语言L(G)的关系及术语 从文法初始符开始,反复用产生式右部替换左部的非终结符,直到推出的符号串全部由终结符组成.得到G所定义的各种句子. 例如:E=E+E=E*E +E=i * E + E= i * i + E = i * i + i定义: 若B,经产生式 B替换后

42、得到 ,称B直接 推出. , , (VT VN) *,用=表示直接推出. 若存在1= 2 = 3.= n ,称1可推出n; 1= n表示经一步或若干步1可推出n. 1= n表示经零步或若干步1可推出n.定义:设S 是G的开始符号,若 S=, (VT VN) *, 则称 是 G的一个句型;若 VT *,则称是 G的一个句子. (*各概念举例)+*78定义: 文法 G 所产生的句子的全体,为G所描述的语言,记为 L(G)= |S=, VT * + 文法 G 正规式 V G: 描述句子结构; V:描述单词结构; L(G):G的全体句子; L(V):V的全体单词. 一个句型到另一个句型的推导有两种方式

43、:最左推导和最右推导: 最左推导是指每次直接推导,对句型的最左非终结符实行替换; 最右推导是指每次直接推导,对句型的最右非终结符实行替换.794 语法树与文法的二义性 语法树可以表示句型的推导及句型的层次结构. 语法树是一棵倒立树,根结点表示了文法的初始符号,每进行一步推导,树的叶结点构成的有序序列构成一个句型. 例如:E=E+E=E*E +E=i * E + E= i * i + E = i * i + i 可表示为: 语法树可以表示同一句型的多种推导,是多种推导的共性抽象.但未必代表了同一句型的所有推导:E=E*E=E*E +E =i * E + E = i * i + E = i * i

44、 + i EEE+EE*iii语法树EEE*EE+iii80定义: 假设文法 G 的某个句型存在两个不同的语法树表示,称该文法 是二义文法. 因此,文法 E 是二义文法. 二义性导致了i * i + i 的两种不同运算结果: (i*i)+i 以及 i*(i+i). 编译中应防止二义文法. E 文法的二义性是因为没有规定*,+ 运算符的优先顺序,改进 E 后,得到: ET|E+T TF|T*F F(E)| iE为表达式,T 为项,F 为因子 该文法对于句子i * i + i的各种推导,对应的语法树是唯一的.EET+TFT*iFiFi815 乔姆斯基文法分类定义:假设G =(VT,VN,S,P)的

45、每一个产生式型如: , (VT VN) * , 且 至少含有一个非终结符, 称 G 为 0 型文法; , (VT VN) * , 至少含有一个非终结符, 且满足 | , 称 G 为 1 型文法;A A VN , (VT VN) * , 称 G 为 2 型文法(上下文无关文法);A B 或A , A,B VN , VT * , 称 G 为 3 型文法(正那么文法).82第二节 语法分析概述语法分析的任务: 把单词符号作为根本单位,根据文法,分析源程序 (字串)是否为合法的程序.1 语法分析方法自下而上分析法自上而下分析法自下而上是指: 根据文法,对输入字串进行归约,假设能正确地归约 为文法的初始

46、符号,那么表示输入字串是合法的. 典型方法是算符优先分析法.自上而下是指: 从文法的初始符号进行推导,假设能推导出与输入 字串相同的句子,那么表示输入字串是合法的. 典型方法是递归下降分析法.832 归约栈 自下而上分析的根本技术是采用归约栈,如以下图所示:a1a2.an归约栈 字串 把输入符号依次移入栈内,当栈顶符号串形成某产生式的右部时,就归约为产生式左部非终结符;继续移入输入字串,直到栈中归约为文法初始符号S. 这种方法也称为移进归约法.84例如: G: SaAcBe分析句子 abbcde 是否 Ab|Ab 为合法的句子 BdbbcdeabcdeabbcdeaAcdeaAcdeaAbde

47、aAceaAcdeaAcBaAcBeS移入移入移入移入移入移入归约归约归约归约经分析,判定该句子是合法的句子.85定义:栈顶形成的某产生式候选称为归约串. 在上例中,当栈中为 aAb 时,存在两个归约串: b 及 Ab,它们都可以归约为 A. 假设使用 b 进行归约, 栈中得到 aAA, 导致最终不能归约为 S,因此,判定输入字串非法.这是一种错误归约, 原因在于栈中同时存在多个归约串,而只有一个归约串的选择是正确的,如 Ab. 把 Ab 称为可归约串,而 b 为非可归约串. 移进归约的关键问题,就是在栈中如何寻找可归约串.一旦能确定可归约串,句子分析的难点就迎刃而解.863 分析树 分析树也

48、是一棵倒立的树,用于描述归约过程.分析树是从叶结点开始建立的,每进行一次归约,就生成相应的节点.例如,上例中的归约过程可描述为如下分析树:SaAcBeAbbd分析树1234该归约树与句子abbcde 的语法树是一样的.874 标准归约简介 标准归约是一种较常用的自下而上分析方法.该方法实质上是最右推导的逆过程.例如:最右推导: S =aAcBe = aAcde = aAbcde =abbcde标准归约: abbcde = aAbcde= aAcde= aAcBe = S 标准归约采用句柄来刻画可归约串.定义:设 S 为文法 G 的开始符号,假设S A 且 A 其中 , (VT VN) * =*

49、=+那么称 为句型 相对于 A 的短语;假设A 那么称 为句型 相对于 A 的直接短语;一个句型的最左直接短语,称为句柄.88例如: 设句型为 aAbcde 该句型有两个直接短语: Ab, d S=aAcBe = aAcde AAb 所以Ab为直接短语; S=aAcBe = aAbcBe Bd 所以d为直接短语; 注意:b 不是句型 aAbcde 的直接短语; 因此,该句型的句柄为 AbcdeaAb 假设输入串是合法的,那么栈中内容与栈外内容的连接正好为 S 的一个句型. 当栈顶出现句柄时就进行归约.89标准归约分析算法: (1) 在栈底放入 # ,在输入串尾附上 #; (2) 逐个移入输入符

50、号,当栈顶形成句柄时,进行归约; (3) 重复 (2) 直到输入串已全部进栈,仅剩 #, 假设栈中归约为 #S, 表示分析成功,输入串为合法的句子, 否那么为非法句子. 这里,虽然指出对句柄进行归约,但并没有指出如何在栈中 确定句柄,这是第四章的内容.#S90第三节 算符优先分析法 算符优先分析法是一种简单实用的自下而上分析方法,本节将详细介绍该方法,包括 介绍 什么是算符优先文法,优先关系表构造,可归约串的刻画与寻找方法,算符优先分析算法等内容.1 算符优先文法定义1: 假设一个文法 G 的任何产生式右部,都不含两个相继出现的 非终结符, 那么称 G 为算符文法.91定义2: 设 G 是一个

51、算符文法,任何相继出现的终结符对之间存在如下三种归约优先顺序: 1) a b 当且仅当 G 中含有型如 P .ab. 或 P .aQb.的产生式; 2) a b 当且仅当 G 中含有型如 P .aR., 且 R b. 或 R Qb. ; 3) a b 当且仅当 G 中含有型如 P . Rb., 且 R .a 或 R .aQ. 优先关系可以用矩阵表示,称为优先关系表.+=+=+=+92定义3: 假设文法 G 的任何相继终结符对至多只满足以上关系之一, 称该文法为算符优先文法.2 优先关系表的构造 给定一个算符优先文法,求各终结符对间的优先关系.定义: FIRSTVT(P)=a | P a., 或

52、 P Qa. LASTVT(P)=a | P . a,或 P .aQ=+=+=+=+ 对每个非终结符求出这两个集合后,可按如下规则求出各终结符对之间的优先关系: 1) 对每一条产生式,若存在型如 P.ab.或 P.aQb. ,则令 a b; 该关系表示 a b 同时归约. 932) 对每一条产生式,若存在型如 P.aQ.的产生式,对 所有 b FIRSTVT(Q) , 令 a b; 该关系表示 b 应先于 a 归约为 Q.例如: 设文法 G 为: EE+T|T TT*F|F F (E)|i根据定义1,这是一个算符文法.94对每个非终结符,求出:FIRSTVT(F)= ( , i LASTVT(

53、F)= ) , i FIRSTVT(T)= * , ( , i LASTVT(T)= * , ) , i FIRSTVT(E)= + , * , ( , i LASTVT(E)= + , * , ) , i 优先关系表如下: +*()i+(i 根据定义3,该文法是算符优先文法953 可归约串 在算符优先分析法中,用最左素短语描述可归约串.定义:素短语是一个短语,它至少含有一个终结符,且除自身之外不 含更小的素短语. 一个句型的最左素短语即为可归约串.例如:设文法 G 为: EE+T|T 句型 为: F*F+i TT*F|F F (E)|i根据短语的定义,F*F+i 有如下四个短语:其中,素短语

54、有: F*F, i 两个,最左素短语为: F*FE E E F*F+iE E+i E F*FE F*F+T T iE T*F+i T F=*=*=*=*=+=+=+=+964 寻找最左素短语 根据定义,算符优先文法的句型必为如下形式: N1a1N2a2.NmamNm+1 其中 ai Vt Ni Vn Ni可有可无.定理: 一个算符优先文法 G 的任何句型的最左素短语,为满足 如下条件的最左子串: 最左素短语 = Niai.NjajNj+1 且满足ai -1 aiai ai +1 . aj aj aj+1 因此,可以在归约栈中,通过比较优先关系,寻找最左素短语.975 算符优先分析算法 1) 置

55、栈底及输入串尾为 # ,并设 # VT , VT #; 栈顶终结符为 ,输入字为 a ; 2) 若 a 或 a 且 a#, 则 a 移入栈中. 重复 2); 若 a, 则在栈中寻找最左素短语, 归约为 N ,重复 2); 若=a=#, 且栈中为 #N, 则分析成功;否则,输入串为非法字串.98例如: 设文法 G 为: EE+T|T TT*F|F F (E)|i +*()i+(i优先关系表如右,分析表达式 i+i*i 是否为合法的表达式i+i*i#+i*i#i+i*i#N i*i#N+移入归约移入移入99*i# N+i*i#N+Ni# N+N*归约移入移入# N+N* i归约# N+N* N归约

56、# N+N归约# N为合法句子 算符优先分析过程中,产生式以及非终结符名已不再起作用,只有优先关系表决定了分析过程.100第四节 递归下降分析法 递归下降分析法是一种自顶向下分析方法,从文法开始符号自左向右进行推导,假设能推出一个与输入串相等的句子,说明输入串是合法的句子.1 递归下降分析法存在的问题 递归下降分析法本质上是一种最左推导,根据输入串选择相应产生式进行推导.101例如: 设文法为 G : Sa | icT输入串为: icta TtSeS | tS推导如下: S icta 根据输入字 i icT icta 根据输入字 t ictSeS icta 根据输入字 a ictaeS ict

57、a 不匹配 T 有两个候选产生式,如果选择第二个候选推导,则 S icta 根据输入字 i icT icta 根据输入字 t ictS icta 根据输入字 a icta icta 匹配=102 从上面分析可知: 假设允许 P a |a . 的产生式,那么输入字 a 面临多个产生式可选择用于推导,这种情况下,推导只能试探性的进行,一旦后续推导中不能匹配,再回过头( 回溯 ) 选择下一个产生式候选进行推导. 这种方式效率低, 因此,应消除回溯. 另外,递归下降分析中,不允许有如下的左递归推导: P P 这种左递归推导,会导致不匹配任何输入字而无止境的推导(死循环). 因此,递归下降分析法中存在两

58、个主要问题: 1) 文法的左递归 2) 文法的回溯=+1032 无回溯递归下降分析 对文法的要求 要做到无回溯分析, 实际上就是要求文法无回溯及左递归.定义: 设 A 1| 2. | m , A VN , i (VT VN) * ; 令 FIRST(i ) = a | i a., a VT 若 i ,则 FIRST(i ) (i 可能推出的所有首终结符的集合)定义: 设 S为 G的开始符, 令 FOLLOW(A)=a | S .Aa., a VT 若 S .A ,则 # FOLLOW(A) ( 从 S 开始的推导中,所有可能紧跟在 A 之后的终结符)=*=*=+=+104定义: 设 A 1|

59、2. | m , 且有 1) FIRST(i ) FIRST(j )= ,i j ; 2) 假设 FIRST(i ),那么对任意 i ( 1im) 满足 FIRST(i ) FOLLOW(A) = ; 假设文法 G 满足上面条件,那么 G 就是无回溯文法,也称为 LL(1) 文法. 换句话说,只要根据输入的一个字,就能唯一地确定产生式候选,进行最左推导. 一个文法是LL(1) 文法,且不含左递归,就可以进行无回溯的递归下降分析.1053 消除文法的左递归 1) 直接左递归的消除 假设 文法 G 中含有型如 PP | 的产生式, 称 G 含有直接左递归. 可将直接左递归改写为等价的不含左递归的产

60、生式: P P P P | 这两组产生式都可推导出: *; 一般而言,假设产生式为: PP 1 | P 2 |. |P m| 1 | 2 |.| n 那么可改写为如下等价的产生式: P 1 P | 2 P |.| n P P 1 P | 2 P |. | m P | 1062) 间接左递归的消除 若 文法 G 中含有型如 P P 的推导, 称 G 含有间接左递归. 间接左递归可通过如下算法消除:a) 令 VN =P1 ,P2 ,., Pn b) for i:=1 to n do for j:=1 to i-1 do 把型如PiPj 的规则改写为: Pi 1 | 2 |.| k 其中 Pj 1