编译原理(第2版)第二版课后习题答案2.pdf

第三章N=D=0,1,2,3,45,6,7,8,9N=ND=NDDL=a|a(0|l|3.|9)n 且 n=l(0|l|39)n 且 n=lab,an bn n =1第6题.表达达=项=因子=i(2)表达达=项=因子=(表达达)=(项)=(因子)=Xi)(3)表达达=项=项*因子=因子*因子=1*1(4)表达达 =表达达 +项=项+项=项*因子+项=因子*因子+项=因子*因子 +因子=i*i+i(5)表达达 =表达达 +项 =项+项=因子 +项=i+项=i+因子 =i+(表达达)=i+(表达达 +项)=1+(因子+因子)=i+(i+i)(6)表达达 =表达达 +项=项+项=因子 +项=i+项=i+项 *因子 =i+因子 *因子 =i+i*i第 7 题+表 达 式 第9题语法树推 导：S=S S*=S S+S*=a a+a*1 1.推导:E=E+T=E+T*F语 法 树：直 接 短 语：T*F句 柄：T*F1 2.短通乐 T 直接短语挨TxF句柄:13.(1 最左推导左 S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa最右推导右 S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=al bl b2a2a3(2)文法：S ABSS AaS A aB b(3)短语语 al,bl,b2,a2,bb,aa,abbaa,直接短语接al,bl,b2,a2,句柄:al14(1)S ABA aAb|cB aBb|s(2)S ISOS AA 0Al|s第四章1.1.构造下列正规式相应的D F A(1)1(0|1)*1 0 1N F A(2)1(1 0 1 0*1 1(0 1 0)*1)*0N F A(3)N F A(4)NFA2.解：构 造DFA矩阵表示01X0ZXZ*X,ZYX.Z*X,ZX,YYX.YX.YX,Y,Z)XX.Y.Z)*X,Y,Z)X.Y其 中。表示初态，*表示终态用 0,1,2,3,4,5 分别代替X Z 用 Z得DFA状态图为：Y X,Y X,Y,Z)3.解：构 造DFA矩阵表示构 造DFA的矩阵表示01Sv,QQ,UV,QZ,VQ,UQ,UVQ,U,ZZ,V*ZVZQ,U,Z*V,ZQ,U,Z)ZZZ其 中 表示:町态，*表示终态替换后的矩阵010 12构造D F A 状态转换图(略)1322453*66465*35666转换为4.(1)解构造状态转换矩阵：ab 0 ,0,1 1 0,1 ,0,1 1 1 0 2,3 0,1 ab0,121,1220 2,3 a=0,3，0,1 0,l a=l,l 0,l b=2,22)解:首先把 M的状态幡分为两组：组0,和非终和非1,2,3,4,5此时6=(0,1,2,3,4力)l,2,3,4,3a=l,3,0,5(1,2,3,44b=4,3,2,5)由于4a=0 l,2,3,5a=l,3,5因此应此1,2,3,4力划分为4,1,2,3,5)G=(0412,3,5)l,2,3,5a=1,3,5)1,2,3,5 b=4,3,2因为l,5b=4 23b=2,3所以应以1,2,3,5划分为1,5 2,3G=(O1,52,34)l,5a=l,5 l,5b=4所以1,5不用再划用2,3a=l,3 2,3b=3,2因 为2a=l 3a=3所以2,3应划分为23所以化简以化G=(0,2,3,4,1,5A a7.去除多余产1除多余产生造NFA如下确定化，构造DFA矩阵abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD变换为ab0131122*343354165*14634化简：G=(0,1,3,4,6),(2,5)0,1,3,4,6 a=l,3 0,1,3,4,6 b=2,3,4,5,6)所以将 0,1,3,4,6 划 分 为 0,4,6 1,3G=(0,4,6),(1,3),(2,5)(0,4,6 b=3,6,4)所以 划分为 0 ,4,6G=(0),(4,6),(1,3),(2,5)不能再划分，分 别 用 0,4,1,2 代表各状态，构造D F A 状态转换图如下;8.代入得S =O(1 S|1)|l(0 S|0)=0 1 (S|e )|1 0(S|e)=(0 1|1 0)(S|e)=(0 1 1 1 0)S|(0 1 1 1 0)=(0 1|1 0)*(0 1|1 0)构造N F A由 N F A 可得正规式为(0 1 1 1 0)*(0 1 1 1 0)=(0 1 1 1 0)*9.状态态转换函数不是镌，增加死状态8,G =(1,2,3,45,8)X6,7)(l,2,3,4,58)a=(3,4,8)(3,4 应分出(1,2,3,4,郛)b=(2,6,7,8)(l,2,3,4,58)c=(3,8)(l,2,3,4,58)d=(3,8)所以应以(1,2,3,4,郃访为(1,2,5,8)(3,4)G =(1,2,5,8)(3,4)(6,7)(1,2,5,8)a=(3,4,8)8应分出(l,2,5,8)b=(2,8)(1,2,5,8)6(8)(l,2,5,8)d=(8)G =(1,2,5)(8),(3,4)(6,7)(l,2,5)a=(3,4,8)5应分出G =(1,2),(3,4),5(6,7),(8)去掉死状态8,最终终结果(1,2)(3,4)5,(6,7)以1,3,5,6弋替，最简D F A为正规式：b*a(da|c)*bb*第五章1.s-a r|(T)T-T,S|S(a,(a,a)S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,a)S=(T)=(T,S)=(S,S)=(T),S)=(T,S),S)=(T,S,S),S)=(S,S,S),S)=(T),S,S),S)=(T,S),S,S),S)=(S,S),S,S),S )=(a,S),S,S),S)=(a,a),S,S),S)=(a,a),A,S),S)=(a,a),A,(T),S)=(a,a),A,(S),S)=(a,a),A,(a),S)=(a,a),A,(a),a)S-a r|(T)T-T,ST-S消除直接左递归:s-a r|(T)T-S TT-,S T|gSELECT(S-a)=aSELECT(S-A)=ASELECT(S-(T)=(SELECT(T-S T5)=a,A,(SELECT(T，-,S T，)=,SELECT(T-)=FOLLOW(T)=FOLLOW(T)=)构造预测分析表aA()#s-a-A-(T)TST-ST9 s rT，-,S T分 析 符 号 串（a,a）#分析栈剩余输入串所用产生式#s(a,a)#S-(T)#)T(a,a)#（匹配#)Ta,a)#T-S T#)r sa,a)#S-a#)r aa,a)#a 匹配#)r,a)#T 1 ,S F#)r s,a)#,匹配#)r sa)#S-a#)T，aa)#a 匹配#)r)#r -c#)#）匹配#接受2.E-TE E 2+E E-T-FT T5-T T-gP-(E)P-a P-b P-AF-PF F,-*F,F-非终结符名是否=eFIRST 集FOLLOW 集E否(,a,b,A)#，）E，是+,#，）T否(,a,b,A)+,#,)T，是 e,(,a,b,A)+,#,)F否(,a,b,A)(,a,b,+,#,)F，是*,2(,a,b,A,+,#,)P否(,a,b,A)*,(,a,b,3#,)SELECT(E-T E，)=FIRST(TE,)=FIRST(T)=(,a,b,A)SELECT(E5-+E)=+SELECT(E5-e)=FOLLOW(E,)=#,)SELECT(T-F T,)=FIRST(F)=(,a,b,A)SELECT(T5 T)=FIRST(T)=(,a,b,A)SELECT(T,-e)=FOLLOW(T,)=+,#,)SELECT(F-P F,)=FIRST(F)=(,a,b,ASELECT(F,-*F,)=*SELECT(F,-e)=FOLLOW(F,)=(,a,b,3 +,#,)3.S-MH S-a H-Lso H-K-dML K-&L-eHf M-K M-bLMFIRST(S)=FIRST(MH)=FIRST(M)UFIRST(H)U 殳 Ua=a,d,b,eFIRST(H)=FIRST(L)U 殳=e,1FIRST(K)=dFIRST(M)=FIRST(K)U(b=d,b,&FOLLOW(S)=#,oFOLLOW(H)=FOLLOW(S)Uf =f,#,oFOLLOW(K)=FOLLOW(M)=e,#,oFOLLOW(L)=FIRST(S)-坛 Uo UFOLLOW(K)U FIRST(M)-坛 UFOLLOW(M)=a,d,b,e,#,o)FOLLOW(M)=FIRST(H)殳 UFOLLOW(S)14 FIRST(L)-=e,#,oSELECT(S-MH)=(FIRST(M H)-)UFOLLOW(S)=(FIRST(M)UFIRST(H)-殳)UFOLLOW(S)=d,b,e,#,oSELECT(S-a)=aSELECT(H-LSo)=FIRST(LSo)=eSELECT(H-&)=FOLLOW(H)=f,#,o SELECT(K-dML)=dSELECT(K-)=FOLLOW(K)=e,#,oSELECT(L-eHf)=eSELECT(M-K)=(FIRST(K)焚)LFOLLOW(M)=d,e,#,oS E L E CT (M -b L M )=b 构 造 LL(1)分析表abedf0#s-a-M H-MH-M H-M H-M HHLSo-c-K-1-dM L-C-L-eH fM-bLM-K-K-K-K4.文法含有左公因式，变为S-C$b,aC-bA b C-aB aA-bAA b A-a A a S一否A一否A，一是B 一否C 一否D一否D，一是E一否F否A C$,a,b A9-C a,b B-a B BaB-b B9b$,a,b B-C a,b 5.v 程 序 S 语句表-A 语句-B 无条件语句-C 条件语句-D如果语句）-E 如果子句-FS-begin A endS-begin A end begin A-BA-BAa,ifA-A;BA5-;B A；end B-CB-C a B-DB-DifC-aC-aaD-ED-E DifD-E else BD-else B else D?&,end E-FCE-FCifF-if b thenF-if b thenif非终结符是否为空FIRST=begin FIRST(A)=FIRST(B)U FIRST(A)U =a,if,;,FIRST(V)=;,FIRST(B)=FIRST(C)U FIRST(D)=a,if FIRST(C)=aFIRST(D)=FIRST(E)=ifFIRSR(D,)=else,&FIRST(E)=FIRST(F)=if FIRST(F)=ifFOLLOW(S)=#FOLLOW(A)=endFOLLOWCV)=end FOLLOW(B)=;,end FOLLOW(C)=;,end,else FOLLOW(D)=;,end FOLLOW(D9)=;,end FOLLOW(E)=else,;end)FOLLOW(F)=aSA A B C D D E Fif then else begin end a b;ifthenelsebeginendab9#s-begin A endA-BA9 BAA，-；BA9B-D-CC-aD-ED9D5-else BD，-C-cE-FCF-if b then S A|B(2)A-aA|a(3)B-bB|b提 取(2),(3)左公因子 S-A|B(2)A-aA9(3)A|g(4)B-bB，B9-B|C2.(1)S-AB ABa|g B-Db|D(4)D-d|提 取(3)左公因子(1)S-AB(2)A-Ba|(3)B-DB(4)B，b D-d|C3.(l)S-aAaB IbAbB AS|db(3)B-bB|a4(1)S-i|(E)(2)E-E+S|E-S|S提 取(2)左公因子 S-i|(E)E-SE(3)E S E 1-S E”g5(1)S-SaA|bB(2)A-aB|c(3)B-Bb|d消 除(1)(3)直接左递归 S-bBS9SaA Sg A-aB|c(4)B-dB9(5)B，bB1gXI/lzXI/XI/1234(-ZIVz(v(1)M-MaH|H(2)H-b(M)|(M)|b消 除(1)直接左递归，提 取(2)左公因子M-HMM，aHM”H-bH91 (M)H9-(M)|C7.(1)1)A-baB2)A-3)B-Abb4)B-a将 1)、2)式代入3)式1)A-baB2)A-g3)B-baBbb4)B-bb5)B-a提取3)、4)式左公因子1)A-baB2)A-g3)BbB4)B,-aBbb|b5)B-a(3)1)S-Aa2)S-b3)A-SB4)B-ab将 3)式代入1)式1)S-SBa2)S-b3)A-SB4)B-ab消 除 1)式直接左递归1)S-bS2)S,-BaS,|3)S-b4)A-SB5)B-ab删除多余产生式4)1)S-bS92)S,-BaS,|3)S-b4)B-ab(5)1)S-Ab2)S-Ba3)A-aA4)A-a5)B-a提取3)4)左公因子1)S-Ab2)S-Ba3)A aA4)A|g5)B-a将 3)代 入 1)5)代入21)S-aA9b2)S-aa3)A-aA94)A9-A|g5)B-a提 取 1)2)左公因子1)S aS2)S Ab|a3)A-aA94)A9-A|g5)B-a删除多余产生式5)1)S-aS92)S，Ab|a3)AaA4)A，A|gA A S S将 3)代入4)1)S-aS2)S-A，b|a3)AaA4)A-aA|将 4)代入2)1)S-aS2)S，aA，b3)S9-a4)S，b5)A-aA6)A9-aA”C对 2)3)提取左公因子1)S-aS92)S S”3)S”一次b|C4)Sb5)A 4 a A 6)A5-aA”删除多余产生式5)1)S-aS92)S，aS”3)SAb|C4)Sb5)A-aA|第六章1S a I A I(T )T -T ,S|S解：(1)增 加 辅 助 产 生 式 S 9#S#求 F I R S T V T 集F I R S T V T (S )=#F I R S T V T (S)=a A(=a A (F I R S T V T (T)=,U F I R S T V T (S )=,a A(求 L A S T V T 集L A S T V T (S )=#L A S T V T (S)=a A)LASTVT(T)=,a A)(2)算符优先关系表aA()9#a A *(=9#=因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法(3)1A()9#F 1 11 1 11g 111 1 11f22 1321g22 21 21f33 1331g44 41 21f33 1331g44 41 21(4)栈优先关系当前符号剩余输入串移进或规约#(a,a)#移进#(a)#规约#(T 9a)#移进#(T,)#规约#(T,T*)#规约#(T=)#移进#(T)*#规约#T=#接受4.扩展后的文法S今#S#S-S;G S-G G-G(T)G-H H-a H(S)T 今 T+S T9S(1)FIRSTVT(S)=;U FIRSTVT(G)=;,a,()FIRSTVT(G)=(U FIRSTVT(H)=a,(FIRSTCT(H)=a,(FIRSTVT(T)=+U FIRSTVT(S)=+,;,a,()LASTVT(S)=;ULASTVT(G)=;,a,)LASTVT(G)=)U LASTVT(H)=a,)LASTVT(H)=a,)LASTVT(T)=+U LASTVT(S)=+,;,a,)构造算符优先关系表9()a+#(*=*a*+#=因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法(2)句型a(T+S);H;的短语有：a(T+S);H;(S)a(T+S);H a(T+S)a T+S(S)H直接短语有:a T+S H(S)句柄：a素短语：a T+S(S)最左素短语：a(3)分析 a；(a+a)分析 a；(a+a)栈优先关系当前符号剩余输入串移进或规约#(a+a)#规约#T(a+a)#移进#T；(a+a)#移进#T；(+a)#规约#T；(T+a)#移进#T；(T+)#规约#T；(T+T)#规约#T；(TL Z L )#移进#T；(T)#规约#T；T#规约#T-#接受(4)栈优先关系当前符号剩余输入串移进或规约#(a+a)#移进#(+a)#规约#(T+a)#移进#(T+)#规约#(T+T)#规约#(T-)#移进#(T)#规约#T-#接受不能用最右推导推导出上面的两个句子。第七章1、已知文法：A -*a A d|a A b|&判断该文法是否是S L R (1)文法，若是构造相应分析表，并对输入串a b#给出分析过程。解：(0)A f A(1)A a A d(2)A f a A b(3)A f g构造该文法的活前缀D F A：由上图i构造SL1 0：A f AA f a A dA f a A bA f a文,b：A f a A dA f a A bA f a A dA f a A bA 一,AI 3：A f a A dA a A b_d,a A b-I 4：A f a A d aR)3ibk:A -*U U 1 UA11A、a c cV小 -普R 33I i：A-*A F gyw(A)14R IR IR I5R 2R 2R 2输入串a b#的分析过程：步骤状态栈符号栈输入串A CT I O NG O T O10a b#S 220 2Uab#R 3330 23#a AbitS 540 235#a A b#R 2150 1能A#a c c3、考虑文法：S f A S|b A-S A|a(1)列出这个文法的所有L R (0)项目(2)按(1)列出的项目构造识别这个文法活前缀的N F A,把这个N F A 确定化为D F A,说明这个D F A的所有状态全体构成这个文法的L R(0)规范族。(3)这个文法是SL R的吗？若是，构造出它的SL R分析表。(4)这个文法是L A L R或 L R(1)的吗？解：(0)S-S (l)S-A S(2)S-b(3)A-SA (4)A-a(1)列出所有L R(0)项目：S，f sS f bSJf s-Sb S-*ASA f SAS一 A SA f S ASf AS A f SA A aA-a (3)构造该文法的活前缀NFA：由上可知：h I3 15中存在着移进和归约冲突在h中含项目：s，一 s 归约项F o llo w S )=#A-*a移进项Follow(S)A a=S一 b移进项Fol low(S*)Cl b=#在I3中含项目：A T A 归约项Fol low(A)=(a,bS一 b移进项Fol low(A)A bW$A a移进项Fol low(A)C l a W f在I5中含项目：s一 AS 归约项Follow(S)=#,a,bAf a移进项Fol low(S)0 a W$S一 b移进项Fol low(S)0 bW$由此可知，13、15的移进与归约冲突不能解决，所以这个文法不是SLR(1)文法。(4)做LR(1)项目集规范族Io：S 一 S,#S f A S,a/b/US b,a/b/#A -SA ,a/bA -*a,a/bS-S ，#A f S,A ,a/bA f SA ,a/bA f a,a/bS-*A S,a/bS f b,a/bs-AS,a/b/#s A S,a/b/#s b,a/b/#A f SA,a/bA-*a,a/bS-b ,a/b/#A f a ,a/b/#16：(IrS-)A -S A,a/bA 一 SA,a/bA -*a,a/bS 一 A S,a/bS 一 b,a/bI7：(l2-S-)S 一 A S,a/b/#A f S A,a/b/#A -SA,a/bA f a,a/bS 一 A S,a/bS-b,a/bk：A-SA ,a/bSf A S,a/bSf A S,a/bS-*b,a/bA-SA ,a/bA-*a,a/b由上可知该文法不是L R(1)文法，也不是L A L R(1)文法。5、一个类A L G OL 的文法如下：-;f begin d-;d-S end-S;-begin试构造其L R(0)分析表。解：设 Pr ogr am 二 A =B =C=D =EA-BA C B-*D；E D f begin d D-*D;d E-*s end E-*s;E C f begin E(O)A -A(1)A-B(2)A-C (3)B-*D;E (4)D-begin d(5)D f D;d(6)E-s end(7)E-s;E (8)C-begin E构造该文法的活前缀D F A：构造L R(0)分析表:状A C TI ONG OTO态begin*dSend#ABCDE0S512341acc2RIRIRIRIRIRI3R2R2R2R2R2R24S65S9S786SilS71 07S1 3S1 26、文法 G=(U,T,S,a,b,c,d,e,P,S)其中 P 为:8R8R8R8R8R8R89R4R4R4R4R4R41 0R3R3R3R3R3R31 1R5R5R5R5R5R51 2R6R6R6R6R6R61 3S71 41 4R7R7R7R7R7 rR7SfUTa|Tb T-S|Sc|d U-US|e(1)判断 G 是 L R(0),SL R(1),L A L R(1)还是 L R(1),说明理由。2)构构造相应的分析表解：(O)S?-S (l)S-U T a(2)STb(3)T-S (4)T Sc(5)Td(6)UUS(7)Ue首先做LR(0)分 析：10:S抻SS穰Ta S穰b U穰S U稹T穰T穰c T稣I1:S?S?TS(Il产生移进-颊约冲突，但Follow(S?)c=可以用SLR(D解决)12:SU 1兹a UU穰S粳Ta S移b U粳S U稹T糠T秣c T稣I3:ST.b14:Ue?I5:Td?I6:TSc?I7:SUT 樨 ST 概I8:UUS?TS?TS穆产生移进一规约喝规约一规约冲突 F ollow(U)=d,e F ollow(T)=a,b可以用SL R(1)的方法解决1 9:SUTa 1 1 0:S9 Tb 所以该文法是SL R(1)文法，也是L A L R(1)文法，L R(1)文法。构造SL R(1)分析表:状态ACTIONGOTOabcde#SUT0S12s n1231S6acc2S5S48273S104R7R75R5R56R4R47S9S108R3R3S6R6R69RIRIRIRI10R2R2R2R27证明下面文法不是L R(0)但是SL R(1).SfA A-A b|bB a B-aA c|a|aA b证明：(0)S-S(1)S-A (2)A-A b(5)B-a(6)B-aA b(3)A-bB a(4)B-aA c构造该文法的活前缀D F A：19：B f aAb,A f Ab,在k项目集中含有：S-A 归约项A-A b 移进项在L项目集中含有：B-a 归约项A f bBa 移进项在19项 目 集 中 有B-aAb 规约项A fA b 规约项Follow(B)D文法的冲突项可以用SLR(1)文法来解Follow(S)=#Fol low(S)D b=0Follow(B)=aFol low(B)D b=0Follow(B)=aFollow(A)=b,c,#)Follow(A)=f夬，所以该文法是SLR(1)文法，不是LR文法。11、设文法G 法为:S-A S|&A-*aA|b(1)证明G S是LR(1)文法；(2)构造它的LR(1)分析表；(3)给出输入符号串abab#的分析过程。解：(0)S-S (l)S-A S(2)(3)A-aA(4)A-b证明：构造该文法的活前缀DFA：S在该文法Io,1 2 中出现了归约一一移进冲突，由于归约项目的搜索符集合与移进项目的待移进符号不相交，所以在Io，b 中当面临输入符为#时归约，为 a或 b 时移进。所以该文法是LR(1)文法。构造它的LR(1)分析表:状态A C TI ONG OTOab#SA0S3S4R2121acc2S3S4R2523S3S464R4R4R45RI6R3R3R3构造输入符号串abab#的分析过程:步骤状态栈符号栈输入串A C TI ONG OTO10#abab#S320 3t t abab#S430 3 4#abab#R4640 3 6#aAab#R3250 2#Aab#S360 2 3#A ab#S470 2 3 4#A abR4680 2 3 6#A aA#R3290 2 2#A A#R251 00 2 2 5#A A S#RI51 10 2 5#A S#RI11 20 1#S#acc1 6、给定文法：S-*do S or S|do S|S;S|act(1)构造识别该文法活前缀的D F A o(2)该文法是L R(0)吗？是 SL R(1)吗？说明理由。(3)若对一些终结符的优先级以及算符的结合规则规定如下：a)or 优先性大于do；b);服从左结合；c)；优先性大于皿；d);优先性大于更；请构造该文法的L R分析表。解：(O)S-S(l)S-do S or S(2)S-do S(3)S-S;S(4)S-act构造该文法的活前缀D F A：由上可知：在L中含有项目：SS S-S ；s归约项目移进项目F ollow(S*)=#F ollows )n ；=f在1 4中含有项目：s-d o S-S-*do S,or SS-S ；s归约项目 F ollow(s)=#,or,；)移进项目 F ol low(s)D or f移进项目 F ol low(s)A ；#$在I 5中含有项目：S-S;S S-S ;S归约项目移进项目F ollow(s)=#,or,；F ol low(s)A ；r$在I7中含有项目：S-*do S or S S-S ;S归约项目 F ollow(s)=#,or,；移进项目 F ollow(s)D ；K 4所以该文法不是L R(0),也不是SL R(1)文法。根据算符优先关系构造该文法的L R分析表：状态ACTIONGOTODooract#S0S2S811S3acc2S2S843S2S854S6S3R25R3R3R36S2S877RIS3RI1 8、对算术表达式文法G E ；E-*E +T|T T-*T*F|F F-(E)|i(1)构造算符优先关系表和LR 分析表，并对G E 进行适合的改写后构造预测分析表。(2)分别使用三种表对句子i+i*i#进行分析。(3)对于错误的输入串：(i+(*i)#和*+i)+(i*#分别查看错误的发现时刻和输入串出错的位置。解：(1)构造算符优先关系表，文法扩展后为E f#E#E E+T ET T T*F T F F-(E)FTF i rst VT(E)=悔 L a st VT(E )=#F i rst YT(E)=+,*,(,i L a st VT(E)=+,*,),i F i rst VT(T)=*,(,i L a st VT(T)=*,),i F i rst VT(F)=(,i L a st VT(F)=),i 构造算符优先关系表：+*()i#+*(=i#T*F (4)T-F (5)F 今(E)F i1 0：E -E E f E+T E 9 T T-T*F T f F F-(E)F 玲 iI I:E -E E f E +T(I l产生移进一规约冲突，但 F ollow (E )n+=,可以用SL R (1)解决)1 2：E 今T T T *F(1 2 产生移进一规约冲突，但 F ollow (E)C *=0 可以用S L R(l)解决)1 3:T-F 1 4:F 9(E)E f E+T1 5:F-i 1 6:E E+T T 少 T*F1 7:T fT*F F 9 (E)1 8:F-(E )E fE +T1 9:E 今E+T T f T *FE f T T 9 T*FT-F F 9 (E)F-iT 玲 F (E)F-iF 9 -i(1 2 产生移进一规约冲突，但 F ollow (E)H *=1 可以用SL R (1)解决)1 1 0:T 9T*F I ll:F f (E)构造SL R (1)分析表状态ACTION GOTO+*()i#ETF0S4S51231S6acc做LL（1）分析：消除左递除左递归，文ETE?2R2S7R2R23R4R44S4S58235R6R6R6R66S4S5937S4S5108S6Sil9RIS7RIRI10R3R3R3R311R5R5R5R5E?TE?E?eTFT?T?FT?T生F(E)Fi求selec麋select(ETE1)=first(TE?=first(T)=first(FT)=first(F)=(,i)select(E?TE?=+SELECT(E%)=Follow(E=Follow(E)=#,)SELECT(TFT)=first(F)=(,iSelect(T?FT?)=*Select(T=folio w(T)=+,),#Select(F(B)=(Select(Fi)=i构造预测分析表1*()i#E)T E-T E E，)+T E 今TWTFT9e9*FT-)F9(E)第八章w hi le a b or c d a nd e f d oi f x y t he n t:=m+n1 0 0：i f a b g ot o 1 0 61 0 1:g ot o 1 0 21 0 2:i f c d g ot o 1 0 41 0 3:g ot o 1 1 11 0 4:i f e f g ot o 1 0 61 0 5:g ot o 1 1 11 0 6:i f xB then while AC do A:=A-Belse if D and F then A:=A+100100:if AB goto 102101102103104105106107108109110111112goto 107if AC goto 104goto 114tl:=A-BA:=tlgoto 102goto 114if D goto 110goto 114if F 112goto 114t2:=A+100113 A:=t21 1 4补充习题1 .对下列各语言写出它们的正规表达式和有限自动机(a)字母表 a,b,c 上的串，其中第一个a先于第一个b解：我们关心的状态是什么时候出现了第一个a,可以设出现第一个a后的状态为1,出现第一个a之前的状态为0.必须保证在状态1 之前不能出现b:a,b,c转换为4*t a|b|c)*1(b)其中有偶数个a的字母表 a,b,c 上的串解：我们关心的状态是a的个数的奇偶性，可以设定偶数个a时的状态是0,奇数个a的状态是1,我们要偶数个a,因此。状态是终结状态：(b|c)*(a (b|c)*a)*(c)0,1 上的串，该串看成二进制是4的倍数解：A=(0 1 1)*0 0(d)0,1 上不含子串0 1 1的串解：我们关心的状态是出现0 1时，这时只要保证0 1后不能是1即可:1 0 02 y(e)0,1 上的串有偶数个0和奇数个1解：我们关心的状态是0和1的奇偶性，组合情况有4个:0：偶数个0,偶数个1I：偶数个0,奇数个I 一一终结状态2:奇数个0,偶数个13：奇数介7,奇数个1(0(1 1)*0)*(1 I 0(1 1)*1 0 )(0 0 I 0 1(1 1)*1 0|(1|0 1(1 1 )*0)(0 (1 1)*0)*(1 I 0 (1 1)*1 0)*2.试从文法G sS-(L)|aL 9L,S|S中消除左递归,并为之构造一个递归预测分析器和L L(1)分析表.请说明句子(a,(a,a)在L L(1)分析器中的动作.解：改写为S-(L)|aL 今 SL L f e|,SL SE L E C T(S-(L)=(SE L E C T(S9 a)=a SE L E C T(L Sf )=(,a SE L E C T(f 今 e)=)SE L E C T(f 今，SL )=,非终结符是 否*eF I R ST 集F OL L OW 集S否(,a)#,)L否(,a)L 是 一)预测分析表:(a)S今(D-aL今SL 6 SI/L，今，SL 今 e对符号串（a,（a,a）#的分析过程步骤分析栈剩余输入串所用产生式1#s(a,(a,a)#s 9(L)2#)L(a,(a,a)t t（匹配3#)La,(a,a)#L SL 4#)L Sa,(a,a)#S-a5#)L aa,(a,a)#a 匹配6#)1 7,(a,a)#L,6,SL 7#)1 7 S,(a,a)#,匹配8#)L S(a,a)#S-(L)9#)1 7)L(a,a)#（匹配1 0#)1 7)La,a)#L 今 SL 1 1#)1 7)1 7 Sa,a)#S9a1 2#)1 7)f aa,a)#a匹配1 3#)1 7)1 7,a)冲L 9,SL 1 4#)1 7)1/S,a)#,匹配1 5#)1 7)1/Sa)#ST a1 6#)1 7)f aa)#a匹配1 7#)1 7)1/)#L 9 e1 8#)1 7)#）匹配1 9#)1 7)#L 今 e2 0#)#）匹配2 1#接受步骤分析栈剩余输入串所用产生式1#s(a,(a,a)#S9(L)2#)L(a,(a,a)#（匹配3#)La,(a,a)#L 9SL 4#)1/Sa,(a,a)#S-a5#)L,aa,(a,a)#a ,匹配6#)L(a,a)#L f SL 7#)L S(a,a)#s今(D8#)L )L(a,a)#（匹配9#)1 7)La,a)#L 9SL 1 0#)L )f Sa,a)#ST a1 1)1 7)1/aa,a)#a匹配1 2#)1 7)1/,a)#f 9,SI/1 3#)1 7)f S,a)#,匹配1 4#)1 7)f Sa)#S今a1 5#)1 7)1 7 aa)#a匹配1 6#)7)f)#L -e1 7#)L，)#）匹配1 8#)1 7)#L 1 9#)#）匹配2 0#接受3.对于文法G b e xprb e xpr-b e xpr or b t e rm|b t e rmb t e rm-b t e rm a nd b f a c t or|b f a c t orb f a c t or-not b f a c t or|(b f a c t or)|t ru e|f a lse构造一个预测分析器解：b e xpr：S b t e rm：A b f a c t or：B原文法变为：S今S or A|AA今A a nd B|BB-not B|(B)|t ru e|f a lse改写为：SASS 今 e|or AS，A9BAA 今|a nd BAB-not B|(B)|t ru e|f a lse非终结符是否*“eF I R ST 集F OL L OW 集S否 not ,(,t ru e ,f a lse )#是 or e#A否 not ,(,t ru e ,f a lse )#,orA,是 a nd#,orB否not ,(,t ru e ,f a lse#,),a nd)SE L E C T(S-ASJ)=not ,(,t ru e ,f a lse SE L E C T (S,-)=#SE L E C T(S)今or AS)=orSE L E C T(A-BAJ)=not ,(,t ru e ,f a lse SE L E C T(A;9 e)=#,or SE L E C T(A)-a nd BA,)=a nd SE L E C T (B not B)=not SE L E C T (B 今(B)=(SE L E C T(Bft ru e)=t ru e SE L E C T(Bf