编译原理词法解析学习教案

1、会计学1编译原理词法编译原理词法(cf)解析解析第一页，共42页。2第一节 状态(zhungti)转换图一 单词分类及表示 编译中,把高级语言的单词分为五类: 标识符,基本(jbn)字,常数,运算符,界符 基本(jbn)字,运算符,界符都是有限可枚举的;而标识符,常数可认为是无限的. 简单起见,单词可表示为如下二元组: (单词分类号,单词自身值); 或者为: (单词种别码,单词自身值); 标识符,常数 各为一个种别码,而由于基本(jbn)字,运算符,界符的有限性,可以设计为一字一个种别码.第1页/共42页第二页，共42页。3例如:单词 单词种别码分类号 标识符1 1常数 2 2if 3 3th

2、en4 3end90 3,91 4;92 4=151 5+152 5保留字界符运算符第2页/共42页第三页，共42页。4二 词法分析器的设计1 源程序的预处理子程序 源程序中,存在许多(xdu)编辑用的符号,它们对程序逻辑功能无任何影响. 例如:回车,换行,多余空白符,注释行等.在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单.源程序输入(shr)缓冲区预处理子程序扫描(somio)缓冲区2扫描缓冲区1 缓冲区分为两部分,每个长度为256字节,这样单词的总长度可达到256字节.预处理子程序把处理好的字符串轮流放入两个缓冲区中,供词法分析程序使用.第3页/共42页第四页，共42页。52

3、 词法分析程序 词法分析程序又称为词法分析器或扫描器.可以单独为一个程序;也可以作为整个(zhngg)编译程序的一个子程序,当需要一个单词时,就调用词法分析子程序返回一个单词.这里,作为子程序介绍. 词法分析器的结构:源程序输入(shr)缓冲区预处理子程序扫描(somio)缓冲区2扫描缓冲区1词法分析子程序调用返回一单词数据第4页/共42页第五页，共42页。63 词法规则的表示-状态转换图定义:状态转换图是一有向图,由有限个结点(ji din)及有向边连接而成; 每个结点(ji din)称为状态;状态图有一个初态,多个终态;每条边上 有相应的字符. 状态转换图用于表示单词结构,从状态转换图的初

4、态到终态间,每条路径上字符的连接,就构成了该状态图的合法单词.例如: 012初态终态字母(zm)字母(zm)数字其它*1标识符的状态图表示:星号表示单词尾部多跟一个字符,应该去掉.第5页/共42页第六页，共42页。7012初态终态数字(shz)数字(shz)其它(qt)*2整数的状态图表示:016初态终态数字数字其它*3实数的状态图表示:23456数字数字 数字E+或 数字E其它数字第6页/共42页第七页，共42页。84 单词的识别(shbi) 状态图即可以表示单词规则,同时也可以用于识别(shbi)单词. 设有一字符串S = s1s2.sn, 若状态图中存在一初态到终态的路径,且路径上字符的

5、连接为: s1s2.sn, 称 S 可被状态图识别(shbi).例如: S=var1012初态终态var1其它(qt)* 保留字由于满足标识符定义,因此可以跟标识符用同样的状态图表示(biosh)与识别,只需增加一个保留字表,当识别出一个标识符时,通过查保留字表来区别保留字及普通标识符.因此 var1 是一个合法的标识符.第7页/共42页第八页，共42页。95 一个简单示例 构造一个简单语言所有单词的状态(zhungti)转换图.该语言的单词种类如下表所示:单词符号 种别码 助记符 内码值 DIMIFDOSTOPEND标识符正常数=+*,()1234567891011121314$DIM$IF

6、$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR( 1 , )( 2 , )( 3 , )( 4 , )( 5 , )( 6 , 串值)( 7 , 数值)( 8 , )( 9 , )( 10, )( 11, )( 12, )( 13, )( 14, )第8页/共42页第九页，共42页。100 1 2初态终态字母(zm)字母(zm)数字(shz)其它*空白 3 4 终态数字数字非数字* 5 = 6 + 7* 9 8*非 * *10,11(12)13其它第9页/共42页第十页，共42页。116 状态转换图的程序实现 为便于程序实现

7、,假设每个单词间都有界符或运算符或空格(kn )隔开,并引入下面的全局变量及子程序:1) CHAR 字符变量2) TOKEN 单词字符串3) GETCHAR 读一个字符到 CHAR 中4) GETBC 读一个非空白字符到CHAR 中5) CONCAT 把CHAR 中字符连接到TOKEN 之后6) LETTER 判断CHAR 中字符是否为字母7) DIGIT 判断CHAR 中字符是否为数字8) RESERVE 用TOKEN中的字符串查找保留字表,并返回保留 字种别码,若返回零,则非保留字9) RETRACT 把CHAR 中字符回送到缓冲区第10页/共42页第十一页，共42页。12 下面分析(fn

8、x)状态图的结构特点.每个状态图都由三种结构构成: 分支结构 循环结构 终结点1分支结构程序设计 i i2i1 inc1c2cnstate i:GETCHAR; CASE CHAR OF c1 :CONCAT；state i1: . c2 :CONCAT；state i2: . cn :CONCAT；state in: . ELSE ERROR END;第11页/共42页第十二页，共42页。132循环(xnhun)结构程序设计 i j C其它(qt)state i:GETCHAR; WHILE CHAR=C DO CONCAT;GETCHAR; RETRACT；state j: . 3终结点程

9、序设计 一般对应一条返回语句: return( c,val); c 为种别码, val 为单词值. 带 * 号的终结点,必须用RETRACT 退还多余字符(z f) 下面程序为简单示例语言的实现:第12页/共42页第十三页，共42页。14TYPE WORDTYPE=RECORD C：INTEGER； VAL：CHAR； END；FUNCTION RETURN_WORD( ):WORDTYPE; STATE0: TOKEN:=;GETCHAR;GETBC; CASE CHAR OF A.Z: CONCAT; STATE1:GETCHAR; WHILE (LETTER OR DIGIT) DO C

10、ONCAT;GETCHAR; RETRACT； STATE2: C:=RESERVE; IF C=0 THEN RETURN($ID,TOKEN) ELSE RETURN(C,_ ) 第13页/共42页第十四页，共42页。15 0. 9: CONCAT; STATE3:GETCHAR; WHILE ( DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE4: RETURN($INT,TOKEN ); =: STATE5:RETURN($ASSIGN,_ ); +: STATE6:RETURN($PLUS,_ ); *: STATE7:GETCHAR; STATE9:

11、 IF CHAR=* THEN RETURN($POWER,_ ); STATE8: RETRACT; RETURN($STAR,_ ); , : STATE10:RETURN($COMMA,_ ); ( : STATE11:RETURN($LPAR,_ ); ) : STATE12:RETURN($RPAR,_ ); ELSE STATE13: ERROR第14页/共42页第十五页，共42页。 这节介绍词法规则的形式(xngsh)表示(正规式),从正规式向有限自动机的转化.正规(zhnggu)式有限(yuxin)自动机词法分析器控制程序自动生成器转化合成第二节 正规式与有限自动机第15页/共

12、42页第十六页，共42页。17一 基本概念 定义 1 字与字集 假设: 是一有穷字符集,它的每个元素称为一个(y )字符; 字- 上的一个(y )字,是由 中的字符所构成的一个(y )有穷序列;空串-不包含任何元素的序列称为空串,记为;闭包*- 上所有可能的字的全体; 空字集-不含任何字的集合称为空字集;记为 = ; 例如: =a,b 则 *=,a,b,aa,ab,ba,bb. 注意: , , 三者间的关系定义 2 连接运算 设 U,V * 则 UV= | U, V 一般 UVVU Vn =VV.V 称为 V 的 n 次积第16页/共42页第十七页，共42页。18例如: 设 U=a,aa, V

13、=b 则UV=ab,aab VU=ba,baa定义 3 V的闭包 设 V 为字集,且 V0= 令 V*=V0V1 V2 . V+= V* - 称V* 为V的闭包 称V+ 为V的正则闭包 注意(zh y): * 与 V* 的区别.第17页/共42页第十八页，共42页。19 二 正规式与正规集 *是一个无穷集,在程序语言中,我们只研究满足词法规则(正规式)的单词集(正规集).定义 1 正规式与正规集的递归定义 : 1) , 是 上的正规式, 所表示的正规集为 , ; 2) 若 a ,则 a 为正规式, 所表示的正规集为 a; 3) 设U,V 为 上的正规式, 所表示的正规集为 L(U),L(V);

14、 则 U|V为 上的正规式, 所表示的正规集为 L(U) L(V); UV为 上的正规式, 所表示的正规集为 L(U) L(V); V* 为 上的正规式, 所表示的正规集为 L(V)* ; 4) 仅当有限次使用上述(shngsh)三步骤而定义的表达式,才是 上的正规式 , 而这些正规式所表示的字集才是上的正规集.第18页/共42页第十九页，共42页。20示例: 令=A.Z,0.9 则整数的正规式为: (0|1|2.|9)(0|1|2.|9) * 所表示的正规集为所有整数; 标识符的正规式为:(A|B|.Z)(A|B|.Z| 0|1|.|9) * 所表示的正规集为所有标识符定义(dngy) 2

15、若两个正规式 U,V 所表示的正规集相同,即 L(V)=L(U), 则称两个正规式等价,记为 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 =U第19页/共42页第二十页，共42页。21三 确定有限自动机 一个确定有限自动机(DFA M)是一个五元式: DFA M=(S, , f,s0,Z) 其中 S 是一有限集,每个元素称为一个状态; 是一个有穷字母表,每个元素为一字符(z f); f 是一个单值映射函数,f

16、(si,a)=sj ( si , sj S, a ); 其含义为:在状态 si ,输入字符(z f) a 时,将转换到下一状态sj. 称sj为 si的后继状态. s0 S, 是唯一的初态; Z S ,是终态集. 一个DFAM可用状态转换矩阵或状态图表示第20页/共42页第二十一页，共42页。22例如: 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状态转换矩阵(j zhn)可表示为: 状态图可表示为:ab012132213333

17、状态字 符013初态终态2abbaaabb第21页/共42页第二十二页，共42页。23四 非确定有限(yuxin)自动机 一个非确定有限(yuxin)自动机(NFA M)是一个五元式: NFA M=(S, , f,S0,Z) 其中 S 是一有限(yuxin)集,每个元素称为一个状态; 是一个由穷字母表,每个元素为一字符; 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 ,是终态

18、集. 一个NFAM也可用状态图表示,此时每条边用字串表示.第22页/共42页第二十三页，共42页。24例如(lr):01初态终态2aabba,ba,ba,b终态DFAM 是 NFAM 的特例.定义: 状态图中,从初态到终态任一路径上的字串连接(linji),称为该状态图可识别的单词,可识别单词的全体记为:L(M). 若L(M)= L(M),称M 与M等价. 第23页/共42页第二十四页，共42页。25五 正规式与有限自动机的等价性 前面,介绍了正规式,DFAM,NFAM, 下面讨论这三个概念间的关系.定理1 : 对任意正规式V,存在一个NFAM ,使得L(V)=L(NFAM);证明: (1)构

19、造一个拓广转换图 显然,该转换图能识别(shbi)的 单词集为:L(V)XYV第24页/共42页第二十五页，共42页。26(2) 进行如下等价变换(binhun),直到转换图的每条边上的标志为上的 字符. ijV1V2ijV1kV2aijV1 | V2iV1jV2bijV*ijkcV 等价变换后的转换图M 符合 NFAM的定义,显然有 L(V)=L(M).该定理说明,从正规式可逐步构造(guzo)一个NFAM.第25页/共42页第二十六页，共42页。27定义:设 S 是一个状态集, _CLOSURE(S)定义如下(rxi): a) 若 s S,则 s _CLOSURE(S); b) 若 s S

20、,则 从 s 出发经过任意条 边所能到达的状态 s 都属于 _CLOSURE(S). 状态集_CLOSURE(S)称为 S 的_ 闭包.定理2: 对任意NFAM,存在一个DFAM ,使得L(DFAM)=L(NFAM);证明: (1) 对 NFAM 进行等价变换,使得变换后的转换图NFAM中 仅含边和 上的字符边; (2) 用状态转换矩阵M 表示NFAM;第26页/共42页第二十七页，共42页。28其中, I0 为初态集的_ 闭包.Ii a = _ CLOSURE f(si 1 , a) f(si 2 , a) f(sik , a) si 1 , si 2 ,. sik Ii (3) 将M 中的

21、状态集换名, si = Ii 得到一新的状态转换(zhunhun)矩阵 M , M 满足 DFAM 的定义.Iabc.I0I1Ii Ii a Ii b Ii cInM第27页/共42页第二十八页，共42页。29证毕.推论: 对任意正规式V,存在(cnzi)一个DFAM ,使得L(DFAM)= L(V).Sabc.s0s1si si a si b si csnM第28页/共42页第二十九页，共42页。30示例: 设正规式为 ( a|b) *(aa|bb)(a|b) *,求与之等价的DFAM. (1) 由定理 1 的证明方法(fngf),可如下构造NFAMXY( a|b) *(aa|bb)(a|b

22、) *等价变换(binhun)得到:513264aaaabbbbNFAMXY(2) 用状态转换(zhunhun)矩阵M 表示NFAM;第29页/共42页第三十页，共42页。31Iabx,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 中的状态集换名, s

23、i = Ii 得到(d do)一新的状态转换矩阵 M注意: M 与 M等价.第30页/共42页第三十一页，共42页。32Sabs0 s1 s2s1 s3 s2s2 s1 s4 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5MM满足确定有限自动机的定义(dngy),状态图表示如下: s0s1s3s5s6s4abbs2aaaaaabbbbb第31页/共42页第三十二页，共42页。33 第三节 词法分析器的 自动生成(shn chn)原理及LEX语言正规(zhnggu)式确定自动机状态转换(zhunhun)矩阵词法分析器控制程序自动生成器转化合成一 自动生成原理第32页/共4

24、2页第三十三页，共42页。34二 LEX 语言 LEX 语言用正规式描述单词(dnc)的词法规则,并通过LEX编译,自动生成词法扫描器.LEX语言(yyn)源程序LEX编译(biny)词法分析器 LEX语言源程序由两部分组成:正规式辅助定义式识别规则第33页/共42页第三十四页，共42页。351 辅助定义(dngy)式 辅助定义(dngy)式是如下形式的 LEX 语句D1 R1D2 R2Dn Rn Ri为正规式, Di为简名. 规定(gudng)Ri中只能出现上的字符及之前已定义过的D1. Di -1 .例如:Letter A|B|.|Z|a|b|.|zDigit 0|1|2.|9Iden L

25、etter(Letter| Digit)*第34页/共42页第三十五页，共42页。362 识别(shbi)规则Unsignedint Digit( Digit)*Sign +| - | signedint Sign Unsignedint P1 A1P2 A2Pm Am Pi为正规式, 规定Pi中只能出现(chxin)上的字符及D1. Dn ;P1. Pm 代表了某种高级语言的所有词形. Ai为一段程序代码,指出当识别出满足规则Pi的单词时,扫描器应采取的动作.第35页/共42页第三十六页，共42页。373 LEX编译(biny)的工作原理 LEX编译(biny)对源程序进行处理, 产生一个词法分析器.主要有三个步骤: 1 对每条识别规则Pi ,构造一个非确定有限自动机 Mi , 设一 初态X ,用边连接每个Mi的