编译原理电子教案第三章

第三章有穷自动机,本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。,3.1概述,有穷状态自动机(Finite-stateAutomata或简称FSA)在识别功能上与正规文法类等价，而且也等价于一个特殊类型的语言产生器正规表达式(RegularExpression)。因此许多简单的程序语言都可由FSA所识别。事实上，它是描述词法的有效工具，也是进行词法分析的主要理论基础。有穷状态自动机在计算机系统中的价值是很明显的，它提供了一种逻辑地探测方式，去探测一些输入串是否属于某种语言，也就是说，它可以作为一种语法检查器(SyntaxChecker)。,3.2有穷自动机的形式定义,定义3.1一个确定有穷自动机DFSA是一个五元组M=(Q,t,q0,F)其中，Q是非空有穷状态集,其中的每个元素称为一个状态；是有穷输入字母表，它的每一个元素称为一个输入符号；t是一个单值映射QQ，也称状态转换函数，t(q,x)=q意指：当现行状态为q，面临的输入符号为x时，将转到下一状态q，q称为q的一个后继状态；q0Q称之为开始状态；FQ称为终止状态集，至少由一个终止状态组成。,3.2.1状态转换表,例3.1有穷自动机A=(Q,t,q0,F)其中，Q=S,A,B,G,H，=+，-，d，S是开始状态，终止状态集F=B,H，映射t:QQ由下表所示的状态转换表给出。,3.2.2状态转换图,例3.2有穷自动机A(记为DFSAA)，A=(Q,t,q0,F)其中，Q=q0,q1,q2,q3，=a,b，q0是开始状态，终止状态集F=q0，映射t:QQ由下图所示的状态转换图给出。在图中，状态q0用双圆圈标记，表明它是终止状态；同时，用一个箭头标记，表明它是开始状态。,3.2.3构形和移动,构形(q0，)称为初始构形，其中q0是初始状态，是由该自动机可接收或拒绝的任何输入串。构形(q,)称为终止构形，其中是空串，qF(终态集)。自动机的移动(记为)是从一种构形到另一种构形的转换。记号+称为的传递闭包；*称为的自反闭包。*表示“0次或多次移动”；+表示“一次或多次移动”。,3.2.4自动机的等价性,定义3.2M和M是等价的，当且仅当对每一个串x，M接收x当且仅当M接收x。定义3.3如果M仅通过重新标记它的状态就能转换称M,则M和M称为同构的(Isomorphic)。FSA的一个基本定理是：对每一个自动机M，存在一个等价的具有最少状态个数的自动机M，而且对于每一个其状态个数与M相同且等价于M的自动机M,必是与M同构的。换句话说，M在结构上是唯一的。,3.2.5非有穷状态自动机,定义3.4一个非确定有穷自动机NDFSA是一个五元组NDFSA=(Q,t,q0,F)其中，Q是一个非空有穷状态集，是一个非空有穷输入字母集，映射t为QQ的子集(即t是一个多值映射)，Q0Q是开始状态集，FQ是终止状态集。同样的，NDFSA也可以用状态转换表和状态转换图表示。,3.2.5非有穷状态自动机,非确定有穷自动机与确定有穷自动机的主要区别有三：1NDFSA有一个开始状态集，而DFSA只有一个开始状态。2NDFSA的映射是QQ的子集，是一个多值映射，而DFSA的映射是QQ，是一个单值映射。3NDFSA在没有扫描任何输入符号的情况下，也可以进行移动，这种移动称为空移。我们用表示法：t(q,)=某些状态的集合将这种情况包括在状态转换函数中。注意，甚至当输入串已经完全扫描完之后还可能需要空移。,3.3NDFSA到DFSA的转换,通过下述步骤可将一个NDFSA转换称等价的DFSA：寻找并消除空移环路；消除余下的空移；确定化。,3.3.1空移环路的寻找和消除,例图(a)所示的是一个NDFSA，结点q0是开始状态，q3是终止状态，结点q0、q1与q4形成一个空移环路。要消除这个空移环路，只需将3个结点q0、q1与q4合并成一个结点，以q0标记，并消除原来3个结点之间所有的环。由于这3个结点中的q0是开始状态，因此，合并之后的新结点q0被设置为开始状态，如图(b)所示。,3.3.2消除空移,下面给出一个消除空移的算法。给定从状态A到B的一个空移(即从状态A到B经由连线的一个转换，换言之，t(A,)=，B，)。置t(A,)=，对每个a和q，如果qt(B,a)，则将q加到t(A,a)。如果A是开始状态，则将B也加入开始状态集。如果B是终止状态，则将A也加入终止状态集。,3.3.3利用状态转换表消除空移,利用FSA的状态转换表，可以很容易地消除空移。这种方法地基本步骤示：首先，找出直接经由一个空移到达某个终态地所有状态。每当找到这样一个状态，便将它标记终态。然后，考虑消除与未被标记为终态的那些状态相关的空移。对表中每一个具有射出连线的状态继续按上述方式处理，直到状态转换表不再变动为止。最后从表中删除列和没有任何元素的空行便得到一个不含空移的状态转换表。,3.3.4确定化子集法,设NDFSAM=(Q,t,Q0,F)是一个非确定有穷自动机，它的语言（即它能接受的符号串集合）记为L(A)。那么，一定可以构造一个和它等价的确定有穷自动机DFSAM=(Q,t,q0,F)，使L(A)=L(A)。构造如下：M的状态集Q是由M的状态集Q的所有子集组成的。用p1,p2,pi表示Q的元素，其中p1,p2,pi是Q中的状态。以后，我们总假定状态p1,p2,pi是按某种规范顺序排列的。例如，对于子集p1p2=p2，p1，Q的状态是p1,p2。若p是M的一个终态，则M中每一个包含p的状态，p，都是M的一个终态。,3.3.4确定化子集法,若S=S1,S2,Sj是M的初态，则S=S1,S2,Sj是M的初态。令p1,p2,pn是M中的一个状态，其中p1,p2,pn是M中的一个状态。对某个输入符号a，考虑M中的转换函数：t(p1,a),t(p2,a),，t(pn,a)根据这些转换函数，我们可按如下方法构造M中的转换函数t：(a)令t(p1,a)t(p2,a)t(pn,a)=Q1,Q2,Qr。也就是将状态p1,p2,pn分别面临输入符号a时所确定出的状态统统汇集起来并取名为Q1,Q2,Qr。(b)置t(p1,p2,pn,a)=Q1,Q2,Qr。注意，这是一个确定的转换函数。即M中的状态p1,p2,pn面临输入符号a时恰好确定出下一状态Q1,Q2,Qr。对M每一状态和每个输入符号a，重复步骤4。这个算法总是可以终止的。因为虽然M中含有许多可能的状态子集，但其不同子集的最大个数是有穷的。事实上，若M有a个状态，则M中最大可能的状态个数是(-1)。,3.3.5确定化造表法,造表法是比子集法简单而有效的一种确定化方法。定义3.5设NDFSAM=(Q,t,Q0,F)，假定I是M中状态集的一个子集，定义-closure(I)如下：若qI，则qclosure(I);若q-closure(I)，q是由q出发经多条弧所到达的状态，则q-closure(I)。定义3.6假定I是NDFSAM中状态集的一个子集，a，定义=-closure(J)其中J是所有那些可从子集I中的任一状态出发，经过一条a连线(跳过a连线前的连线)而到达的状态(结)的全体。,3.3.5确定化造表法,造表法的具体步骤：假定给定的NDFSAM中仅含两个符号a，b。可用如下方法将M确定化：采用造表的方式，该表的每一行有三列(若中含有n个符号，则该表有n+1列)，第一列记为I，第二、三列分别记为Ia,Ib。置该表的第一行第一列为-closure(Q0)，即一列包含M初态集Q0的-闭包。然后计算它的Ia和Ib,分别填入第二、三列上，一般，若某一行的第一列上的I已确定，便可根据前述定义求出这一行的第二、第三列上的Ia和Ib。检查Ia和Ib，看它们是否已在表的第一列中出现，把未曾出现者之一填入下一空行的第一列上，再计算该行的第二、第三列上的Ia和Ib。,3.3.5确定化造表法,重复第二步，直至表中所有第二、第三列上的元素全部再第一列出现为止。因为M中的状态(子集)的个数是有限的，所以上述三步必定在有限步内终止。将由上述过程得到的最终形式的表看作一个状态转换表，即把其中第一列中的元素作为状态，把Ia,Ib分别看作是输入符号a，b，把其余信息看作是状态转换函数之值。这个表唯一地刻画了一个确定的有穷状态自动机M，其初态是该表第一行第一列的元素，其终态是该表中所有那些含有原终态的元素。可以证明，这个DFSAM和NDFSAM是等价的。,3.3.6消除不可达状态,在自动机中，从开始状态没有任何一条路径能达到的状态称为不可达状态。由于不可达状态事实上是无用的，因此可以删除它们。下面给出识别可达状态的算法。当该算法终止时，每一个未标记的状态就是不可达状态。识别DFSA中可达状态的算法。标记开始状态S；给定任意标记过的状态P，如果对某个输入符号存在从状态P到Q的转换，则标记每一个这样的状态Q；重复步骤，直到不再有可标记的状态为止。,3.3.7确定的有穷自动机的化简,所谓确定有穷自动机M的化简是指：寻找一个状态数必M少的确定的有穷自动机M，使得L(M)=L(M)。定义3.7假定q1和q2是M中的两个不同状态，称q1和q2是等价的：如果从状态q1出发能扫描任意串w而停止于终态，那么从状态q2出发也能扫描同一个串w而停止于终态；反之，亦然。定义3.8如果两个状态q1和q2不等价，则称这两个状态是可区分的。,3.3.7确定的有穷自动机的化简,DFSAM的化简算法。给定DFSAM=(Q,t,q0,F)，化简M的算法如下：将Q划分为二组：F（终态组）和Q-F（非终态组），以构成初始分划0；给定k，用下述方法构造新的分划k+1:fork中的每一子组Gidobegin2-1)试图对Gi进行分划，使得状态s，t并入Gi的同一子组中iffa，有t(s,a)和t(t,a)都落入k的同一子组中；否则，必须对Gi进行分划，使得分划后的某个子组包含s，另一子组包含t；2-2)将经上述分划后的子组并入k+1end；,3.3.7确定的有穷自动机的化简,若k+1k，则用k+1“替代”k，重复；否则，分划过程终止，转；得到化简后的DFSAM，其中Q的状态数即最终分划i的子组个数，取i中每个子组中的一个状态代表该子组构成Q。注意，此时，i中的每个子组是不相交的，且任何不同两个子组中的状态都是可区分的，而同一子组中的任何状态都是等价的。q0即i中含q0的子组；F即包含F中任一状态的所有子组；=；t即i中子组到子组之间的变换(可能会合并一些连线)；去掉不可达状态和无用状态，便得到最终化简后的DFSAM。,3.3.7确定的有穷自动机的化简,一个DFSAM的状态化简过程就是把M的状态集分划成一些不相交的子集，使得任何不同的两子集的状态都是可区分的，而同一子集的任何两个状态都是等价的。最后，从每个子集选出一个代表(代表该子集)，同时消去其它等价状态。,3.3.8从化简后的DFSA到程序表示,识别标识符的DFSA1（见图(a)）需改为图(b)所示状态，其中，l代表字母，d代表数字。图（a）图（b）如果赋予状态q0、q1与q2一定的操作，则可得识别单词标识符的程序流程图(见下图)。,3.4正规文法与有穷自动机,正规文法与有穷自动机FA有着特殊的关系。可以证明：对任何正规文法G，可以构造一个FSA，它能而且只能识别语言L(G);反过来，对任何FSA，可以构造一个相应的正规文法G，它能生成由该FSA所识别的语言。,3.4.1从正规文法到FSA,设正规文法G有形如UaV(aVT,VVN或V=)的产生式。由正规文法G可以直接构造一个有穷自动机A(简称自动机A)，使L(A)=L(G)。构造步骤如下：令正规文法G的终结符号集作为有穷自动机A的字母表；文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符作为自动机A的开始状态；在自动机A中增加一个新状态z作为自动机的终止状态；对于文法G的形如UaV(aVT或a=,VVN)的产生式，在自动机A中构造形如t(U,a)=V的映射；对于文法G的形如Ua(aVT)的产生式，在自动机A中构造形如t(U,a)=z的映射。,3.4.2从FA到正规文法,从正规文法可直接构造其自动机，反之，由自动机也可直接构造其正规文法。构造步骤如下：自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记将作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。对于自动机的映射t(U,a)=V（其中，U、V为自动机的状态标记；a为输入符号），构造文法的一条产生式UaVU、V为文法的非终结符，a为终结符。对于自动机的终止状态Z，在正规文法中增加一条产生式Z,3.5正规表达式与FA,3.5.1正规表达式的定义3.5.2正规表达式的CFG3.5.3正规表达式与FSA的对应性3.5.4正规表达式到NDFSA的转换3.5.5NDFSAM到正规表达式的转换3.5.6从正规文法到正规表达式,3.5.1正规表达式的定义,正规语言是正规集。正规表达式是用于描述称之为正规集的语言类的一种表示形式。以下是正规表达式的一些相关定义。,3.5.1正规表达式的定义,定义3.9字母表上的正规表达式和正规集递归定义如下：a，a是上的一个正规表达式，它所表示的正规集为a。空串是上的一个正规表达式，它所表示的正规集为。空集是上的一个正规表达式，它所表示的正规集为。设e1与e2都是上的正规表达式，它们所表示的正规集分别为L(e1)与L(e2)，则i)e1e2也是正规表达式，它所表示的正规集为L(e1e2)=L(e1)L(e2)；ii)e1e2也是正规表达式，它所表示的正规集为L(e1e2)=L(e1)L(e2)；iii)(e1)*也是正规表达式，它所表示的正规表达式为L(e1)*)=(L(e1)*。,3.5.1正规表达式的定义,定义3.10设e1与e2是上的两个正规表达式，若L(e1)=L(e2)，则称e1与e2等价，记为e1=e2，如a(ba)*=(ba)*a,3.5.1正规表达式的定义,定理3.1设e1、e2和e3都是上的正规表达式，则e1e2=e2e1(交换律)(e1e2)e3=e1(e2e3),(e1e2)e3=e1(e2e3)（结合律）e1(e2e3)=e1e2e1e3,(e1e2)e3=e1e3e2e3（分配律）e1=e1=e1()*=(空集的闭包是空串)e1=e1=e1*=e1|e1*(e1*)*=e1*e1|=e1,3.5.2正规表达式的CFG,正规表达式是由下面的CFGGR=（N,P,R）描述的。其中，N=R，C，L=|,(,),*,a,产生式集合P为：RR|C(选择)RCCCL(连结)CLL(R)(括号)LR*(闭包)La(正规语言中的任何符号)L(空串)该文法描述了操作符：连结，选择和闭包的优先级以及形成正规表达式的结构规则。,3.5.3正规表达式与FSA的对应性,正规表达式和FSA是定义语言（符号串集）的两种不同形式。同一个语言，既可用FSA描述，也可用正规表达式描述。,3.5.4正规表达式到NDFSA的转换,对于字母表上任意一个正规表达式e，一定可以构造一个NDFSAM，使L(M)=L(e)。先构造一个NDFSAM的一个广义转换图，其中，只有S与Z两个状态，S是开始状态，Z是终止状态，弧上是正规表达式e。然后，按照下图所示的替换规则对正规表达式e逐步进行分解，直到转换图中所有的弧上都是中的单个符号或为止。,3.5.4正规表达式到NDFSA的转换,（1）替换成（2）替换成（3）替换成,3.5.5NDFSAM到正规表达式的转换,对于一个具有输入字母表的NDFSAM，在上也可以构造一个正规表达式e，使L(e)=L(M)。具体操作如下：首先，对NDFSAM进行拓广，在M的状态转换图中，新设置一个唯一的开始状态S和唯一的终止状态Z，并允许状态转换图中弧上可以为正规表达式。然后，从开始状态S到原来所有的开始状态连接弧，再从原来所有的终止状态到Z状态也连接弧。修改后,构成了一个新的NDFSA，它只有一个初态结点S和一个终态结点Z，这个新的NDFSAM显然和原NDFSAM等价。接着，利用下图所示的替换规则，逐步消去M中属于M的所有结点和有关连线，直到状态转换图中只剩下状态S和Z为止(这个过程称为消结)。在消结过程中，用相应的正规表达式标记连线。,3.5.5NDFSAM到正规表达式的转换,（1）替换成（2）替换成（3）替换成,3.5.6从正规文法到正规表达式,本节介绍两种转换方法：首先，正规文法中的每个非终结符都可以表示成关于它的一个正规表达式方程。把一正规文法中所有这样一些方程写在一起便构成该正规文法的一个联立正规表达式方程组。以下例介绍这种转换方法：例现有正规文法G22S:S0A|1B|0|1A0S|1B|1B0A|1S可以写成如下关于变量S，A，B的一个正规表达式方程组：S=(0+1)+0A+1B（1）A=1+0S+1B(2)B=1S+0A(3),3.5.6从正规文法到正规表达式,解上方程组得：S=(0+10)(10)*(0+11)+11