第3章词法分析精选PPT.ppt

《第3章词法分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《第3章词法分析精选PPT.ppt（118页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章词法分析第1页，本讲稿共118页第3章词法分析1.1.本章介绍编译第一个阶段词法分析的本章介绍编译第一个阶段词法分析的设计原理和设设计原理和设计方法计方法，要求明确此阶段的，要求明确此阶段的任务任务。2.2.理解通常的单词理解通常的单词分类和构词规则分类和构词规则。3.3.会使用单词的会使用单词的描述和识别描述和识别机制。机制。4.4.要求掌握要求掌握正规文法、状态图、正规文法、状态图、DFADFA、NFANFA、正规式和、正规式和正规集正规集的基本概念和它们之间的关系。的基本概念和它们之间的关系。5.5.掌握词法分析程序的掌握词法分析程序的手工手工实现方法。实现方法。6.6.掌握词法分

2、析程序的掌握词法分析程序的自动自动构造原理。构造原理。教学目标第2页，本讲稿共118页3.1 3.1 词法分析的任务词法分析的任务3.2 3.2 词法分析程序的输出形式词法分析程序的输出形式3.3 3.3 词法分析程序的设计与实现词法分析程序的设计与实现3.4 3.4 正规式与有穷自动机正规式与有穷自动机3.5 3.5 词法分析程序的自动生成工具词法分析程序的自动生成工具LEXLEX3.6 PL/03.6 PL/0编译程序的词法分析编译程序的词法分析教学内容第3页，本讲稿共118页（1 1）分析和识别单词及属性，）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符等；包括识别语言

3、的关键字、标识符、常数、运算符等；（2 2）跳过各种分隔符，如空格，回车，制表符等；）跳过各种分隔符，如空格，回车，制表符等；（3 3）删除注释；）删除注释；（4 4）进行词法检查，报告所发现的错误；）进行词法检查，报告所发现的错误；（5 5）建立符号表。）建立符号表。3.1词法分析的任务第4页，本讲稿共118页main()/*ADD*/int x=10,y=20,sum;sum=x+y;main、(、)、int、x、=、10、,、y、=、20、,、sum、;、sum、=、x、+、y、;、词法分析 第5页，本讲稿共118页实现方案：实现方案：基本上有两种1.词法分析单独作为一遍2.词法分析程序

4、作为单独的子程序S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串优点优点:结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺点：效率低S.P.(字符串)词法分词法分析程序析程序语法分语法分析程序析程序取单词单词第6页，本讲稿共118页单词的种类单词的种类（1 1）关键）关键字：字：if、for、while（2 2）标识符：标识符：（3 3）常数：常数：（4 4）运算符：运算符：+、-、*（5 5）分界符：）分界符：,、;、(、)3.2词法分析程序的输出形式第7页，本讲稿共118页词法分析程序的输出形式词法分析程序的输出形式-二元式二元式单词类别 单词的属性值单词类

5、别可以用整数编码表示单词类别可以用整数编码表示:一类一种或一字一种一类一种或一字一种单词类别关键字标识符常数运算符分界符编码12345第8页，本讲稿共118页表3.1 int x=10,y=20,sum;词法分析的结果单词类别单词的属性值1int2指向x的符号表入口指针4=3105,2指向y的符号表入口指针4=3205,2指向sum的符号表入口指针5;表3.1 int x=10,y=20,sum;词法分析的结果 第9页，本讲稿共118页3.3词法分析程序的设计与实现词法规则 状态图 词法分析程序第10页，本讲稿共118页结点结点代表状态，用圆圈表示，为非终结符代表状态，用圆圈表示，为非终结符有

6、向弧有向弧表示状态转移表示状态转移弧上的标记弧上的标记表示在射出弧的结点状态下可能出现的输入字表示在射出弧的结点状态下可能出现的输入字符，为终结符符，为终结符1.状态图：状态图：为识别单词而专门设计的有向图，为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。是设计词法分析程序的一种好途径。SUVZ111000一张状态图包含有穷个状一张状态图包含有穷个状态，只能有一个态，只能有一个初态初态，至，至少要有一个少要有一个终态终态（用双圈（用双圈表示）表示）3.3.1 正规文法及其状态图第11页，本讲稿共118页【例3.1】某语言的标识符可使用以下正规文法GS来定义：SlAA|lA|dAl

7、a,b,z，d1,2,9试构造此文法的状态图。试构造此文法的状态图。SAll|d状态图可识别单词状态图可识别单词第12页，本讲稿共118页2.由正规文法构造状态图由正规文法构造状态图（1）对于右线性文法）对于右线性文法步骤步骤1增加结点增加结点Z为终态；为终态；步骤步骤2将每个非终结符号设置为一个对应的状态；将每个非终结符号设置为一个对应的状态；步骤步骤3对于对于Aa，引一条从，引一条从A到到Z的弧，弧上标记为的弧，弧上标记为a；而而对于对于AaB，引一条从，引一条从A到到B的弧，弧上标记为的弧，弧上标记为a。SlAA|lA|dAl|dAZSlAZll|d第13页，本讲稿共118页（2）对于左

8、线性文法）对于左线性文法步骤步骤1增加结点增加结点S为初态；为初态；步骤步骤2将每个非终结符号设置为一个对应的状态；将每个非终结符号设置为一个对应的状态；步步骤骤3对对于于Aa，引引一一条条从从S到到A的的弧弧，弧弧上上标标记记为为a；而而对对于于ABa，引一条从，引一条从B到到A的弧，弧上标记为的弧，弧上标记为a。Al|Al|Adl|dASlSlAA|lA|dA第14页，本讲稿共118页词法规则 状态图 词法分析程序3.3.2 词法分析程序的实现（1 1）根据词法规则写出正规文法；）根据词法规则写出正规文法；（2 2）将正规文法转换成状态图；将正规文法转换成状态图；（3 3）将状态图转换成流

9、程图。）将状态图转换成流程图。第15页，本讲稿共118页 标识符标识符 关键字关键字(标识符的子集）标识符的子集）常数常数 运算符运算符 +、*、=分界符分界符 ,、;【例3.2】假设某种语言的单词符号的子集有：试构造此语言子集的词法分析程序。第16页，本讲稿共118页（1）根据词法规则写出正规文法字母字母|字母字母|数字）数字）数字数字|数字数字+|*|,|;=第17页，本讲稿共118页标识符出口S1非字母数字字母字母、数字无符号整数出口S2非数字数字数字单字符分界符出口S3其他字符+*=,;双字符分界符出口S4其他字符5=非=字母字母|字母字母|数字）数字）数字数字|数字数字+|*|+|*

10、|,|;=（2）将正规文法转换成状态图第18页，本讲稿共118页合并合并 将初始状态合并为一个唯一的初态；将初始状态合并为一个唯一的初态；化简调整状态冲突并对冲突状态重新编号；化简调整状态冲突并对冲突状态重新编号；如有必要，增加出错状态。如有必要，增加出错状态。第19页，本讲稿共118页标识符无符号整数单界符双界符S1非字母数字字母字母、数字2非数字数字数字3其他字符+*，（）出口4其他字符5=非=出错其他读字符查保留字表返回S合并后的状态图第20页，本讲稿共118页（3）将状态图转换成流程图，如图3.5写出词法分析程序第21页，本讲稿共118页3.5字母表字母表,定义在定义在 上的正规式和正

11、规集递归定义如下上的正规式和正规集递归定义如下:1.1.和和 都是都是 上的正规式上的正规式,它们所表示的正规集分别为它们所表示的正规集分别为:和和;2.2.任何任何a a ,a,a是是 上的正规式上的正规式,它所表示的正规集为它所表示的正规集为:a;:a;3.3.假定假定U U和和V V 上的正规式上的正规式,它们所表示的正规集分别记为它们所表示的正规集分别记为L(e1)L(e1)和和L(e2),L(e2),那么那么e1|e2,e1e1|e2,e1e2e2和和e1e1*也都是也都是 上的正规式上的正规式,它们所表示的它们所表示的 正规集分别为正规集分别为L(e1)L(e1)L(e2)L(e2

12、)、L(e1)L(e1)L(e2)L(e2)和和(L(e1)(L(e1)*4.4.任何任何 上的正规式和正规集均由上的正规式和正规集均由1 1、2 2和和3 3产生。产生。3.4正规表达式与有穷自动机3.4.1 正规式与正规集第22页，本讲稿共118页正规式中的运算符：正规式中的运算符：|-或（选择）或（选择）-连接连接*或或-重复重复（）（）-括号括号运算符的优先级：运算符的优先级：先先*,后后,最后最后|在正规式中可以省略在正规式中可以省略.正规式相等正规式相等这两个正规式表示的语言相等这两个正规式表示的语言相等第23页，本讲稿共118页【例例3.3】设设=a,b正规式正规集ba*所有以b

13、为首后跟任意多个a的符号串a(a|b)*所有以a为首的符号串(a|b)*abb所有以abb为尾的a，b符号串(a|b)*(aa|bb)(a|b)*所有含有两个相继的a或相继的b的符号串(aa|ab|ba|bb)*空串和任何长度为偶数的符号串(a|b)(a|b)(a|b)*任何长度大于等于2的符号串第24页，本讲稿共118页【例3.3】使用正规式来表示例3.2中的相应单词符号。字母字母|字母字母|数字）数字）数字数字|数字数字+|*|+|*|,|;=标识符：l(l|d)*无符号整数：dd*单界符：+|*|,|;双界符：=第25页，本讲稿共118页设设r，s，t均是正规式，则有以下性质：均是正规式

14、，则有以下性质：（1）交换律：）交换律：r|s=s|r（2）结合律：）结合律：r|(s|t)=(r|s)|t(rs)t=r(st)（3）分配律：）分配律：(r|s)t=rt|st（4）同一律：）同一律：r=r=r第26页，本讲稿共118页1.正规文法正规文法正规式正规式规则1规则2规则3文法产生式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=x*yA=x|y步骤1 将每条产生式改写为正规式；步骤2 用代入法解正规式方程组，最后只剩下一个开始符号定义的正规式，其中不含非终结符。3.4.2 正规文法与正规式第27页，本讲稿共118页【例例3.5】GS:SaA|a

15、AdA|d规则1规则2规则3文法产生式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=x*yA=x|yS=aA|aA=d*d代入:S=ad*d|a ad*第28页，本讲稿共118页2.正规式正规式正规文法正规文法步骤步骤1构造构造Sr步骤步骤2不断利用表不断利用表3.4的规则做变换的规则做变换,直到每个产生式直到每个产生式最多含有一个终结符为止最多含有一个终结符为止规则1规则2规则3文法产生式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=x*yA=x|y第29页，本讲稿共118页【例3.6】求正规式(a|b)(a|b|0|1

16、)*对应的正规文法S(a|b)(a|b|0|1)*S(a|b)AaA|bA|0A|1A|GS：SaA|bAAaA|bA|0A|1A|A(a|b|0|1)*第30页，本讲稿共118页下面是用正规式表示的变量声明：(int|float)id(,id)*请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。(int|float)id(,id)*D(int|float)LLid(,id)*DintL|floatLLL,id|idGD：DintL|floatLLL,id|id第31页，本讲稿共118页3.4.3 有穷自动机标识符无符号整数单界符双界符S1非字母数字字母字母、数字2非数字

17、数字数字3其他字符+*，（）出口4其他字符5=非=出错其他读字符查保留字表返回S状态图的形式化描述第32页，本讲稿共118页有穷自动机是一种有穷自动机是一种数学模型数学模型，具有离散的输入与输出，具有离散的输入与输出，系统可处于有穷状态中的任何一个系统可处于有穷状态中的任何一个它能准确地它能准确地识别正规集识别正规集，即识别正规文法所定义的语言，即识别正规文法所定义的语言和正规式所表示的集合和正规式所表示的集合引入有穷自动机这个理论，正是为引入有穷自动机这个理论，正是为词法分析程序的自动词法分析程序的自动构造构造寻找特殊的方法和工具寻找特殊的方法和工具有穷自动机分为两类：有穷自动机分为两类：确

18、定的有穷自动机确定的有穷自动机（DFADFA）(Deterministic Finite Automata)(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机（NFANFA）(Nondeterministic Finite Automata)(Nondeterministic Finite Automata)第33页，本讲稿共118页2型文法（不确定的下推自动机）1型文法（不确定的界限自动机）0型文法（图灵机）3型文法（有限自动机）第34页，本讲稿共118页1.确定的有穷自动机（确定的有穷自动机（DFA）M=(,Q,f,S,Z)：有穷字母表，它的

19、每个元素称为一个输入符号：有穷字母表，它的每个元素称为一个输入符号Q：有穷集，它的每个元素称为一个状态：有穷集，它的每个元素称为一个状态SK，是唯一的初态，是唯一的初态Z K是一个终态集，终态也称可接受状态或结束状态是一个终态集，终态也称可接受状态或结束状态f是转换函数，是是转换函数，是QQ上的单值映射：上的单值映射：f（q1，a）=q2第35页，本讲稿共118页状态转移函数f可用一矩阵来表示：输入 字符 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3例如例如:M:M:（0,1,2,3,a,b,0,1,2,3,a,b,f，0，3）f（0，a）=1f（0，b）=2f（1，a）=3f

20、（1，b）=2f（2，a）=1f（2，b）=3f（3，a）=3f（3，b）=3所谓确定的状态机，其确定性表现在状态转移函数是单值函数！字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。M=(,Q,f,S,Z)第36页，本讲稿共118页一个DFA也可以用一状态转换图表示：输入 字符 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3DFA的状态图表示：1032aabba,bba字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。第37页，本讲稿共118页换言之：若存在一条初始状态到某一终止状态

21、的路径，且这条路径上所有弧的标记符号连接成符号串，则称为DFA M（接受）识别。DFA MDFA M所接受的语言为：所接受的语言为：L(M)=|L(M)=|f(S,)=S)=Sn,n,S Sn n ZZDFA MDFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)L(M)若若M M的初态结点同时为终态，或者存在一条从初态到某个终态的初态结点同时为终态，或者存在一条从初态到某个终态结点的结点的通路，则通路，则为为M M所识别。所识别。第38页，本讲稿共118页 （0，abaab）=（1，baab）=（2，aab）=（1，ab）=（3，b）=3(接受接受)DFA的状态图表示：10

22、32aabba,bba （0，abab）=（1，bab）=（2，ab）=（1，b）=2(拒绝拒绝)对于符号串对于符号串abaababaab对于符号串对于符号串abababab第39页，本讲稿共118页f是一个多值函数，是从是一个多值函数，是从Q*到到Q的子集的映射：的子集的映射：f：Q2Q其中其中2Q是是Q的幂集，即的幂集，即Q中所有子集组成的集合。中所有子集组成的集合。2.不确定的有穷自动机（不确定的有穷自动机（NFA）M=(,Q,f,S,Z)有穷自动机的不确定性表现在在某个状态下，对于某个输入有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的字

23、符存在多个后继状态，即状态的转向是不确定的第40页，本讲稿共118页例：例：NFAN=(a,b,c,1,2,3,4,f,1,4)符号符号状态状态abc142，322433，44第41页，本讲稿共118页对于对于*上的任何符号串上的任何符号串，若存在一条从某一初态到某，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接一终态的通路，且该通路上所有弧的标记字符依次连接成的串等于成的串等于，则称，则称 可以被可以被NFAN所识别或接受。所识别或接受。若若N的初态结点同时为终态，或者存在一条从初态到某的初态结点同时为终态，或者存在一条从初态到某个终态结点的个终态结点的 通路，则通

24、路，则 为为N所识别。所识别。NFAN所能识别的符号串的全体记为所能识别的符号串的全体记为L(N)，称为，称为NFAN所识别的语言所识别的语言 第42页，本讲稿共118页上例题相应的状态图为：1234abacacN所接受的语言（正规式）R=aa*b|ac*c|符号 状态 a b c 1 4 2，3 2 2 4 3 3，4 4 第43页，本讲稿共118页能接受能接受0001111010001110000001(0|1)(0|1)*(000|111)(0|1)(000|111)(0|1)*不能接受不能接受0001100第44页，本讲稿共118页画出能够识别C语言注释/*/的DFA12453othe

25、rsothers/*/6othersothersall all第45页，本讲稿共118页12453othersothers/*/状态1：注释开始状态。状态2：进入注释体前的中间状态。状态3：表明目前正在注释体中的状态。状态4：离开注释前的中间状态。状态5：注释结束状态，即接受状态。第46页，本讲稿共118页q用于某些重要软件的设计和构造设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件;验证所有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。有穷自动机的其它应用有穷自动机的其它应用阅读两篇论文阅读两篇论文基于协议分析状态机的入

26、侵检测系统基于协议分析状态机的入侵检测系统有限自动机在有限自动机在BBS信息监测系统中的运用信息监测系统中的运用第47页，本讲稿共118页 已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：NFA NDFA M构造成一个使得 L(M)=L(N)DFA是是NFA的特例。有一种算法，将的特例。有一种算法，将NFA转换成接受同样语转换成接受同样语言的言的DFA.第48页，本讲稿共118页 已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：NFAMDFA M构造成一个使得使得L(M)=L(M)DFA是是NFA的特例。有一种算法

27、，将的特例。有一种算法，将NFA转换成接受同样语转换成接受同样语言的言的DFA.这种算法称为这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一不唯一3.NFA的确定化的确定化第49页，本讲稿共118页从从NFANFA的矩阵表示中可以看出，表项通常是一状态的集的矩阵表示中可以看出，表项通常是一状态的集合，而在合，而在DFADFA的矩阵表示中，表项是一个状态。的矩阵表示中，表项是一个状态。NFANFA到相应的到相应的DFADFA的构造的基本思路是：的构造的基本思路是：DFADFA的每一个的每一个状态对应状态对应NFANFA的一组状态的一组状态.符号符号状态状态abc142，322

28、433，441234abacac第50页，本讲稿共118页(1)合并如果有 ，则把S2合并到S1S1S2转换需解决的问题：ijkmaban（a）i,jmkaabn（b）第51页，本讲稿共118页(2)状态合并0123aabc（a）01,23abc（b）第52页，本讲稿共118页定义定义1状态集合状态集合I I的的-闭包，表示为闭包，表示为-closure(I)-closure(I)若若qIqI，则，则qq-closure(I)-closure(I)；若若qIqI，则从，则从q q出发经过任意条出发经过任意条 弧而能到达的任何状弧而能到达的任何状态态qq都属于都属于-closure(I)-clo

29、sure(I)。为了使得NFA确定化，我们首先给出两个定义：_closure(I)IIS2S2S1S1S3S3第53页，本讲稿共118页例：例：如图所示的状态图：如图所示的状态图：令令I=1，求求-closure（I）=？156432aaa根据定义：根据定义：-closure（I）=1，3课堂练习：令I=1,2，求-closure（I）=？第54页，本讲稿共118页I I是状态集，由是状态集，由I I中的状态出发，经过一条中的状态出发，经过一条a a弧可能到弧可能到达的状态的集合称为达的状态的集合称为movemove（I I，a a），则），则I Ia a=_closure(move(I,a)

30、=_closure(move(I,a)定义定义2I Ia a子集子集第55页，本讲稿共118页例：令 I=1 Ia=-closure(move（I，a）)=-closure(f（1，a）=-closure(2，4）=2，4，6根据定义根据定义1 1，2 2，可以将上述的，可以将上述的MM确定化（即可构造出状态确定化（即可构造出状态转换矩阵）转换矩阵）156432aaa课堂练习：课堂练习：令令I=1,2,3求求IaIa=？第56页，本讲稿共118页课堂练习：课堂练习：令令I=1I=1，设，设SS=-closure=-closure（I I），求），求SS？SSa a=？将从状态将从状态S S出发

31、经过任意条出发经过任意条 弧所弧所能到达的状态作为能到达的状态作为DFADFA的初态的初态S S 从从S S 出发，把遇到输入符号出发，把遇到输入符号a a所所转移到的后继状态集作为转移到的后继状态集作为DFADFA的新的新状态状态如此重复，直到不再有新的状态如此重复，直到不再有新的状态出现为止出现为止 NFA转换为转换为DFA的思想的思想1234abacac第57页，本讲稿共118页 I Ia Ib Ic 1,42,3 2,3243,4 224 4 3,43,4（1 1）构造一张表，它共有）构造一张表，它共有+1+1列列（2 2）第一行第一列为）第一行第一列为-closure(S)-clos

32、ure(S)（3 3）求）求IaIa（4 4）重复步骤（）重复步骤（3 3）（5 5）将状态子集重新命名）将状态子集重新命名1234abacac第58页，本讲稿共118页将求得的状态转换矩阵重新编号DFA M状态转换矩阵：符号状态abc0 2 341221_3344第59页，本讲稿共118页DFAM的状态图：的状态图：注意：包含原初始状态1的状态子集为DFA M的初态 包含原终止状态4的状态子集为DFA M的终态。014231,42,342acabbc3,41234abacac第60页，本讲稿共118页课堂练习4f35621iaaaabbbbstart第61页，本讲稿共118页 等价的DFAa

33、CDBAEFSbaaaaabbbbbabFstart第62页，本讲稿共118页4.DFA的最小化的最小化如果不同的如果不同的DFA能识别相同的语言，则称它们是等价的能识别相同的语言，则称它们是等价的DFA。在等价的在等价的DFA中，如果某一个中，如果某一个DFA的状态数是最少的，则这个的状态数是最少的，则这个DFA是最简的。是最简的。对于任一个对于任一个DFA，存在一个唯一的状态最少的等价的，存在一个唯一的状态最少的等价的DFA最简的最简的DFA它没有多余它没有多余状态和等价状态状态和等价状态第63页，本讲稿共118页定义定义1多余状态：多余状态：从开始状态出发从开始状态出发,任何输入串也不能

34、到达的状态任何输入串也不能到达的状态01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s101s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例:画状态图可以看出s4,s6,s8为不可达状态应该消除第64页，本讲稿共118页定义定义2等价状态等价状态状态状态s和和t的等价条件是的等价条件是:状态状态S和和T必须同时为终态或非终态必须同时为终态或非终态对于所有输入符号，对于所有输入符号，S和和T必须转换到等价的状态里必须转换到等价的状态里第65页，本讲稿共118页把把DFA的状态划分成一些不相交的子集的状态划分成一

35、些不相交的子集任何不同的两个子集的状态都是可区分的任何不同的两个子集的状态都是可区分的同一子集中的任何两个状态都是等价的同一子集中的任何两个状态都是等价的5724361srartaaaaaaabbbbbbbDFA最小化算法的基本思想最小化算法的基本思想(没有多余状态没有多余状态)：第66页，本讲稿共118页解:(一)区分终态与非终态12345663731546737414212ab区号123123456637315467374142ab区号（1）将所有状态分成两个子集：终态集和非终态集）将所有状态分成两个子集：终态集和非终态集（2）把等价的状态构成一个子集，若不等价继续划分）把等价的状态构成一

36、个子集，若不等价继续划分（3）结束后，重新标号或从每个子集中选一个状态做代表）结束后，重新标号或从每个子集中选一个状态做代表第67页，本讲稿共118页123456637315467374142ab12431243123456637315467374142ab5区号区号第68页，本讲稿共118页将区号代替状态号得将区号代替状态号得:12345ab521435523115 5243aaaaabbbbb化简后的有穷自动机具有较少的状态，实现起来更加简洁。化简后的有穷自动机具有较少的状态，实现起来更加简洁。第69页，本讲稿共118页3.4.4 正规式与有穷自动机的等价性（1）对于字母表）对于字母表上的

37、上的NFAM，可以构造一个，可以构造一个上的正规式上的正规式R，使得，使得L(R)=L(M)；（2）对于字母表）对于字母表上的每个正规式上的每个正规式R，可以构造一个，可以构造一个上的上的NFAM，使得，使得L(M)=L(R)。第70页，本讲稿共118页1.NFAM正规式正规式R(1)(1)在在M上加两个结点上加两个结点S,ZS,Z，从，从S S结点用结点用弧到弧到M的所有初态，的所有初态，从从M的所有终态用的所有终态用到到Z结成与结成与M等价的等价的M，M只有一个初只有一个初态态S和一个终态和一个终态Z.例例:M M:03214starta,ba,ba,bbbaa解解:(1)(1)加加S Z

38、S ZS03412Zaa,ba,ba,babb第71页，本讲稿共118页(2)逐步消去逐步消去M中的所有结点中的所有结点,直至剩下直至剩下S和和Z结点结点,在消在消结过程中结过程中,逐步用正规式来标记弧逐步用正规式来标记弧,规则如下规则如下:1 1.对于对于代之为代之为2 2.对于对于 代之为代之为 3 3.对于对于代之为代之为R1R212331R1R21221R2R1R2R1|R1R312331R1R2R3R2第72页，本讲稿共118页(2)(2)消除消除M M中的所有结点中的所有结点a|bx024yaabba|ba|bx0yaa(a|b)*bb(a|b)*a|b解解:(1)(1)加加xyx

39、yx03412yaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*第73页，本讲稿共118页2.正规式正规式RNFAM（1）对对NFAM构构造造一一个个广广义义的的状状态态图图，其其中中只只有有一一个个初初态态S和终态和终态Z，连接，连接S和和Z的有向弧标记为正规式。的有向弧标记为正规式。（2）对对正正规规式式依依次次进进行行分分解解，分分解解的的过过程程是是一一个个不不断断加加入入结结点点和和弧弧的的过过程程，直直到到转转换换图图上上的的所所有有弧弧标标记记上上都都是是字字母母表表上的元素或上的元素或 为止。为止。第74页，本讲稿共118页若若s,ts,t为为上的正规式上的

40、正规式(a)对于正规式R=stxystxystt(b)对于正规式R=s|txys|txyst(c)对于正规式R=rs*txyrs*txyrtts第75页，本讲稿共118页AZS(a|b)*abb例例:为为R=(a|b)abbR=(a|b)abb构造构造NFA,NFA,使得使得L(N)=L(R)L(N)=L(R)*SZbabABbaZbbSa|bAa第76页，本讲稿共118页3.4.5 正规文法与有穷自动机的等价性（1）对对于于NFAM，存存在在一一个个右右线线性性文文法法（左左线线性性文文法法）G，使得使得L(G)=L(M)；（2）对对于于右右线线性性文文法法（左左线线性性文文法法）G，可可以

41、以构构造造一一个个NFAM，使得，使得L(M)=L(G)。第77页，本讲稿共118页1.NFA正规文法正规文法（1 1）NFANFA的字母表为文法的终结符号集；的字母表为文法的终结符号集；（2 2）NFANFA的状态集为文法的非终结符号集；的状态集为文法的非终结符号集；（3 3）NFANFA的初态对应于文法的开始符号；的初态对应于文法的开始符号；（4 4）NFANFA的转换函数的转换函数f(A,t)=Bf(A,t)=B，写成一个产生式，写成一个产生式AtBAtB；（5 5）对）对NFANFA的终态的终态Z Z，增加一个产生式，增加一个产生式ZZ。ABt第78页，本讲稿共118页例例:给出如图给

42、出如图NFANFA等价的正规文法等价的正规文法G GABCDaaabbbbG=（A，B，C，D，a，b，P，A）其中其中P:AaBAbDBbCCaACbDCDaBDbDD第79页，本讲稿共118页（1 1）文法的终结符号集为）文法的终结符号集为NFANFA的字母表；的字母表；（2 2）文法的非终结符号集为）文法的非终结符号集为NFANFA的状态集；的状态集；（3 3）文法的开始符号作为）文法的开始符号作为NFANFA的初态；的初态；（4 4）对文法中形如）对文法中形如AtBAtB的产生式，其中的产生式，其中t t为终结符为终结符或或，A A和和B B为非终结符，构造为非终结符，构造NFANFA

43、的一个转换函数的一个转换函数f(A,t)=Bf(A,t)=B；（5 5）对文法中形如）对文法中形如AtAt的产生式，构造的产生式，构造NFANFA的一个转的一个转换函数换函数f(A,t)=Zf(A,t)=Z。2.正规文法正规文法NFA第80页，本讲稿共118页例例:求与文法求与文法GSGS等价的等价的NFANFA GS:SaA|bB|GS:SaA|bB|AaB|bA AaB|bA BaS|bA|BaS|bA|SZABaaabbb求得：第81页，本讲稿共118页正规文法正规文法NFA正规式正规式654312DFA最小化转换方法转换方法转换方法转换方法87第82页，本讲稿共118页判断题1对任意一

44、个右线性文法G，都存在一个NFA M，满足L(G)=L(M).2对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M).3对任何正规表达式e，都存在一个NFA M，满足L(M)=L(e).4对任何正规表达式e，都存在一个DFA M，满足L(M)=L(e).第83页，本讲稿共118页LEX源程序源程序LEX编译器编译器C程序3.53.5词法分析程序的自动生成工具词法分析程序的自动生成工具LEXLEXC程序程序C编译器编译器词法分析程序输入流输入流词法分词法分析程序析程序单词序列第84页，本讲稿共118页3.5.1LEX的源程序的源程序一个LEX源程序主要由三个部分组成 说明部分 可

45、选%必须有识别规则 必须有（LEX的核心）%可选辅助过程 可选第85页，本讲稿共118页1、说明部分、说明部分:变量、常量说明和正规式定义变量、常量说明和正规式定义正规式定义格式如下：正规式定义格式如下：D1R1D2R2 DnRn其中：其中：R1,R2，Rn为正规式为正规式D1,D2，Dn为正规式名字为正规式名字第86页，本讲稿共118页例：标识符：digit 0-9 letter A-Za-z id (letter|_)(letter|digit|_)*带符号整数：带符号整数：integerdigit(digit)*sign+|-|signintegersigninteger说明部分可用一个

46、名字代表一个正规式，增加程序的可读性第87页，本讲稿共118页2、识别规则：是一串如下形式的、识别规则：是一串如下形式的LEX语句：语句：R1A1R2A2 RmAmRi：正规式正规式Ai：Ai为语句序列，在识别出单词为语句序列，在识别出单词Ri以后，词法分析器所以后，词法分析器所应作的动作。应作的动作。其基本动作是返回单词的类别编码和单词值。其基本动作是返回单词的类别编码和单词值。3、辅助过程、辅助过程:用户定义的子程序用户定义的子程序第88页，本讲稿共118页下面是识别下面是识别C语言部分单词符号的语言部分单词符号的LEX源程序：源程序：/*说明部分说明部分*/digit0-9letterA

47、-Za-zid(letter|_)(letter|digit|_)*%/*识别规则，识别规则，每条规则中的动作都用大括号括起来每条规则中的动作都用大括号括起来*/“main”|”int”|”if”Upper(yytext,yyleng);printf(%s,KEYn,yytext);idprintf(%s,IDn,yytext);“+”|”-”|”*”printf(%s,SYMBOLn,yytext);第89页，本讲稿共118页%/*辅助过程*/Upper(char*s,int l)int i;for(i=0;i=、=等等标识符：标识符：用户定义的变量名、常数名、过程名用户定义的变量名、常数名

48、、过程名常数：常数：如如1010、2525、100100等整数等整数分界符：分界符：如如,、.、;、(、)等等第106页，本讲稿共118页通过三个全局变量区分所识别的单词：sym：存放单词的类别,如beginsym,ident,numberid：存放用户所定义的标识符的值num：存放用户定义的数char*symbol32=nul,ident,number,plus,minus,times,slash,oddsym,eql,neq,lss,leq,gtr,geq,lparen,rparen,comma,semicolon,period,becomes,beginsym,endsym,ifsym,

49、thensym,whilesym,writesym,readsym,dosym,callsym,constsym,varsym,procsym;第107页，本讲稿共118页（1 1）滤空格）滤空格（2 2）识别关键字：识别后将内部编码赋给变量）识别关键字：识别后将内部编码赋给变量symsym（3 3）识识别别标标识识符符：识识别别后后将将symsym置置为为标标识识符符的的内内部部编编码码“identident”，而将标识符本身的值放在，而将标识符本身的值放在idid中中（4 4）拼拼数数：拼拼成成真真正正的的十十进进制制数数，之之后后将将symsym置置为为数数的的内内部部编码编码“numb

50、ernumber”，而将数值本身的值放在，而将数值本身的值放在numnum中中（5 5）识识别别单单个个字字符符：识识别别后后将将相相应应单单词词的的内内部部编编码码赋赋给给变变量量symsym，如识别出，如识别出“+”后，将其内部编码后，将其内部编码“plusplus”赋给赋给symsym（6 6）识别组合字符：识别后将相应单词的内部编码赋给变）识别组合字符：识别后将相应单词的内部编码赋给变量量symsym，如识别出，如识别出“:=:=”后，将其内部编码后，将其内部编码“becomesbecomes”赋给赋给sym sym PL/0编译程序词法分析的任务编译程序词法分析的任务第108页，本讲