编译原理第3章.词法分析.ppt

资源描述

《编译原理第3章.词法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理第3章.词法分析.ppt（93页珍藏版）》请在三一办公上搜索。

1、第三章词法分析,2023/9/18,2,回忆：词法分析程序的功能：对构成源程序的字符串从左到右进行扫描和分解，并根据语言的词法规则识别出一个个具有独立意义的单词符号。具体：设计成单独一遍扫描。设计成子程序，当语法分析器需要新单词时调用它。,第三章.词法分析3.0 词法分析程序的功能,源程序,词法分析,单词符号序列,语法分析,源程序,词法分析子程序,语法分析,取单词,2023/9/18,3,3.1 词法分析程序的输入输出,一.输入：字符串表示的源程序二.输出：单词符号或单词符号表示的源程序1.语言的单词符号：是指语言中具有独立意义的最小语法单位。共分五类：保留字、标识符、常数、运算符、和界符2

2、.单词符号的内部表示：二元组（单词种别码，单词自身值）继续,2023/9/18,4,单词种别码,保留字：一字一种：1begin 2end 3if 4then全体为一种：0 或者 k标识符：全体为一种常数：数据类型：整型、实型、字符型、布尔型全体为一种运算符：一符一种全体为一种界符：一符一种全体为一种返回,2023/9/18,5,单词自身值,如果一个种别码对应一个单词符号，则种别码可以代表单词自身。如果一个种别码对应多个单词符号，则单词自身值是单词符号的机内码。,机内码：标识符：自身串（ASCII码）常数：二进制值、逻辑值,If a 1 then b=100,词法分析器,（3，）（6，a）（1

3、2，）（7，1的二进制）（4，）（6，b）（10，）（7，100的二进制）,2023/9/18,6,用相应符号表项的指针值来区分同类中不同的单词符号。K表：I表：C表：,if a 1 then b=100,词法分析器,（k，3）（I，1）（P，18）（C，1）（K，4）（I，2）（P，10）（C，2）,返回,2023/9/18,7,3.2 词法分析程序的设计一.输入、预处理,输入缓冲区,预处理子程序,扫描缓冲区,源程序,词法分析的预处理程序：从源程序中处理出一串确定长度的输入字符，并将其装进词法分析程序的扫描缓冲区。处理：删除注解、空格、回车符、换行符之类非必要信息。把标识符登录入符号表以及某

4、些预加工处理等。,扫描缓冲区的设计：两个指针：起点指针,搜索指针两个半区：左右半区互补使用,起点指针,搜索指针,2023/9/18,8,二.单词符号的识别以及超前搜索,词法分析程序在识别单词时,对有些单词需要向源程序中多看若干个字符才能被识别,称为超前搜索。1.关键字的识别:有些语言中关键字的识别需要超前搜索。例如:FORTRAN语言中:1DO99K=1,102DO99K=1.102.标识符的识别:以运算符、界符、空格等结束。3.常数的识别:需要超前搜索。例如:5.EQ.M 和 5.E08。4.运算符和界符的识别:需要超前搜索。例如:=,2023/9/18,9,状态转换图:是由一组矢线连接的有

5、限个结点所组成的有向图。其作用是识别相应的字符串。例如:标识符:I l|I l|I d 初态=终态例如:数字|数字=,三.状态转换图,l,非 l,非 d,l/d,d,非d,d,2023/9/18,10,利用状态转换图识别(或接受)字符串的过程:从初态出发,按照与符号串余留部分中最左字符相匹配的原则,游历状态图,直至符号串的末端为止。如果这时恰好到达终态,则符号串为该文法的句子；否则不是。例如：识别 num1、1001初态=终态,l,非 l,非 d,l/d,d,非d,d,2023/9/18,11,大多数程序设计语言的单词符号都可以用状态转换图来识别。可以用一张状态转换图或若干张状态转换图来描述一

6、个语言的所有单词。例如：图3.3是简单语言词法分析的状态转换图。,2023/9/18,12,2.由正规文法构造状态转换图(1).右线性文法=状态转换图,已知:G=(VN,VT,P,S)P:AaB|a A,BVN,aVT*求:状态转换图M设:|VN|=k,则状态转换图M共有k+1个结点方法:初态=S,增设终态结点F对G中形如AaB 的产生式,从结点A引一条矢线到结点B,并用 a 标记。对G中形如Aa 的产生式,从结点A引一条矢线到终态结点F,并用 a 标记。对G中形如A 的产生式,从结点A引一条矢线到终态结点F,并标记为,或令A为接受状态。,2023/9/18,13,例如:文法GZ:Z 0AA

7、0A|0BB 1A|语言为:L(G)=0(0|01)*0 求:状态转换图。,2023/9/18,14,(2).左线性文法=状态转换图,已知:G=(VN,VT,P,S)P:ABa|a A,BVN,aVT*求:状态转换图M设:|VN|=k,则状态转换图M共有k+1个结点方法:新增初态=R,S=终态结点对G中形如ABa 的产生式,从结点B引一条矢线到结点A,并标记为 a。对G中形如AB 的产生式,从结点B引一条矢线到结点A,并标记为。对G中形如Aa 的产生式,从初态R引一条矢线到结点A,并标记为 a。,2023/9/18,15,例如:文法GS:S S1|U1U U0|0,2023/9/18,16,

8、四.状态转换图=程序,词法分析程序的设计步骤:1.画出状态转换图(正规文法、正规式)2.对于状态转换图中的每一个状态构造一段程序代码。功能为:从输入串中读一个字符。判断所读字符与该状态哪条弧相匹配,转到匹配弧状态。都不匹配时便失败(不能到达正常出口)。具体:不含回路的分支结点,对应一个switch 或 ifthenelse语句构成的程序段。(P44-45)含回路的分支结点,对应一个while 和 if 语句构成的程序段。(P45)终态结点,对应一个形如 return(code,value)的语句。例如:P4246 简单语言的词法分析程序。,2023/9/18,17,int code value

9、;strToken=;GetChar();GetBC();if(IsLetter()while(IsLetter()|IsDidit()Concat();GetChar();Retrace();code=Reserve();if(code=0)value=InsertId(strToken);return($ID,Value);else return(code,-);else if(Isdigit()while(IsDigit()Concat();GetChar();Retrace();value=InserConst(strToken);return($INT,Value);,2023/9/

10、18,18,else if(ch=)return($ASSIGN,-);else if(ch=+)return($PLUS,-);else if(ch=*)GetChar();if(ch=*)return($POWER,-);Retract();return($STAR,-);else if(ch=;)return($SEMICOLON,-);else if(ch=()return($LPAR,-);else if(ch=)return($RPAR,-);else if(ch=)return($LBRACE,-);else if(ch=)return($RBRACE,-);else ProcE

12、e1)L(e2)e1*也是正规式，相应的正规集L(e1*)=(L(e1)*,2023/9/18,21,例：令a,b，下面是上的正规式和相应的正规集正规式正规集ba*上b开头任意个aa(a|b)*上所有以a为首的字a+b+上ambn,m,n1的字例：令A，B，1，则正规式正规集（A|B)(A|B|0|1)*上的标识符的全体（0|1)(0|1)*上数的全体结论：正规式是正规语言的另一种表示方法定义：若正规式R1和R2所描述的正规集相同，则称正规式R1和R2等价，并记为：R1R2。例如：b(ab)*=(ba)*b(a|b)*=(a*b*)*。,2023/9/18,22,二、正规文法与正规式1、正规文

14、则得,B=(aa)*(a+b)(5),(5)代入(1)中的B得,即正规文法GA所生成语言的正规式是,A=(a+b)(aa)*(a+b),R=(a|b)(aa)*(a|b),A=aB+bB(1),B=aC+a+b(2),C=aB(3),例3 设有正规文法G：,相应的正规式方程组为,Z U0|V1,U Z1|1,V Z0|0,Z=U0+V1(1),U=Z1+1(2),V=Z0+0(3),(2)和(3)代入(1)得,Z=Z10+10+Z01+01(4),对(4)使用求解规则得,即正规文法GZ所生成语言的正规式是,Z=U0+V1(1),U=Z1+1(2),V=Z0+0(3),Z=(10+01)(10+

15、01)*,R=(10|01)(10|01)*,例4 已知描述“标识符”单词符号的正规文法为,lld,根据前述求解规则,可知该文法所描述语言的正规式是 l(l|d)*,2.正规式到正规文法的转换,(1)令 VT=。,(2)对任何正规式R选择一个非终结符Z生成规则ZR并令SZ。,(3)若a和b都是正规式，对形如 Aab 的规则转换成 AaB 和 Bb 两规则，其中B是新增的非终结符。,(4)对已转换的文法中,形如A a*b 的规则，进一步转换成 A aA|b。,(5)不断利用规则(3)和(4)进行变换，直到每条规则最多含有一个终结符为止。,例1 将 R=(a|b)(aa)*(a|b)转

17、变换为,去掉规则,即前面描述标识符的右线性文法。,I lT,T lT|dT|,I l|lT,T l|d|lT|dT,2023/9/18,34,一个确定的有穷自动机M是一个五元组，M（S,f,s0,Z),其中：S：状态的有穷非空集。：有穷的输入字母表 f：状态转移函数，是从SS的单值映射函数f(S1,a)=S2 表示当前状态为S1，输入字母为a时，将转到下一状态S2(单值：唯一地确定了下一个要转移的状态)。s0：唯一初态。（s0S)Z：是终态集。,3.4正规式与有穷自动机一.确定的有穷自动机(DFA),2023/9/18,35,例如：设有DFAM（q0,q1,q2,a,b,f,q0,q2)其中

18、f 为f(q0,a)=q1 f(q1,a)=q1 f(q2,a)=q2f(q0,b)=q2 f(q1,b)=q1 f(q2,b)=q1对于这个DFA，还可以用下面的方法来描述：状态转移矩阵状态转换图,对中的字符串有一条从初态到终态的路，路上的字符组成的字符串时，称自动机可以识别。语言为 L(M)=ba*1=baaa(可以到达终态）2=abbab（不可以到达终态）,2023/9/18,36,一个非确定的有穷自动机N是一个五元组，N（S,f,s0,Z),其中：S：状态的有穷非空集。：有穷的输入字母表 f：状态转移函数，是从SS的多值映射函数f(S1,a)=某些状态的集合。s0：非空初态集。Z：是

19、终态集。,二非确定的有穷自动机（NFA),2023/9/18,37,例如：设有NFAN=(1,2,3,a,b,f,1,3,2)f为:f(1,a)=3f(2,a)=f(3,a)=f(1,b)=1,2f(2,b)=3f(3,b)=2L(N)=b*(b|ab)(bb)*bbb有三条路状态转换矩阵状态转换图,2023/9/18,38,三.正规表达式=确定的有穷自动机,由正规表达式构造确定的有穷自动机共分三步：第一步：正规式 R=NFA采用分裂法第二步：NFA=DFA采用子集法第三步：DFA=最小化DFA采用分划法,2023/9/18,39,1.正规表达式 R=NFA(分裂法）,理论依据：定理：设 L(

20、R)是正规式R所描述的正规集，则存在一个NFA识别 L(R)。输入：字母表上的正规式R。输出：识别L(R)的NFA N。方法：引进初态结x和终态结y，把R表示成如下形式的拓广转换图。,2023/9/18,40,R=R=R=a=若R是复合正规式，则按下列方式对R进行分裂和加进新结点，直到每条边上留下一个符号为止。,x,y,x,x,y,y,a,2023/9/18,41,例：试构造识别语言(a|b)*abb 的 NFA。例：构造正规式 0(1*)*|01 的NFA。返回解：(A*)*=A*0(1*)*|01=01*|01=0(1*|1)=0 1*,x,0,x,x,y,1,3,2,y,1,2,3,y

21、,=,=,=,(a|b)*abb,(a|b)*,a,a,b,b,b,b,a,b,2023/9/18,42,2.NFA=DFA(子集法）,理论依据：设L是一个由NFA接受的正规集，则存在一个DFA接受L。基本思想：f(S,a)=某些状态的集合=s1，s2，sn=A DFA的一个状态是NFA状态集合的子集。输入：一个NFA N输出：一个识别相同语言的DFA M方法：利用构造闭包的方法将NFA确定化为DFA,2023/9/18,43,-闭包的概念：设I是NFA N的一个状态子集，则-closure(I)定义如下：若SI，则 S-closure(I)若SI，那么从S出发经任意条弧而能到达的任何状态S都

22、属于-closure(I)例如：下图中 I=s则-closure(I)=s,s,s,s=A,2023/9/18,44,NFA=DFA 的算法已知：NFA N=(S,f,x,y)求：DFA M=(D,f,初态，终态集)算法begin 主要求开始时D=求-closure(x)并置为无标记送入 Dwhile D中存在一个无标记状态 T=s1,s2,sn dobeginfor 每个输入符号 a dobegin 求y:J=f(s1,s2,sn,a)=x1,x2,xn y=-closure(J);if yD and y then 置y为无标记并送入D；if y then 置 fT,a=y;if y中至少

23、有一个是N的终态 then y为M的终态；end;for对T置标记；end;whileend;,2023/9/18,45,例如：正规式(a|b)*abb=NFA=DFA,-closure(x)=x,0,1=Af(A,a)=0,2-closure(0,2)=0,1,2=Bf(A,b)=0-closure(0)=0,1=Cf(B,a)=0,2-closure(0,2)=0,1,2=Bf(B,b)=0,3-closure(0,3)=0,1,3=Df(C,a)=0,2-closure(0,2)=0,1,2=Bf(C,b)=0-closure(0)=0,1=C,2023/9/18,46,f(D,a)=0

24、,2-closure(0,2)=0,1,2=Bf(D,b)=0,y-closure(0,y)=0,1,y=Ef(E,a)=0,2-closure(0,2)=0,1,2=Bf(E,b)=0-closure(0)=0,1=C返回菜单返回分划1返回分划2,2023/9/18,47,3.DFA最小化（分划法）,DFA最小化：所谓DFA M最小化是指寻找一个状态数比M更少的DFA M，使得L(M)=L(M)。等价状态：假设DFA M中有状态s和t，如果从s出发能识别某一字符串 x而停止于终态，则从t出发也能识别某一字符串 x而停止于终态；反之亦然。则称状态s和t是等价的。否则，称s和t是可区分的。例如：

25、终态与非终态是可区分的P51图3.8中状态1和状态2是可区分的,2023/9/18,48,化简的方法：输入：一个DFA M输出：接受与M语言相同并且状态数尽可能少的DFA M。基本思想：采用分划的方法。把M的状态集分划成一些不相干的子集，使得每个子集中任何两个状态是等价的，而不同的两个子集中的状态是可区别的。步骤：首先将DFA M的状态集分划成两个子集：终态集和非终态集，构成初始分划。上例中：1=A,B,C,D,E,2023/9/18,49,按下面的方法构成新的分划，直到中每个状态子集不能再分划为止。for 中的的每个状态集G dobegin把G分划成子集，使得G的两个状态s和t属于同一个子集

26、的条件是：当且仅当对任何输入符号a，状态s和t转到同一状态子集中的状态；把这样形成的子集放进新分划中。end合并等价状态，删除无用状态。,2023/9/18,50,上例中1=A,B,C,D,E A,B,C,D a=B A,B,C,D b=C,D,E 2=A,B,C,D,E A,B,C a=B A,B,C b=C,D 3=A,C,B,D,E A,C a=B A,C b=C,2023/9/18,51,合并等价状态，删除无用状态。=A,B,D,E 则最小化的DFA为：,2023/9/18,52,例如：构造正规表达式a(ab*|ba*)*b的DFA,2023/9/18,53,分划：1=0，1，2，5，

27、3，4 2=0，1，2，5，3，4 1，2，5a=2，5 1，2，5b=3，4 3，4a=5 3，4b=3，4 将原状态集合分划为0，1，2，5，3，4,2023/9/18,54,四.有穷自动机=正规表达式（消结法）,定理:上的NFA N 所能识别的字符串全体 L(N)是上的一个正规式。引进初态结x与终态结y合并成复杂正规式(恰与分裂法相反),2023/9/18,55,例如:,例如:文法GZ:Z 0AA 0A|0BB 1A|状态转换图见下图，求正规式。返回,A,A,2023/9/18,56,举例：试用一种高级语言编写识别实数的词法分析程序,设要识别的实数包含如下各种形式（正号可以省略）d d*

28、（其中d0,1,2,3,4,5,6,7,8,9)d d*.d d*（为方便起见，用f代表）d d*.d d*e d d正规式=NFA,NFA:,2023/9/18,57,将NFA=DFA,2023/9/18,58,DFA=最小化的DFA1=0,2,4,7,8,9,1,3,5,6,10 0,2,4,7,8,9 分划成 0,7,8,2,4,9 1,3,5,6,10 分划成 1,3,5,6,102=0,7,8,2,4,9,1,3,5,6,10,2023/9/18,59,2,4,9 分划成2,4,93=0,7,8,2,4,9,1,3,5,6,10所以最小化的DFA为：,2023/9/18,60,3.5

29、正规文法与有穷自动机一右线性正规文法G=有穷自动机M,已知：G=(VN,VT,P,S)P:AaB|a A,BVN,aVT*求：M（Q,f,q0,F)转换规则：Vt,Q=VnDD增设终态F=D,q0=S对G中形如AaB 的产生式,则令f(A,a)=B对G中形如Aa 的产生式,则令f(A,a)=D对G中形如A 的产生式,则令A为接受状态或令f(A,)=D。,2023/9/18,61,举例：构造下述文法的自动机，该自动机是确定的吗？它相应的语言是什么？文法GZ:Z 0AA 0A|0BB 1A|,方法一：消结法正规文法自动机正规式,A,求语言,2023/9/18,62,方法二：方程组法：正规文法正规

30、式方程组正规式1Z=0AA=0A+0B B=1A+2利用求解规则R：若x=x+则解为x=*若x=x+则解为x=*将代入得 Z=0AZ=0AA=0A+0(1A+)A=(0+01)A+0由R：A=(0|01)*0Z=0(0|01)*0,2023/9/18,63,二左线性正规文法G=有穷自动机M,G=(VN,VT,P,S)P:ABa|a A,BVN,aVT*求：M（Q,f,q0,F)转换规则：Vt,Q=Vnq0 q0增设初态F=S文法开始符号作为M的终态对G中形如ABa 的产生式,则令f(B,a)=A对G中形如Aa 的产生式,则令f(q0,a)=A,2023/9/18,64,举例：构造下述文法的自动

31、机，该自动机是确定的吗？它相应的语言是什么？P:（1）消结法（2）方程组法,2023/9/18,65,消结法：L=(10|01)(10|01)*=(10|01)+返回,2023/9/18,66,方程组法：,Z=(Z1+1)0+(Z0+0)1=Z(10+01)+(10+01)Z=(10+01)(10+01)*=(10+01)+L=(10|01)+,2023/9/18,67,三.有穷自动机=正规文法,已知：M（G,f,q0,F)求：G=(VN,VT,P,S)（以右线性文法为例）P:AaB|a A,BVN,aVT*转换规则：VN=G,VT=,S=q0若f(A,a)=B,则BF时，令AaB 若BF时，

32、令AaB|a 或 AaB,B如果文法开始符号S是一个终态，则令S,2023/9/18,68,例如：设DFA M=(A,B,C,D,0,1,f,A,B)其中：f(A,0)=B f(B,0)=D f(C,0)=B f(D,0)=D f(A,1)=D f(B,1)=C f(C,1)=D f(D,1)=D求右线性文法G使得L(G)=L(M)。,C,右线性文法为：A0B|0B1CC0B|0语言为：L=0(10)*,3.6 词法分析程序的编写方法,在例中，我们规定所有关键字,用户不得使用它们作为自己定义的标识符，这样我们可以把关键字作为一类特殊的标识符来处理，不再专设对应的转换图。但需把它们预先安排在一个

33、表格中，此表叫关键字表。当利用状态转换图识别出一个标识符时，就去查关键字表，以确定它是否是一个关键字。,其次规定，若关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔，即此时的空白符是有意义的。,根据状态转换图构造出词法分析程序最简单的办法是让每个状态对应一小段程序。,1.ch 字符变量，存放当前读进的源程序字符。,2.token 字符数组,存放构成单词符号的字符串。,3.getch()读字符函数，每调用一次从输入缓冲区中读进源程序的下一个字符放在ch中，并把读字符指针指向下一个字符。,4.getbc()函数，每次调用时，检查ch中的字符是否为空白字符，若是空白

34、字符，则反复调用getbc()，直至ch中进入一个非空白字符为止。,首先，我们引进词法分析程序所用的全局变量和需调用的函数如下：,2023/9/18,71,3.6 词法分析程序的编写方法,6.letter(ch)和 degit(ch)布尔函数，它们分别判定 ch 中的字符是否为字母和数字，从而给出true 或 false。,7.reserve()整型函数，对token中的字符串查关键字表，若它是一个关键字,则回送它的编码，否则回送标识符的种别码10。,5.concat()函数，每次调用把当前ch中的字符与token中的字符串联接。例如，假定token字符数组中原有值为“ab”,ch中存放着“c

35、”,经调用concat()后，token数组中的值变为“abc”。,2023/9/18,72,3.6 词法分析程序的编写方法,8.retract()函数，读字符指针回退一个字符。,9.return()函数，收集并携带必要的信息返回调用程序，即返回语法分析程序。,10.dtb()进制转换函数,它将token中的数字串转换成二进制数值表示,并以此作为函数值返回。,根据该语言的状态转换图用C语言编写出词法分析程序如下:,Scaner()token=NULL;getch();getbc();if(letter(ch)while(letter(ch)|digit(ch)concat();getch();

36、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-:return(14,);break;case*:return(15,);break;case/:return(16,);break;case)return(18,);r

37、etract();return(19,);break;case:getch();if(ch=)return(22,);retract();return(21,);break;case;:return(23,);break;default:error();break;,由此可知,只要构造出识别语言单词符号的有穷自动机,就很容易构造出识别语言单词符号的词法分析程序。,3.6 词法分析程序的编写方法,本章小结,本章重点介绍了词法分析程序的设计思想和构造方法。主要内容有：,1.词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号。,输出单词符号的形式是二元组:（单词种别，

38、单词自身值）,例如定义“标识符”单词的正规式是 l(l|d)*,正规文法是标识符 l|标识符l|标识符d,2程序语言单词符号的两种定义方式,正规文法,正规式,3有穷自动机有确定的和非确定两大类：,NFA N=(Q,f,S,Z)其中f是多值映射函数，S为非空初态集。,有穷自动机通常表示为状态转换图，它是有穷自动机的非形式化描述。,DFA M=(Q,f,S,Z)其中是f单值映射函数，S是唯一初态,从单词两种定义方式中构造词法分析程序的过程是：,2023/9/18,81,4正规式、正规文法和有穷自动机三者都是描述正规集的工具,它们的描述能力是等价的，它们之间可相互转换。,5证明两正规式是等价的,如

39、果它们的最小状态DFA是相同的。也可以利用正规式的基本等价关系将一个正规式化简来证明两正规式之间的等价性或两正规式识别的语言一样。,本章小结,例1 构造正规式R=1(0|1)*101的状态最小化的DFA,分析首先对R采用分裂法构造NFA，见下图:,对NFA采用子集法构造其等价的DFA的状态转换矩阵,见右表,AFBCDE,字符,状态,0,1,X,1,2,3,2,3,4,2,3,5,2,3,4,Y,2,3,2,3,1,2,3,2,3,4,2,3,2,3,4,2,3,5,2,3,4,2,3,2,3,4,Y,2,3,5,2,3,4,对DFA采用分化的方法化简，得到状态最小化的DFA，见下图:,202

40、3/9/18,85,例2.构造一个DFA它接收=0,1上所有满足如下条件的字符串，每个1都有0直接跟在右边。,分析首先给出描述语言的正规式R=(0|10)*,采用分裂法从正规式构造NFA,2023/9/18,86,采用子集法将NFA确定化为DFA,采用分化方法将DFA化简,字符,状态,0,1,X,A,Y,B,A,Y,A,Y,B,B,A,Y,A,Y,2023/9/18,87,分析给出描述语言的正规文法,S0S|1A|A 0S,根据右线性文法构造有穷自动机的方法,构造出如下的状态转换图:,例3.构造一个DFA它接收=0,1上所有满足如下条件的字符串，每个1都有0直接跟在右边。,2023/9/1

41、8,88,S0A|1B A1S|1 B0S|0,分析根据正规文法转换成正规式的方法，首先给出该正规文法对应的正规式方程组：,S=0A+1B(1)A=1S+1(2)B=0S+0(3),将(2)、(3)代入(1)得 S=01S+01+10S+10(4),对(4)使用求解规则得 S=(01|10)(01|10),即正规文法所生成语言的正规式是(01|10)(01|10)。,例4.给出下述文法所对应的正规式：,2023/9/18,89,例5 将右图确定化和最小化。,图示是一个无边转移的NFA,采用子集法将NFA确定化为DFA,采用分化方法将DFA化简,字符,状态,a,b,0,1,0,1,0,1,1,1,0,1,0,例6.设字母表=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，见下图。,对NFA采用子集法构造其等价的DFA的状态转换矩阵，见表。,XBAYEF,字符,状态,a,b,X,1,2,1,2,4,5,Y,6,5,Y,3,3,3,1,2,1,2,4,5,Y,6,5,Y,5,Y,6,5,Y,对DFA采用分化的方法得到状态最小化的DFA，见图。,

展开阅读全文