《编译原理第3章(2).ppt》由会员分享，可在线阅读，更多相关《编译原理第3章(2).ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 3.4.5 DFA的化简的化简 1.DFA的化简的化简 所谓一个所谓一个DFA M 的化简是指寻找的化简是指寻找一个状态数比一个状态数比 M 少的少的 DFA M，使得使得 L(M)=L(M)。(1)没有多余状态没有多余状态。化简了的化简了的DFA满足两个条件满足两个条件:(2)它的状态集中没有两个状态是它的状态集中没有两个状态是 互相等价的。互相等价的。所谓有穷自动机的所谓有穷自动机的多余状态多余状态是指从是指从该自动机的开始状态出发，任何输入串该自动机的开始状态出发，任何输入串也也不能不能到达的状态。到达的状态。3.4.5 DFA的化简的化简 2.多余状态多余状态3.等价状态等价状态 设
2、设 DFA M(Q,f,S0,F),s,t Q，若若对任何对任何 *,f(s,)F 当且仅当当且仅当f(t,)F，则称状态，则称状态 s 和和 t 是是等价的等价的。例如，例如，终态与非终态是可区别的终态与非终态是可区别的。因因为终态有一条到达自身的为终态有一条到达自身的道路，而非道路，而非终态没有到达终态的终态没有到达终态的道路道路。3.4.5 DFA的化简的化简 如果如果 s 和和 t 不等价不等价,则称则称 s 和和 t 是是可区可区别的别的。5.5.化简方法化简方法(1)(1)一致性条件一致性条件:状态状态s s和和t t必须同时为必须同时为 终态或非终态终态或非终态。4.4.两个状态
3、等价的条件两个状态等价的条件:(2)(2)蔓延性条件蔓延性条件:对于所有输入符号对于所有输入符号a,状态状态 s 和和 t 必须转到必须转到等价等价的状态里的状态里。输入：输入：一个一个DFA M。输出：输出：接受与接受与M相同语言的相同语言的DFA M，且其状态数最少且其状态数最少。3.4.5 DFA的化简的化简 无多余状态下把无多余状态下把M的状态集的状态集 Q 分划分划成一些不相交的子集，使得每个子集中成一些不相交的子集，使得每个子集中任何两个状态是等价的，而任何两个属任何两个状态是等价的，而任何两个属于不同子集的状态都是可区别的。于不同子集的状态都是可区别的。化简方法化简方法:然后在每
4、个子集中任取一个状态作然后在每个子集中任取一个状态作“代表代表”,而删去子集中其余状态而删去子集中其余状态,并把并把射向其余状态的箭弧都改作射向作射向其余状态的箭弧都改作射向作“代代表表”的状态中的状态中。3.4.5 DFA的化简的化简 下面给出化简算法的具体执行步骤下面给出化简算法的具体执行步骤:1.将将DFA M的状态集的状态集Q分成两个子集：分成两个子集：终终态集态集F和非终态集和非终态集F，形成初始分划形成初始分划。2.对对使用如下方法建立新分划使用如下方法建立新分划NEW：(1)把把G分划成新的子集，使得分划成新的子集，使得G的两个的两个状态状态s和和t属于同一子集属于同一子集，当且
5、仅当对，当且仅当对任何任何输入符号输入符号a，状态状态s和和t转换到的状态都属于转换到的状态都属于的的同一子集同一子集。对对的每个状态子集的每个状态子集G:3.4.5 DFA的化简的化简(2)用用G分划出的所有新子集分划出的所有新子集替换替换G,形形(3)成成新的分划新的分划NEW；3.如果如果NEW，则执行第则执行第4步；步；否则否则令令 NEW，重复第重复第2步。步。4.分划结束后，对分划中的每个状态子集，分划结束后，对分划中的每个状态子集，5.选出一个状态作选出一个状态作代表代表，而，而删去删去其它一切其它一切等价的状态，并把射向其它状态的箭弧改等价的状态，并把射向其它状态的箭弧改为射向
6、这个作为代表的状态为射向这个作为代表的状态。3.4.5 DFA的化简的化简 例例1.将右面的将右面的DFA最小化最小化 初始分划初始分划=(A,B,C,DE)A,B,C,Da=B分析分析 由图可知，给定由图可知，给定的的DFA中无多余状态。中无多余状态。A,B,C,Db=C,D,E=(A,B,CDE)A,B,Ca=BA,B,Cb=C,D=(A,CBDE)A,Ca=BA,Cb=C=(A,CBDE)ABCDEaaaaabbbbbEDBAaaaabbbb例例2.将右面的将右面的DFA M最小化最小化 1,2l=2=(1,20)分析分析 由图可知，由图可知，给定的给定的DFA无多无多余状态。余状态。初
7、始分划初始分划=(1,20)1,2d=2 02llldd1d01ll 3.4.5 DFA的化简的化简 3.4.6 有穷自动机到正规式的转换有穷自动机到正规式的转换 1.在在 M 的转换图上添加两个结点的转换图上添加两个结点：X 结和结和Y结结。从。从X结用结用连线连结到连线连结到M的的所有初态结点，从所有初态结点，从 M 的所有终态结点的所有终态结点用用连线连结到连线连结到 Y 结，从而构成一新的结，从而构成一新的非确定有穷自动机非确定有穷自动机 M，它只有一个初它只有一个初态结态结 X和一个终态结和一个终态结Y。显然，显然，L(M)=L(M)。即，这两个即，这两个NFA是等价是等价的。的。3
8、.4.6 有穷自动机到正规式的转换有穷自动机到正规式的转换 2.逐步逐步消去消去M中的其它结点中的其它结点，直直至只剩下至只剩下X，Y结点。结点。在消除结点过程在消除结点过程中，逐步用中，逐步用正规式正规式来标记相应的箭弧。来标记相应的箭弧。消除结点的过程是很直观的，只消除结点的过程是很直观的，只需反复使用下图的替换规则即可。需反复使用下图的替换规则即可。3.4.6 有穷自动机到正规式的转换有穷自动机到正规式的转换 对于对于代换为代换为ABr1r2ACBr1r2对于对于ABr1|r2代换为代换为代换为代换为ABr1r2*r3ABr1r2对于对于ACBr1r3r2 3.4.6 有穷自动机到正规式
9、的转换有穷自动机到正规式的转换 例例1.设有穷自动机的状态图如图所示。设有穷自动机的状态图如图所示。试求该自动机识别语言的正规式。试求该自动机识别语言的正规式。R=(10|01)(10|01)*3.5 正规文法与有穷自动机正规文法与有穷自动机 右线性正规文法到有穷自动机的转换方法右线性正规文法到有穷自动机的转换方法 则相应的有穷自穷自动机则相应的有穷自穷自动机 M=(Q,f,q0,Z)1.令令 Q=VND (D VN)Z=D =VT q0=S2.对对G中每一形如中每一形如 AaB(A,BVN,aVT)的产生式的产生式,令令 f(A,a)=B设给定了一个右线性正规文法设给定了一个右线性正规文法
10、G=(VN,VT,P,S)/a=AB令令f(A,)=B AaBAa3.5.1 右线性正规文法到有穷自动右线性正规文法到有穷自动 机的转换方法机的转换方法3.对对G中每一形如中每一形如Aa(AVN,aVT)的产生式的产生式,令令 f(A,a)=D4.对对G中每一形如中每一形如A(AVN)的产生的产生 式式,令令A为为接受状态接受状态或令或令 f(A,)=D例例1 构造下述文法构造下述文法GZ的有穷自动机的有穷自动机。其状态图如图其状态图如图(a)或或(b)所示。所示。显然显然,自动机自动机M是非确定是非确定的。它识别的语言就是文的。它识别的语言就是文法法GZ所描述的语言即所描述的语言即L(GZ)
11、=L(M)=0(0|01)*0。Z0AA0A|0BB1A|BAZ0010(a)AZ0010(b)DB3.5.2 左线性正规文法到有穷自动左线性正规文法到有穷自动 机的转换方法机的转换方法则相应的有穷自穷自动机则相应的有穷自穷自动机 M=(Q,f,q0,Z)1.令令 Q=VNq0 (q0 VN)Z=S =VT 2.对对G中每一形如中每一形如 ABa(A,BVN,aVT)的产生式的产生式,令令 f(B,a)=A设给定了一个左线性正规文法设给定了一个左线性正规文法 G=(VN,VT,P,S)/a=AB令令f(B,)=A ABaAa 3.5.2 左线性正规文法到有穷自动左线性正规文法到有穷自动 机的转
12、换方法机的转换方法3.对对G中每一形如中每一形如 Aa(AVN,aVT)的产生式的产生式,令令 f(q0,a)=A例例1.构造下述文法构造下述文法GA的自动机。的自动机。其状态图如下图所示。其状态图如下图所示。显然显然,该自动机是确定的。它识别的语言该自动机是确定的。它识别的语言就是文法就是文法GA所描述的语言。所描述的语言。即即 L(GA)=L(M)=00*11*BB0|0AA1|B1ABS0101 3.5.3 有穷自动机到正规文法的转换有穷自动机到正规文法的转换设给定有穷自动机设给定有穷自动机M=(Q,f,q0,Z)则相应的则相应的正规文法正规文法 G=(VN,VT,P,S)1.令令 VN
13、=Q VT=S=q0 2.若若f(A,a)=B 且且B 时，则将产生式时，则将产生式 AaB 加到加到P中。中。Z /3.若若f(A,a)=B 且且BZ时，则将产生式时，则将产生式 AaB|a 或将产生式或将产生式AaB、B 加到加到P中。中。3.5.3 有穷自动机到正规文法的转换有穷自动机到正规文法的转换4.若文法的开始符号S是一个终态，则 将产生式 S 加到P中。例1 设有穷自动机 M=(S,A,a,b,0,1,f,S,A)M的状态转换图如图所示。根据上述转换规则,与M等价的正规文法G为:其中P:或P:自动机M所识别的语言L(M)=L(G)=(a|b)(0|1|a|b)*。f(S,a)=A
14、 f(S,b)=Af(A,a)=A f(A,b)=Af(A,0)=A f(A,1)=A其中G=(S,A,a,b,0,1,P,S)SaA|bAAaA|bA|0A|1A|SaA|bA|a|bAaA|bA|0A|1A|a|b|0|1例2 设DFA M=(A,B,C,D,0,1,A,B)该自动机相应的状态转换图如下图所示。构造一个右线性文法G,使得L(G)=L(M)。(A,0)=B (A,1)=D(B,0)=D (B,1)=C(C,0)=B (C,1)=D(D,0)=D (D,1)=DBCA001D0110,1其中：从状态转换图可以看出,状态D是多余的,可以去掉,于是得到与M等价的DFA M的状态转换
15、图如图所示。3.5.3 有穷自动机到正规文法的转换有穷自动机到正规文法的转换BCA001BCA001D0110,13.5.3 3.5.3 有穷自动机到正规文法的转换有穷自动机到正规文法的转换G=(A,B,C,0,1,P,A)其中P为或 该自动机所识别的语言为 0(10)*。A0B|0B1CC0B|0根据转换规则所求右线性文法为A0BB1C|C0B BCA001 3.6 词法分析程序的编写方法词法分析程序的编写方法 构造词法分析程序的方法:第二种方法是利用词法分析程序的自动生成工具LEX自动生成词法分析程序，本书附录对LEX作了简单介绍。第一种方法是用手工方式，即根据识别语言单词的状态转换图，使
16、用某种高级语言，例如C语言直接编写词法分析程序。下面以某种简单语言为例，对第一种方法作简要的介绍。例如，下表列出了某个简单语言的所有单词符号，以及它们的种别编码和单词值。单词符号 种别编码单词值1234567101113141516171819212223内部字符串二进制数值表示beginendifthenelsewhiledo标识符整常数+-*/=:=;右图是一张识别前表的单词符号的状态转换图。图中,状态0为初态,凡带双圈者均为终态;状态17是识别不出单词符号的出错情况。l 代表任一字母，d 代表任一数字。根据这张转换图，我们用C语言直接编写出识别该语言所有单词的词法分析程序。3.6 词法分
17、析程序的编写方法词法分析程序的编写方法 在例中，我们规定所有关键字,用户不得使用它们作为自己定义的标识符，这样我们可以把关键字作为一类特殊的标识符来处理，不再专设对应的转换图。但需把它们预先安排在一个表格中，此表叫关键字表。当利用状态转换图识别出一个标识符时，就去查关键字表，以确定它是否是一个关键字。其次规定，若关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔，即此时的空白符是有意义的。根据状态转换图构造出词法分析程序最简单的办法是让每个状态对应一小段程序。1.ch 字符变量，存放当前读进的源程序字符。2.token 字符数组,存放构成单词符号的字符串。3.g
18、etch()读字符函数，每调用一次从输入缓冲区中读进源程序的下一个字符放在ch中，并把读字符指针指向下一个字符。4.getbc()函数，每次调用时，检查ch中的字符是否为空白字符，若是空白字符，则反复调用getbc()，直至ch中进入一个非空白字符为止。首先，我们引进词法分析程序所用的全局变量和需调用的函数如下：3.6 词法分析程序的编写方法词法分析程序的编写方法 6.letter(ch)和 degit(ch)布尔函数，它们分别判定 ch 中的字符是否为字母和数字，从而给出true 或 false。7.reserve()整型函数，对token中的字符串查关键字表，若它是一个关键字,则回送它的编
19、码，否则回送标识符的种别码10。5.concat()函数，每次调用把当前ch中的字符与token中的字符串联接。例如，假定token字符数组中原有值为“ab”,ch中存放着“c”,经调用concat()后，token数组中的值变为“abc”。3.6 词法分析程序的编写方法词法分析程序的编写方法 8.retract()函数，读字符指针回退一个字符。9.return()函数，收集并携带必要的信息返回调用程序，即返回语法分析程序。10.dtb()进制转换函数,它将token中的数字串转换成二进制数值表示,并以此作为函数值返回。根据该语言的状态转换图用C语言编写出词法分析程序如下:Scaner()to
20、ken=NULL;getch();getbc();if (letter(ch)while(letter(ch)|digit(ch)concat();getch();retract();c=reserve();if(c!=10)return(c,token);else return(10,token);相对于状态转换图用C语言编写出词法分析程序如下:else if(digit(ch)while(digit(ch)concat();getch();retract();return(11,dtb();else switch(ch)case+:return(13,);break;case-:retur
21、n(14,);break;case*:return(15,);break;case/:return(16,);break;case)return(18,);retract();return(19,);break;case:getch();if(ch=)return(22,);retract();return(21,);break;case;:return(23,);break;default:error();break;由此可知,只要构造出识别语言单词符号的有穷自动机,就很容易构造出识别语言单词符号的词法分析程序。3.6 词法分析程序的编写方法词法分析程序的编写方法 思考题 3.1 (1),(
22、3)3.3 3.5 3.11本章小结 本章重点介绍了词法分析程序的设计思想和构造方法。主要内容有：1.词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号。输出单词符号的形式是二元组:（单词种别，单词自身值）本章小结 例如定义“标识符”单词的正规式是 l(l|d)*正规文法是 标识符 l|标识符l|标识符d2程序语言单词符号的两种定义方式 正规文法正规式本章小结 3有穷自动机有确定的和非确定两大类：NFA N=(Q,f,S,Z)其中f是多值映射函数，S为非空初态集。有穷自动机通常表示为状态转换图，它是有穷自动机的非形式化描述。DFA M=(Q,f,S,Z)其中是f
23、单值映射函数，S是唯一初态本章小结 从单词两种定义方式中构造词法分析程序的过程是：正规式正规文法NFA分裂法转换规则子集法DFA分化法状态最小化DFA词法分析程序4正规式、正规文法和有穷自动机三者都是描述正规集的工具,它们的描述能力是等价的，它们之间可相互转换。5证明两正规式是等价的,如果它们的最小状态DFA是相同的。也可以利用正规式的基本等价关系将一个正规式化简来证明两正规式之间的等价性或两正规式识别的语言一样。本章小结 本章小结 例1 构造正规式R=1(0|1)*101的状态最小化的DFA 分析 首先对R采用分裂法构造NFA，见下图:Y54321X111010 对NFA采用子集法构造其等价
24、的DFA的状态转换矩阵,见右表 ABFCDE字符状态01X1,2,32,3,42,3,52,3,4,Y2,32,31,2,32,3,42,32,3,42,3,52,3,42,32,3,4,Y2,3,52,3,4Y54321X111010本章小结 对DFA采用分化的方法化简，得到状态最小化的DFA，见下图:ABCDE字符状态01X1,2,32,3,42,3,52,3,4,Y2,32,31,2,32,3,42,32,3,42,3,52,3,42,32,3,4,Y2,3,52,3,4EDCBA110100110例2.构造一个DFA它接收=0,1上所有满足如下条件的字符串，每个1都有0直接跟在右边。分
25、析 首先给出描述语言的正规式R=(0|10)*采用分裂法从正规式构造NFAYAXB010 采用子集法将NFA确定化为DFA 采用分化方法将DFA化简字符状态01X,A,YBA,YA,YBBA,YA,YXB010YAXB010分析 给出描述语言的正规文法S0S|1A|A 0S根据右线性文法构造有穷自动机的方法,构造出如下的状态转换图:SA010例2.构造一个DFA它接收=0,1上所有满足如下条件的字符串，每个1都有0直接跟在右边。S0A|1B A1S|1 B0S|0 分析 根据正规文法转换成正规式的方法，首先给出该 正规文法对应的正规式方程组：S=0A+1B(1)A=1S+1 (2)B=0S+0
26、 (3)将(2)、(3)代入(1)得 S=01S+01+10S+10 (4)对(4)使用求解规则得 S=(01+10)(01+10)即正规文法所生成语言的正规式是(01|10)(01|10)。例3.给出下述文法所对应的正规式：例4 将右图确定化和最小化。图示是一个无 边转移的NFA,采用子集法将NFA确定化为DFA采用分化方法将DFA化简本章小结 字符状态ab010,10,1110,1001aba01a,baa本章小结 例4.设字母表=a,b，给出上的正规式 R=b*ab(b|ab)*1.试构造状态最小化的DFA M，使得L(M)=L(R)。2.求右线性文法G，使L(G)=L(M)。本章小结 对正规式R=b*ab(b|ab)*采用分列法构造NFA，见下图。Y5432abb1Xb6ab对NFA采用子集法构造其等价的DFA的状态转换矩阵，见表。XBAYEF字符状态abX,1,21,24,5,Y65,Y3331,21,24,5,Y65,Y5,Y65,YY5432abb1Xb6ab本章小结 对 DFA采 用分化的方法得到状态最小化的DFA，见图。X AY字符状态abX,1,21,24,5,Y65,Y3331,21,24,5,Y65,Y5,Y65,YYAXbabab