第三四章习题课编译原理课件.ppt

《第三四章习题课编译原理课件.ppt》由会员分享，可在线阅读，更多相关《第三四章习题课编译原理课件.ppt（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+)，则解为x = *若

2、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 进行分裂和加进新结，直至每个边上只留下一个符号（或 ）为止。,整个分裂过程中，所有新结点均采用不同的名字，保留 X，Y 为全图

3、唯一初态结点和终态结点,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 进行如下变换：把 G 分划成新的子集

4、，使得 G 的两个状态 s 和 t 属于同一子集，当且仅当对任何输入符号 a，状态 s 和 t 转换到的状态都属于 的同一子集。用 G 分划出的所有新子集替换 G，形成新的分划 new 。如果 new，则执行第（4）步；否则令new，重复第（2）步。分划结束，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把射向其余状态的箭弧都改为射向作为“代表”的状态。,8,增加新初态 X，与所有原初态用相连，增加新终态 Y，与所有原终态用相连，从而构成一个新的 FA M，它只有一个初态 X 和一个终态 Y。在X 与 Y 之间进行弧合并：,在X 和 Y之间的表达式即为所求的正规式 R

5、。,代之以,代之以,代之以,自动机转化为正规式,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)，则相应的有穷自动机 M=(Q,f,q0,Z)（1）将VN中的每一个

6、非终结符视作 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且BZ时，则将规则 AaB 加到P中。(3)若f(A,a)=B且BZ时，则将规则AaB

7、a或 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),注意: 若初态无入弧，则去掉该非终结符,终点开始，考虑入弧！,13,习题7(1/4),7、构造下列正规式的相应的DFA1(0|1)*101解题步

8、骤：1.由正规式R构造NFA N2.构造确定化后的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,它既不包含在A,B,C,D,E中也不包含在F之中，因此，应把A,B,C,D,E一分为二。因为状态 E 经 1 弧到达状态 F，而状态A

9、、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无法再分。至此，整个分划含有四组： A、B,D、C、E、F 。每个组都不可再分。,习题7(4/4),17,习题8(1/3),8、给出下面正规表达

10、式(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|1|2|9)*(0|5)|0|5,19,习题8(3/3),(3) 奇数个1：0*1(0|10*1)* 奇数个0：1*0(1|01*0)*所以正则表达

11、式为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,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

12、,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)分别确定化和最少化。,(a),24,习题12(2/3),(a),25,已经是确定化，对其最小化。1:0,1,2,3,4,50,1a=0,10,1b=2,42,3,4,5a=1,3,0,5

13、2:0,1,2,4,3,52,4b=3,53,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 C0C|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

14、,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|b A1A0A0 AnAn-1An-1考虑词形An(1)把An中所有简名都换掉，最终所得的正规式的长度是多少；(2)字集An的元素是什么？把它们非形式地表示成n的函数；(3)证明识别An

15、的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+1需要2(k+1)+1个状态，即n=k+1时成立。综上所述，识别An的DFA只需要用2n+1个状态。,34,

16、补充题,构造a,b上的含有偶数个a且奇数个b的正规文法。解：左线性文法GL=(S,A,B,C,0,1,f,S)S识别偶数个a,偶数个b; A识别奇数个a,偶数个b;B识别奇数个a,奇数个b; C识别偶数个a,奇数个b.,S,a,A,a,b,b,C,B,a,a,b,b,SaA|bC|AaS|bBBaC|bACaB|bS,35,语法分析自上而下分析(1/5),自上而下分析法,确定的自上而下分析法非确定的自上而下分析法(带回溯的自上而下分析法),递归下降分析法预测分析法,36,语法分析自上而下分析(2/5),LL(1)文法要求：（1）文法不含左递归。（2）对文法中的每一个非终极符 A， 若 A 1|

17、2|.|n， 则 FIRST（i） FIRST（j）= （3）对文法中的每一个非终极符 A，若它存在某个候选首符集包含 ， 则 FIRST（A） FOLLOW（A）=,左递归的消除：PP| 改为： PP P P|,FIRST集：FIRST()= a | a, a VT 若 ， FIRST(),FOLLOW集：FOLLOW(A)=a |S .Aa.，aVT 若S.A，则规定 #FOLLOW（A）,*,*,非LL(1)文法改写为LL(1)文法：消除左递归和反复提取公共左因子。提取公共左因子： A1|2|.|n|1|2|.|m 修改成： A A|1|2|.|m A1|2|.|n,37,语法分析自上而

18、下分析(3/5),递归下降分析程序的构造：当遇到终结符 a 时，则编写语句if (当前读到的输入符号=a) 读入下一个输入符号。当遇到非终结符 A 时，则编写语句调用 A.当遇到 A 规则时，则编写语句if (当前读到的输入符号 FOLLOW(A) ERROR。当某个非终结符的规则有多个候选式时，按LL(1)文法的条件唯一现在一个候选式进行推导。,38,实验二：预测分析算法的设计与实现,预测分析器预测分析表分析栈总控程序,Tj,分析栈Sk,总控程序,预测分析表,输出,39,预测分析表的构造,1、构造文法 G 的每一个非终结符的FIRST集和FOLLOW集2、构造分析表 MA，a（1）对文法G的

19、每个规则A，执行第二步和第三步；（2）对每个终极符aFIRST(）,则置MA,a=A；（3）若FIRST(）,则对任何bFOLLOW（A）, 则置MA,bA；（4）把所有无定义的 MA,a 标上“出错标志” (表中用空格表示)。,40,FIRST集的构造,若XVT，则 FIRST(X)=X。若XVN，且有规则Xa，aVT，则aFIRST(X)。若XVN，且有规则X，则FIRST(X)中。若有规则XY1Y2Yn，对任意的i(1in)，当Y1Y2Yi-1都是非终极符且Y1Y2Yi-1=(即对任何j(1ji-1)，FIRST(YJ)都含有)，则把 FIRST(Yi)中的所有非-元素加到 FIRST(

20、X)中；特别地，若Y1Y2Yn=(即所有的FIRST(Yj)中均含有，1jn)，则FIRST（X）。反复使用上面的规则，直到每个FIRST集不再增大为止,41,FOLLOW集的构造,(1)对文法的开始符号 S，置#于FOLOOW（S）中；(2)若AB 是一个规则，则把FIRST()-加到FOLLOW(B)中；(3)若AB 是一个规则，或AB 是一个规则，而 =，即FIRST(),则把FOLLOW(A)加至FOLLOW(B)中。(4)反复使用上面的规则，直到每个非终结符的FOLLOW集 不再增大为止。,42,总控程序,43,预测分析的过程,若X=a=#，则宣布分析成功；若X=a#，则将栈顶符号

21、X（终极符）弹出，让 IP 指针指向下一个输入符号；若 X 是一个非终极符，则查看分析表 M。如果分析表的 MA,a 中是一条产生式，则先将栈顶符号 X（非终极符）弹出，然后把该产生式右端符号串按反序（从右到左）压入栈中（串不入栈）。,44,习题1(1/4),1、考虑下面文法G1： Sa|(T) TT,S|S（1）消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。（2）经过改写的文法是否是LL（1）的？给出它的预测分析表。,45,习题1(2/4),解：（1）消去G1的左递归：Sa|(T) TST T ,ST|递归子程序：PROCEDURE S;IF SYM=a THEN ADVAN

22、CEELSE IF SYM= THEN ADVANCEELSE IF SYM= ( THEN BEGIN ADVANCE T; IF SYM= ) THEN ADVANCE ELSE ERROR ENDELSE ERROR;,PROCEDURE T;BEGINS;TEND;PROCEDURE T;IF SYM= , THEN BEGIN ADVANCE S;T END;ELSE IF SYM) THEN ERROR,判断输入符号是否属于FOLLOW集,46,习题1(3/4),（2）FIRST(a)=a FIRST()= FIRST(T)= ( FIRST(,ST)=, FIRST()= FIR

23、ST(S)= a,( FOLLOW(S)= #, , , , ) FIRST(T)= a,( FOLLOW(T)= ) FIRST(T)= , FOLLOW(T)= ) FIRST(a)FIRST() FIRST(T)= FIRST(,ST) FIRST()= FIRST(T) FOLLOW(T)= 所以改写后的文法是LL（1）文法。,47,习题1(4/4),预测分析表如下：,48,习题2(1/6),2、对下面的文法G： ETE E+E| TFT TT| FPF F*F| P(E)|a|b|(1)计算这个文法的每个非终结符的FIRST和FOLLOW。(2)证明这个文法是LL(1)的。(3)构造

24、它的预测分析表。(4)构造它的递归下降分析程序。,49,习题2(2/6),解：(1)FIRST和FOLLOW集如下表：,50,习题2(3/6),(2)FIRST(+E)FIRST()= + = FIRST(T) FIRST()= (,a,b, = FIRST(*F)FIRST()= * = FIRST(E)FIRST(a) FIRST(b) FIRST()= ( a b = FIRST(E) FOLLOW(E)= FIRST(T) FOLLOW(T)= FIRST(F) FOLLOW(F)= 所以该文法是LL(1)文法。,51,习题2(4/6),(3)预测分析表为：,52,习题2(5/6),(

25、4)递归下降分析程序为：PROCEDURE E;BEGIN T;EEND;PROCEDURE T;BEGIN F;TEND;PROCEDURE E;IF SYM=+ THENBEGIN ADVANCE; EEND;ELSE IF SYM) AND SYM# THEN ERROR,PROCEDURE F;BEGIN P;FEND;PROCEDURE T;IF SYM=a OR SYM=b OR SYM= OR SYM=( THENBEGIN ADVANCE; TEND;ELSE IF SYM) AND SYM+ AND SYM# THEN ERROR,53,习题2(6/6),PROCEDURE

26、P;IF SYM=( THENBEGIN ADVANCE; E; IF SYM!=) THEN ADVANCE; ELSE ERRORENDELSE IF SYM=a OR SYM=b OR SYM= THEN ADVANCE; ELSE ERROR,PROCEDURE F;IF SYM=* THENBEGIN ADVANCE; F;ENDELSE IF SYM( AND SYMa AND SYMb AND SYM AND SYM+ SYM) AND SYM# THEN ERROR,54,习题3(1/3),3、下面文法那些是LL(1)文法？(1)S Abc A a| Bb|(2)S Ab A

27、a|B| Bb|(3)S ABBA A a | Bb|(4)S aSe|B B bBe |C CcCe|d,55,习题3(2/3),解：(1)文法无左递归 FIRST(a)FIRST()= a = FIRST(b)FIRST()= b = FIRST(A)FOLLOW(A)= a, b= FIRST(B)FOLLOW(B)= b, =所以该文法是LL(1)文法。(2)文法无左递归FIRST(a)FIRST(B)FIRST()= ab, 所以该文法不是LL(1)文法。,56,习题3(3/3),(3)文法无左递归 FIRST(a)FIRST()= a = FIRST(b)FIRST()= b =

28、FIRST(A)FOLLOW(A)= a, a,b, #所以该文法不是LL(1)文法。(4)文法无左递归 FIRST(aSe)FIRST(B)= a b,= FIRST(bBe)FIRST(C)= b c,d= FIRST(cCe)FIRST(d)= c d=所以该文法是LL(1)文法。,57,习题4(1/3),4、对下面文法： Expr_Expr Expr(Expr)| Var ExprTail ExprTail_ Expr| Varid VarTail VarTail(Expr)| (1)构造LL（1）分析表(2)给出对句子id_ _id(id) 的分析过程,58,习题4(2/3),解：(

29、1)FIRST集和FOLLOW集如下表：,LL(1)分析表为：,59,习题4(3/3),(2) 步骤 符号栈 输入串 所用产生式,反序压入栈,60,习题5(1/5),5、把下面文法改写为LL(1)的：DeclistDeclist；Decl|DeclDeclIdList:TypeIdListIdList,id|idTypeScalarType|array(ScalarTypeList) of TypeScalarTypeid|Bound.BoundBoundSign IntLiteral|idSign+|-|ScalarTypeListScalarTypeList,ScalarType|Scal

30、arType,61,习题5(2/5),解：消除左递归：DeclistDeclDeclistDeclist;DeclDeclist|DeclIdList:TypeIdListidIdListIdList,idIdList|TypeScalarType|array(ScalarTypeList) of TypeScalarTypeid|Bound.BoundBoundSign IntLiteral|idSign+|-|ScalarTypeListScalarTypeScalarTypeListScalarTypeList,ScalarTypeScalarTypeList|,62,习题5(3/5),

31、判断是否为LL(1)文法：FIRST(;DeclDeclist)FIRST() =;=FIRST(,idIdList )FIRST() =,=FIRST(ScalarType)FIRST(array(ScalarTypeList) of Type)=id,+,-,IntLiteralarray=FIRST(id)FIRST(Bound.Bound) =idid,+,-, IntLiteralFIRST(Sign IntLiteral)FIRST(id) =+,-, IntLiteralid=FIRST(+ )FIRST(-)FIRST()=+-=FIRST(,ScalarTypeScalarT

32、ypeList)FIRST() =,=FIRST(Declist) FOLLOW(Declist)=;,#=,63,习题5(4/5),FIRST(IdList) FOLLOW(IdList)=,:=FIRST(Sign) FOLLOW(Sign)=+,-,IntLiteral=FIRST(ScalarTypeList) FOLLOW(ScalarTypeList)=,)=所以该文法不是LL(1)文法。不是LL(1)文法是由ScalarTypeid|Bound.Bound存在公共左因子id引起的，提取左因子得：,64,习题5(5/5),DeclistDeclDeclistDeclist;DeclDeclist|DeclIdList:TypeIdListidIdListIdList,idIdList|TypeScalarType|array(ScalarTypeList) of TypeScalarTypeidScalarType | Sign IntLiteral.BoundScalarType|.BoundBoundSign IntLiteral|idSign+|-|ScalarTypeListScalarTypeScalarTypeListScalarTypeList,ScalarTypeScalarTypeList|该文法是LL(1)文法。,问题？,