2025年《编译原理》课程复习1.pdf

该【2025年《编译原理》课程复习1 】是由【小屁孩】上传分享，文档一共【33】页，该文档可以免费在线阅读，需要了解更多关于【2025年《编译原理》课程复习1 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..为天地立心,为生民立命,为往圣继绝学,为万世开太平。——张载《编译原理》课程复习五、计算题:1、考虑下面程序…………Vara:integer;ProcedureS(X);VarX:integer;Begina:=a+1;X:=a+XEnd;Begina:=5;S(a);Print(a):若参数传递方式分别采取传名和传值时,程序执行后输出a的值是什么?答:传名:a=12传值:a=62、写出表达式(a+b*c)/(a+b)-d的逆波兰表示及三元式序列。逆波兰表示:abc*+ab+/d-三元式序列:①(*,b,c)②(+,a,①)③(+,a,b)④(/,②,③)⑤(-,④,d)3、已知文法G(S)S→a|∧|(T)T→T,S|S写出句子((a,a),a)的规范归约过程及每一步的句柄。句型归约规则句柄((a,a),a)S→aa((S,a),a)T→SS((T,a),a)S→aa((T,S),a)T→T,ST,S((S),a)T→SS((T),a)S→S(T)(T)(S,a)T→SS(T,a)S→aa:..人人好公,则天下太平;人人营私,则天下大乱。——刘鹗(T,S)T→T,ST,S(T)S→(T)(T)S4、写一个文法,使其语言是奇数集,且每个奇数不以0开头。解:文法G(N):N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D5、设文法G(S):S→(L)|aS|aL→L,S|S(1)消除左递归和回溯;(2)计算每个非终结符的FIRST和FOLLOW;(3)构造预测分析表。解:S→(L)|aS’S’→S|εL→SL’L’→SL’|εFIRST)S)={(,a}FOLLOW(S)={#,,,)}FIRST(S’)={,a,ε}FOLLOW(S’)={#,,,)}FIRST(L)={(,a}FOLLOW(L)={)}FIRST(L’)={,,ε}FOLLOW(L’)={}}6、Whilea>0∨b<0doBeginX:=X+1;ifa>0thena:=a-1elseb:=b+1End;翻译成四元式序列。解:(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)E→T|E+TT→F|T*FF→(E)|i(1)给出句型(T*F+i)的最右推导及画出语法树;(2)给出句型(T*F+i)的短语、素短语。解:(1)最右推导:E→T→F→(E)→(E+T)→(E+F)→(E+i)→(T+i)→(T*F+i)(2)短语:(T*F+i),T*F+i,T*F,i素短语:T*F,i8、设布尔表达式的文法为E→E(1)∨E(2)E→E(1)∧E(2)E→i假定它们将用于条件控制语句中,请(1)改写文法,使之适合进行语法制导翻译和实现回填;(2)写出改写后的短个产生式的语义动作。解:(1)E0→E(1)E→E0E(2)EA→E(1)E→EAE(2)E→i(2)E→E(1){BACKPATCH(E(1)·FC,NXQ);E0·TC:=E(1)·TC}E→E0E(2){E·FC:=E(2)·FC;E·TC:=MERG(E0·TC,E(2)·TC)}EA→E(1){BACKPATCH(E(1)·TC,NXQ);E0·FC:=E(1)·FC}E→EAE(2){E·TC:=E(2)·TC;E·FC:=MERG(EA·FC,E(2)·FC}E→i{E·TC:=NXQ;E·FC:=NXQ+1;GEN(jn2,entry(i),-0);GEN(j,-,-,0)9、设有基本块T1:=2T2:=10/TT3:=S-R:..老当益壮,宁移白首之心;穷且益坚,不坠青云之志。——唐·王勃T4:=S+RA:=T2*T4B:=AT5:=S+RT6:=T3*T5B:=T6假设基本块出口时只有A,B还被引用,请写出优化后的四元序列。解:优化后的四元式T3:=S-RT4:=S+RA:=5*T4B:=T3*T410、给定文法G=({S,L},{a,(,)},{S→(L)|aL→L,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)S→aA|bBA→aS|bC|eB→bS|aCC→bA|aB12、将文法G[S]:S→[AA→AS|B]B→Bi|i改写为等价的LL(1)文法,并给出相应的LL(1)分析表。解:B→iCC→iC|eA→B]A’A’→ASA’|eS→[AFirst(ASA’)={i},FOLLOW(A’)={[]FIRST(iC)={i},FOLLOW(C)={}}可知文法满足LL(1)文法的条件。分析表::..去留无意,闲看庭前花开花落;宠辱不惊,漫随天外云卷云舒。——《幽窗小记》13、化简文法G[S]:S→ASe|BCaD|aD|ACA→Cb|DBSC→bC|dB→AcD→aD解:化简后:S→ASe|ACA→CbC→bC|d14、设Lí{a,b,c}*是满足下述条件的符号串构成的语言:(1)若出现a,则其后至少紧跟两个c;(2)若出现b,其后至少紧跟一个c。试构造识别L的最小化的DFA,并给出描述L的正规表达式。解:DFA如图所示。相应的正规式为(c|acc|bc)*。15、已给文法G[S]:S→SaP|Sf|PP→qbP|q将G[S]改造成LL(1)文法,并给出LL(1)分析表。解:改造后的文法:S→PS'S'→aPS'|fS'|eP→qP'P'→bP|e各候选式的FIRST集,各非终结符的FOLLOW集为产生式FIRST集FOLLOW集S→PS'{q}{#}S'→aPS'{a}{#}→fS'{f}→e{e}P→qP'{q}{a,f,#}P'→bP{b}{a,f,#}→e{e}LL(1)分析表为16、给定文法G[S]:S→Aa|dAb|Bb|dBaA→cB→c,构造文法G[S]的LR(1)分析表。:..以家为家,以乡为乡,以国为国,以天下为天下。——《管子》解:分析表如下图所示17、将下面的条件语句表示成逆波兰式和四元式序列:ifa>bthenx:=a+b*celsex:=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*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+F假定出基本块后,只有A、C、E是活跃的,给出用DAG图完成优化后的代码序列。解:化简后的的四元式序列为D:=E+FA:=D+12E:=E+FC:=2819、试构造生成语言L={anbnci|n?1,i?0}的文法:..志不强者智不达,言不信者行不果。——墨翟解:G(Z):Z→ABA→aAb|abB→cB|ε?20、已知语言L={anbbn|n31},写出产生L的文法。[解]:G[S]:S→aAbA→aAb|b21、已知文法G=({A,B,C},{a,b,c},A,P),其中产生式P由以下组成:A→abcA→aBbcBb→bBBc→bC→CbaC→aaBaC→aa问:此文法表式的语言是什么?[解]:由于A为开始符。由于A→aBbc→abBc→→→语言为:{,n>0}22、试构造语言L={anbnci|n>=1,i>=0}的文法。[解]:G(Z):Z→ABA→aAb|abB→cB|ε?23、试写一文法,使其描述的语言L(G)是能被5整除的整数集合。解:G(Z):Z→(+|-)A(0|5)A→0|1|2|3|4|5|6|7|8|9|AA|e24、已知语言L={x|x?{a,b,c}*,且x重复排列是对称的(aabcbaa,aabbaa,等)写出该语言的文法。解:G(Z):Z→aZa|bZb|cZc|a|b|c|ε25、写能被5整除的十进制整数的文法及正则表达式。解:能被5整除的文法:G[Z]:Z→(+|-)A(0|5)A→0|1|2|3|4|5|6|7|8|9|AA|ε如果要求:除零以外不以0开头,则文法为:G[Z]:Z→(+|-)A(0|5)A→AB|CB→0|C|BBC→0|1|2|3|4|5|6|7|8|9正则表达式:G[Z]:Z=(+|-)A*(0|5)A∈(0,1,2,3,4,5,6,7,8,9)26、写一个文法,使其语言是奇数集,且每个奇数不以0开头。解:文法G(N):N→AB|B:..英雄者,胸怀大志,腹有良策,有包藏宇宙之机,吞吐天地之志者也。——《三国演义》A→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D27、写出能被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)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:S?PD|DP->NP|ND?0|2|4|6|8N->0|1|2|3|4|5|6|7|8|9(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)P:S?PD|P0|DP->NR|NR->QR|QD?2|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语法树见下图:(1)i(2)(i)(3)i*i<表达式><表达式><表达式><项><项><项><因子><因子><项>*<因子>i(<表达式>)<因子>i<项>i<因子>i(4)i*i+i(5)i+(i+i)(6)i+i*i<表达式><表达式><表达式><表达式>+<项><表达式>+<项><表达式>+<项><项><因子><项><因子><项><项>*<因子><项>*<因子>i<因子>(<表达式>)<因子><因子>i<因子>ii<表达式>+<项>iii<项><因子><因子>ii30、为句子i+i*i构造两棵语法树,从而证明下述文法G[<表达式>]是二义的。<表达式>::=i|(<表达式>)|<表达式><运算符><表达式><运算符>::=+|-|*|/解:为句子i+i*i构造的两棵语法树如下::..百川东到海,何时复西归?少壮不努力,老大徒伤悲。——汉乐府<表达式><表达式><表达式>+<表达式><表达式>*<表达式>i<表达式>*<表达式><表达式>+<表达式>iiiii所以,该文法是二义的。31、令文法G[E]为:E?T|E+T|E-TT?F|T*F|T/FF?(E)|i证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。解:可为E+T*F构造一棵语法树(见下图),所以它是句型。EE+TT*F从语法树中容易看出,E+T*F的短语有:T*F是句型E+T*F的相对于T的短语,也是相对于规则T?T*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为01101012341下表由子集法将NFA转换为DFA:II=ε-closure(MoveTo(I,0))I=ε-closure(MoveTo(I,1))01A[0]B[1]B[1]B[1]C[1,2]C[1,2]D[1,3]C[1,2]D[1,3]B[1]E[1,2,4]E[1,4]B[1]B[1,4]:..博学之,审问之,慎思之,明辨之,笃行之。——《礼记》001101ABCDE110,1(2)1(1010*|1(010)*1)*0对应的NFA为εε11010**********εε1001789ε下表由子集法将NFA转换为DFA:II=ε-closure(MoveTo(I,0))I=ε-closure(MoveTo(I,1))01A[0]B[1,6]B[1,6]C[10]D[2,5,7]C[10]D[2,5,7]E[3,8]B[1,6]E[3,8]F[1,4,6,9]F[1,4,6,9]G[1,2,5,6,9,10]D[2,5,7]G[1,2,5,6,9,10]H[1,3,6,9,10]I[1,2,5,6,7]H[1,3,6,9,10]J[1,6,9,10]K[2,4,5,7]I[1,2,5,6,7]L[3,8,10]I[1,2,5,6,7]J[1,6,9,10]J[1,6,9,10]D[2,5,7]K[2,4,5,7]M[2,3,5,8]B[1,6]L[3,8,10]F[1,4,6,9]M[2,3,5,8]N[3]F[1,4,6,9]N[3]O[4]O[4]P[2,5]P[2,5]N[3]B[1,6]:..以家为家,以乡为乡,以国为国,以天下为天下。——《管子》1L**********ABDEFIKM1001000CGHJ110101PON033、已知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图如下010xy010z0下表由子集法将NFA转换为DFA:II=ε-closure(MoveTo(I,0))I=ε-closure(MoveTo(I,1))01A[x]B[z]A[x]B[z]C[x,z]D[y]C[x,z]C[x,z]E[x,y]D[y]E[x,y]E[x,y]F[x,y,z]A[x]F[x,y,z]F[x,y,z]E[x,y]1100000ABCDEF101下面将该DFA最小化:(1)首先将它的状态集分成两个子集:P={A,D,E},P={B,C,F}12(2)区分P:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F,C等价。由于2:..不飞则已,一飞冲天;不鸣则已,一鸣惊人。——《韩非子》F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D,E不等价(见下步),从而B与C,F可以区分。有P={C,F},P={B}。2122(3)区分P1:由于A,E输入0到终态,而D输入0不到终态,所以D与A,E可以区分,有P={A,E},P={D}。1112(4)由于F(A,0)=B,F(E,0)=F,而B,F不等价,所以A,E可以区分。(5)综上所述,DFA可以区分为P={{A},{B},{D},{E},{C,F}}。所以最小化的DFA如下:11101000ABDEF034、将下图确定化:V0000,1SQ1Z0,111U1解:下表由子集法将NFA转换为DFA:II=ε-closure(MoveTo(I,0))I=ε-closure(MoveTo(I,1))01A[S]B[Q,V]C[Q,U]B[Q,V]D[V,Z]C[Q,U]C[Q,U]E[V]F[Q,U,Z]D[V,Z]G[Z]G[Z]E[V]G[Z]F[Q,U,Z]D[V,Z]F[Q,U,Z]0CE011A1F10,1G0000,1BD35、把下图的(a)和(b)分别确定化和最小化::..子曰:“知者不惑,仁者不忧,勇者不惧。”——《论语》bb023abaaaaba,b14501baaab(a)(b)解:(a):下表由子集法将NFA转换为DFA:IIa=ε-closure(MoveTo(I,a))I=ε-closure(MoveTo(I,b))bA[0]B[0,1]C[1]B[0,1]B[0,1]C[1]C[1]A[0]可得图(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所在的行。)BaaaAbbACbCaa(a1)确定化的DFA(a2)最小化的DFA(b):该图已经是DFA。下面将该DFA最小化:(6)首先将它的状态集分成两个子集:P={0},P={1,2,3,4,5}12(7)区分P:由于F(4,a)=0属于终态集,而其他状态输入a后都是非终态集,所以区分P22如下:P={4},P={1,2,3,5}。2122(8)区分P:由于F(1,b)=F(5,b)=4属于P,而F(2,b)与F(3,b)不等于4,即不属于P,所222121以区分P如下:P={1,5},P={2,3}。22221222(9)区分P:由于F(1,b)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5等价。221(10)区分P:由于F(2,a)=1属于P,而F(3,a)=3属于P,所以2,3可区分。P区分为222221222222P{2},P{3}。22212222(11)结论:该DFA的状态集可分为:P={{0},{1,5},{2},{3},{4}},其中1,5等价。删去状态5,将原来引向5的引线引向与其等价的状态1,有图(b1)。bb023abaaab14ba:..子曰:“知者不惑,仁者不忧,勇者不惧。”——《论语》(b1)最小化的DFA36、构造一个DFA,它接收Σ={0,1}上所有满足如下条件的字符串:每个1都有0直接跟在右边。然后再构造该语言的正则文法。解:根据题意,DFA所对应的正规式应为:(0|(10))*。所以,接收该串的NFA如下:ε100120下表由子集法将NFA转换为DFA:II=ε-closure(MoveTo(I,0))I=ε-closure(MoveTo(I,1))01A[0]B[0,2]C[1]B[0,2]B[0,2]C[1]C[1]B[0,2]110ACB00显然,A,B等价,所以将上述DFA最小化后有:01AC0对应的正规文法为:G[A]:A?1C|0A|εC?0A37、给出下述文法所对应的正规式:S?0A|1BA?1S|1B?0S|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、对文法G[S]S?a|∧|(T)T?T,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)由于有T?T,S的产生式,所以消除该产生式的左递归,增中一个非终结符U有新的文法G/[S]:S?a|∧|(T)T?SUU?,SU|ε分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序。(1)对于每个非终结号U,编写一个相应的子程序P(U);(2)对于规则U::=x1|x2|..|xn,有一个关于U的子程序P(U),P(U)按如下方法构造:IFCHINFIRST(x1)THENP(x1)ELSEIFCHINFIRST(x2)THENP(x2)ELSE......IFCHINFIRST(xn)THENP(xn)ELSEERROR其中,CH存放当前的输入符号,是一个全程变量;ERROR是一段处理出错信息的程序;P(xj)为相应的子程序。(3)对于符号串x=y1y2...yn;p(x)的含义为:BEGINP(y1);P(y2);...P(yn);END如果yi是非终结符,则P(yi)代表调用处理yi的子程序;如果yi是终结符,则P(yi)为形如下述语句的一段子程序IFCH=yiTHENREAD(CH)ELSEERROR即如果当前文法中的符号与输入符号匹配,则继续读入下一个待输入符号到CH中,否则表明出错。(4)如果文法中有空规则U::=EPSILON,则算法中的语句IFCHINFIRST(xn)THENP(xn)ELSEERROR改写为:IFCHINFIRST(xn)THENP(xn)ELSEIFCHINFOLLOW(U)THENRETURN:..古之立大事者,不惟有超世之才,亦必有坚忍不拔之志。——苏轼ERROR(5)Str,应在该串的后面加上一个串括号'#',并从子程序P(S)(S为文法的开始符号)开始,如果中途没有产生错误,并且最后CH='#',Str串合法,否则该串不合法。对每个非终结符写出不带回溯的递归子程序如下:charCH;//存放当前的输入符号voidP_S()//非终结符S的子程序{if(CH==’a’)READ(CH);//产生式S?aelseif(CH==’^’)READ(CH);//产生式S?^elseif(CH==’(’)//产生式S?(T){READ(CH);P_T();IF(CH==’)’)THENREAD(CH)elseERROR}elseERR;}voidP_T()//非终结符S的子程序{if(IsIn(CH,FIRST_SU))//FIRST_SU为T?SU的右部的FIRST集合{P_S();P_U();}}voidP_U()//非终结符U的子程序{if(CH==’,’)//产生式U?,SU{READ(CH);P_S();P_U();}else//产生式U?ε{if(IsIn(CH,FOLLOW_U))//FOLLOW_U为U的FOLLOW集合return;elseERR;}}(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(S?a)={a}:..以家为家,以乡为乡,以国为国,以天下为天下。——《管子》SELECT(S?∧)={∧}SELECT(S?(T))={(}SELECT(T?SU)=FIRST(S)={a,∧,(}SELECT(U?,SU)={,}SELECT(U?ε)=FOLLOW(U)={)}可见,相同左部产生式的SELECT集的交集均为空,所以文法G/[S]是LL(1)文法。文法G/[S]的预测分析表如下:a∧(),#S?a?∧?(T)T?SU?SU?SUU?ε?,SU(5)给出输入串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式1#S(a,a)#S?(T)2#)T((a,a)#(匹配3#)Ta,a)#T?SU4#)USa,a)#S?a5#)Uaa,a)#a匹配6#)U,a)#U?,SU7#)US,,a)#,匹配8#)USa)#S?a9#)Uaa)#a匹配10#)U)#U?ε11#))#)匹配12##接受39、对下面的文法G:E?TE/E/?+E|εT?FT/T/?T|εF?PF/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)={+,),#};//不包含ε