《第三四章习题课编译原理资料》由会员分享，可在线阅读，更多相关《第三四章习题课编译原理资料（65页珍藏版）》请在金锄头文库上搜索。
1、第三、四章习题,P64：7,8,9,12,14,15,20,补充题 P81：1,2,3,4,5,2,词法分析,正规式,自动机,正规文法,3,正规式与正规文法的转化,: 令 VT = 对任意正规式 R 选择一个非终结符 Z 生成规则ZR，并令 SZ； 若 a 和 b 都是正规式，对形如 Aab的规则转换成 AaB 和 Bb； 在已转换的文法中，将形如 Aa*b 的规则进一步转换成 A aA | b； 不断利用上上面后两条规则进行转换，直到每条规则最多含有一个 终结符为止。,: 将每个非终结符表示成关于它的正规式方程，获得一个联立方程组。 依照求解规则： 若 x = x | (或x = x+)，则
2、解为x = * 若 x = x | (或x = x+)，则解为x = * 以及正规式的分配率、交换率和结合率求关于文法开始符号的正规式 方程组的解。,4,正规式转化为NFA(1/2),(1)引进初始结点 X 和终止结点 Y，把 R 表示成拓广转换图。如图,(2)分析 R 的语法结构，用如下规则对 R 中的每个基本符号构造 NFA。 R，构造 NFA 如图： R，构造 NFA 如图：,Ra(a)，构造 NFA 如图：,5,正规式转化为NFA(2/2),若 R 是复合正规式，则按下图的转换规则对 R 进行分裂和加进新结，直至每个边上只留下一个符号（或 ）为止。,整个分裂过程中，所有新结点均采用不同
3、的名字，保留 X，Y 为全图唯一初态结点和终态结点,6,NFA确定化为DFA,首先将从初态 S 出发经过任意条 弧所能到达的状态所组成的集合作为 M 的初态 S，然后从 S 出发，经过对输入符号 a 的状态转移所能到达的状态(包括读输入符号之前或之后所有可能的 转移所能到达的状态)所组成的集合作为 M 的新状态，如此重复，直到不再有新的状态出现为止。,从 NFA N=(Q,F,S,Z)构造等价的DFA M=(Q,F,S,Z)的方法,7,DFA的化简,将 DFA M 的状态集 Q 分成两个子集：终态集 F 和非终态集 F，形成初始分划 。 对 建立新的分划 new。对 的每个状态子集 G 进行如
4、下变换： 把 G 分划成新的子集，使得 G 的两个状态 s 和 t 属于同一子集，当且仅当对任何输入符号 a，状态 s 和 t 转换到的状态都属于 的同一子集。 用 G 分划出的所有新子集替换 G，形成新的分划 new 。 如果 new，则执行第（4）步；否则令new，重复第（2）步。 分划结束，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把射向其余状态的箭弧都改为射向作为“代表”的状态。,8,增加新初态 X，与所有原初态用相连， 增加新终态 Y，与所有原终态用相连， 从而构成一个新的 FA M， 它只有一个初态 X 和一个终态 Y。 在X 与 Y 之间进行弧合并：
5、,在X 和 Y之间的表达式即为所求的正规式 R。,代之以,代之以,代之以,自动机转化为正规式,9,正规文法转化为自动机(1/2),设给定一个右线性正规文法 G=(VN,VT,P,S)，则相应的有穷自动机 M=(Q,f,q0,Z) （1）将VN中的每一个非终结符视作 M 中的一个状态， 并增加一个新终态 D，且 DVN， 令 Q=VND,Z=D,=VT,q0=S （2）对 AaB（A,BVN,aVT ），令f(A,a)=B。 构造弧 （3）对 Aa（AVN,aVT ），令f(A,a)=D。 构造弧,10,正规文法转化为自动机(2/2),设给定一个左线性正规文法 G=(VN,VT,P,S)，则相应
6、的有穷自动机 M=(Q,f,q0,Z) （1）将VN中的每一个非终结符视作 M 中的一个状态， 并增加一个初始状态 q0，且 q0VN， 令 Q=VNq0,Z=S,=VT (将文法G的开始符号S看成终态) （2）对 ABa（A,BVN,aVT ）令f(B,a)=A。 构造弧 （3）对 Aa（AVN,aVT ），令f(q0,a)=A。 构造弧,11,自动机转化为正规文法(1/2),设给定有穷自动机 M=(Q,f,q0,Z)，按照下述方法可 以从 M 构造出相应的右线性正规文法 G=(VN,VT,P,S)， 使得L(M)=L(G) (1)令 VN=Q,VT=,S=q0 (2)若f(A,a)=B且B
7、Z时， 则将规则 AaB 加到P中。 (3)若f(A,a)=B且BZ时，则将规则 AaBa 或 AaB, B 加到P中。 (4)若文法的开始符号 S 是一个终态，则将规则 S 加到P中。,注意: 若终态无出弧，则去掉该非终结符,起点开始，考虑出弧！,12,自动机转化为正规文法(1/2),设给定有穷自动机 M=(Q,f,q0,Z)，按照下述方法可 以从 M 构造出相应的左线性正规文法 G=(VN,VT,P,S)， 使得L(M)=L(G) (1)令 VN=Q,VT=,S=Z (2)若f(S,a)=A,则Aa|Sa (3)若f(A,a)=B,则BAa(AS),注意: 若初态无入弧，则去掉该非终结符,
8、终点开始，考虑入弧！,13,习题7(1/4),7、构造下列正规式的相应的DFA 1(0|1)*101 解题步骤： 1.由正规式R构造NFA N 2.构造确定化后的DFA的状态矩阵 3.生成确定化后的DFA的状态转换图 4.化简DFA,14,习题7(2/4),由正规式构造NFA 构造确定化后的DFA的状态矩阵,15,生成确定化后的DFA的状态转换图,B,F,D,E,0,1,0,C,1,1,0,0,A,1,0,1,习题7(3/4),1,16,化简DFA,0,首先 M的状态分成两组：终态组F，非终态组A,B,C,D,E 考察A,B,C,D,E，由于A,B,C,D,E1 属于B,C,F, 它既不包含在
9、A,B,C,D,E中也不包含在F之中，因此，应把A,B,C,D,E一分为二。因为状态 E 经 1 弧到达状态 F，而状态A、B,C,D经 1 弧都到达 B,C，因此，应把 E 分出来，形成A,B,C,D、E、F。 A,B,C,D0 属于D,E,它不含在任何划分中，因为状态 C 经 0弧到达状态 E，而状态A,B,D经 0 弧都到达 D，因此，应把 C 分出来，形成A,B,D、C、E、F。 由于A,B,D1=B,C，它不包含在任何划分之中，因此，应把A,B,D一分为二。因为状态B、D经 1 弧都到达 C，经 0弧都到达 D因此，应把 A分出来，形成A、B,D、C、E、F。B,D无法再分。 至此，
10、整个分划含有四组： A、B,D、C、E、F 。每个组都不可再分。,习题7(4/4),17,习题8(1/3),8、给出下面正规表达式 (1)以01结尾的二进制数串; (2)能被5整除的十进制整数; (3)包含奇数个1或者奇数个0的二进制数串; (7)不包含子串abb的由a和b组成的符号串的全体。,18,习题8(2/3),解： (1)末两位是01，其他位为0、1组成的任意的字符串。 (a|b)*表示a、b组成的任意字符串。 所以正规表达式为(0|1)*01。 (2) 若是一位数，为0或5 若是多于一位的数，为 (1|2|3|9)(0|1|2|9)*(0|5) 所以正规表达式为(1|2|3|9)(0
11、|1|2|9)*(0|5)|0|5,19,习题8(3/3),(3) 奇数个1：0*1(0|10*1)* 奇数个0：1*0(1|01*0)* 所以正则表达式为 0*1(0|10*1)*| 1*0(1|01*0)* (7)ab后只能跟a,所以可以是ab、a组成的任意符号串，即(a|ab)*。 又若以b开始，所以正则表达式为 b* (a|ab)*。,20,习题9(1/3),9、对下面的情况给出DFA以及正规表达式。 (1)0，1上的含有子串010的所有串。 解：首先必须含有010，然后首尾为0、1组成的任意字符串，所以正规式为(0|1)*010(0|1)*。,X,1,5,0,1,0,Y,2,3,4,
12、6,0,0,1,1,21,习题9(2/3),B,H,C,0,1,D,1,1,0,0,A,0,0,1,G,E,F,1,1,1,0,0,0,1,化简后的DFA：,B,A,0,E,D,0,1,0,0,1,1,1,22,习题9(3/3),(2) 0，1上不含子串010的所有串。 解：1*(0|111*)*1*,X,1,3,Y,4,2,5,6,1,1,6,6,1,0,1,1,A,C,B,E,G,D,F,H,1,0,0,0,0,0,0,0,1,1,1,1,1,1,A,B,D,0,1,1,1,0,化简后的DFA,DFA,NFA,23,习题12(1/3),12、将图3.18的(a)和(b)分别确定化和最少化。
13、,(a),24,习题12(2/3),(a),25,已经是确定化，对其最小化。 1:0,1,2,3,4,5 0,1a=0,1 0,1b=2,4 2,3,4,5a=1,3,0,5 2:0,1,2,4,3,5 2,4b=3,5 3,5b=2,4,习题12(3/3),26,习题14(1/2),14、构造DFA,接收0，1上所有满足每个1都有0直接跟在后面的字符串。 解：正规表达式为(10|0)*,27,(10|0)*,X,Y,1,0,1,2,0,0,1,0,1,0,A,B,C,习题14(2/2),28,习题15(1/3),15、给定右线性文法G： S0S|1S|1A|0B A1C|1 B0C|0 C0
14、C|1C|1|0 求出一个与G等价的左线性文法。,29,习题15(2/3),解：与文法G等价的自动机M=(S,A,B,C,D,0,1,f,S,D) f(S,0)=S,B f(S,1)=S,A f(A,1)=C,D f(B,0)=C,D f(C,0)=C,D f(C,1)=C,D,S,A,1,0,1,B,0,0,1,1,0,0,D,C,0,1,1,30,习题15(3/3),与文法G等价的左线性文法GL=(S,A,B,C,D,0,1,f,D) DA1|B0|C0|C1 CA1|B0|C0|C1 B0|S0 A1|S1 S0|1|S0|S1,31,习题20(1/3),20、假定有正规定义式 A0a|
15、b A1A0A0 AnAn-1An-1 考虑词形An (1)把An中所有简名都换掉，最终所得的正规式的长度是多少； (2)字集An的元素是什么？把它们非形式地表示成n的函数； (3)证明识别An的DFA只需要用2n+1个状态就足够了。,32,习题20(2/3),解: (1)AnAn-1An-1 An-2An-2An-2An-2 An-3An-3An-3An-3An-3An-3An-3An-3 即 ，所以长度为2n。 (2)f(n)=,33,习题20(3/3),(3)用归纳法证明。 当n=0时，只需要1个状态，即 假设当n=k时成立，需要2k+1个状态； Ak+1= (a|b)(a|b),S,a,b,S,A,B,C,a,a,b,b,.,第2k+1个状态,D,E,a,a,b,b,所以Ak+
