《编译原理》课程简介 (16).pdf
编译原理 C O M P I L A T I O N P RIN C IP LE第三章 词法分析3.3 正规式与有限自动机3.3 正规式与有限自动机一、基本概念二、确定有穷状态自动机（DFA）三、非确定有穷状态自动机（NFA）四、正规式和有限自动机的等价性五、DFA的化简3.3 正规式与有限自动机n一个确定有限自动机M的化简是指：寻找一个状态数比M少的DFA M，使得L(M)=L(M)n假定s和t是M的两个不同状态，我们称s和t是等价的：如果从状态s出发能读出某个字w而停于终态，那么同样，从t出发也能读出同样的字w而停于终态；反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出同样的w而停于终态。n可区别的：如果DFA M的两个状态s和t不等价。五、DFA的化简相关概念3.3 正规式与有限自动机n字符串W把状态s和状态t区别开：n等价状态：无法区别开的两个状态n基本思想：把状态集划分成互不相交的子集，使子集中的状态是等价的n化简DFA的算法步骤：u划分状态集u合并状态:取每组状态中的代表状态，删去其他等价状态u若有死状态或不可达状态，则把它们删去。死状态：无法达到终止状态的非终止状态不可达状态：不能从开始状态达到它的那些状态五、DFA的化简3.3 正规式与有限自动机n对M的状态集S进行分划的步骤是：首先，把S的终态和非终态分开，分成两个子集，形成基本分划II。显然，属于这两个不同子集的状态是可区别的。假定到某个时候II已含m个子集，记II=I(1),I(2),I(m)，并且属于不同子集的状态是可区别的。检查 II 中的每个I(i)看能否进一步分划。对于某个I(i),令I(i)=q1,q2,qk，若存在一个输入字符a使得I(i)a不全包含在现行II的某一子集I(i)中，就将I(i)一分为二。例如，假定状态s1和s2经a弧分别达到状态t1和t2，而t1和t2属于现行 II 的两个不同子集，那就将I(i)分成两半，使得一半含有s1：I(i1)=s|s I(i)且s经a弧到达t1所在子集中的某状态n另一半含有s2：I(i2)=I(i)-I(i1)由于t1和t2是可区别的，即存在一个字w。t1将读出w而停于终态，而t2或读不出w或虽然可以读出w但不到达终态；或情形恰好相反。因而字aw将状态s1和s2区别开来。也就是说，I(i1)中的状态与I(i2)中的状态是可区别的。至此我们将I(i)分成两半形成了新的分划。3.3 正规式与有限自动机n一般地，若I(i)a落入现行II中N个不同子集，则应将I(i)划分为N个不相交的组，使得每个组J的Ja都落入II的同一个子集，这样形成新的分划。重复上述过程，直至分划中所含的子集数不再增长为止。至此，II中的每个子集已不可再分。也就是说，每个子集中的状态是互相等价的，而不同子集中的状态则是可互相区别的。n经过上述过程后，得到一个最后分划II。对于这个II中的每一个子集，我们选取子集中的一个状态代表其他状态。例如，假定I=q1,qk是这样一个子集，我们即可挑选q1代表这个子集。在原来的自动机中，凡导入到q2,qk的弧都改成导入到q1.然后，将q2,qk从原来的状态集S中删除。若I中含有原来的初态，则q1是新初态；若I中含有原来的终态，则q1是新终态。可以证明，经如此化简之后得到的DFA M和原来的M是等价的。若从M中删除所有无用状态，则M便是最简的（包含最少状态）。3.3 正规式与有限自动机举 例n划分状态集为4和 0,1,2,3n对于0,1,2,3和输入字符a和b:M(0,a)=1 M(1,a)=1M(2,a)=1 M(3,a)=1M(0,b)=2 M(1,b)=3M(2,b)=2 M(3,b)=4只有状态3在输入为b时映像的后继状态不在0,1,2,3中，因此该状态集划分为3和0,1,2n对于0,1,2:状态1在输入为b时的后继状态不在0,1,2中，因此划分为1和0,202314bbbbbaaaaau对于0,2:对于相同输入字符，该子集中每一状态映像得到的后继状态都相同，因此不再可划分u最后划分为：4 3 1 0,2 3.3 正规式与有限自动机举 例（续1）n对于划分结果4,3,1,0,2，把0,2合并为一个状态，其状态转换图如图：02314bbbbbaaaaa0213aaaabbbb3.3 正规式与有限自动机课堂教学实例第三章 词法分析教会学生如何设计出一个高级语言的词法分析器目的是设计一个功能等价的DFA，每个节点一段程序方法是设计DFA，DFA化简，程序实现过程是如何设计出DFA？是否唯一？简化后是否一样？困惑是书上算法是否完备？自己能否完善之？挑战是3.3 正规式与有限自动机设计一个DFA M，它识别二进制偶数（不以0开头的无符号数）知识点讲解示范：DFA的设计例v解1写出正规式 1（1|0）*0 3.确定化为DFA M2画出NFA M 细化为：1y1（1|0）*01Xy1001NAMENAMEI I0 0I I1 1A11,Y1,Y1,Y1113.3 正规式与有限自动机v或细化为：同学们重新做v结果：102101102X10113y03121011001 I II I0 0I I1 10X1，2,32,3,Y2,32,3,Y2,3,Y2,3,Y1，2,32,32,32,31323.3 正规式与有限自动机n根据前面学习的DFA的词法分析程序实现，方法是每个节点对应一段程序。n对于图2，显然节点个数多余图1，也就是说需要辨析的子程序个数多。n化简就是优化，寻找等价的DFA，但节点个数少。n根据书上的算法，可以考虑如下：p初始分划为非终态集和终态集：0，1，3，2p考虑 0，1，3读入0为2；0，1，3读入1为1，3p全部落在上述分划的某一个子集，根据书上算法，不需要再分。n所以简化为2个节点，图3：讲解示范2：DFA的化简10210110021003.3 正规式与有限自动机n没有问题，两个都正确，那必然两个相等自然导出 DFA化简与等价 两个结果不一样，问题出在哪？课后思考n根据书上化简算法，发现问题,让学生回家思考如何解决，下次课程随机回答v下一堂课内容
