编译原理2词法解析优秀PPT.ppt

《编译原理2词法解析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《编译原理2词法解析优秀PPT.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1内容提要内容提要:状态转换图状态转换图正规式与有限制动机正规式与有限制动机词法分析器的自动生成词法分析器的自动生成词法分析器词法分析器源程序源程序单词序列单词序列第一节第一节 状态转换图状态转换图一一 单词分类及表示单词分类及表示 编译中编译中,把高级语言的单词分为五类把高级语言的单词分为五类:标识符标识符,基本字基本字,常数常数,运算符运算符,界符界符 基本字基本字,运算符运算符,界符都是有限可枚举的界符都是有限可枚举的;而标识而标识符符,常数可认为是无限的常数可认为是无限的.简洁起见简洁起见,单词可表示为如下二元组单词可表示为如下二元组:(单词分类号单词分类号,单词自身值单词自身值);或

2、者为或者为:(单词种别码单词种别码,单词自身值单词自身值);标识符标识符,常数常数 各为一个种别码各为一个种别码,而由于基本字而由于基本字,运算符运算符,界符的有限性界符的有限性,可以设计为一字一个种别码可以设计为一字一个种别码.2例如例如:单词单词 单词种别码单词种别码分类号分类号 标识符标识符1 1常数常数 2 2if 3 3then4 3end90 3,91 4;92 4=151 5+152 5保留字保留字界符界符运算符运算符3二二 词法分析器的设计词法分析器的设计1 源程序的预处理子程序源程序的预处理子程序 源程序中源程序中,存在很多编辑用的符号存在很多编辑用的符号,它们对程序逻它们对

3、程序逻辑功能无任何影响辑功能无任何影响.例如例如:回车回车,换行换行,多余空白符多余空白符,注注释行等释行等.在词法分析之前在词法分析之前,首先要剔除掉这些符号首先要剔除掉这些符号,使使得词法分析更为简洁得词法分析更为简洁.源程序源程序输入缓冲区输入缓冲区预处理子程序预处理子程序扫描缓冲区扫描缓冲区2扫描缓冲区扫描缓冲区1 缓冲区分为两部分缓冲区分为两部分,每每个长度为个长度为256字节字节,这样这样单词的总长度可达到单词的总长度可达到256字节字节.预处理子程序预处理子程序把处理好的字符串轮番把处理好的字符串轮番放入两个缓冲区中放入两个缓冲区中,供供词法分析程序运用词法分析程序运用.42 词

4、法分析程序词法分析程序 词法分析程序又称为词法分析器或扫描器词法分析程序又称为词法分析器或扫描器.可以单独为一个可以单独为一个程序程序;也可以作为整个编译程序的一个子程序也可以作为整个编译程序的一个子程序,当须要一个单词当须要一个单词时时,就调用词法分析子程序返回一个单词就调用词法分析子程序返回一个单词.这里这里,作为子程序介绍作为子程序介绍.词法分析器的结构词法分析器的结构:源程序源程序输入缓冲区输入缓冲区预处理子程序预处理子程序扫描缓冲区扫描缓冲区2扫描缓冲区扫描缓冲区1词法分析子程序词法分析子程序调用调用返回一单词返回一单词数据数据53 词法规则的表示词法规则的表示-状态转换图状态转换图

5、定义定义:状态转换图是一有向图状态转换图是一有向图,由有限个结点及有向边连接而成由有限个结点及有向边连接而成;每个结点称为状态每个结点称为状态;状态图有一个初态状态图有一个初态,多个终态多个终态;每条边上每条边上 有相应的字符有相应的字符.状态转换图用于表示单词结构状态转换图用于表示单词结构,从状态转换图的初态到终态从状态转换图的初态到终态间间,每条路径上字符的连接每条路径上字符的连接,就构成了该状态图的合法单词就构成了该状态图的合法单词.例如例如:012初态初态终态终态字母字母字母字母数字数字其它其它*1标识符的状态图表示标识符的状态图表示:星号表示单词尾部多跟星号表示单词尾部多跟一个字符一

6、个字符,应当去掉应当去掉.6012初态初态终态终态数字数字数字数字其它其它*2整数的状态图表示整数的状态图表示:016初态初态终态终态数字数字数字数字其它其它*3实数的状态图表示实数的状态图表示:23456数字数字数字数字 数字数字E+或或 数字数字E其它其它数字数字74 单词的识别单词的识别 状态图即可以表示单词规则状态图即可以表示单词规则,同时也可以用于识别单词同时也可以用于识别单词.设有一字符串设有一字符串S=s1s2.sn,若状态图中存在一初态到终态的若状态图中存在一初态到终态的路径路径,且路径上字符的连接为且路径上字符的连接为:s1s2.sn,称称 S 可被状态图识别可被状态图识别.

7、例如例如:S=var1012初态初态终态终态var1其它其它*保留字由于满足标识符定义保留字由于满足标识符定义,因此可以跟标识符用同样的状因此可以跟标识符用同样的状态图表示与识别态图表示与识别,只需增加一个保留字表只需增加一个保留字表,当识别出一个标识符时当识别出一个标识符时,通过查保留字表来区分保留字及一般标识符通过查保留字表来区分保留字及一般标识符.因此因此 var1 是一个合法的标识符是一个合法的标识符.85 一个简洁示例一个简洁示例 构造一个简洁语言全部单词的状态转换图构造一个简洁语言全部单词的状态转换图.该语言的单词种类如下表所示该语言的单词种类如下表所示:单词符号单词符号 种别码种

8、别码 助记符助记符 内码值内码值 DIMIFDOSTOPEND标识符标识符正常数正常数=+*,()1234567891011121314$DIM$IF$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,)90 1 2初态初态终态终态字母字母字母字母数字数字其它其它*空白空白 3 4 终态终态数字数字数字数字非数字非数字*5=6+7*9 8*非非*10,11(12)13其它其它106 状态转换图的程

9、序实现状态转换图的程序实现 为便于程序实现为便于程序实现,假设每个单词间都有界符或运算符或空格隔假设每个单词间都有界符或运算符或空格隔开开,并引入下面的全局变量及子程序并引入下面的全局变量及子程序:1)CHAR 字符变量字符变量2)TOKEN 单词字符串单词字符串3)GETCHAR 读一个字符到读一个字符到 CHAR 中中4)GETBC 读一个非空白字符到读一个非空白字符到CHAR 中中5)CONCAT 把把CHAR 中字符连接到中字符连接到TOKEN 之后之后6)LETTER 推断推断CHAR 中字符是否为字母中字符是否为字母7)DIGIT 推断推断CHAR 中字符是否为数字中字符是否为数字

10、8)RESERVE 用用TOKEN中的字符串查找保留字表中的字符串查找保留字表,并返回保留并返回保留 字种别码字种别码,若返回零若返回零,则非保留字则非保留字9)RETRACT 把把CHAR 中字符回送到缓冲区中字符回送到缓冲区11 下面分析状态图的结构特点下面分析状态图的结构特点.每个状态图都由三种结构构成每个状态图都由三种结构构成:分支结构分支结构 循环结构循环结构 终结点终结点1分支结构程序设计分支结构程序设计 i i2i1 inc1c2cnstate i:GETCHAR;CASE CHAR OF c1:CONCAT；state i1:.c2:CONCAT；state i2:.cn:CO

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

12、；VAL：CHAR；END；FUNCTION RETURN_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,_)14 0.9:CONCAT;STATE3:GETCHAR;WHILE (DIGIT)DO CONCAT;GETCHAR;RETRACT；STATE4

13、:RETURN($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:ERROR1516 这节介绍词法规则的这节介绍词法规则的形式表示形式表示(正规式正规式),从正规式向

14、有限自动从正规式向有限自动机的转化机的转化.正规式正规式有限自动机有限自动机词法分析器词法分析器限制程序限制程序自动生成器自动生成器转化转化合成合成其次节 正规式与有限自动机一一 基本概念基本概念 定义定义 1 字与字集字与字集 假设假设:是一有穷字符集是一有穷字符集,它的每个元素称为一个字符它的每个元素称为一个字符;字字-上的一个字上的一个字,是由是由 中的字符所构成的一个有穷序列中的字符所构成的一个有穷序列;空串空串-不包含任何元素的序列称为空串不包含任何元素的序列称为空串,记为记为;闭包闭包*-上全部可能的字的全体上全部可能的字的全体;空字集空字集-不含任何字的集合称为空字集不含任何字的

15、集合称为空字集;记为记为=;例如例如:=a,b 则则 *=,a,b,aa,ab,ba,bb.留意留意:,三者间的关系三者间的关系定义定义 2 连接运算连接运算 设设 U,V *则则 UV=|U,V 一般一般 UVVU Vn =VV.V 称为称为 V 的的 n 次积次积17例如例如:设设 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*的区分的区分.1819示例示例:令令=A.Z,0.9 则

16、整数的正规式为则整数的正规式为:(0|1|2.|9)(0|1|2.|9)*所表示的正规集为全部整数所表示的正规集为全部整数;标识符的正规式为标识符的正规式为:(A|B|.Z)(A|B|.Z|0|1|.|9)*所表示的正规集为全部标识符所表示的正规集为全部标识符定义定义 2 若两个正规式若两个正规式 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)

17、W 4)U(V|W)=UV|UW (U|V)W=UW|VW 5)U=U=U20三三 确定有限自动机确定有限自动机 一个确定有限自动机一个确定有限自动机(DFA M)是一个五元式是一个五元式:DFA M=(S,f,s0,Z)其中其中 S 是一有限集是一有限集,每个元素称为一个状态每个元素称为一个状态;是一个有穷字母表是一个有穷字母表,每个元素为一字符每个元素为一字符;f 是一个单值映射函数是一个单值映射函数,f(si,a)=sj(si,sj S,a);其含义为其含义为:在状态在状态 si ,输入字符输入字符 a 时时,将转换到下一状态将转换到下一状态sj.称称sj为为 si的后继状态的后继状态.

18、s0 S,是唯一的初态是唯一的初态;Z S,是终态集是终态集.一个一个DFAM可用可用状态转换矩阵状态转换矩阵或或状态图状态图表示表示21例如例如: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初态初态终态终态2abbaaabb22四四 非确定有限自动机非确定有限自动机 一个非确定有限自动机一个非确定有限自动机(N

19、FA M)是一个五元式是一个五元式:NFA M=(S,f,S0,Z)其中其中 S 是一有限集是一有限集,每个元素称为一个状态每个元素称为一个状态;是一个由穷字母表是一个由穷字母表,每个元素为一字符每个元素为一字符;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也可用也可用状态图状态图表示表示,此时每条边用字串表示

20、此时每条边用字串表示.23例如例如:01初态初态终态终态2aabba,ba,ba,b终态终态DFAM 是是 NFAM 的特例的特例.定义定义:状态图中状态图中,从初态到终态任一路径上的字串连接从初态到终态任一路径上的字串连接,称为该状称为该状态图可识别的单词态图可识别的单词,可识别单词的全体记为可识别单词的全体记为:L(M).若若L(M)=L(M),称称M 与与M等价等价.24五五 正规式与有限自动机的等价性正规式与有限自动机的等价性 前面前面,介绍了正规式介绍了正规式,DFAM,NFAM,下面探讨这三个概念间的下面探讨这三个概念间的关系关系.定理定理1:对随意正规式对随意正规式V,存在一个存

21、在一个NFAM ,使得使得L(V)=L(NFAM);证明证明:(1)构造一个拓广转换图构造一个拓广转换图 明显明显,该转换图能识别的该转换图能识别的 单词集为单词集为:L(V)XYV25(2)进行如下等价变换进行如下等价变换,直到转换图的每条边上的标记为直到转换图的每条边上的标记为上的上的 字符字符.ijV1V2ijV1kV2aijV1|V2iV1jV2bijV*ijkcV 等价变换后的转换图等价变换后的转换图M 符合符合 NFAM的定义的定义,明显有明显有 L(V)=L(M).该定理说明该定理说明,从正规式可逐步构造一个从正规式可逐步构造一个NFAM.26定义定义:设设 S 是一个状态集是一

22、个状态集,_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 表示

23、表示NFAM;27其中其中,I0 为初态集的为初态集的_ 闭包闭包.Ii a=_ CLOSURE f(si 1,a)f(si 2,a)f(sik,a)si 1,si 2,.sik Ii(3)将将M 中的状态集换名中的状态集换名,si=Ii 得到一新的状态转换矩阵得到一新的状态转换矩阵 M,M 满足满足 DFAM 的定义的定义.Iabc.I0I1Ii Ii a Ii b Ii cInM28证毕证毕.推论推论:对随意正规式对随意正规式V,存在一个存在一个DFAM ,使得使得L(DFAM)=L(V).Sabc.s0s1si si a si b si csnM29示例示例:设正规式为设正规式为 (a|

24、b)*(aa|bb)(a|b)*,求与之等价的求与之等价的DFAM.(1)由定理由定理 1 的证明方法的证明方法,可如下构造可如下构造NFAMXY(a|b)*(aa|bb)(a|b)*等价变换得到等价变换得到:513264aaaabbbbNFAMXY(2)用状态转换矩阵用状态转换矩阵M 表示表示NFAM;30Iabx,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

25、,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等价等价.31Sabs0 s1 s2s1 s3 s2s2 s1 s4 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5MM满足确定有限自动机的定义满足确定有限自动机的定义,状态图状态图表示如下表示如下:s0s1s3s5s6s4abbs2aaaaaabbbbb32 第三节第三节 词法分析器的词法分析器的 自动生成原理及自动生成原理及LEX语言语言正规式

26、正规式确定自动机确定自动机状态转换矩阵状态转换矩阵词法分析器词法分析器限制程序限制程序自动生成器自动生成器转化转化合成合成一一 自动生成原理自动生成原理33二二 LEX 语言语言 LEX 语言用正规式描述单词的词法规则语言用正规式描述单词的词法规则,并通过并通过LEX编译编译,自自动生成词法扫描器动生成词法扫描器.LEX语言语言源程序源程序LEX编译编译词法分析器词法分析器 LEX语言源程序由两部分组成语言源程序由两部分组成:正规式辅助定义式正规式辅助定义式识别规则识别规则341 协助定义式协助定义式 协助定义式是如下形式的协助定义式是如下形式的 LEX 语句语句D1 R1D2 R2Dn Rn

27、 Ri为正规式为正规式,Di为简名为简名.规定规定Ri中只能出现中只能出现上的字符及之前上的字符及之前已定义过的已定义过的D1.Di-1.例如例如:Letter A|B|.|Z|a|b|.|zDigit 0|1|2.|9Iden Letter(Letter|Digit)*352 识别规则识别规则Unsignedint Digit(Digit)*Sign +|-|signedint Sign Unsignedint P1 A1P2 A2Pm Am Pi为正规式为正规式,规定规定Pi中只能出现中只能出现上上的字符及的字符及D1.Dn;P1.Pm 代表了某代表了某种高级语言的全部词形种高级语言的全部

28、词形.Ai为一段程序代码为一段程序代码,指出当识别出满指出当识别出满足规则足规则Pi的单词时的单词时,扫描器应实行的动作扫描器应实行的动作.363 LEX编译的工作原理编译的工作原理 LEX编译对源程序进行处理编译对源程序进行处理,产生一个词法分析器产生一个词法分析器.主要有三个步骤主要有三个步骤:1 对每条识别规则对每条识别规则Pi,构造一个非确定有限自动机构造一个非确定有限自动机 Mi ,设一设一 初态初态X,用边连接每个用边连接每个Mi的初态的初态,构成一个总的构成一个总的NFAM;M1 M2 Mm x P1 P2Pm NFAM372依据定理依据定理 3,把把 NFAM 确定化确定化,得

29、到一确定有限自动机得到一确定有限自动机 DFAM 的状态转换矩阵的状态转换矩阵;3产生一个限制程序产生一个限制程序.输出如下所示的词法分析器输出如下所示的词法分析器:状态转状态转换矩阵换矩阵限制限制程序程序 限制程序用于扫描输入字符串限制程序用于扫描输入字符串,限制状态的转移限制状态的转移;(对任何对任何 转换矩阵转换矩阵,其限制程序是一样的其限制程序是一样的)当识别出某词形当识别出某词形Pi后后,执行执行Ai.(返回种别码及值返回种别码及值)词法分析器词法分析器 38 本章习题本章习题1)构造如下正规式相应的构造如下正规式相应的DFA 11(0|1)*1012)构造一个构造一个DFA,它接受

30、它接受=0,1上全部满足如下上全部满足如下 条件的字符串条件的字符串:每个每个1后都有后都有0干脆根在后边干脆根在后边;根根 据据DFA的状态图的状态图,编写一个识别程序编写一个识别程序.39 课程设计课程设计1词法分析器设计词法分析器设计 设计题目：手工设计设计题目：手工设计c语言的词法分析器语言的词法分析器 （可以是（可以是c语言的子集）语言的子集）设计内容：处理设计内容：处理c语言源程序，过滤掉无用符号，推断源程语言源程序，过滤掉无用符号，推断源程序中单词的合法性，并分解出正确的单词，以二元组形式序中单词的合法性，并分解出正确的单词，以二元组形式存放在文件中。存放在文件中。设计目的：了解

31、高级语言单词的分类，了解状态图以及如设计目的：了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，驾驭状态图到识别程序的编程。何表示并识别单词规则，驾驭状态图到识别程序的编程。结果要求：课程设计报告。结果要求：课程设计报告。完成日期：第十五周提交报告完成日期：第十五周提交报告40一、用正规式表达如下的单词规则：）偶数规则；）带符号（+，-）以及无符号整数的规则；）首字符为的标识符规则。4）S=0，1上的正规集S由倒数其次个字符为1的全部字符串组成，写出满足条件的串的正规式；二、设有正规式 11(0|10)(0|10)*111、求与正规式等价的NFAM；2、求与正规式等价的DFAM（用状态图表示）。4142