编译原理及实现课后答案

1、5.1 考虑以下的文法：SS;T|TTa（1） 为这个文法构造LR(0)的项目集规范族。（2） 这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。（3） 对输入串“a;a”进行分析。解：（1）拓广文法GS： 0：SS 1：SS;T 2：ST 3：Ta构造LR(0)项目集规范族状态项目集转换函数0SSSS;TSTTaGO0，S1GO0，S1GO0，T2GO0，a31SSSS;TACCEPTGO1，;42STR23TaR34SS;TTaGO4，T5GO4，a35SS;TR1（2）该文法不存在“归约归约”和“归约移进”冲突，因此是LR(0)文法。LR(0)分析表如下：状态ACTIONGO

2、TO；a#ST0S3121S4ACCEPT2R2R2R23R3R3R34S355R1R1R1（3）对输入串“a;a”进行分析如下：步骤状态栈符号栈输入符号栈ACTIONGOTO00#a;a#S3103#a;a#R32302#T;a#R21401#S;a#S45014#S;a#S360143#S;a#R3570145#S;T#R11801#S#ACCEPT5.2 证明下面文法是SLR(1)文法，但不是LR(0)文法。SAAAb|bBaBaAc|a|aAb解：文法GS：0：SA1：AAb2：AbBa3：BaAc4：Ba5：BaAb构造LR(0)项目集规范族：状态项目集转换函数0SAAAbAbBaG

3、O0，A1GO0，A1GO0，b21SAAAbACCEPTGO1，b32AbBaBaAcBaBaAbGO2，B4GO2，a5GO2，a5GO2，a53AAbR14AbBaGO4，a65BaAcBaBaAbAAbAbBaGO5，A7R4GO5，A7GO5，A7GO5，b26AbBaR27BaAcBaAbAAbGO7，c8GO7，b9GO7，b98BaAcR39BaAbAAbR5R1状态5存在“归约移进”冲突，状态9存在“归约归约”冲突，因此该文法不是LR(0)文法。状态5：FOLLOW(B)a，因此，FOLLOW(B)b状态9：FOLLOW(B)a，FOLLOW(A)#，b，c，因此FOLLOW

4、(B)FOLLOW(A)状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表如下：状态ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。5.3 证明下面文法是LR(1)文法，但不是SLR(1)文法。SAaAb|BbBaAB解：拓广文法GS：0：SS1：SAaAb2：SBbBa3：A4：B构造LR(0)项目集规范族：状态项目集转换函数0SSSAaAbSBbBaABGO0，S1GO0，A2GO0，B3R3R

5、41SSACCEPT2SAaAbGO2，a43SBbBaGO3，b54SAaAbAGO4，A6R35SBbBaBGO5，B7R46SAaAbGO6，b87SBbBaGO7，a98SAaAbR19SBbBaR2状态0存在“归约归约”冲突，且FOLLOW(A) a,b，FOLLOW(B)a,b，即FOLLOW(A)FOLLOW(B)a,b，所以该文法不是SLR(1)文法。构造LR(1)项目集规范族：状态项目集转换函数0SS，#SAaAb，#SBbBa，#A，aB，bGO0，S1GO0，A2GO0，B3R3R41SS，#ACCEPT2SAaAb，#GO2，a43SBbBa，#GO3，b54SAaAb

6、，#A，bGO4，A6R35SBbBa，#B，aGO5，B7R46SAaAb，#GO6，b87SBbBa，#GO7，a98SAaAb，#R19SBbBa，#R2LR(1)分析表：状态ACTIONGOTOab#SAB0R3R41231ACCEPT2S43S54R365R476S87S98R19R2分析表无重定义，说明该文法是LR(1)文法，不是SLR(1)文法。5.4 考虑以下的文法：EEEEEE*Ea（1）为这个文法构造LR(1)项目集规范族。（2）构造LR(1)分析表。（3）为这个文法构造LALR(1)项目集规范族。（4）构造LALR(1)分析表。（5）对输入符号串“aa*a+”进行LR(1

7、)和LALR(1)分析。解：（1）拓广文法GS：0：SE1：EEE2：EEE*3：Ea构造LR(1)项目集规范族：状态项目集转换函数0SE ，#EEE ，a:#EEE* ，a:#Ea ，a:#GO0，E1GO0，E1GO0，E1GO0，a21SE ，#EEE ，a:#EEE* ，a:#EEE ，*:+EEE* ，*:+Ea ，*:+ACCEPTGO1，E3GO1，E3GO1，E3GO1，E3GO1，a42Ea ，a:#R33EEE ，a:#EEE* ，a:#EEE ，*:+EEE* ，*:+EEE ，*:+EEE* ，*:+Ea ，*:+GO3，5GO3，*6GO3，E7GO3，E7GO3，E

8、7GO3，E7GO3，a44Ea ，*:+R35EEE ，a:#R16EEE* ，a:#R27EEE ，*:+EEE* ，*:+EEE ，*:+EEE* ，*:+EEE ，*:+EEE* ，*:+Ea ，*:+GO7，+8GO7，*9GO7，E7GO7，E7GO7，E7GO7，E7GO7，a48EEE ，*:+R19EEE* ，*:+R2（2）构造LR(1)分析表状态ACTIONGOTO*a#E0S211S4ACCEPT32R3R33S5S6S474R3R35R1R16R2R27S8S9S478R1R19R2R2（3）构造LALR(1)项目集规范族:状态项目集转换函数0SE ，#EEE ，a:

9、#EEE* ，a:#Ea ，a:#GO0，E1GO0，E1GO0，E1GO0，a21SE ，#EEE ，a:#EEE* ，a:#EEE ，*:+EEE* ，*:+Ea ，*:+ACCEPTGO1，E3GO1，E3GO1，E3GO1，E3GO1，a22Ea ，a:#:*:+R33EEE ，a:#:*:+EEE* ，a:#:*:+EEE ，*:+EEE* ，*:+EEE ，*:+EEE* ，*:+Ea ，*:+GO3，4GO3，*5GO3，E3GO3，E3GO3，E3GO3，E3GO3，a24EEE ，a:#:*:+R15EEE* ，a:#:*:+R2（4）构造LALR(1)分析表。状态ACTIO

10、NGOTO*a#E0S211S2ACCEPT32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2（5）对输入符号串“aa*a+”进行LR(1)分析:步骤状态栈符号栈输入串ACTIONGOTO10#aa*a+#S2202#aa*a+#R3 1301#Ea*a+#S44014#Ea*a+#R335013#EE*a+#S660136#EE*a+#R21701#Ea+#S48014#Ea+#R339013#EE+#S5100135#EE+#R111101#E#ACCEPT对输入符号串“aa*a+”进行LALR(1)分析:步骤状态栈符号栈输入串ACTIONGOTO10#aa*a+#S

11、2202#aa*a+#R31301#Ea*a+#S24012#Ea*a+#R335013#EE*a+#S560135#EE*a+#R21701#Ea+#S28012#Ea+#R339013#EE+#S4100134#EE+#R111101#E#ACCEPT5.5 说明以下的文法是LR(1)文法，但不是LALR(1)文法。SaAd|bBd|aBe|bAeAcBc解：拓广文法：0：SS1：SaAd2：SbBd3：SaBe4：SbAe5：Ac6：Bc构造LR(1)项目集规范族状态项目集转换函数0SS，#SaAd，#SbBd，#SaBe，#SbAe，#GO0，S1GO0，a2GO0，b3GO0，a2G

12、O0，b31SS ，#ACCEPT2SaAd，#SaBe，#Ac，dBc，eGO2，A4GO2，B5GO2，c6GO2，c63SbBd，#SbAe，#Ac，eBc，dGO3，B7GO3，A8GO3，c9GO3，c94SaAd，#GO4，d105SaBe，#GO5，e116Ac ，dBc ，eR5R67SbBd，#GO7，d128SbAe，#GO8，e139Ac ，eBc ，dR5R610SaAd ，#R111SaBe ，#R312SbBd ，#R213SbAe ，#R4构造LR(1)分析表：状态ACTIONGOTOabcde#SAB0S2S311ACCEPT2S6453S9874S105S11

13、6R5R67S128S139R6R510R111R312R213R4同核项目集合并，构造LALR(1)项目集规范族：状态项目集转换函数0SS，#SaAd，#SbBd，#SaBe，#SbAe，#GO0，S1GO0，a2GO0，b3GO0，a2GO0，b31SS ，#ACCEPT2SaAd，#SaBe，#Ac，dBc，eGO2，A4GO2，B5GO2，c6GO2，c63SbBd，#SbAe，#Ac，eBc，dGO3，B7GO3，A8GO3，c6GO3，c64SaAd，#GO4，d95SaBe，#GO5，e106Ac ，d:eBc ，d:eR5R67SbBd，#GO7，d118SbAe，#GO8，e

14、129SaAd ，#R110SaBe ，#R311SbBd ，#R212SbAe ，#R4构造LALR(1)分析表：状态ACTIONGOTOabcde#SAB0S2S311ACCEPT2S6453S9874S105S116R5/R6R5/R67S128S139R110R311R212R4从LR(1)分析表可以看出，分析表无重定义，因此该文法是LR(1)文法。从LALR(1)分析表可以看出，分析表ACTION6,d和ACTION6,e存在重定义，因此该文法不是LALR(1)文法。7.1 给出编译下面程序的有序符号表。main() int m,n5; real x; char name;解：名字类

15、型维数mint0mainkeyword0nint1namechar0xreal07.2 按“质数除余法”，给出编译上题程序的散列符号表。解：正整数HASC函数（字符串），质数5，散列符号表如下所示：名字正整数H%5m1094main4211n1100name4172x1200位置名字域属性域0n1main2name34mx 7.3 给出编译到下面程序a、b、c处的栈式符号表。 real x,y; char str;a int fun1(int ind) int x; b x=m2(ind+1); main() char y; c x=2;y=5; printf(%dn,fun1(x/y); 解

16、：05xystrfun1Topmainy04xystrfun1Topindx0xystrTopa：b：c：10.1 对下列基本块应用DAG进行优化：(=，3， ，B)(+，A，C，D)(*，A，C，E)(+，D，E，F)(*，B，F，G)(+，A，C，H)(*，A，C，I)(+，H，I，J)(*，B，5，K)(+，K，J，L)(=，L， ，M)解：构造DAG如下：+D,Hn4An2Cn33Bn1*E,In5+F,Jn6*Gn715Kn8+L,Mn9按照上图的DAG结点顺序，优化后生成的程序如下：(=，3， ，B)(+，A，C，D)(=，D， ，H)(*，A，C，E)(=，E， ，I)(+，D，

17、E，F)(=，F， ，J)(*，3，F，G)(=，15， ，K)(+，15，J，L)(=，L， ，M)10.2 对下面程序段画出程序流图，并进行循环优化。 I=1; J=10; K=5;L1:X=K*I; Y=J*I; Z=X*Y; I=I+1IF I100 GOTO L1; 解：程序流图如下：B1：I=1; J=10; K=5;B2：X=K*I; Y=J*I; Z=X*Y;I=I+1;IF I100 GOTO B2;从程序流图可知，要优化的循环是基本块B2。对循环B2中代码分别实行代码外提、强度删弱和删除归纳变量优化如下：（1） 代码外提：循环中无不变运算、（2） 强度删弱：由于循环中有X=K*I;Y=J*I;其中，K，J在循环中值不发生改变，I每次增加1。因此，对X，Y可进行强度删弱，将乘法运算（*）改为加法运算（）。强度删弱后程序