编译原理张晶版第三章词法分析

1、第三章第三章 词法分析词法分析第三章第三章 词法分析词法分析词法分析是编译的第一个阶段，在单词的级别上分词法分析是编译的第一个阶段，在单词的级别上分析和翻译源程序析和翻译源程序理论基础：理论基础： - -有限自动机理论有限自动机理论 -有限自动机理论与正规文法、正规式之有限自动机理论与正规文法、正规式之间在描述语言方面有一一对应的关系间在描述语言方面有一一对应的关系学习目标学习目标: : - -掌握有限自动机与正规文法、正规式之掌握有限自动机与正规文法、正规式之间的转换间的转换 -能够构造词法分析程序，完成实验一能够构造词法分析程序，完成实验一第三章第三章 词法分析程序（词法分析程序（2 2）

2、第一节第一节 正规文法和有限自动机正规文法和有限自动机一、正规文法、正规集与正规式正规文法、正规集与正规式1.1.正规文法正规文法 - -是是chomsky 3chomsky 3型文法型文法注：正规文法是描述正规集的文法，可用于描述注：正规文法是描述正规集的文法，可用于描述程序设计语言的语法部分。例如：标识符这种单程序设计语言的语法部分。例如：标识符这种单词可以用下面的规则描述词可以用下面的规则描述 （ ） :表示任意英文字母，表示任意英文字母， :表示任意表示任意数字数字第三章第三章 词法分析程序（词法分析程序（3 3）2.2.正规集正规集-由正规文法产生的语言由正规文法产生的语言注：正规集

3、是集合，可有穷也可无穷，注：正规集是集合，可有穷也可无穷，可通过正规式来形式化表示可通过正规式来形式化表示第一节第一节 正规文法和有限自动机正规文法和有限自动机一、一、正规文法、正规集与正规式正规文法、正规集与正规式第三章第三章 词法分析程序（词法分析程序（4 4）3 3、正规式、正规式-设设A A是非空的有限字母表，是非空的有限字母表，A=aA=ai i i=1,2, i=1,2,.n,.n,则则 1. 1. e e, ,和和a ai i（i=1,2,i=1,2,.n).n)都是正规式都是正规式 2. 2.若若a a，b b是正规式，则是正规式，则a a| |b b， a ab b , ,a

4、 a* *，b b* * 也也是正规式是正规式 3. 3.正规式只能通过有限次使用正规式只能通过有限次使用1,21,2规则获得规则获得注注: : 1) 1) “ | | ”读作读作 “ 或或 ” , ,也可写作为也可写作为“ + + ” 或或“ , ,” ， “ ” 读作连接读作连接 2) 2) 仅由字母表仅由字母表A=aA=ai i |i=1,2,|i=1,2,.n.n上的正规式上的正规式a a所组成的语言称作正规集所组成的语言称作正规集, ,记作记作L(L(a a) ) 3) 3)利用正规集相同利用正规集相同, ,可用来证明相应正规式等价可用来证明相应正规式等价第三章第三章 词法分析程序（

5、词法分析程序（5 5）一、正规文法、正规集与正规式一、正规文法、正规集与正规式例：证明例：证明 b(ab)b(ab)* *=(ba)=(ba)* *b b证明证明: : L(b(ab) L(b(ab)* *)=b,bab,babab,)=b,bab,babab,. L(ba) L(ba)* *b)=b,bab,bababb)=b,bab,babab. 又又正规集的前正规集的前n n项相同项相同 可知它们的正规集相等的可知它们的正规集相等的 故正规式故正规式b(ab)b(ab)* *=(ba)=(ba)* *b b第三章第三章 词法分析程序（词法分析程序（7 7）一、正规文法、正规集与正规式一、

6、正规文法、正规集与正规式4 .4 .三个概念间关系三个概念间关系-一个正规语言可以用正规文法定义，也可一个正规语言可以用正规文法定义，也可以用正规式定义，对任意一个正规文法，存在以用正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；同样，对每个一个定义同一个语言的正规式；同样，对每个正规式，存在一个生成同一语言的正规文法；正规式，存在一个生成同一语言的正规文法；有些正规语言，很容易用文法定义，有些则用有些正规语言，很容易用文法定义，有些则用正规式定义更容易；两者之间是可以转换的，正规式定义更容易；两者之间是可以转换的，结构上具有等价性。结构上具有等价性。-由正规文法或正规式定义的

7、正规语言的集合由正规文法或正规式定义的正规语言的集合构成正规集构成正规集第三章第三章 词法分析程序（词法分析程序（6 6）一、正规文法、正规集与正规式一、正规文法、正规集与正规式5 .定理：定理：若若a,b,ga,b,g是正规式，则下述等价式成立是正规式，则下述等价式成立a+b=b+aa+b=b+aa+(b+g)=(a+b)+g a(bg)=(ab)ga+(b+g)=(a+b)+g a(bg)=(ab)ga(b+g)=ab+ag (a+b)g=ag+bga(b+g)=ab+ag (a+b)g=ag+bgea=ae=aea=ae=a(a(a* *) )* *=a=a* *a a* *=a=a+

8、+e a+e a+ +=aa=aa* *=a=a* *a a(a+b)(a+b)* *=(a=(a* *+b+b* *) )* *=(a=(a* *，b b* *) )* *第三章第三章 词法分析程序（词法分析程序（8 8）一、正规文法、正规集与正规式一、正规文法、正规集与正规式6 .6 .正规文法转换成相应正规式正规文法转换成相应正规式其步骤为：其步骤为： -1. -1.由正规文法由正规文法G G的各个产生式写出对应的的各个产生式写出对应的正规方程式，得到联立方程组正规方程式，得到联立方程组 -2 .-2 .把方程组中的非终结符当作变元把方程组中的非终结符当作变元 -3.-3.求此正规式方程

9、组的解，得到关于开始求此正规式方程组的解，得到关于开始符号符号S S的解：的解： S= S= w w, ,w wVVT T* *, ,w w就是所求正规式就是所求正规式第三章第三章 词法分析程序（词法分析程序（1010） 假设正规文法G是右线性的，每个产生式的右部只含一个终结符，从文法G的产生式获得相应正规式方程式的规则如下： （1）若有Aa，则有A=a；若有A，则A= ； （2）若有AaA，则有A=a*A； （3）若有AaB且BA，则有A=aB； （4）若有Aa1|a2|an|aA，则有 A=a*(a1|a2|an)；例：已知正规文法例：已知正规文法G1G1的产生式，求出它所定义的的产生式，

10、求出它所定义的正规式正规式 -产生式为：产生式为：S aS |aB B bB |bA A cA |c 解：解：1.1.由产生式写出对应的联立方程组由产生式写出对应的联立方程组 S = a*S (1) S=aB (2) B= b*B (3) B=bA (4) A = c*A (5) A=c (6)第三章第三章 词法分析程序（词法分析程序（1111） 2.根据定理根据定理: :将将(6)代入代入(5)得到得到A=c+ (7)将将(7)代入代入(4)得到得到B=bc+ (8)将将(8)代入代入(3)得到得到B=b+c+ (9)将将(9)代入代入(2)得到得到S=ab+c+ (10)将将(10)代入代

11、入(1)得到得到S=a+b+c+ 3. 故：正规式为故：正规式为S=a+b+c+第三章第三章 词法分析程序（词法分析程序（1212）二、有限自动机二、有限自动机（Finite automation FA)1 1、有限自动机、有限自动机有限自动机是一种识别装置，他能准确地识别正规有限自动机是一种识别装置，他能准确地识别正规集，它为词法分析程序的构造提供了方法和工具。集，它为词法分析程序的构造提供了方法和工具。有限自动机是具有离散输入输出系统的数学模型，有限自动机是具有离散输入输出系统的数学模型，它具有有限数目的内部状态，系统可以根据当前所它具有有限数目的内部状态，系统可以根据当前所处的状态和面临

12、的输入字符决定系统的后继行为，处的状态和面临的输入字符决定系统的后继行为，其当前状态概括了过去输入处理的信息其当前状态概括了过去输入处理的信息第三章第三章 词法分析程序（词法分析程序（1313）2 2、有限自动机模型、有限自动机模型abcde.z输入带输入带有限状态控制器有限状态控制器读头读头状态变换状态变换注：状态分为初始状态，中间状态和终止状态注：状态分为初始状态，中间状态和终止状态. .终终止状态可以有若干个，而初始状态一般只有一个止状态可以有若干个，而初始状态一般只有一个第三章第三章 词法分析程序（词法分析程序（1414）2 2、有限自动机模型、有限自动机模型abcde.z输入带输入带

13、有限状态控制器有限状态控制器读头读头状态：初态状态：初态第三章第三章 词法分析程序（词法分析程序（1515）2 2、有限自动机模型、有限自动机模型abcde.z输入带输入带有限状态控制器有限状态控制器读头读头状态：中间状态状态：中间状态第三章第三章 词法分析程序（词法分析程序（1616）2 2、有限自动机模型、有限自动机模型a ab bc cd de e.z z输入带输入带有限状态控制器有限状态控制器读头读头状态：终态状态：终态读头全部读完，而此时状态是终止状态，则读头全部读完，而此时状态是终止状态，则说明此输入串正确说明此输入串正确第三章第三章 词法分析程序（词法分析程序（1717）a ab

14、 bc cd de e.z z输入带输入带有限状态控制器有限状态控制器读头读头状态：非终态状态：非终态2 2、有限自动机模型、有限自动机模型读头全部读完，而此时状态不是终止状态，则说明读头全部读完，而此时状态不是终止状态，则说明此输入串错误此输入串错误注：可用状态转换图表示状态变换，状态用结点表示，注：可用状态转换图表示状态变换，状态用结点表示，读入符号用边表示读入符号用边表示第三章第三章 词法分析程序（词法分析程序（1818）二、有限自动机（二、有限自动机（Finite automation -FA)Finite automation -FA)正规式正规式: : （ ）* *的状态转换的状态

15、转换状态转换图形式如下：状态转换图形式如下：1 12 2字母字母字母字母数字数字程序中标识符的程序中标识符的xtempxtemp的识别匹配过为：的识别匹配过为：12222x2temp第三章第三章 词法分析程序（词法分析程序（1919）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)1 12 2字母字母数字数字q0q100101字母字母第三章第三章 词法分析程序（词法分析程序（2020）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)3、确定有限自动机确定有限自

16、动机DFADFA（Deterministic FA)Deterministic FA) 定义：确定有限自动机定义：确定有限自动机DFADFA是一个五元式是一个五元式 M(S, ,f,s M(S, ,f,s0 0,Z),Z)- - 其中：其中：S S：有限状态集：有限状态集- - ：有限字母表：有限字母表- f: S- f: S S S上的单值映射，上的单值映射，f(s,a)=sf(s,a)=s- s- s0:0:唯一的初态唯一的初态，s s0 0SS- Z:- Z:终止状态集，终止状态集，ZSZS注：这里确定的含义，就是状态转换关系注：这里确定的含义，就是状态转换关系f f是一个函数，即对是一

17、个函数，即对于给定的当前状态于给定的当前状态S S和当前读入的符号和当前读入的符号a a，有唯一确定的下一，有唯一确定的下一状态状态S S第三章第三章 词法分析程序（词法分析程序（2121）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)（2 2）状态转换表示）状态转换表示-状态转换矩阵：状态转换矩阵：DFADFA的映射关系由一个矩阵来表示。的映射关系由一个矩阵来表示。-状态转换图：状态转换图： 注：注：1 1）用矩阵表示转换便于计算机处理，但不直观，）用矩阵表示转换便于计算机处理，但不直观，而用状态转换图表示比较直观而用状态

18、转换图表示比较直观 2 2）在整个状态转换图中只有一个初始状态结点，）在整个状态转换图中只有一个初始状态结点，用用“ ”射入的结点表示初始状态，可有若干终止状射入的结点表示初始状态，可有若干终止状态（也可能没有），用双圆圈表示。若初始状态结点同态（也可能没有），用双圆圈表示。若初始状态结点同时又是终止状态结点，则表示空串时又是终止状态结点，则表示空串e e可为相应可为相应DFADFA识别。识别。第三章第三章 词法分析程序（词法分析程序（2222）例例： DFA M=(0,1,2,3,a,b,f,0,3)-f:f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2- f(2,a)

19、=1 f(2,b)=3 f(3,a)=3 f(3,b)=3 输输 入入ab012132213333状态状态状态转换矩阵状态转换矩阵102ababbaba3第三章第三章 词法分析程序（词法分析程序（2323）例：构造一个例：构造一个DFA MDFA M，它接受字母表，它接受字母表a,b,c a,b,c 上上, , 以以a a或或b b开始的字符串，或以开始的字符串，或以c c开始但所含的开始但所含的a a不多于一不多于一个的字符串。个的字符串。0132accbbabcbca第三章第三章 词法分析程序（词法分析程序（2424）故故：DFA： M=（0,1,2,3,a,b,c,f,0,1,2,3)-

20、其中其中：f: f(0,a)=1 f(0,b)=1 f(0,c)=2 f(1,a)=1 f(1,b)=1 f(1,c)=1 f(2,a)=3 f(2,b)=2 f(2,c)=2 f(3,b)=3 f(3,c)=3 第三章第三章 词法分析程序（词法分析程序（2525）二、有限自动机（二、有限自动机（Finite automation -FA)Finite automation -FA)(3) 、一步动作一步动作-每读一个字符，状态就向前进至下一状态；记为每读一个字符，状态就向前进至下一状态；记为“ ”，- k 表示自动机做了表示自动机做了k k步动作步动作- *表示自动机做了表示自动机做了0 0

21、步动作或步动作或0 0步以上的动作步以上的动作- +表示自动机做了表示自动机做了1 1步动作或步动作或1 1步以上的动作步以上的动作(4)4)、DFADFA对字符串的识别对字符串的识别定义：串定义：串a a*为为DFA M=(S, ,f,s0,Z)所识别，所识别，当前仅当当前仅当（s0,a a) *(s,e e),且且sZ第三章第三章 词法分析程序（词法分析程序（2626）(4)(4)、DFADFA对字符串的识别对字符串的识别二、有限自动机（二、有限自动机（Finite automation-FA)Finite automation-FA)注：能被注：能被DFA MDFA M所接受的字符串的集

22、合，称为所接受的字符串的集合，称为自动机自动机M M所能识别的语言，记为所能识别的语言，记为L(M)L(M)不能被不能被DFA MDFA M所接受的字符串有两种情况：所接受的字符串有两种情况：-读完输入串，状态不停在终止状态，读完输入串，状态不停在终止状态， 即即：（s0,a a) * (s,e e),且且s Z-在读过程中出现不存在的映射，使自动机在读过程中出现不存在的映射，使自动机无法继续工作。无法继续工作。第三章第三章 词法分析程序（词法分析程序（2727）二、有限自动机（二、有限自动机（Finite automation- FA)Finite automation- FA)4 .4 .

23、不确定有限自动机不确定有限自动机NFA(Non-deterministic FA)NFA(Non-deterministic FA)（1 1）定义：不确定有限自动机是一个五元式，）定义：不确定有限自动机是一个五元式， M= M=（S, ,f,SS, ,f,S0,0,Z)Z)-其中：其中：S:S:有限状态集有限状态集-：有限字母表：有限字母表- f:S- f:S 2 2s s(S(S的子集）上的映射的子集）上的映射-S-S0 0：非空的初态集，：非空的初态集，S S0 0是是S S的真子集的真子集-Z-Z：终止状态集，：终止状态集，Z Z是是S S的子集，可为空集的子集，可为空集注：注：1 1）

24、非确定主要是指后继状态可有多个）非确定主要是指后继状态可有多个 2 2）DFADFA是是NFANFA的特例的特例第三章第三章 词法分析程序（词法分析程序（2828）例：设例：设NFA M=NFA M=（qq0 0,q,q1 1,0,1,f,q,0,1,f,q0 0,q,q1 1)映射为映射为01q0q0q1q1q0,q1q0字符字符状态状态q010001q1第三章第三章 词法分析程序（词法分析程序（2929）二二、有限自动机有限自动机（Finite automation -FA)4 4、不确定有限自动机、不确定有限自动机NFA(Non-deterministic -NFA)NFA(Non-de

25、terministic -NFA)(2).(2).两自动机等价：两自动机等价：-任何两个有限自动机任何两个有限自动机M M和和M M，若它们识别的语言相，若它们识别的语言相同（同（L(M)=L(ML(M)=L(M) )）, ,则称则称M M和和M M等价等价-注：存在判定任何两个有限自动机等价性的算法注：存在判定任何两个有限自动机等价性的算法5 5、NFA NFA 确定化确定化(1).定理：对于每个定理：对于每个NFA MNFA M，存在一个，存在一个DFA MDFA M L(M)=L(ML(M)=L(M) )，即，设，即，设L L是一是一NFANFA接受的正规集，则存在接受的正规集，则存在一

26、个一个DFADFA接受接受L L第三章第三章 词法分析程序（词法分析程序（3030）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)(2)(2)算法算法由由NFA M=NFA M=（S,f,SS,f,S0 0,Z,Z ）构造一个等价的）构造一个等价的DFA MDFA M= =（ Q,Q,I,I0 0,F,F）1.1.取取I I0 0=S=S0 0，2.2.若状态集若状态集Q Q中有状态中有状态I Ii i=S=S0 0，S S1 1S Sj j ，S SK KSS，0Kj0Kj；而且而且M M中有中有f f（SS0 0，S S

27、1 1, ,.S.SJ J,a),a)=f(s=f(s0 0,a) f(s,a) f(s1 1,a) ,a) . f(s. f(sj j,a)= f(s,a)= f(sk k,a),a)=(s=(s0 0,s,s1 1, ,.s.st t)=I)=It t, ,若若I It t不在不在Q Q中，则将中，则将I It t加入加入Q QjK=0第三章第三章 词法分析程序（词法分析程序（3131）(2)(2)、算法（续）、算法（续）3.3.重复步骤重复步骤2 2，直到，直到Q Q中无新状态加入为止。中无新状态加入为止。4.4.取终态取终态F=I|IQF=I|IQ，且，且IZ IZ 注：注：1 1）上

28、述过程可在有限步内完成，因为）上述过程可在有限步内完成，因为M M机状态的幂集是有机状态的幂集是有限的；限的； 2 2）上述过程也可用表格法来描述，其中列是字符集）上述过程也可用表格法来描述，其中列是字符集中中的字符；行是的字符；行是Q Q中的各状态，开始仅包含中的各状态，开始仅包含I I0 0状态，随着算法状态，随着算法的执行，的执行，Q Q的状态逐渐增多直至不再增加为止；表格元素就的状态逐渐增多直至不再增加为止；表格元素就是是映射函数。映射函数。二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)第三章第三章 词法分析程序（词

29、法分析程序（3232）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)注：注：3 3）NFANFA确定化的实质是以原有状态集的覆盖片确定化的实质是以原有状态集的覆盖片（COVERCOVER）作为）作为DFADFA的一个状态。将原状态间的转换的一个状态。将原状态间的转换改为覆盖片间的转换，从而将不确定问题确定化。改为覆盖片间的转换，从而将不确定问题确定化。 4 4）通常，经确定化后，状态数增加，而且可能）通常，经确定化后，状态数增加，而且可能出现一些等价状态，这时需要化简。出现一些等价状态，这时需要化简。第三章第三章 词法分析程

30、序（词法分析程序（3333）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA) 例：设例：设NFA M=NFA M=（qq0 0,q,q1 1,0,1,f,q,0,1,f,q0 0,q,q1 1) 映射为映射为 将其确定化将其确定化01q0q0q1q1q0,q1q0字符字符状态状态q010001q1第三章第三章 词法分析程序（词法分析程序（3434）M M的状态：的状态：I I0 0=q=q0 0,则则Q Q中就有了中就有了I I0 0状态。状态。由由Q Q中的状态中的状态I I0 0 =q=q0 0,查看查看M M机，有机，有

31、f(qf(q0 0,0)=q,0)=q0 0= I= I0 0 f(qf(q0 0,1)=q,1)=q1 1= I= I1 1 此时，此时，Q=IQ=I0 0， I I1 1 由由Q Q中的状态中的状态I I1 1=q=q1 1,查看查看M M机。机。 有：有：f(qf(q1 1,0)= q,0)= q0 0, q, q1 1= I= I2 2, f(q, f(q1 1,1)=q,1)=q0 0= I= I0 0 此时，此时，Q=IQ=I0 0, I, I1 1, I, I2 2 由由Q Q中的状态中的状态I I2 2=q=q0 0, q, q1 1 ，查看，查看M M机，机， 有：有： f(

32、qf(q0 0, q, q1 1,0)= q,0)= q0 0, q, q1 1= I= I2 2, , f(q f(q0 0, q, q1 1,1)= q,1)= q0 0, q, q1 1= I= I2 2， 此时此时,Q=I,Q=I0 0，I I1 1，I I2 2 F=IF=I1 1， I I2 2 第三章第三章 词法分析程序（词法分析程序（3535）NFA NFA 经过确定化后，经过确定化后，变为：变为： DFA MDFA M=(I=(I0 0,I,I1 1,I,I2 2,0,1, ,0,1, ,I,I0 0,I,I1 1,I,I2 2)01I0=q0I0=q0I1=q1I1=q1I

33、2=q0,q1I0=q0I2=q0,q1I2=q0,q1I2=q0,q1Q第三章第三章 词法分析程序（词法分析程序（3636）01I0I0I1I1I2I0I2I2I2状态转换图如下状态转换图如下: :I0I1I2011001第三章第三章 词法分析程序（词法分析程序（3737）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)6.6.确定有限自动机的化简确定有限自动机的化简( (最小化最小化) )(1)(1)化简条件化简条件: :接受的语言必须相同接受的语言必须相同(2)(2)化简化简( (最小化最小化) )算法基本思想算法基本思

34、想-划分法划分法-1.-1.将将DFA MDFA M中的状态划分为互不相交的子集中的状态划分为互不相交的子集, ,每个子集内部的状态都等价每个子集内部的状态都等价, ,而在不同子集间的状而在不同子集间的状态均不等价态均不等价-2.-2.从每个子集中任选一个状态作为代表从每个子集中任选一个状态作为代表, ,消去消去其它等价状态其它等价状态. .-3.-3.把那些原来射入其它等价状态的弧改为射把那些原来射入其它等价状态的弧改为射入相应的代表状态入相应的代表状态第三章第三章 词法分析程序（词法分析程序（3838）二、有限自动机（二、有限自动机（Finite automation FA)Finite

35、automation FA)6.6.确定有限自动机的化简确定有限自动机的化简( (最小化最小化) )(3) (3) 状态等价状态等价: :设设DFA MDFA M中有两个状态中有两个状态s,ts,ts,t s,t 等价等价: :-(s,w) -(s,w) * *(s(s1 1, ,e e) ) 同时同时(t,w) (t,w) * *(t(t1 1, ,e e),s),s1 1,t,t1 1都都是终态，是终态，wVwVt t* *, ,那如果从状态那如果从状态S S出发能读出某个字出发能读出某个字w w 而停于终态而停于终态, ,从从t t出发也能读出同样的字出发也能读出同样的字w w而停于终态

36、而停于终态, ,则称则称s,ts,t等价等价s,ts,t可区别可区别: :如果如果s,t s,t 不等价不等价, ,则称则称s,ts,t可区别可区别第三章第三章 词法分析程序（词法分析程序（3939）6.6.确定有限自动机的化简确定有限自动机的化简(4) (4) 化简化简( (最小化最小化) )算法算法1.1.把状态把状态S S划分为终态集和非终态集划分为终态集和非终态集:0 0=I=I0 01 1,I,I0 02 2 I I0 01 1属于非终态集属于非终态集,I,I0 02 2属于终态集属于终态集, ,因为终态能识别因为终态能识别e e, ,而非终态不能，所以它们是可区别的而非终态不能，所

37、以它们是可区别的. .假定经过假定经过K K次划分后：次划分后：k k I Ik k0 0,I,Ik k1 1, ,.I.Ik km m 这这m m个子集可区分个子集可区分, ,子集内部还是否可以划分子集内部还是否可以划分? ?-任取一个子集任取一个子集I IK Ki i=s=s1 1,s,s2 2, ,.s.sk k.若存在某读若存在某读入字符入字符a,a,使使f(If(Ik ki i,a),a)的结果不是全部包含在的结果不是全部包含在k k的某的某个子集中个子集中, ,则说明则说明I Ik ki i中有不等价的状态中有不等价的状态, ,还要进一步还要进一步划分划分. .-对对k k中所有子

38、集都进行测试中所有子集都进行测试, ,以完成一次划分以完成一次划分. .第三章第三章 词法分析程序（词法分析程序（4040）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)(4) (4) 化简化简( (最小化最小化) )算法（续）算法（续）3.3.重复步骤重复步骤2 2，直到所含的子集数不再增加为止。，直到所含的子集数不再增加为止。4.4.对每个子集任取一状态为代表，若该子集包含原对每个子集任取一状态为代表，若该子集包含原有的初态，则相应代表状态就是最小化后的有的初态，则相应代表状态就是最小化后的M M的初的初态；同样，若该子

39、集包含原有的终态，则相应代态；同样，若该子集包含原有的终态，则相应代表状态就是最小化后表状态就是最小化后M M的终态。的终态。6.6.确定有限自动机的化简确定有限自动机的化简第三章第三章 词法分析程序（词法分析程序（4141）二、有限自动机（二、有限自动机（Finite automation FA)Finite automation FA)注：注：1 1）当一个自动机没有任何多余的状态，并且它）当一个自动机没有任何多余的状态，并且它的状态中没有两个是互相等价的时候，我们说这个的状态中没有两个是互相等价的时候，我们说这个有限自动机是化简了的。有限自动机是化简了的。 2 2）可以通过消除多余状态，

40、合并等价状态而转）可以通过消除多余状态，合并等价状态而转化成一个最小化的、与之等价的有限自动机。化成一个最小化的、与之等价的有限自动机。6.6.确定有限自动机的化简确定有限自动机的化简第三章第三章 词法分析程序（词法分析程序（4242）例：设有一例：设有一DFADFA的状态转换图如下，试化简之的状态转换图如下，试化简之 125346babbaabaabab0ba第三章第三章 词法分析程序（词法分析程序（4343）解：解：1.1.把把M M的状态集分为两组：终态集、非终态集的状态集分为两组：终态集、非终态集 0 0=0,1,2,3,4,5,6=0,1,2,3,4,5,62.12.1考察非终态集考

41、察非终态集: : f(0,1,2,a)=1,3, f(0,1,2,a)=1,3,不属于不属于0 0的任何一个子集的任何一个子集, ,所以所以0,1,20,1,2要分开要分开. .得到：得到： 1 1=1=1，0,2,3,4,5,60,2,3,4,5,6再看再看:f(0,2,a)=1 :f(0,2,a)=1 属于属于1 1的子集的子集f(0,2,b)=2,5f(0,2,b)=2,5不属于不属于1 1的任何子集的任何子集, ,所以所以0,20,2要分开要分开. .得到得到: : 1 1”=1,0,2,3,4,5,6=1,0,2,3,4,5,6第三章第三章 词法分析程序（词法分析程序（4444）解解

42、: : ( (续续) )2.22.2考察终态集考察终态集: :f(3,4,5,6,a)=3,6f(3,4,5,6,a)=3,6包含于包含于1 1”的子集的子集3,4,5,63,4,5,6f(3,4,5,6,b)=4,5f(3,4,5,6,b)=4,5包含于包含于1 1”的子集的子集3,4,5,63,4,5,6所以所以3,4,5,63,4,5,6不可再划分不可再划分. .3.3.整个划分为整个划分为4 4个组个组: : 2 2=1,0,2,3,4,5,6=1,0,2,3,4,5,64.4.令状态令状态3 3代表代表3,4,5,6,3,4,5,6,把原来到达状态把原来到达状态4,5,64,5,6的

43、弧都导入的弧都导入3,3,并删除并删除4,5,64,5,6。得。得: :第三章第三章 词法分析程序（词法分析程序（4545）123bbaaba0ab即为化简了的即为化简了的DFADFA第三章第三章 词法分析程序（词法分析程序（4646）第一节第一节 正规文法与有限自动机正规文法与有限自动机三、正规式与有限自动机之间的关系三、正规式与有限自动机之间的关系1.1.关系定理关系定理: :定理定理:上的上的NFA MNFA M所能识别语言所能识别语言L(M)L(M)可以用可以用上的正规式来上的正规式来表示表示. .即即: :对对上的上的NFA M,NFA M,可构造一个正规式可构造一个正规式a,a,

44、使得使得L(a)= L(M)L(a)= L(M)定理定理:上任何正规式上任何正规式a,a,存在存在NFA M,NFA M,使得使得L(M) = L(a) L(M) = L(a) 即即: :由正规式由正规式a a可以构造一个可以构造一个NFA M,NFA M,使得使得L(M) = L(a) L(M) = L(a) 第三章第三章 词法分析程序（词法分析程序（4747）2.2.有限自动机有限自动机M M向正规式向正规式a a的转换的转换. .1)1)把状态转换图的概念拓广把状态转换图的概念拓广, ,令每条弧上都可以用一个正规式令每条弧上都可以用一个正规式作标记作标记, ,2) M2) M转换图上加两

45、个结点转换图上加两个结点:x,y,:x,y,从从x x用用e e弧连接到弧连接到M M的所有初态结的所有初态结点点; ;从从M M的终态结点用的终态结点用e e弧连接到弧连接到y,y,这个新的这个新的NFANFA为为M M, ,且且L(M) L(M) = L(M= L(M) ) 3)3)通过引入的通过引入的3 3条有限自动机替换规则逐步消去条有限自动机替换规则逐步消去M M中的所有结中的所有结点点, ,直到只剩下直到只剩下x x和和y y为止为止, ,这样这样, ,在在x x至至y y的弧线上的标记就是的弧线上的标记就是上的正规式上的正规式, ,也就是也就是M M接受的正规式接受的正规式. .

46、注注: :在消除结点的过程中在消除结点的过程中, ,逐步用正规式来标记弧逐步用正规式来标记弧. .第一节第一节 正规文法与有限自动机正规文法与有限自动机三、正规式与有限自动机之间的关系三、正规式与有限自动机之间的关系第三章第三章 词法分析程序（词法分析程序（4848）有限自动机替换规则有限自动机替换规则1131211312222ababbaaba|bab*第三章第三章 词法分析程序（词法分析程序（4949）例例: :将下面的将下面的DFA MDFA M所接受的语言表示为正规式所接受的语言表示为正规式. .302111110000ye ee ex第三章第三章 词法分析程序（词法分析程序（5050

47、）y03x10|0101|1000|1100|11e ee e0y(10|01)(00|11)*(01|10)xe ee e00|11x(10|01)(00|11)*(01|10)| (00|11)*y第三章第三章 词法分析程序（词法分析程序（5151）3.3.正规式正规式a a向确定有限自动机向确定有限自动机M M的转换的转换1)1)由正规式构造一个如下仅有两个结点由正规式构造一个如下仅有两个结点x,yx,y的状态图的状态图第一节第一节 正规文法与有限自动机正规文法与有限自动机三、正规式与有限自动机之间的关系三、正规式与有限自动机之间的关系yxa2)2)按所引入的按所引入的3 3条正规式分裂

48、规则分裂条正规式分裂规则分裂a a3)3)重复步骤重复步骤2 2直到每个弧上的标记是直到每个弧上的标记是上的一个字符上的一个字符或或e e为止为止4)4)将所得的将所得的NFA M(NFA M(因为包含因为包含e e弧弧) )进行确定化就得进行确定化就得DFADFA正规式分裂规则正规式分裂规则. .第三章第三章 词法分析程序（词法分析程序（5252）112122aba|bb*1131122abbaeb1e正规式分裂规则正规式分裂规则第三章第三章 词法分析程序（词法分析程序（5353）第一节第一节 正规文法与有限自动机正规文法与有限自动机三、正规式与有限自动机之间的关系三、正规式与有限自动机之间

49、的关系3.3.正规式正规式a a向确定有限自动机向确定有限自动机M M的转换的转换注注: :这里将这里将NFA MNFA M进行确定化与前面所讲的子集法确进行确定化与前面所讲的子集法确定化是一回事定化是一回事, ,不过不过, ,这里的这里的NFA MNFA M中含有中含有e e弧弧, ,所以所以在求覆盖片时应考虑在求覆盖片时应考虑e e弧弧, ,方法是求方法是求e e闭包闭包( (e eclosure),closure),将此闭包将此闭包( (状态子集状态子集) )作为作为DFADFA的一个状的一个状态使用态使用, ,而将而将NFANFA上的状态间转换变为闭包间的转上的状态间转换变为闭包间的转

50、换换, ,使得不确定的自动机确定化使得不确定的自动机确定化第三章第三章 词法分析程序（词法分析程序（5454）例例: :根据正规式根据正规式(a|b)(a|b)* *(aa|bb) (a|b)(aa|bb) (a|b)* *构造构造DFA M DFA M 使得它们等价使得它们等价yx(a|b)*(aa|bb) (a|b)*yx(a|b)*(aa|bb)(a|b)*xee2eeya|ba|baabb51621xee2eeyaa51634bbaabb第三章第三章 词法分析程序（词法分析程序（5555）第一节第一节 正规文法与有限自动机正规文法与有限自动机三、正规式与有限自动机之间的关系三、正规式与

51、有限自动机之间的关系4.4.对含有对含有e e弧的弧的NFANFA进行确定化进行确定化(1) (1) e e闭包闭包: :是可以从某状态或某些状态通过是可以从某状态或某些状态通过e e弧所能弧所能到达的所有状态的集合到达的所有状态的集合, ,状态集合状态集合I I的的e e闭包闭包( (e eclosure(I)closure(I)形式定义如下形式定义如下: :(a)(a)若若sI,sI,则则sse eclosure(I)closure(I)(b)(b)若若sI,sI,那么从那么从s s出发经过任意段的出发经过任意段的e e弧所能达到弧所能达到的任意状态的任意状态s s都属于都属于e eclo

52、sure(I)closure(I)第三章第三章 词法分析程序（词法分析程序（5656）第一节第一节 正规文法与有限自动机正规文法与有限自动机三、正规式与有限自动机之间的关系三、正规式与有限自动机之间的关系4.4.对含有对含有e e弧的弧的NFANFA进行确定化进行确定化(2)(2)闭包间转换闭包间转换. .设设e eclosure(I)=qclosure(I)=q0 0,q,q1 1, ,q qn n,当读入字母表中字当读入字母表中字母母a a时，它转换到另一闭包时，它转换到另一闭包e eclosure(I)closure(I)e eclosure(J)closure(J)的组成的组成 J=f

53、(qJ=f(q0 0,a) f(q,a) f(q1 1,a) ,a) .f(q.f(qn n,a),a) 对得到的对得到的J J按按e e闭包的定义求闭包的定义求e eclosure(J)closure(J)第三章第三章 词法分析程序（词法分析程序（5757）第一节第一节 正规文法与有限自动机正规文法与有限自动机三、正规式与有限自动机之间的关系三、正规式与有限自动机之间的关系4.4.对含有对含有e e弧的弧的NFANFA进行确定化进行确定化（3 3）对含有）对含有e e弧的弧的NFANFA进行确定化方法进行确定化方法设由设由NFA M=NFA M=（S,f,SS,f,S0 0,Z),Z)构造一

54、个等价的构造一个等价的DFADFA M M= =（Q,d,IQ,d,I0 0,F),F)(a)I(a)I0 0= = e eclosure(Sclosure(S0 0),I),I0 0QQ(b)(b)若状态集若状态集Q Q中有状态中有状态I Ii i=s=s0 0,s,s1 1, ,s sj j,s,sk kS,0kj; S,0kj; 且有且有I It t= = e eclosure(f(Iclosure(f(Ii i,a),a),若若I It t不在不在Q Q中，则将中，则将I It t加入加入Q Q（c)c)重复步骤重复步骤2 2，直到，直到Q Q中无新状态加入中无新状态加入（d)d)取终

55、态取终态F=I|IQF=I|IQ，且，且IZFIZF第三章第三章 词法分析程序（词法分析程序（5858）xee2eeya51634bbaabb例例IabI0=x,5,1I1=5,3,1I2=5,4,1I1=5,3,1I3=5,3,2,1,6,yI2=5,4,1I2=5,4,1I1=5,3,1I4=5,4,1,2,6,yI3=5,3,2,1,6,yI3=5,3,2,1,6,yI5=5,1,4,6, yI4=5,4,1,2,6,yI6=5,3,1,6,yI4=5,4,1,2,6,yI5=5,1,4,6, yI6=5,3,1,6,yI4=5,4,1,2,6,yI6=5,3,1,6,yI3=5,3,2

56、,1,6,yI5=5,1,4,6, ya第三章第三章 词法分析程序（词法分析程序（5959）IabI0I1I2I1I3I2I2I1I4I3I3I5I4I6I4I5I6I4I6I3I5I1I2I4I3I5I6babbaabaababI0baDFA为:第三章第三章 词法分析程序（词法分析程序（6060）四、正规文法和有限自动机四、正规文法和有限自动机1 1、关系定理、关系定理 设设G=G=（V VN N,V,VT T,P,S),P,S)是正规文法，则存在一个有限自是正规文法，则存在一个有限自动机动机M=M=（Q,f,qQ,f,q0 0,Z),Z)使得使得 L(G)=L(M). L(G)=L(M).

57、 注：注：1 1）正规文法分为右线性文法和左线性文法。）正规文法分为右线性文法和左线性文法。但对一个正规文法，不能既是左线性，又是右线但对一个正规文法，不能既是左线性，又是右线性。性。2 2）对每个有限自动机）对每个有限自动机M,M,都存在一个右线性正规文法都存在一个右线性正规文法G GR R和左线性正规文法和左线性正规文法G GL L， 使得使得 L(M)=L(GL(M)=L(GR R)= L(G)= L(GL L).).第三章第三章 词法分析程序（词法分析程序（6161）四、正规文法和有限自动机四、正规文法和有限自动机2 2、右线性文法转换为等价自动机、右线性文法转换为等价自动机设有右线性

58、文法：设有右线性文法： G=G=（V VN N,V,VT T,P,S),P,S)，将其转换为，将其转换为自动机自动机M=M=（Q,f,qQ,f,q0 0,Z),Z)。转换步骤如下：转换步骤如下：1 1）将）将V VN N中的每个非终结符视为状态符号，并增加中的每个非终结符视为状态符号，并增加一个新的终结状态符号一个新的终结状态符号T T，即令，即令Q=VQ=VN NT; T; 同时，同时，令令=V=VT T,q,q0 0=S;=S;若若P P中含有中含有S S e e , ,则令则令Z=S,T,Z=S,T,否则令否则令Z=TZ=T；第三章第三章 词法分析程序（词法分析程序（6262）四、正规文

59、法和有限自动机四、正规文法和有限自动机2 2、右线性文法转换为等价自动机、右线性文法转换为等价自动机2 2）P P中的产生式用如下映射中的产生式用如下映射f f来代替来代替 a) a)对于对于P P中每一条形如中每一条形如A A1 1 aA aA2 2的产生式，的产生式，M M中中设为设为f(Af(A1 1,a)=A,a)=A2 2. . b) b)对于对于P P中每一条形如中每一条形如A A1 1 a a的产生式，的产生式，M M中设中设为为f(Af(A1 1,a)=T.,a)=T. c) c)对对上的所有上的所有a a，取，取f(T,a)= f(T,a)= , ,即在终态下有即在终态下有限

60、自动机无动作限自动机无动作第三章第三章 词法分析程序（词法分析程序（6363）例：有文法例：有文法G=(S,A,B,a,b,c,P,S G=(S,A,B,a,b,c,P,S 其中产其中产生式生式P:P: -S aS|aB -S aS|aB -B bB|bA -B bB|bA -A cA|c -A cA|c构造与之等价的构造与之等价的FAFA解：构造自动机解：构造自动机M=M=（Q,f,qQ,f,q0 0,Z),Z)1 1）增加一个新的终结状态符号）增加一个新的终结状态符号T T，Q=S,B,A,TQ=S,B,A,T=a,b,c,q=a,b,c,q0 0=S,Z=T=S,Z=T第三章第三章 词法