词法分析程序的设计词法分析程序的设计词法分析程序的设计词法分析程序的设计第4章词法分析单词符号的两种定义方式正规式和正规集正规式和正规集正规式和正规集正规式和正规集正规式和正规集5.ba*是正规式，相应的正规集为正规式和正规集正规式和正规集正规式和正规集正规式和正规集正规式和正规集正规文法与正规式正规文法与正规式正规文法与正规式正规文法与正规式正规文法与正规式正规文法与正规式正规文法与正规式第4章词法分析有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合.应用有穷自动机这个理论，为词法分析程序的自动构造寻找有效的方法和工具。有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata)不确定的有穷自动机(NondeterministicFiniteAutomata)关于有穷自动机我们将讨论如下题目确定的有穷自动机DFADFA定义一个DFA的例子：DFA的状态图表示DFA的矩阵表示∑*上的符号串t被DFAM接受DFA的行为很容易用程序来模拟.DFAM=（K，Σ，f，S，Z）的行为的模拟程序K:=S；c:=getchar;whilec<>eofdo{K:=f(K,c);c:=getchar;};ifKisinZthenreturn(‘yes’)elsereturn(‘no’)DFAå={digit,notdigit}不确定的有穷自动机NFA矩阵表示具有转移的不确定的有穷自动机有如下定理:类似DFA,对NFAM=K，，f，S，Z也有如下定义例中NFAM',对符号串β=bbb可由3条路来识别。(0|1)*(000|111)(0|1)*确定有限自动机和不确定有限自动机定义对状态集合I的几个有关运算：NFA确定化算法:状态集合I的有关运算的例子NFA的确定化等价的DFA例构造NFA的DFANFA状态图：2、标记S1：ε-closure({move(S1,a）})={1,2,3,4,6,7,8}=S22、标记S1：ε-closure({move(S1,b）})={1,2,4,5,6,7}=S33、标记S2：ε-closure({move(S2,a)})={1,2,3,4,6,7,8}=S23、标记S2：ε-closure({move(S2,b)})={1,2,4,5,6,7,9}=S44、标记S3：ε-closure({move(S3,a)})={1,2,3,4,6,7,8}=S24、标记S3：ε-closure({move(S3,b)})={1,2,4,5,6,7}=S35、标记S4：ε-closure({move(S4,a)})={1,2,3,4,6,7,8}=S25、标记S4：ε-closure({move(S4,b)})={1,2,4,5,6,7,10}=S56、标记S5：ε-closure({move(S5,a)})={1,2,3,4,6,7,8}=S26、标记S5：ε-closure({move(S5,b)})={1,2,4,5,6,7}=S3ε-closure({0})={0,1,2,4,7}*S1ε-closure(move(S1,a))={3,8,6,7,1,2,4}*S2ε-closure(move(S1,b))={5,6,7,1,2,4}*S3ε-closure(move(S2,a))={3,8,6,7,1,2,4}S2ε-closure(move(S2,b))={5,9,6,7,1,2,4}*S4ε-closure(move(S3,a))={3,8,6,7,1,2,4}S2ε-closure(move(S3,b))={5,6,7,1,2,4}S3ε-closure(move(S4,a))={3,8,6,7,1,2,4}S2ε-closure(move(S4,b))={5,10,6,7,1,2,4}*S5ε-closure(move(S5,a))={3,8,6,7,1,2,4}S2ε-closure(move(S5,b))={5,6,7,1,2,4}S3上节内容回顾DFA的化简DFA的化简DFA的化简DFA的化简DFA的化简{3,第4章词法分析正规文法（式）与自动机的等价性正规文法（式）与自动机的等价性NFA到正规表达式NFA到正规表达式0解：加x,y结点。0正规文法（式）与自动机的等价性正规表达式到NFA正规式，构造NFA为：对应正规式，构造NFA为：对应正规式a，构造NFA为：s,t是正规式，相应NFA为N(s),N(t)，则正规式R=s|t，构造NFA(R)为：例1：L(R)=(a|b)*abb，构造NFA使L(N