[工学]《编译原理》课程复习.doc

编译原理课程复习五、计算题： 1、考虑下面程序 Var a：integer； Procedure S(X)； Var X：integer； Begin a：a1； X：aX End； Begin a：5； S(a)； Print(a) End 试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？答：传名：a12 传值：a6 2、写出表达式(ab*c)/(ab)d的逆波兰表示及三元式序列。 逆波兰表示： abc*ab/d 三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d) 3、已知文法G(S) Sa|(T) TT，S|S 写出句子(a，a)，a)的规范归约过程及每一步的句柄。 句型归约规则句柄 (a，a)，a)Saa (S，a)，a)TSS (T，a)，a)Saa (T，S)，a)TT，S T，S (S)，a) TSS (T)，a) SS(T) (T) (S，a) TSS (T，a) Saa (T，S) TT，S T，S (T) S(T)(T) S4、写一个文法，使其语言是奇数集，且每个奇数不以0开头。解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D 5、设文法G(S)： S(L)|a S|a LL，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。 解： S(L)|aS SS| LSL LSL| FIRST)S)(，a FOLLOW(S)#，) FIRST(S)，a,FOLLOW(S)#，) FIRST(L)(，a FOLLOW(L) ) FIRST(L)，FOLLOW(L) 6、Whilea0 b0do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻译成四元式序列。解： (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4) (j，15) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15) 7、已知文法G(E) ET|ET TF|T * F F(E)|i (1) 给出句型(T * Fi)的最右推导及画出语法树；(2) 给出句型(T * Fi)的短语、素短语。 解：(1) 最右推导： ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi) (2) 短语：(T*Fi)，T*Fi，T*F，i 素短语：T*F，i 8、设布尔表达式的文法为 E E(1)E(2) E E(1) E(2) E i 假定它们将用于条件控制语句中，请 (1) 改写文法，使之适合进行语法制导翻译和实现回填； (2) 写出改写后的短个产生式的语义动作。解：(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei (2) EE(1) BACKPATCH(E(1)FC，NXQ)； E0TC：E(1)TC EE0E(2) EFC：E(2)FC； ETC：MERG(E0TC，E(2)TC) EAE(1) BACKPATCH(E(1)TC，NXQ)； E0FC：E(1)FC EEAE(2) ETC：E(2)TC； EFC：MERG(EAFC，E(2)FC Ei ETC：NXQ；EFC：NXQ1； GEN(jn2，entry(i)，0)； GEN(j，0) 9、设有基本块 T1：2 T2：10/T T3：SR T4：SR A：T2 * T4 B：=A T5：SR T6：T3 * T5 B：T6 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。解：优化后的四元式 T3：SR T4：SR A：5*T4 B：T3*T410、给定文法G=（S,L，a，（，），S(L)|a LL,S|S，S）。给出句型”(S,(a)”的推导和语法树并指出此句型的所有短语、直接短语、句柄和素短语。 解：ST(L) T(L,S) T(L,(L) T(L,(S) T(L,(a) T(S,(a)短语有：“a”,“(a)”,“S”，“S,(a)”，“（S,(a)）”。直接短语有：”S”，“a”句柄：“S”素短语：“a“语法树略。11、设语言L是由奇数个a和偶数（可以是0）个b组成的符号串之集。（1）构造识别L的DFA；（2）给出定义L的正规文法；解：（1）见图： （2）SaA|bB AaS|bC|e BbS|aC CbA|aB12、将文法GS：SA AAS|B BBi|i 改写为等价的LL(1)文法，并给出相应的LL(1)分析表。解：BiC C iC |e ABA A ASA | e SAFirst(ASA)=i, FOLLOW(A)= FIRST(iC)=i, FOLLOW(C) = 可知文法满足LL(1)文法的条件。分析表：13、化简文法 GS ： S ASe | BCaD | aD | AC A Cb | DBS C bC | d B Ac D aD 解：化简后： S ASe|AC A Cb C bC | d14、设 L a,b,c* 是满足下述条件的符号串构成的语言： (1)若出现 a ，则其后至少紧跟两个 c ； (2)若出现 b ，其后至少紧跟一个 c 。 试构造识别 L 的最小化的 DFA ，并给出描述 L 的正规表达式。 解：DFA 如图所示。相应的正规式为 (c|acc|bc)* 。15、已给文法 GS ： S SaP | Sf | P P qbP | q 将 GS 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。 解：改造后的文法： S PS S aPS| fS | e P qP P bP | e 各候选式的 FIRST 集，各非终结符的 FOLLOW 集为 产生式 FIRST 集 FOLLOW 集 S PS q # S aPS fS e a f e # P qP q a,f,# P bP e b e a,f,# LL(1) 分析表为 16、给定文法 GS ： S Aa|dAb|Bb|dBa A c B c，构造文法 GS 的 LR （ 1 ）分析表。 解：分析表如下图所示17、将下面的条件语句表示成逆波兰式和四元式序列： if ab then x:=a+b*c else x:=b-a; 解：（ 1 ）逆波兰式： （ 2 ）四元式：(1) ( j, a, b, (3) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x) (6) ( j, , , (9) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( )18、给定基本块： A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。解：化简后的的四元式序列为 D:=E+F A :=D+12 E :=E+F C :=2819、试构造生成语言L=anbnci|n1, i0的文法 解：G(Z): ZAB A aAb|ab B cB|20、已知语言L=anbbn| n 1, 写出产生L的文法。解： GS: S aAb AaAb|b21、已知文法G=(A,B,C,a,b,c,A,P)，其中产生式P由以下组成： Aabc AaBbc BbbB BcCbcc bCCb aCaaB aCaa 问：此文法表式的语言是什么？解：由于A为开始符。 由于AaBbcabBcabCbccaCbbccaabbcc 语言为： anbncn, n0 22、试构造语言L=anbnci | n=1, i=0的文法。 解： G(Z): ZAB AaAb|ab BcB|23、试写一文法，使其描述的语言L(G) 是能被5整除的整数集合。 解： G(Z): Z(+|- )A(0|5) A0|1|2|3|4|5|6|7|8|9|AA|e24、已知语言L=x | xa,b,c*,且x重复排列是对称的（aabcbaa,aabbaa,等) 写出该语言的文法。 解： G(Z)： ZaZa|bZb|cZc|a|b|c|25、写能被5整除的十进制整数的文法及正则表达式。解：能被5整除的文法： GZ: Z(+|-)A(0|5)A0|1|2|3|4|5|6|7|8|9|AA|如果要求：除零以外不以0开头，则文法为： GZ: Z(+|- ) A (0|5) AAB|C B0|C|BB C 0|1|2|3|4|5|6|7|8|9正则表达式：GZ: Z= (+| - )A*(0|5) A(0,1,2,3,4,5,6,7,8,9)26、26、写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：文法G(N)：NAB|BAAC|DB1|3|5|7|9DB|2|4|6|8C0|D27、27、写出能被3整除十进制整数的文法和正则表达式：解：能被3整除的文法： G=( 0,1,2,3,4,5,6,7,8,9,S, A, B, S, P,) 其中P为：S (0|3|6|9)S|S (1|4|7)A|(2|5|8)BA (0|3|6|9)A|(1|4|7)B|(2|5|8)SB (0|3|6|9)B|(2|5|8)A|(1|4|7)S正则表达式： Z= a*| (bc)*|(cb)*|(a|cibi)*|(ciabi)*(i= 1) a(0,3,6,9) b(1,4,7) c(2,5,8)28、写一文法，使其语言是偶正整数的集合要求：(1) 允许0打头(2) 不允许0打头解：(1) GS=(S,P,D,N,0,1,2,9,P,S)P:SPD|DP-NP|ND0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2) GS=(S,P,R,D,N,Q ,0,1,2,9,P,S)P:SPD|P0|DP-NR|NR-QR|QD2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|929、已知文法G：:=|+|-:=|*|/:=()|i。试给出下述表达式的推导及语法树。(1)i; (2)(i)(3)i*i;(4)i*i+i; (5)i+(i+i);(6)i+i*i。解：(1) v=i=w(2) v=()=()=()=(i)=w(3) v=*=*=i*i=w(4) v=+=+=*+=*+=i*i+i=w(5) v=+=+=+=i+()= i+(+)=i+(+)= i+(+)=i+(i+i)=w(6) v=+=+=+=i+=i+*= i+*= i+i*i=w语法树见下图:30、为句子i+i*i构造两棵语法树，从而证明下述文法G是二义的。:=i|()|:=+|-|*|/解：为句子i+i*i构造的两棵语法树如下：所以，该文法是二义的。31、令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：可为E+T*F构造一棵语法树（见下图），所以它是句型。从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E+T*F的句柄（最左直接短语）是T*F。32、构造下列正规式相应的DFA：(1) 1(0|1)* 101(2) 1(1010* | 1(010)* 1)* 0解：(1)1(0|1)* 101对应的NFA为下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,2，4E1,4B1B1，4(2)1(1010* | 1(010)* 1)* 0对应的NFA为下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B1,6B1,6C10D2,5,7C10D2,5,7E3,8B1,6E3,8F1,4,6,9F1,4,6,9G1,2,5,6,9,10D2,5,7G1,2,5,6,9,10H1,3,6,9,10I1,2,5,6,7H1,3,6,9,10J1,6,9,10K2,4,5,7I1,2,5,6,7L3,8,10I1,2,5,6,7J1,6,9,10J1,6,9,10D2,5,7K2,4,5,7M2,3,5,8B1,6L3,8,10F1,4,6,9M2,3,5,8N3F1,4,6,9N3O4O4P2,5P2,5N3B1,633、已知NFA=（x,y,z,0,1,M,x,z）其中：M(x,0)=z, M(y,0)=x,y, M(z,0)=x,z, M(x,1)=x, M(y,1)=, M(z,1)=y,构造相应的DFA。解：根据题意有NFA图如下下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)AxBzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,zEx,y11下面将该DFA最小化：(1) 首先将它的状态集分成两个子集：P1=A,D,E,P2=B,C,F(2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21=C,F,P22=B。(3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11=A,E,P12=D。(4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。(5) 综上所述，DFA可以区分为P=A，B，D，E，C，F。所以最小化的DFA如下：11010F0BE10DA034、将下图确定化：解：下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)ASBQ,VCQ,UBQ,VDV,ZCQ,UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U,ZDV,ZFQ,U,Z35、把下图的(a)和(b)分别确定化和最小化： (a) (b)解：(a): 下表由子集法将NFA转换为DFA：IIa = -closure(MoveTo(I,a)Ib = -closure(MoveTo(I,b)A0B0,1C1B0,1B0,1C1C1A0可得图（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B等价，可将DFA最小化，即：删除B，将原来引向B的引线引向与其等价的状态A，有图(a2)。（DFA的最小化，也可看作将上表中的B全部替换为A，然后删除B所在的行。） （a1）确定化的DFA （a2）最小化的DFA（b）:该图已经是DFA。下面将该DFA最小化：(6) 首先将它的状态集分成两个子集：P1=0,P2=1,2,3,4,5(7) 区分P2：由于F(4,a)=0属于终态集，而其他状态输入a后都是非终态集，所以区分P2如下：P21=4,P22=1,2,3,5。(8) 区分P22:由于F(1,b)=F(5,b)=4属于P21,而F(2,b)与F(3,b)不等于4,即不属于P21，所以区分P22如下：P221=1,5,P222=2,3。(9) 区分P221:由于F(1,b)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5等价。(10) 区分P222:由于F(2,a)=1属于P221，而F(3,a)=3属于P222,所以2，3可区分。P222区分为P22212，P22223。(11) 结论：该DFA的状态集可分为：P= 0,1,5,2,3,4 ,其中1,5等价。删去状态5，将原来引向5的引线引向与其等价的状态1，有图(b1)。(b1)最小化的DFA36、构造一个DFA，它接收=0，1上所有满足如下条件的字符串：每个1都有0直接跟在右边。然后再构造该语言的正则文法。解：根据题意，DFA所对应的正规式应为：(0|(10)*。所以，接收该串的NFA如下：下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B0,2C1B0,2B0,2C1C1B0,2显然，A，B等价，所以将上述DFA最小化后有：对应的正规文法为：GA：A1C|0A|C0A37、给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0解：把后两个产生式代入第一个产生式有：S=01|01SS=10|10S有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10)*(01|10)即:(01|10)*(01|10)为所求的正规式。38、对文法GSSa|(T)TT,S|S(1) 给出(a,(a,a)和(a,a),(a),a)的最左推导。(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3) 经改写后的文法是否是LL(1)的？给出它的预测分析表。(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。解：(1) (a,(a,a)的最左推导为S(T)(T,S)(S,S)(a,(T)(a,(T,S)(a,(S,a) (a,(a,a)(a,a),(a),a)的最左推导为S(T)(T,S)(S,a)(T),a)(T,S),a)(T,S,S),a)(S,(T),a)(T),(S),a) (T,S),(a),a)(S,a),(a),a)(a,a),(a),a)(2)由于有TT,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/S:Sa|(T)TSUU，SU|分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序。(1) 对于每个非终结号U，编写一个相应的子程序P(U)；(2) 对于规则U:=x1|x2|.|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：IF CH IN FIRST(x1) THEN P(x1)ELSE IF CH IN FIRST(x2) THEN P(x2)ELSE .IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序；P(xj)为相应的子程序。(3) 对于符号串x=y1y2.yn;p(x)的含义为：BEGIN P(y1);P(y2);.P(yn);END如果yi是非终结符，则P(yi)代表调用处理yi的子程序；如果yi是终结符，则P(yi)为形如下述语句的一段子程序IF CH=yi THEN READ(CH) ELSE ERROR即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中，否则表明出错。(4) 如果文法中有空规则U:=EPSILON,则算法中的语句IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR改写为：IF CH IN FIRST(xn) THEN P(xn)ELSE IF CH IN FOLLOW(U) THEN RETURN ERROR(5) 要分析一个OrgStr,应在该串的后面加上一个串括号#,并从子程序P(S)(S为文法的开始符号)开始，如果中途没有产生错误，并且最后CH=#,则说明OrgStr串合法，否则该串不合法。对每个非终结符写出不带回溯的递归子程序如下：char CH;/存放当前的输入符号void P_S()/非终结符S的子程序if(CH=a) READ(CH);/产生式Saelse if(CH=) READ(CH);/产生式Selse if(CH=()/产生式S(T)READ(CH);P_T();IF (CH=) THEN READ(CH) else ERRORelse ERR;void P_T()/非终结符S的子程序if(IsIn(CH,FIRST_SU) /FIRST_SU为TSU的右部的FIRST集合P_S();P_U();void P_U()/非终结符U的子程序if(CH=,)/产生式U，SUREAD(CH);P_S();P_U();else/产生式Uif(IsIn(CH,FOLLOW_U) /FOLLOW_U为U的FOLLOW集合return ;else ERR;(3)判断文法G/S是否为LL(1)文法。各非终结符的FIRST集合如下：FIRST(S)=a,（FIRST(T)=FIRST(S)=a,（FIRST(U)=，,各非终结符的FOLLOW集合如下：FOLLOW(S)=# FIRST(U) FOLLOW(T) FOLLOW(U)=#,，,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)每个产生式的SELECT集合如下：SELECT(Sa)=aSELECT(S)=SELECT(S(T)=(SELECT(TSU)=FIRST(S)=a,（SELECT(U，SU)=，SELECT(U)=FOLLOW(U)=)可见，相同左部产生式的SELECT集的交集均为空，所以文法G/S是LL(1)文法。文法G/S的预测分析表如下：a()，#Sa(T)TSUSUSUU，SU(5) 给出输入串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式123456789101112#S#)T(#)T#)US#)Ua#)U#)US,#)US#)Ua#)U#)#(a,a)#(a,a)#a,a)#a,a)#a,a)#,a)#,a)#a)#a)#)#)#S(T)( 匹配TSUSaa匹配U，SU,匹配Saa匹配U)匹配接受39、对下面的文法G：ETE/E/+E|TFT/T/T|FPF/F/*F/|P(E)|a|b|(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2) 证明这个方法是LL(1)的。(3) 构造它的预测分析表。(4) 构造它的递归下降分析程序。解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E/)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T/)=FIRST(T)=(,a,b,;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F/)=FIRST(P)=*,;FIRST(P)=(,a,b,;FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E/)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;/不包含FOLLOW(T/)=FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;/不包含FOLLOW(F/)=FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;FOLLOW(P)=FIRST(F/)FOLLOW(F)=*,(,a,b,+,),#;/不包含(2)证明这个方法是LL(1)的。各产生式的SELECT集合有：SELECT(ETE/)=FIRST(T)=(,a,b,;SELECT(E/+E)=+;SELECT(E/)=FOLLOW(E/)=),#SELECT(TFT/)=FIRST(F)=(,a,b,;SELECT(T/T)=FIRST(T)=(,a,b,;SELECT(T/)=FOLLOW(T/)=+,),#;SELECT(FPF/)=FIRST(P)=(,a,b,;SELECT(F/*F/)=*;SELECT(F/)=FOLLOW(F/)=(,a,b,+,),#;SELECT(P(E)=(SELECT(Pa)=aSELECT(Pb)=bSELECT(P)=可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是LL(1)文法。(3)构造它的预测分析表。文法GE的预测分析表如下：+*()ab#ETE/TE/TE/TE/E/+ETFT/FT/FT/FT/T/TTTTFPF/PF/PF/PF/F/*F/P(E)ab(4)构造它的递归下降分析程序。对每个非终结符写出不带回溯的递归子程序如下：char CH;/存放当前的输入符号void P_E()/非终结符E的子程序if(IsIn(CH,FIRST_TEP) /FIRST_TEP为TTE/ 的右部的FIRST集合，产生式ETE/P_T();P_EP();else ERR;void P_EP()/非终结符E/的子程序if(CH=+) /产生式E/+EREAD(CH);P_E();else/产生式E/if(IsIn(CH,FOLLOW_EP) /FOLLOW_EP为E/的FOLLOW集合return ;else ERR;void P_T()/非终结符T的子程序if(IsIn(CH,FIRST_FTP) /FIRST_TEP为TFT/ 的右部的FIRST集合，产生式TFT/P_F();P_TP();else ERR;void P_TP()/非终结符T/的子程序if(IsIn(CH,FIRST_T) /FIRST_T为产生式T/T 的右部的FIRST集合，产生式T/TP_T();else/产生式T/if(IsIn(CH,FOLLOW_TP) /FOLLOW_TP为T/的FOLLOW集合return ;else ERR;void P_F()/非终结符F的子程序if(IsIn(CH,FIRST_PFP) /FIRST_PFP为FPF/ 的右部的FIRST集合，产生式FPF/ P_P();P_FP();else ERR;void P_FP()/非终结符F/的子程序if(CH=*) /产生式F/*F/READ(CH);P_FP();else/产生式F/if(IsIn(CH,FOLLOW_FP) /FOLLOW_FP为F/的FOLLOW集合return ;else ERR;void P_P()/非终结符P的子程序if(CH=()READ(CH);P_E();if(CH=) READCH(CH);elseERR;else if(CH=a) READ(CH);else if(CH=b) READ(CH);else if(CH=) READ(CH);else ERR;40、已知文法GS：SMH|aHLSo|KdML|LeHfMK|bLM判断G是否是LL（1）文法，如果是，构造LL（1）分析表。解：首先求各非终结符的FIRST集合：FIRST(S)=aFIRST(M)FIRST(H)=ab,d,e,=a,b,d,e,;FIRST(H)=FIRST(L)=e,;FIRST(K)=d,;FIRST(L)=e;FIRST(M)=FIRST(K)b=b,d,;然后求非终结符的FOLLOW集合：FOLLOW(S)=o,#FOLLOW(H)=FOLLOW(S)f=f,o,#FOLLOW(K)=FOLLOW(M)=FIRST(H)FOLLOW(S)=e,o,#;/不包含FOLLOW(L)=FIRST(S)oFOLLOW(K)FIRST(M)FOLLOW(M)=a,b,d,e,o,#FOLLOW(M)=a,b,d,e,o,#;/不包含FOLLOW(M)=FIRST(L)FIRST(H)FOLLOW(S)=e,o,#/不包含最后求各产生式的SELECT集合：SELECT(SMH)=(FIRST(MH)-)FOLLOW(S)=b,d,eo,#=b,d,e,o,#;SELECT(Sa)=aSELECT(HLSo)=eSELECT(H)=FOLLOW(H)=f,o,#SELECT(KdML)=dSELECT(K)=FOLLOW(K)=e,o,#SELECT(LeHf)=eSELECT(MK)=(FIRST(K)-)FOLLOW(M)=d,e,o,#SELECT(MbLM)=b可见，相同左部产生式的SELECT集的交集均为空，所以文法GS是LL(1)文法。文法GE的预测分析表如下：aodefb#SaMHMHMHMHMHHLSoKdMLLeHfMKKKbLMK41、设有基本块 T1：2 T2：10/T T3：SR T4：SR A：T2 *T4 B：A T5：SR T6：T3 *T5 B：T6 (1)画出DAG图； (2)假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。解：(1)DAG： (2) 优化后的四元式 T3：SR T4：SR A：5*T4 B：T3T442、假定有一个猎人带着一只狼、一头山羊和一棵白菜来到一条河的左岸，拟摆渡过河，而岸边只有一条小船，其 大小仅能装载人和其余三件东西中的一件，也就是说，每一次猎人只能将随行者中的一件带到彼岸。若猎人将狼和山羊留在同一岸上而无人照管，那么，狼就会将羊吃掉；如果猎人把山羊和白菜留在同一岸，山羊也会把白菜吃掉。现在，请你用状态转换图作为工具，描述猎人可能采取的种种摆渡方案，并从中找出可将上述三件东西安全地带到右岸的方案来。解：假设W:表示载狼过河，G:表示载山羊过河，C:表示载白菜过河用到的状态1：狼和山羊在左岸2：狼和白菜载左岸3:羊和白菜在左岸 4:狼和山羊在右岸5:狼和白菜在右岸 6:山羊和白菜在右岸F:全在右岸43、5.2考虑下面的属性文法：Z sX attribution: Z.a=X.c; X.b=X.a； Z.p=X.b； Z t X attribution： X.b=X.d; Z.a=X.b; X u attribution: X.d=1; X.c=X.d; X V attribuion: X.c=2; X.d=X.c; (1) 上述文法中的属性哪些是继承的?哪些是综合的? (2) 上述文法中的属性依赖是否出现了循环? 解：综合属性有：Z.aZ.pX.dX.c 继承属性有：X.b属性依赖出现了循环