第3章词法分析课件

词法分析词法分析l词法分析程序概述词法分析程序概述l正规文法与正规式正规文法与正规式l有穷自动机有穷自动机l正规式与有穷自动机的等价性正规式与有穷自动机的等价性l正规文法与有穷自动机的等价性正规文法与有穷自动机的等价性l一个简单的词法分析器示例一个简单的词法分析器示例 词法分析词法分析程序概述词法分析词法分析程序概述状态图的形式化描述状态图的形式化描述3.3 3.3 有穷自动机有穷自动机S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+*，（）出口出口4其他字符其他字符5=非非=出错出错其他其他标识符标识符无符号整数无符号整数单界符单界符双界符双界符读字符读字符返回返回S S状态图的形式化描述状态图的形式化描述3.3 有穷自动机有穷自动机S1非字母数字字母字母、非字母数字字母字母、l有穷自动机是一种有穷自动机是一种数学模型数学模型，具有离散的输入与输出，系统，具有离散的输入与输出，系统可处于有穷状态中的任何一个；可处于有穷状态中的任何一个；l它能准确地它能准确地识别正规集识别正规集，即识别正规文法所定义的语言和正，即识别正规文法所定义的语言和正规式所表示的集合；规式所表示的集合；l引入有穷自动机这个理论，正是为引入有穷自动机这个理论，正是为词法分析程序的自动构造词法分析程序的自动构造寻找特殊的方法和工具。寻找特殊的方法和工具。有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机（DFADFA）(Deterministic Finite 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 有穷自动机有穷自动机2型文法型文法1型文法（不确定的界限自动机）型文法（不确定的界限自动机）0型文法（图灵机）型文法（图灵机）3型型1.1.确定的有穷自动机（确定的有穷自动机（DFADFA）M=(,Q,f,M=(,Q,f,S,Z)S,Z)l：有穷字母表，它的每个元素称为一个输入符号；：有穷字母表，它的每个元素称为一个输入符号；lQ Q：有穷集，它的每个元素称为一个状态；有穷集，它的每个元素称为一个状态；lSKSK，是唯一的初态；，是唯一的初态；lZ Z K K是一个终态集，终态也称可接受状态或结束状态；是一个终态集，终态也称可接受状态或结束状态；lf f 是转换函数，是是转换函数，是QQQQ上的单值映射：上的单值映射：f f（q1q1，a a）=q2=q2 3.3 3.3 有穷自动机有穷自动机1.确定的有穷自动机（确定的有穷自动机（DFA）：有穷字母表，它的每个元素称：有穷字母表，它的每个元素称状态转移函数状态转移函数f f可用一矩阵来表示：可用一矩阵来表示：输入字符输入字符 状态状态 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所谓确定的状态机，所谓确定的状态机，其确定性表现在状其确定性表现在状态转移函数是单值态转移函数是单值函数！函数！M=(,Q,f,S,Z)3.3 3.3 有穷自动机有穷自动机状态转移函数状态转移函数f可用一矩阵来表示：例如可用一矩阵来表示：例如:M:（0,1,2一个一个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条弧射出，而且每条弧以一个不同的输条弧射出，而且每条弧以一个不同的输入字符标记。入字符标记。一个一个DFA也可以用一状态转换图表示：也可以用一状态转换图表示：DFA的状态图表示：的状态图表示：10换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串有弧的标记符号连接成符号串，则称，则称为为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.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,bba（0，abaab）（0，abab）对于符号串）对于符号串abaab对对f f是一个多值函数，是从是一个多值函数，是从QQ*到到Q Q的子集的映射：的子集的映射：f f：QQ2 2Q Q 其中其中2 2Q Q是是Q Q的幂集，即的幂集，即Q Q中所有子集组成的集合。中所有子集组成的集合。2.2.不确定的有穷自动机（不确定的有穷自动机（NFANFA）M=(,Q,f,M=(,Q,f,S,Z)S,Z)有穷自动机的不确定性表现在在某个状态下，对于某个有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的。输入字符存在多个后继状态，即状态的转向是不确定的。3.3 3.3 有穷自动机有穷自动机f是一个多值函数，是从是一个多值函数，是从Q*到到Q的子集的映射：的子集的映射：2.不确定的不确定的例：例：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 1 1 4 24 2，3 3 2 2 2 2 4 4 3 3 3 3，44 4 4 3.3 3.3 有穷自动机有穷自动机例：例：NFA N=(a,b,c,1,2,3,4l 对于对于*上的任何符号串上的任何符号串，若存在一条从某一初态到某一终态，若存在一条从某一初态到某一终态 的通路，且该通路上所有弧的标记字符依次连接成的串等于的通路，且该通路上所有弧的标记字符依次连接成的串等于，则称则称 可以被可以被NFA NNFA N所识别或接受。所识别或接受。l 若若N N的初态结点同时为终态，或者存在一条从初态到某个终态的初态结点同时为终态，或者存在一条从初态到某个终态 结点的结点的 通路，则通路，则 为为N N所识别。所识别。NFA NNFA N所能识别的符号串的全体记为所能识别的符号串的全体记为L(N)L(N)，称为，称为NFA NFA N N所识别的语言。所识别的语言。3.3 3.3 有穷自动机有穷自动机 对于对于*上的任何符号串上的任何符号串，若存在一条从某一初态到某一终态，若存在一条从某一初态到某一终态N上例题相应的状态图为：上例题相应的状态图为：1234abacacN N所接受的语言（正规式）所接受的语言（正规式）R=aa R=aa*b|ac*c|b|ac*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 上例题相应的状态图为：上例题相应的状态图为：1234abacacN所接受的语言（所接受的语言（能接受能接受 000 000 111 111 1010001 1010001 110000001 110000001(0|1)(0|1)*(000|111)(0|1)(000|111)(0|1)*不能接受不能接受 00 00 01100 011003.3 3.3 有穷自动机有穷自动机能接受能接受(0|1)*(000|111)(0|1)*不能接受不能接受3.画出能够识别画出能够识别C C语言注释语言注释/*/*/的的DFADFA3.3 3.3 有穷自动机有穷自动机12453othersothers/*/6othersothers all画出能够识别画出能够识别C语言注释语言注释/*/的的DFA3.3 有穷自动机有穷自动机状态状态1：注释开始状态。：注释开始状态。状态状态2：进入注释体前的中间状态。：进入注释体前的中间状态。状态状态3：表明目前正在注释体中的状态。：表明目前正在注释体中的状态。状态状态4：离开注释前的中间状态。：离开注释前的中间状态。状态状态5：注释结束状态，即接受状态。：注释结束状态，即接受状态。3.3 3.3 有穷自动机有穷自动机12453othersothers/*/状态状态1：注释开始状态。：注释开始状态。3.3 有穷自动机有穷自动机12453otherq用于某些重要软件的设计和构造用于某些重要软件的设计和构造 设计和检查数字电路行为的软件设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它扫描如网页族等大规模文本以发现字、词或其它 结构的出现频率的软件结构的出现频率的软件;验证所有只有有限多个不同状态的系统的软件，验证所有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。这类系统包括通信协议和信息安全交换协议。有穷自动机的其它应用有穷自动机的其它应用3.3 3.3 有穷自动机有穷自动机用于某些重要软件的设计和构造有穷自动机的其它应用用于某些重要软件的设计和构造有穷自动机的其它应用3.3 有穷有穷已证明：非确定的有穷自动机与确定的有穷自动机从功能已证明：非确定的有穷自动机与确定的有穷自动机从功能 上来说是等价的，也就是说，我们能够从：上来说是等价的，也就是说，我们能够从：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的确定化的确定化已证明：非确定的有穷自动机与确定的有穷自动机从功能已证明：非确定的有穷自动机与确定的有穷自动机从功能NFA N 从从NFANFA的矩阵表示中可以看出，表项通常是一状态的集合，而的矩阵表示中可以看出，表项通常是一状态的集合，而在在DFADFA的矩阵表示中，表项是一个状态。的矩阵表示中，表项是一个状态。NFA NFA到相应的到相应的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 从从NFA的矩阵表示中可以看出，表项通常是一状态的集合的矩阵表示中可以看出，表项通常是一状态的集合(1)(1)合并合并如果有如果有 ，则把，则把S S2 2合并到合并到S S1 1S S1 1S S2 2转换需解决的问题：转换需解决的问题：ijkmaban（a）i,jmkaabn（b）3.3 3.3 有穷自动机有穷自动机(1)合并合并S1S2转换需解决的问题：转换需解决的问题：ijkmaban(2)(2)状态合并状态合并0123aabc（a）01,23abc（b）3.3 3.3 有穷自动机有穷自动机(2)状态合并状态合并0123aabc（a）01,23abc（b）定义定义1 1：状态集合：状态集合I I的的-闭包，表示为闭包，表示为-closure(I)-closure(I)若若qIqI，则，则qq-closure(I)-closure(I)；若若qIqI，则从，则从q q出发经过任意条出发经过任意条 弧而能到达的任何状态弧而能到达的任何状态 qq都属于都属于-closure(I)-closure(I)。为了使得为了使得NFANFA确定化，我们首先给出两个定义：确定化，我们首先给出两个定义：_ closure(I)IIS2S2S1S1S3S33.3 3.3 有穷自动机有穷自动机定义定义1：状态集合：状态集合I的的-闭包，表示为闭包，表示为-closure(I)例：例：如图所示的状态图：如图所示的状态图：令令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、6例：例：156432aaa根据定义：课堂练习：令根据定义：课堂练习：令I=1,2I I是状态集，由是状态集，由I I中的状态出发，经过一条中的状态出发，经过一条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是状态集，由是状态集，由I中的状态出发，经过一条中的状态出发，经过一条a弧可能到达的状态的集弧可能到达的状态的集例：令例：令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,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=1156432aaa课堂练习：令课堂练习：令I=1,课堂练习：课堂练习：令令I=1I=1，设，设S S=-closure=-closure（I I），），求：求：S S？SSa a=？1234abacac3.3 3.3 有穷自动机有穷自动机S S=-closure=-closure（I I）=1=1、44S Sa a=(2=(2、33课堂练习：令课堂练习：令I=1，设，设S=-closure（I），），1（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）（1）将从状态）将从状态S出发经过任意条出发经过任意条 弧所能到达的状态弧所能到达的状态NFA转转（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新状态新状态新状态新状态新状态新状态（1）构造一张表，它共有）构造一张表，它共有+1列；列；1234abacac将求得的状态转换矩阵重新编号，得到将求得的状态转换矩阵重新编号，得到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 c将求得的状态转换矩阵重新编号，得到将求得的状态转换矩阵重新编号，得到DFA M状态转换矩阵：状态转换矩阵：DFA M的状态图：的状态图：014231,42,342acabbc3,41234abacac3.3 3.3 有穷自动机有穷自动机注意：包含原初始状态注意：包含原初始状态1 1的状态子集为的状态子集为DFA MDFA M的初态的初态 包含原终止状态包含原终止状态4 4的状态子集为的状态子集为DFA MDFA M的终态。的终态。DFA M的状态图：的状态图：014231,42,34课堂练习课堂练习4f35621iaaaabbbbstart3.3 3.3 有穷自动机有穷自动机课堂练习课堂练习4f35621i aaaabbbbstart3等价的等价的DFADFAaCDBAEFSbaaaaabbbbbabFstart3.3 3.3 有穷自动机有穷自动机等价的等价的DFAaCDBAEFSbaaaaabbbbbabFst4.DFA的最小化的最小化l 如果不同的如果不同的DFADFA能识别相同的语言，则称它们是等价的能识别相同的语言，则称它们是等价的DFADFA；l 在等价的在等价的DFADFA中，如果某一个中，如果某一个DFADFA的状态数是最少的，则这个的状态数是最少的，则这个 DFA DFA是最简的；是最简的；l 对于任一个对于任一个DFADFA，存在一个唯一的状态最少的等价的，存在一个唯一的状态最少的等价的DFADFA。最简的最简的DFA 它没有多余它没有多余状态和等价状态状态和等价状态3.3 3.3 有穷自动机有穷自动机4.DFA的最小化的最小化 如果不同的如果不同的DFA能识别相同的语言，则称能识别相同的语言，则称定义定义1 1：多余状态：多余状态：从开始状态出发从开始状态出发,任何输入串也不能到达的状态。任何输入串也不能到达的状态。01s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例例:3.3 3.3 有穷自动机有穷自动机画状态图可看出画状态图可看出S4,S6,S8S4,S6,S8为不可达状态应该消除。为不可达状态应该消除。S0S1S2S3S4S5S6S7S801s0s1s2s3s5s7s1s5s7s2s2s5s5s7s1s3s0s1S0S1S2S3S5S7定义定义1：多余状态：从开始状态出发：多余状态：从开始状态出发,任何输入串也不能到达的状态任何输入串也不能到达的状态定义定义2 2：等价状态等价状态 状态状态s s和和t t的等价条件是的等价条件是:状态状态S和和T必须同时为终态或非终态；必须同时为终态或非终态；对于所有输入符号，对于所有输入符号，S和和T必须转换到等价的状态里。必须转换到等价的状态里。3.3 3.3 有穷自动机有穷自动机定义定义2：等价状态：等价状态 状态状态s和和t的等价条件是的等价条件是:状态状态S和和l 把把DFA的状态划分成一些不相交的子集；的状态划分成一些不相交的子集；l 任何不同的两个子集的状态都是可区分的；任何不同的两个子集的状态都是可区分的；l 同一子集中的任何两个状态都是等价的。同一子集中的任何两个状态都是等价的。DFADFA最小化算法的基本思想最小化算法的基本思想(没有多余状态没有多余状态)：3.3 3.3 有穷自动机有穷自动机（1）将所有状态分成两个子集：终态集和非终态集；）将所有状态分成两个子集：终态集和非终态集；（2）把等价的状态构成一个子集，若不等价继续划分；）把等价的状态构成一个子集，若不等价继续划分；（3）结束后，重新标号或从每个子集中选一个状态做代表。）结束后，重新标号或从每个子集中选一个状态做代表。把把DFA的状态划分成一些不相交的子集；的状态划分成一些不相交的子集；DFA最小化算法的基最小化算法的基解解:(一一)区分终态与非终态区分终态与非终态ab12345663731546737414212区号区号123123456637315467374142ab区号区号3.3 3.3 有穷自动机有穷自动机a ab b5724361a ab ba aa ab ba ab ba ab bb ba ab b解解:(一一)区分终态与非终态区分终态与非终态ab1234566373154671 12 23 34 45 56 66 63 37 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 b123456637315467374142ab1243区号区号1将区号代替状态号得将区号代替状态号得:12345ab521435523115 5243aaaaabbbbb化简后的有穷自动机具有较少的状态，实现起来更加简洁。化简后的有穷自动机具有较少的状态，实现起来更加简洁。3.3 3.3 有穷自动机有穷自动机将区号代替状态号得将区号代替状态号得:12345ab5214355231155