第03章_词法分析

1、12S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理3教学目标教学目标1.1. 本章介绍编译第一个阶段词法分析的本章介绍编译第一个阶段词法分析的设计原理和设计原理和设计方法设计方法，要求明确此阶段的，要求明确此阶段的任务任务。2.2. 理解通常的单词理解通常的单词分类和构词规则分类和构词规则。3.3. 会使用单词的会使用单词的描述和识别描述和识别机制。机制。4.4. 要求掌握要求掌握正规文法、状态图、正规文法、状态图、DFADFA、NFANFA、正

2、规式、正规式和正规集和正规集的基本概念和它们之间的关系。的基本概念和它们之间的关系。5.5. 掌握词法分析程序的掌握词法分析程序的手工手工实现方法。实现方法。6.6. 掌握词法分析程序的掌握词法分析程序的自动自动构造原理。构造原理。43.1 3.1 词法分析的功能词法分析的功能3.2 3.2 程序语言的单词符号种类及词法分析程序语言的单词符号种类及词法分析输出输出3.3 3.3 正则文法及状态图正则文法及状态图3.4 3.4 词法分析程序的设计与实现词法分析程序的设计与实现3.5 3.5 正则表达式正则表达式3.6 3.6 有穷自动机有穷自动机3.7 3.7 词法分析程序的自动生成器词法分析程

3、序的自动生成器LEXLEX教学内容教学内容5（1 1）分析和识别单词及属性，）分析和识别单词及属性， 包括识别语言的包括识别语言的关键字、标识符、常数、运算符关键字、标识符、常数、运算符等；等；（2 2）跳过各种分隔符，如）跳过各种分隔符，如空格，回车，制表符空格，回车，制表符等；等；（3 3）删除注释；）删除注释；（4 4）进行词法检查，报告所发现的错误；）进行词法检查，报告所发现的错误；（5 5）建立符号表。）建立符号表。6main( )/*ADD*/ int x=10,y=20,sum; sum=x+y;main、(、)、int、x、=、10、,、y、=、20、,、sum、;、sum、=

4、、x、+、y、;、词法分析词法分析 71、词法分析作为独立的一遍、词法分析作为独立的一遍词法分析的输出存入一个中间文件供语法分析使用词法分析的输出存入一个中间文件供语法分析使用S.P.(字符串)词法分析词法分析S.P.(符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串实现方案一实现方案一8实现方案二实现方案二2、词法分析程序作为单独的子程序、词法分析程序作为单独的子程序S.P.(字符串)词法分词法分析程序析程序语法分语法分析程序析程序取单词取单词单词单词词法分析作为语法分析程序的一个子程序。词法分析作为语法分析程序的一个子程序。每当语法分析需要一个新的符号时，就调用词法分析每当语法

5、分析需要一个新的符号时，就调用词法分析子程序，词法分析子程序从字符串源程序中识别出一子程序，词法分析子程序从字符串源程序中识别出一个具有独立意义的单词，将其符号返给语法分析。个具有独立意义的单词，将其符号返给语法分析。9单词的种类单词的种类 （1 1）保留）保留字：字：if、for、while等等 （2 2）标识符：标识符：用户定义，如变量名、函数名等用户定义，如变量名、函数名等 （3 3）无符号数：无符号数：如如127、0.12等等 （4 4）单分界符：单分界符：如如+、*、；、（等、；、（等 （5 5）双分界符：）双分界符：如如=、=、=、,!,= /=*结束组合标识符查保留字 保留字 输

6、出保留字 输出标识符组合整数 组合整数 输出单分符 读字符 读字符读字符输出双分符 读字符输出单分符/ 注释处理 输出单分符 错误处理 YYYYYYYYYYNNNNNNNNNN31323334假设输入文件假设输入文件AAA.T中程序如下，运行词法分析程序，给中程序如下，运行词法分析程序，给出输出结果。出输出结果。 int a;a=10;解：将解：将AAA.T文件与词法分析程序最好在同一目录下，这文件与词法分析程序最好在同一目录下，这样运行词法分析程序时可以省略路径。运行词法分析程序：样运行词法分析程序时可以省略路径。运行词法分析程序：屏幕提示输入文件名：（输入屏幕提示输入文件名：（输入AAA.

7、T）和输出文件名：）和输出文件名：（输入（输入BBB.T），运行结束后，屏幕提示词法分析成功。），运行结束后，屏幕提示词法分析成功。打开打开BBB.T文件，看到上面示例小程序的词法分析结果如文件，看到上面示例小程序的词法分析结果如下：下：其中第一列是单词记号，第二列是单词值。其中第一列是单词记号，第二列是单词值。 intintIDa;IDa=NUM10;3536正规式中的运算符：正规式中的运算符：|或（选择）：或（选择）：R1|R2= x|xL1或 xL2 连接：连接： R1 R2=xy|xL1，yL2* 或或 重复重复 R1=x|x L1*， L1*=L10L11L12（）（）括号括号运算符

8、的优先级：运算符的优先级： 先先*, 后后 , 最后最后 | 在正规式中可以省略在正规式中可以省略.正规式相等正规式相等 这两个正规式表示的语言相等这两个正规式表示的语言相等37正则表达式的形式定义正则表达式的形式定义38正规式正规式正规集正规集ba*所有以所有以b为首后跟任意多个为首后跟任意多个a的符号串的符号串a(a|b)*所有以所有以a为首的符号串为首的符号串(a|b)*abb所有以所有以abb为尾的为尾的a，b符号串符号串(a|b)*(aa|bb) (a|b)*所有含有两个相继的所有含有两个相继的a或相继的或相继的b的符的符号串号串(aa|ab|ba|bb) *空串和任何长度为偶数的符

9、号串空串和任何长度为偶数的符号串(a|b)(a|b)(a|b) *任何长度大于等于任何长度大于等于2的符号串的符号串39例例3.53.5，设字母表，设字母表=a,b=a,b，则，则a,b, a,b, 和和都是都是上上的正则表达式，所描述的语言为的正则表达式，所描述的语言为aa、bb、，求表达式求表达式abab、a|ba|b和和aa|ab|ba|bbaa|ab|ba|bb定义的语言。定义的语言。40例例3.63.6，设字母表，设字母表=0=0，求表达式，求表达式0000与与000|0000|0定定义的语言。义的语言。正则表达式的部分操作符满足正则表达式的部分操作符满足结合律结合律、交换律交换律和

10、和分配分配律律: :即即 (ab)c=a(bc) (a|b)|c=a(b|c) (ab)c=a(bc) (a|b)|c=a(b|c) a|b=b|a a(b|c)=ab|ac a|b=b|a a(b|c)=ab|ac注意：连接不满足交换律，即注意：连接不满足交换律，即abba abba 41设设r，s，t均是正规式，则有以下性质：均是正规式，则有以下性质：（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= r42步骤步骤1 将每条产生式

11、改写为正规式；将每条产生式改写为正规式；步骤步骤2 用代入法解正规式方程组，最后只剩下一用代入法解正规式方程组，最后只剩下一个开始符号定义的正规式，其中不含非终结符。个开始符号定义的正规式，其中不含非终结符。规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,Ay A=xy A=xyA=xA=x* *y y A=x|y A=x|y43GS:SaA|a AdA|d规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xy

12、A=xA=x* *y yA=x|yA=x|yS=aA|aA= d*d代入代入:S=ad*d|a =ad*44先用元符号先用元符号“”和和“”将文法改将文法改写成如下：写成如下：S=aaBB =bCC = aa然后按解方程组的方法可得：然后按解方程组的方法可得：C=aaB= baaS=aabaa最终转成正则表达式最终转成正则表达式S=aabaa可以验证，它表示的语言与原来可以验证，它表示的语言与原来的正则文法描述的语言相同。的正则文法描述的语言相同。45正规式正规式正规文法正规文法步骤步骤1 构造构造 Sr步骤步骤2 不断利用表不断利用表3.4的规则做变换的规则做变换,直到每个产生直到每个产生式

13、最多含有一个终结符为止式最多含有一个终结符为止 规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xyA=xA=x* *y y A=x|y A=x|y46例：求正规式例：求正规式(a|b)(a|b|0|1)*对应的正规文法对应的正规文法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)*规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,Ay

14、Ax,AyA=xyA=xyA=xA=x* *y y A=x|y A=x|y47 有穷自动机是一种有穷自动机是一种数学模型数学模型，具有离散的输入与输出，系，具有离散的输入与输出，系统可处于有穷状态中的任何一个统可处于有穷状态中的任何一个 它能准确地它能准确地识别正规集识别正规集，即识别正规文法所定义的语言和，即识别正规文法所定义的语言和正规式所表示的集合正规式所表示的集合 引入有穷自动机这个理论，正是为引入有穷自动机这个理论，正是为词法分析程序的自动构词法分析程序的自动构造造寻找特殊的方法和工具寻找特殊的方法和工具有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机（DFA

15、DFA）(Deterministic Finite Automata)(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机（NFANFA）(Nondeterministic Finite Automata) (Nondeterministic Finite Automata) 48标识符标识符无符号整数无符号整数单界符单界符双界符双界符读字符读字符查保留字表查保留字表返回返回S状态图的形式化描述状态图的形式化描述S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+ * ，（ ）出口出口4其他字符其他

16、字符5=非非 =出错出错其他其他491.确定的有穷自动机（确定的有穷自动机（DFA M） M=（ Q， ，q0，F，）Q：有穷集，它的每个元素称为一个状态：有穷集，它的每个元素称为一个状态：有穷字母表，它的每个元素称为一个输入符号：有穷字母表，它的每个元素称为一个输入符号q0 ： q0 Q，是唯一的初态，是唯一的初态 F：F Q，是一个终态集，终态也称可接受状态或结束状，是一个终态集，终态也称可接受状态或结束状态态：是状态转换函数，是：是状态转换函数，是QQ上的单值映射：上的单值映射：f（q1，a）=q2 50这是一个单值函数，表示在当前状态为这是一个单值函数，表示在当前状态为q q下，下，输

17、入符号为输入符号为a a时，自动机将从状态时，自动机将从状态q q转换到下一转换到下一个状态个状态q q，q q称为称为q q的后继状态。的后继状态。51例如例如: M: M:（0,1,2,3,a,b,0,1,2,3,a,b,0, , 3 , , ） （0，a）=1 （0，b）=2 （1，a）=3 （1，b）=2 （2，a）=1 （2，b）=3 （3，a）=3 （3，b）=3M=（ Q， ，q0，F，）字母表字母表含有含有n n个输入字个输入字符，那末任何一个状态符，那末任何一个状态结点最多有结点最多有n n条弧射出，条弧射出，而且每条弧以一个不同而且每条弧以一个不同的输入字符标记。的输入字符

18、标记。52 输入输入 字符字符 状态状态 a b 0 1 2 1 3 2 2 1 3 3 3 3DFADFA的状态图表示：的状态图表示：1032aabba,bba所谓确定的状态机，其确定性表现在所谓确定的状态机，其确定性表现在状态转移函数是单值函数！状态转移函数是单值函数！53DFADFA识别的字：若存在一条初始状态到某一终止状识别的字：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成态的路径，且这条路径上所有弧的标记符号连接成符号串符号串，则称，则称为为DFA MDFA M（接受）识别。（接受）识别。DFA MDFA M所接受的语言为：所接受的语言为：DFA MDF

19、A M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)L(M)若若M M的初态结点同时为终态，或者存在一条从初态到的初态结点同时为终态，或者存在一条从初态到某个终态结点的某个终态结点的通路，则通路，则为为M M所识别。所识别。 54 （0，abaab） =（1，baab） =（2，aab） =（1，ab） =（3，b） =3 (接受接受)DFADFA的状态图表示：的状态图表示：1032aabba,bba （0，abab） =（1，bab） =（2，ab） =（1，b） =2 (拒绝拒绝)对于符号串对于符号串abaababaab对于符号串对于符号串abababab55SABC1101

20、0010下面判别下面判别110101、11101能否被该自能否被该自动机接受：动机接受：(S，110101)=(A，10101) =(S，0101)=(B，101) =(C，01)=(A，1) = S(接受接受)(S，11101)=(A，1101) =(S，101)=(A，01) =(C，1) = B(拒绝拒绝) 56 有穷自动机的不确定性表现在在某个状态下，对有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向于某个输入字符存在多个后继状态，即状态的转向是不确定的。是不确定的。 5758例：例： NFA N=(1,2,3,4, a,b,c, 1, 4, )5

21、9u对于对于*上的任何符号串上的任何符号串 ，若存在一条从某一初，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字态到某一终态的通路，且该通路上所有弧的标记字符依次连接成的串等于符依次连接成的串等于 ，则称，则称 可以被可以被NFA N所所识别或接受。识别或接受。u若若N的初态结点同时为终态，或者存在一条从初的初态结点同时为终态，或者存在一条从初态到某个终态结点的态到某个终态结点的 通路，则通路，则 为为N所识别。所识别。 NFA N所能识别的符号串的全体记为所能识别的符号串的全体记为L(N)，称为，称为NFA N所识别的语言所识别的语言 601234abac ac 符号符号 状

22、态状态 a b c 1 4 2，3 2 2 4 3 3，4 4 61能接受能接受0001111010001110000001不能接受不能接受0001100(0|1)(0|1)* *(000|111)(0|1) (000|111)(0|1) * *62画出能够识别画出能够识别C语言注释语言注释/* */的的DFA12453othersothers/*/6othersothersall all6312453othersothers/*/状态状态1：注释开始状态。：注释开始状态。状态状态2：进入注释体前的中间状态。：进入注释体前的中间状态。状态状态3：表明目前正在注释体中的状态。：表明目前正在注释体

23、中的状态。状态状态4：离开注释前的中间状态。：离开注释前的中间状态。状态状态5：注释结束状态，即接受状态。：注释结束状态，即接受状态。 64已证明：非确定的有穷自动机与确定的有穷自动已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够机从功能上来说是等价的，也就是说，我们能够从：从：DFA是是NFA的特例。有一种算法，将的特例。有一种算法，将NFA转换成接转换成接受同样语言的受同样语言的DFA。这种算法称为这种算法称为子集法子集法。与某一与某一NFA等价的等价的DFA不唯一不唯一 NFA NDFA M构造成一个构造成一个使得使得 L(M)=L(N)L(M)=L(

24、N)65正规文法正规文法NFA正规式正规式654312DFA最小化最小化8766 输入输入 字符字符 状态状态 a b 0 1 2 1 3 2 2 1 3 3 3 3DFA 符号符号 状态状态 a b c 1 4 2，3 2 2 4 3 3，4 4 NFA从从NFANFA的矩阵表示中可以看出，表项通常是一状态的的矩阵表示中可以看出，表项通常是一状态的集合，而在集合，而在DFADFA的矩阵表示中，表项是一个状态。的矩阵表示中，表项是一个状态。NFANFA到相应的到相应的DFADFA的构造的基本思路是：的构造的基本思路是： DFADFA的每一个的每一个状态对应状态对应NFANFA的一组状态的一组状

25、态. .67 (1) 合并如果有 ，则把S2合并到S1S S1 1S S2 2转换需解决的问题：转换需解决的问题：ijkmaban（a）i,jmkaabn（b）68(2)状态合并0123aabc（a）01,23abc（b）69定义定义1 状态集合状态集合I I的的 - -闭包，表示为闭包，表示为 -closure(I) -closure(I) 若若qIqI，则，则qq -closure(I)-closure(I)； 若若qIqI，则从，则从q q出发经过任意条出发经过任意条 弧而能到达弧而能到达的任何状态的任何状态qq都属于都属于 -closure(I)-closure(I)。 为了使得为了使

26、得NFANFA确定化，我们首先给出两个定义确定化，我们首先给出两个定义：_ closure(I)IIS2S2S1S1S3S370例：例：如图所示的状态图：如图所示的状态图：令令I=1，求求-closure（I）=？156432aaa根据定义：根据定义：-closure（I）=1，3课堂练习：课堂练习：令令I=1,2，求求-closure（I）=？71定义定义2 2 状态集状态集P P的的a a弧转换集弧转换集I I是状态集，由是状态集，由I I中的状态出发，经过一条中的状态出发，经过一条a a弧弧可能到达的状态的集合称为可能到达的状态的集合称为movemove（I I，a a），），则则: :

27、I Ia a= _closure ( move( I , a ) )= _closure ( move( I , a ) )72例：令例：令 I=1I=1 I Ia a=-closure(move=-closure(move（I I，a a）) ) =-closure( =-closure(（1 1，a a） =-closure(2=-closure(2，44）=2=2，4 4，66根据定义根据定义1 1，2 2，可以将上述的，可以将上述的MM确定化（即确定化（即可构造出状态转换矩阵）可构造出状态转换矩阵）156432aaa课堂练习：课堂练习：令令I=1,2,3求求I Ia a =？73课堂练

28、习：课堂练习：令令I=1I=1，设，设SS= -closure= -closure（I I），求），求SS？SSa a = =？将从状态将从状态S S出发经过任意条出发经过任意条 弧所能到达的状态作为弧所能到达的状态作为DFADFA的初态的初态S S 从从S S 出发，把遇到输入符号出发，把遇到输入符号a a所转移到的后继状态集作所转移到的后继状态集作为为DFADFA的新状态的新状态如此重复，直到不再有新的如此重复，直到不再有新的状态出现为止状态出现为止 NFA转换为转换为DFA的思想的思想1234abacac74 I Ia Ib Ic 1,4 2,3 2,3 2 4 3,4 2 2 4 4

29、3,4 3,4 （1 1）构造一张表，它共有）构造一张表，它共有+1+1列列（ 2 2 ） 第 一 行 第 一 列 为） 第 一 行 第 一 列 为 - -closure(S)closure(S)（3 3）求）求I Ia a、I Ib b、I Ic c（4 4）重复步骤（）重复步骤（3 3）（5 5）将状态子集重新命名）将状态子集重新命名1234abacac75将求得的状态转换矩阵重新编号将求得的状态转换矩阵重新编号DFA M状态转换矩阵：状态转换矩阵： 符号符号状态状态abc0 2 341221_334476DFA M的状态图：的状态图：注意：包含原终止状态注意：包含原终止状态4的状态子集为

30、的状态子集为DFA M的终态。的终态。1234abacac14231,42,342acabbc3,407778S0S1S0S1S0S1a图图3.16 、和和a的状态转换图的状态转换图 792)2)连接：连接：设设R1R1和和R2R2都是基本正则表达式，则构造与正都是基本正则表达式，则构造与正则表达式则表达式R1.R2R1.R2等价的等价的NFANFA如图如图3.173.17： S0S1R1.R2 S0S2S1R1 R2 图3.17 R1.R2的状态转换图的状态转换图 3)3)选择：选择：设设R1 R1 和和R2 R2 都是正则表达式，则构造与正则都是正则表达式，则构造与正则表达式表达式R1|R

31、2R1|R2等价的等价的NFANFA如图如图3.183.18： S0S1R1|R2 S0S1R1 R2 图3.18 R1|R2的状态转换图的状态转换图 804) 4) 重复：重复：设设R R是正则表达式，则构造与正则表达式是正则表达式，则构造与正则表达式RR等价的等价的NFANFA如图如图3.193.19： S0S1R S0S2S1 R图3.19 R 的状态转换图的状态转换图 81正规表达式正规表达式R=(a|b)R=(a|b)* *abbabb构造构造NFA,NFA,使得使得L(N)=L(R)L(N)=L(R) AZS(a|b) *abb SZbabABbaZbbSa|bAa82例例: :M

32、 M: :03214starta,ba,ba,bbbaa解解: (1)(1)加加S ZS ZS03412Zaa,ba,ba,babb(1)(1)在在M上加两个结点上加两个结点S,ZS,Z，从从S S结点用结点用弧到弧到M的所有初的所有初态，从态，从M的所有终态用的所有终态用到到Z结成与结成与M等价的等价的M，M只有只有一个初态一个初态S和一个终态和一个终态Z.83(2)逐步消去逐步消去M中的所有结点中的所有结点,直至剩下直至剩下S和和Z结点结点,在消结过程中在消结过程中,逐步用正规式来标记弧逐步用正规式来标记弧, 规则如下规则如下:13R1.R2 123R1 R2 图3.25 由NFA构造正则

33、表达式R1R2 8412R1|R2 12R1 R2 图3.26由NFA构造正则表达式R1|R2 13R 123 R图3.27由NFA构造正则表达式R 85(2)(2)消除消除M M中的所有结点中的所有结点a|bx024yaabba|ba|bx0yaa(a|b) *bb(a|b) *a|b例例: (1)(1)加加xyxyx03412yaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*86如果不同的如果不同的DFADFA能识别相同的语言，则称它们能识别相同的语言，则称它们是是等价的等价的DFADFA。在等价的在等价的DFADFA中，如果某一个中，如果某一个DFADFA的状态数是最

34、的状态数是最少的，则这个少的，则这个DFADFA是最简的是最简的。 对于任一个对于任一个DFADFA，存在一个唯一的状态最少的，存在一个唯一的状态最少的等价的等价的DFADFA最简的最简的DFA 它没有多余它没有多余状态和等价状态状态和等价状态871 1、等价状态与不等价状态等价状态与不等价状态 在一个确定的有穷自动机里，如果从在一个确定的有穷自动机里，如果从S S1 1状态出发状态出发接受的所有符号串集合与从接受的所有符号串集合与从S S2 2状态出发接受的所有符状态出发接受的所有符号串集合一样，那么称状态号串集合一样，那么称状态S S1 1和和S S2 2是等价的；否则是是等价的；否则是不

35、等价的。不等价的。02134abaab状态状态1 1和状和状态态2 2等价等价 88多余状态有两种。多余状态有两种。一是指从初始状态出发，输入任何输入串也无法到达一是指从初始状态出发，输入任何输入串也无法到达的状态，即从初始状态到该状态之间没有通路。的状态，即从初始状态到该状态之间没有通路。二是指从初始状态出发能够到达的状态，但从它出发二是指从初始状态出发能够到达的状态，但从它出发却无法到达终止状态的状态，即从该状态到终止状态却无法到达终止状态的状态，即从该状态到终止状态之间没有通路。之间没有通路。2 2、多余状态多余状态012345bbbaa0234bba893 3、DNADNA化简算法化简

36、算法设设DFA M= DFA M= （Q Q， ， ，q q0 0，F F），化简算法如下：），化简算法如下：1 1）先将自动机的状态划分成终止状态集合）先将自动机的状态划分成终止状态集合S1S1和非终止和非终止状态集合状态集合S2S2： Q= S1S2Q= S1S201234bbbaaabaab123401232143434S1S2abS10，1，2S23，4902 2）对各状态集合按下面方法划分，直到所有状态集合不再产生）对各状态集合按下面方法划分，直到所有状态集合不再产生新的划分为止。设第新的划分为止。设第m m次划分将次划分将Q Q分成分成N N个状态集合，即个状态集合，即Q= Q=

37、S1S2S1S2SnSn。对状态集合。对状态集合SiSi（i=1i=1，2 2，n n）中的各个状）中的各个状态逐一检查，设状态态逐一检查，设状态q q1 1和和q q2 2是状态集合是状态集合SiSi中的两个状态，对于输中的两个状态，对于输入符号入符号a a（aa），有），有(q(q1 1,a)= S,a)= S、(q(q2 2,a)=S,a)=S”, ,若状态若状态S S和和S S”属于同一状态集合，则将状态属于同一状态集合，则将状态q q1 1和和q q2 2放在同一状态集合中；放在同一状态集合中；否则，将状态否则，将状态q q1 1和和q q2 2分为两个集合。分为两个集合。12340

38、1232143434S1S2abS10，1，2S23，4213401214323434S3S2abS4 S30，2 S41S23，4913 3）重复第）重复第2 2步，直到所有状态集合都不能划分。此步，直到所有状态集合都不能划分。此时，每个状态集合中的状态都是等价的。时，每个状态集合中的状态都是等价的。213401214323434S3S2abS4 S30，2 S41S23，4213401214323434S5S2abS4S6 S50S62 S41S23，4924 4）将每个状态集合中的等价状态合并成一个等价代表状态。将）将每个状态集合中的等价状态合并成一个等价代表状态。将状态函数中的所有状态

39、用相应的等价代表状态表示。从状态图状态函数中的所有状态用相应的等价代表状态表示。从状态图上看，要将一个状态集合中的等价状态结点合并成一个结点。上看，要将一个状态集合中的等价状态结点合并成一个结点。5 5）删除多余状态。）删除多余状态。 0123bbbaaaab图图3.31 化简后的有穷自动机化简后的有穷自动机 S50S41 S62S23，4S50S41 S62S23939495输入字符序列 分析表 控制程序 图3.32表驱动的词法分析程序的模型 图3.33分析表 96输入字符序列 分析表 控制程序 图3.32表驱动的词法分析程序的模型 图3.33分析表 其控制程序的算法是：其控制程序的算法是：

40、 1)1)在输入字符序列后面加一个字符在输入字符序列后面加一个字符# #，叫结束符。将扫描指针，叫结束符。将扫描指针设在输入序列的最左端，状态参数设在输入序列的最左端，状态参数i i设为开始状态。设为开始状态。2)2) 扫描下一字符扫描下一字符a a，如果是结束符，如果是结束符# #，则停止；否则，根据状，则停止；否则，根据状态参数态参数I I和输入的字符和输入的字符a a查分析表，将状态参数查分析表，将状态参数i i设为查分析表（设为查分析表（i i，a a）后得到的状态。）后得到的状态。3)3) 如果如果i i是终态，则表示识别出一个单词转到是终态，则表示识别出一个单词转到4 4；否则，转到；否则，转到2 2。4 4）处理识别出的单词，输出单词符号。状态参数）处理识别出的单词，输出单词符号。状态参数i i设为开始状态，设为开始状态，转到转到2 2。 97构造词法分析器的一般步骤：构造词法分析器的一般步骤：1)1) 用正则表达式对程序设计语言单词组成进行描述。用正则表达式对程序设计语言单词组成进行描述。2)2)为每一个正则表达式构造一个不确定的有穷自动机，用来识