1、第三章第三章 词法分析词法分析词法分析词法分析l词法分析程序概述词法分析程序概述l正规文法与正规式正规文法与正规式l有穷自动机有穷自动机l正规式与有穷自动机的等价性正规式与有穷自动机的等价性l正规文法与有穷自动机的等价性正规文法与有穷自动机的等价性l一个简单的词法分析器示例一个简单的词法分析器示例 状态图的形式化描述状态图的形式化描述3.3 3.3 有穷自动机有穷自动机S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+*，（）出口出口4其他字符其他字符5=非非=出错出错其他其他标识符标识符无符号整数无符号整数单界符单界符双界符双界符读字符读字
2、符返回返回S Sl 有穷自动机是一种有穷自动机是一种数学模型数学模型，具有离散的输入与输出，系统，具有离散的输入与输出，系统可处于有穷状态中的任何一个；可处于有穷状态中的任何一个；l 它能准确地它能准确地识别正规集识别正规集，即识别正规文法所定义的语言和正，即识别正规文法所定义的语言和正规式所表示的集合；规式所表示的集合；l 引入有穷自动机这个理论，正是为引入有穷自动机这个理论，正是为词法分析程序的自动构造词法分析程序的自动构造寻找特殊的方法和工具。寻找特殊的方法和工具。有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机（DFADFA）(Deterministic Fin
3、ite Automata)(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机（NFANFA）(Nondeterministic Finite Automata)(Nondeterministic Finite Automata)3.3 3.3 有穷自动机有穷自动机2 2型文法型文法（不确定的下推自动机）（不确定的下推自动机）1 1型文法型文法（不确定的界限自动机）（不确定的界限自动机）0 0型文法型文法（图灵机）（图灵机）3 3型文法型文法（有限自动机）（有限自动机）3.3 3.3 有穷自动机有穷自动机1.1.确定的有穷自动机（确定的有穷自动机（
4、DFADFA）M=(,Q,f,M=(,Q,f,S,Z)S,Z)l：有穷字母表，它的每个元素称为一个输入符号；：有穷字母表，它的每个元素称为一个输入符号；lQ Q：有穷集，它的每个元素称为一个状态；有穷集，它的每个元素称为一个状态；lSKSK，是唯一的初态；，是唯一的初态；lZ Z K K是一个终态集，终态也称可接受状态或结束状态；是一个终态集，终态也称可接受状态或结束状态；lf f 是转换函数，是是转换函数，是Q QQQ上的单值映射：上的单值映射：f f（q1q1，a a）=q2=q2 3.3 3.3 有穷自动机有穷自动机状态转移函数状态转移函数f f可用一矩阵来表示：可用一矩阵来表示：输入字
5、符输入字符 状态状态 a a b b 0 1 2 0 1 2 1 3 2 1 3 2 2 1 3 2 1 3 3 3 3 3 3 3例如例如:M:M:（0,1,2,3,a,b,f0,1,2,3,a,b,f，0 0，33）f f（0 0，a a）=1 f=1 f（0 0，b b）=2=2 f f（1 1，a a）=3 f=3 f（1 1，b b）=2=2 f f（2 2，a a）=1 f=1 f（2 2，b b）=3=3 f f（3 3，a a）=3 f=3 f（3 3，b b）=3=3所谓确定的状态机，所谓确定的状态机，其确定性表现在状其确定性表现在状态转移函数是单值态转移函数是单值函数！函数
6、！M=(,Q,f,S,Z)3.3 3.3 有穷自动机有穷自动机一个一个DFADFA也可以用一状态转换图表示：也可以用一状态转换图表示：DFADFA的状态图表示：的状态图表示：1032aabba,bba3.3 3.3 有穷自动机有穷自动机 输入字符输入字符 状态状态 a a b b 0 1 2 0 1 2 1 3 2 1 3 2 2 1 3 2 1 3 3 3 3 3 3 3字母表字母表含有含有n n个输入字符，那末任何一个状态结个输入字符，那末任何一个状态结点最多有点最多有n n条弧射出，而且每条弧以一个不同的输条弧射出，而且每条弧以一个不同的输入字符标记。入字符标记。换言之：若存在一条初始状
7、态到某一终止状态的路径，且这条路径上换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串所有弧的标记符号连接成符号串，则称，则称为为DFA MDFA M（接受）识别。（接受）识别。DFA MDFA M所接受的语言为：所接受的语言为：L(M)=|f(S,)=Sn,Sn ZL(M)=|f(S,)=Sn,Sn ZDFA MDFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)L(M)若若M M的初态结点同时为终态，或者存在一条从初态到某个终态结的初态结点同时为终态，或者存在一条从初态到某个终态结点的点的通路，则通路，则为为M M所识别。所识别。3.
8、3 3.3 有穷自动机有穷自动机（0 0，abaababaab）=（1 1，baabbaab）=（2 2，aabaab）=（1 1，abab）=（3 3，b b）=3(=3(接受接受)（0 0，abababab）=（1 1，babbab）=（2 2，abab）=（1 1，b b）=2(=2(拒绝拒绝)对于符号串对于符号串abaababaab对于符号串对于符号串abababab3.3 3.3 有穷自动机有穷自动机DFADFA的状态图表示：的状态图表示：1032aabba,bbaf f是一个多值函数，是从是一个多值函数，是从Q Q*到到Q Q的子集的映射：的子集的映射：f f：Q Q2 2Q Q
9、其中其中2 2Q Q是是Q Q的幂集，即的幂集，即Q Q中所有子集组成的集合。中所有子集组成的集合。2.2.不确定的有穷自动机（不确定的有穷自动机（NFANFA）M=(,Q,f,M=(,Q,f,S,Z)S,Z)有穷自动机的不确定性表现在在某个状态下，对于某个有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的。输入字符存在多个后继状态，即状态的转向是不确定的。3.3 3.3 有穷自动机有穷自动机例：例：NFA N=(a,b,c,1,2,3,4,f,1,4)NFA N=(a,b,c,1,2,3,4,f,1,4)符号符号状态状态 a b c a b c
10、1 1 4 24 2，3 3 2 2 2 2 4 4 3 3 3 3，44 4 4 3.3 3.3 有穷自动机有穷自动机l 对于对于*上的任何符号串上的任何符号串，若存在一条从某一初态到某一终态，若存在一条从某一初态到某一终态 的通路，且该通路上所有弧的标记字符依次连接成的串等于的通路，且该通路上所有弧的标记字符依次连接成的串等于，则称则称 可以被可以被NFA NNFA N所识别或接受。所识别或接受。l 若若N N的初态结点同时为终态，或者存在一条从初态到某个终态的初态结点同时为终态，或者存在一条从初态到某个终态 结点的结点的 通路，则通路，则 为为N N所识别。所识别。NFA NNFA N所
11、能识别的符号串的全体记为所能识别的符号串的全体记为L(N)L(N)，称为，称为NFA NFA N N所识别的语言。所识别的语言。3.3 3.3 有穷自动机有穷自动机上例题相应的状态图为：上例题相应的状态图为：1234abacacN N所接受的语言（正规式）所接受的语言（正规式）R=aaR=aa*b|acb|ac*c|c|3.3 3.3 有穷自动机有穷自动机例：例：NFA N=(a,b,c,1,2,3,4,f,1,4)符号符号 状态状态 a b c 1 4 2，3 2 2 4 3 3，4 4 能接受能接受 000000 111 111 1010001 1010001 110000001 1100
12、00001(0|1)(0|1)*(000|111)(0|1)(000|111)(0|1)*不能接受不能接受 0000 01100 011003.3 3.3 有穷自动机有穷自动机画出能够识别画出能够识别C C语言注释语言注释/*/的的DFADFA3.3 3.3 有穷自动机有穷自动机12453othersothers/*/6othersothers all状态状态1：注释开始状态。：注释开始状态。状态状态2：进入注释体前的中间状态。：进入注释体前的中间状态。状态状态3：表明目前正在注释体中的状态。：表明目前正在注释体中的状态。状态状态4：离开注释前的中间状态。：离开注释前的中间状态。状态状态5：注
13、释结束状态，即接受状态。：注释结束状态，即接受状态。3.3 3.3 有穷自动机有穷自动机12453othersothers/*/q用于某些重要软件的设计和构造用于某些重要软件的设计和构造 设计和检查数字电路行为的软件设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它扫描如网页族等大规模文本以发现字、词或其它 结构的出现频率的软件结构的出现频率的软件;验证所有只有有限多个不同状态的系统的软件，验证所有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。这类系统包括通信协议和信息安全交换协议。有穷自动机的其它应用有穷自动机的其它应用3.3 3.3 有穷自
14、动机有穷自动机已证明：非确定的有穷自动机与确定的有穷自动机从功能已证明：非确定的有穷自动机与确定的有穷自动机从功能 上来说是等价的，也就是说，我们能够从：上来说是等价的，也就是说，我们能够从：NFA NDFA M构造成一个构造成一个使得使得L(M)=L(N)L(M)=L(N)DFA DFA是是NFANFA的特例。有一种算法，将的特例。有一种算法，将NFANFA转换成接受转换成接受同样语言的同样语言的DFADFA。这种算法称为这种算法称为子集法子集法。与某一与某一NFANFA等价的等价的DFADFA不唯一。不唯一。3.3 3.3 有穷自动机有穷自动机3.NFA3.NFA的确定化的确定化 从从NF
15、ANFA的矩阵表示中可以看出，表项通常是一状态的集合，而的矩阵表示中可以看出，表项通常是一状态的集合，而在在DFADFA的矩阵表示中，表项是一个状态。的矩阵表示中，表项是一个状态。NFANFA到相应的到相应的DFADFA的构造的基本思路是：的构造的基本思路是：DFADFA的每一个状态对应的每一个状态对应NFANFA的一组状态。的一组状态。1234abacac3.3 3.3 有穷自动机有穷自动机例：例：NFA N=(a,b,c,1,2,3,4,f,1,4)符号符号 状态状态 a b c 1 4 2，3 2 2 4 3 3，4 4 (1)(1)合并合并如果有如果有 ，则把，则把S S2 2合并到合
16、并到S S1 1S S1 1S S2 2转换需解决的问题：转换需解决的问题：ijkmaban（a）i,jmkaabn（b）3.3 3.3 有穷自动机有穷自动机(2)(2)状态合并状态合并0123aabc（a）01,23abc（b）3.3 3.3 有穷自动机有穷自动机定义定义1 1：状态集合：状态集合I I的的-闭包，表示为闭包，表示为-closure(I)-closure(I)若若qIqI，则，则qq-closure(I)-closure(I)；若若qIqI，则从，则从q q出发经过任意条出发经过任意条 弧而能到达的任何状态弧而能到达的任何状态 qq都属于都属于-closure(I)-clos
17、ure(I)。为了使得为了使得NFANFA确定化，我们首先给出两个定义：确定化，我们首先给出两个定义：_ closure(I)IIS2S2S1S1S3S33.3 3.3 有穷自动机有穷自动机例：例：如图所示的状态图：如图所示的状态图：令令I=1，求求-closure（I）=？156432aaa根据定义：根据定义：-closure-closure（I I）=1=1，33课堂练习：令课堂练习：令I=1,2I=1,2求：求：-closure-closure（I I）=？3.3 3.3 有穷自动机有穷自动机-closure（I）=1、2、3、6I I是状态集，由是状态集，由I I中的状态出发，经过一条
18、中的状态出发，经过一条a a弧可能弧可能到达的状态的集合称为到达的状态的集合称为movemove（I I，a a），则：），则：I Ia a=_closure(move(I,a)=_closure(move(I,a)定义定义2 2：I Ia a子集子集3.3 3.3 有穷自动机有穷自动机例：令例：令I=1I=1 Ia=-closure(move Ia=-closure(move（I I，a a）)=-closure(f =-closure(f（1 1，a a）=-closure(2=-closure(2，44）=2=2，4 4，66156432aaa课堂练习：令课堂练习：令I=1,2,3I=1
19、,2,3求求Ia=Ia=？3.3 3.3 有穷自动机有穷自动机Ia=-closureIa=-closure（move(I,amove(I,a）=-closuref(1,a)=-closuref(1,a)、f(2,a)f(2,a)、f(3,a)f(3,a)=-closure2 =-closure2、4 4、5=25=2、6 6、3 3、55课堂练习：课堂练习：令令I=1I=1，设，设SS=-closure=-closure（I I），求：求：SS？SSa a=？1234abacac3.3 3.3 有穷自动机有穷自动机S=-closureS=-closure（I I）=1=1、44SSa a=(2
20、=(2、33（1 1）将从状态）将从状态S S出发经过任意条出发经过任意条 弧所能到达的状态弧所能到达的状态 作为作为DFADFA的初态的初态S S;（2 2）从）从S S出发，把遇到输入符号出发，把遇到输入符号a a所转移到的后继状所转移到的后继状态态 集作为集作为DFADFA的新状态的新状态;（3 3）如此重复，直到不再有新的状态出现为止）如此重复，直到不再有新的状态出现为止。NFANFA转换为转换为DFADFA的思想的思想3.3 3.3 有穷自动机有穷自动机-closure(S对于每一个输入符号啊，求对于每一个输入符号啊，求IaIa对于每一个新状态，重复（对于每一个新状态，重复（2 2）
21、（1 1）构造一张表，它共有）构造一张表，它共有+1+1列；列；（2 2）第一行第一列为）第一行第一列为-closure(S)-closure(S)；（3 3）对于每一个输入符，求）对于每一个输入符，求IaIa；（4 4）重复步骤（）重复步骤（3 3）；）；（5 5）将状态子集重新命名。）将状态子集重新命名。1234abacac3.3 3.3 有穷自动机有穷自动机 I Ia Ib Ic 1,4 2,3 2,3 2 4 3,4 2 2 4 4 3,4 3,4 -closure(S-closure(S新状态新状态新状态新状态新状态新状态将求得的状态转换矩阵重新编号，得到将求得的状态转换矩阵重新编号
22、，得到DFA MDFA M状态转换矩阵：状态转换矩阵：符号状态abc0 2 341221_33443.3 3.3 有穷自动机有穷自动机 I Ia Ib Ic 1,4 2,3 2,3 2 4 3,4 2 2 4 4 3,4 3,4 0 01 12 23 34 41 12 22 2-3 33 3-4 4-4 4a b cDFA M的状态图：的状态图：014231,42,342acabbc3,41234abacac3.3 3.3 有穷自动机有穷自动机注意：包含原初始状态注意：包含原初始状态1 1的状态子集为的状态子集为DFA MDFA M的初态的初态 包含原终止状态包含原终止状态4 4的状态子集为的
23、状态子集为DFA MDFA M的终态。的终态。Ia Ib i,1,2 1,2,3 1,2,4 1,2,3 1,2,3,5,6,f 1,2,4 1,2,4 1,2,3 1,2,4,5,6,f 1,2,3,5,6,f 1,2,3,5,6,f 1,2,4,6,f 1,2,4,5,6,f 1,2,3,6,f 1,2,4,5,6,f 1,2,4,6,f 1,2,3,6,f 1,2,4,5,6,f 1,2,3,6,f 1,2,3,5,6,f 1,2,4,6,f 课堂练习课堂练习4f35621iaaaabbbbstartSABACBBADCCEDFDEFDFCE3.3 3.3 有穷自动机有穷自动机等价的等价
24、的DFADFAaCDBAEFSbaaaaabbbbbabFstart3.3 3.3 有穷自动机有穷自动机4.DFA的最小化的最小化l 如果不同的如果不同的DFADFA能识别相同的语言，则称它们是等价的能识别相同的语言，则称它们是等价的DFADFA；l 在等价的在等价的DFADFA中，如果某一个中，如果某一个DFADFA的状态数是最少的，则这个的状态数是最少的，则这个 DFADFA是最简的；是最简的；l 对于任一个对于任一个DFADFA，存在一个唯一的状态最少的等价的，存在一个唯一的状态最少的等价的DFADFA。最简的最简的DFA 它没有多余它没有多余状态和等价状态状态和等价状态3.3 3.3
25、有穷自动机有穷自动机定义定义1 1：多余状态：多余状态：从开始状态出发从开始状态出发,任何输入串也不能到达的状态。任何输入串也不能到达的状态。01s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例例:3.3 3.3 有穷自动机有穷自动机画状态图可看出画状态图可看出S4,S6,S8S4,S6,S8为不可达状态应该消除。为不可达状态应该消除。S0S1S2S3S4S5S6S7S801s0s1s2s3s5s7s1s5s7s2s2s5s5s7s1s3s0s1S0S1S2S3S5S7定义定义2 2：等价状态等价状态 状态状态s s和和t t的等价
26、条件是的等价条件是:状态状态S和和T必须同时为终态或非终态；必须同时为终态或非终态；对于所有输入符号，对于所有输入符号，S和和T必须转换到等价的状态里。必须转换到等价的状态里。3.3 3.3 有穷自动机有穷自动机l 把把DFA的状态划分成一些不相交的子集；的状态划分成一些不相交的子集；l 任何不同的两个子集的状态都是可区分的；任何不同的两个子集的状态都是可区分的；l 同一子集中的任何两个状态都是等价的。同一子集中的任何两个状态都是等价的。DFADFA最小化算法的基本思想最小化算法的基本思想(没有多余状态没有多余状态)：3.3 3.3 有穷自动机有穷自动机（1）将所有状态分成两个子集：终态集和非
27、终态集；）将所有状态分成两个子集：终态集和非终态集；（2）把等价的状态构成一个子集，若不等价继续划分；）把等价的状态构成一个子集，若不等价继续划分；（3）结束后，重新标号或从每个子集中选一个状态做代表。）结束后，重新标号或从每个子集中选一个状态做代表。解解:(一一)区分终态与非终态区分终态与非终态ab12345663731546737414212区号区号123123456637315467374142ab区号区号3.3 3.3 有穷自动机有穷自动机a ab b5724361a ab ba aa ab ba ab ba ab bb ba ab b1 12 23 34 45 56 66 63 37
28、 73 31 15 54 46 67 73 37 74 41 14 42 2a ab b1 12 24 43 3区号区号1 12 24 43 31 12 23 34 45 56 66 63 37 73 31 15 54 46 67 73 37 74 41 14 42 2a ab b5 5区号区号3.3 3.3 有穷自动机有穷自动机123123456637315467374142ab区号区号a ab b5724361a ab ba aa ab ba ab ba ab bb ba ab b将区号代替状态号得将区号代替状态号得:12345ab521435523115 5243aaaaabbbbb化简后的有穷自动机具有较少的状态，实现起来更加简洁。化简后的有穷自动机具有较少的状态，实现起来更加简洁。3.3 3.3 有穷自动机有穷自动机
