编译原理课后答案.doc

第二章 高级语言及其语法描述4令+、*和代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*22*12的值：（1） 优先顺序（从高至低）为+，*和，同级优先采用左结合。（2） 优先顺序为，+，*，同级优先采用右结合。解：（1）1+1*22*12=2*21*12=412=42=16 （2）1+1*22*12=1+1*2*1=2*2*1=2*2=46令文法G6为 ND|ND D0|1|2|3|4|5|6|7|8|9（1） G6 的语言L（G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。解：（1）L（G6）=a|a+,=0,1,2,3,4,5,6,7,8,9 （2）N ND NDD NDDD DDDD 0DDD 01DD 012D 0127 N ND N7 ND7 N27 ND27 N127 D127 0127 N ND DD 3D 34 N ND N4 D4 34 N ND NDD DDD 5DD 56D 568 N ND N8 ND8 N68 D68 5687写一个文法，使其语言是奇数集，且每个奇数不以0开头。解：ASN, S+|-|, ND|MDD1|3|5|7|9, MMB|1|2|3|4|5|6|7|8|9 B0|1|2|3|4|5|6|7|8|98. 文法：最左推导:最右推导:语法树：/*/9证明下面的文法是二义的：S iSeS|iS|I解：因为iiiiei有两种最左推导，所以此文法是二义的。10把下面文法改写为无二义的：SSS|(S)|()解：S ST|T, T (S)|()11给出下面语言的相应文法 L1=anbnci|n1,i0 L2=aibncn|n1,i0 L3=anbnambm|n,m0 L4=1n0m1m0n|n,m0解：（1）S AB|A A aAb|ab B c|cB(2) S AB|B A a|aAB bBc|bc(3) S AB|A|B|A aAb|abB aBb|ab(4) S 1S0|0A1A 0A1|01第三章 词法分析7.构造下列正规式的相应的DFA1(0|1)*1011(1010*|1(010)*1)*00*10*10*10*(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*解答：（1）1(0|1)*101II0I1XA,B,CA,B,C B,C B,C,DB,C B,C B,C,DB,C,D B,C,E B,C,DB,C,E B,CB,C,D,yB,C,D,yB,C,E B,C,DS01ABBCDCCDDEDECFFED(2) 1(1010*|1(010)*1)*0II0I1X A,B,CA,B,CyD,H,I,LyD,H,I,LE,JB,CE,JB,C,F,G,KB,CyD,H,I,LB,C,F,G,KB,C,G,I,L,yD,H,I,LB,C,G,I,L,yB,C,G,J,yB,C,D,H,I,L B,C,G,J,yB,C,G, yD,H,I,LD,H,I,K,LE,I,J,LB,CE,J,yB,C,F,G,K E,I,J,LJB,C,F,G,K JKKI,LI,LJB,C8.给出下面正规表达式（1） 以01结尾的二进制数串（2） 能被5整除的十进制整数（3） 包含奇数个1或者奇数个0的二进制数串（4） 英文字母组成的所有符号串，要求符号串中的字母按照字典序排列。（7）不包含子串abb的由a和b组成的符号串的全体。解答：（1） （0|1）*01（2） (1|2|9)(0|1|2|9)*(0|5)|0|5（3） 0*1(0*10*10*)*（4） A*B*Z*(7) b*(a|ab)*9.对下面的情况给出DFA以及正规表达式。（1）0，1上的含有子串010的所有串。（2）0，1上不含子串010的所有串。解答：（1）（0|1）*010（0|1）*（2）1*(0|1*|1)*1*12 将图3.8的（a）和(b)分别确定化和最少化。解：1 确定化a b0 0,1 10,1 0,1 11 0 _令A=0 B=0，1 C=1则状态转换图为：2 最少化首先，所有状态可分为 终态集A B 非终态集C其次，考察A B，由于A B由a到B，由b到C，所以不可分，令A=A B则最少化后的状态转换图为：14 构造一个DFA，它接受0,1上所有满足下列条件的字符串，每个1都有0直接跟在右边。解：1 正规式为： （0|10）2 由正规式转化为NFA： 3 由NFA到DFA： 0 1X X b b X _令A=X B=b则状态转换图为：4 最少化 终态集A 非终态集B 显然不可再划分，则最简的DFA即为：15 给定右线性文法G： S0S|1S|1A|0B A1C|1 B0C|0 C0C|1C|1|0求出一个与G等价的左线性文法。解：1 由右线性文法构造NFA： 2 从NFA中构造左线性文法： FA1|B0|C0|C1 AS1|1 BS0|0 CC0|C1|A1|B0 SS0|S1|1|0第四章 语法分析自上而下分析1. 考虑下面文法 G1:Sa|(T)TT,S|S(1) 消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。(2) 经过改写的文法是否是LL（1）的？给出它的预测分析表。解答：（1） 消去G1的左递归：Sa|(T) TSTT ,ST|递归子程序：PROCEDURE S;IF sym=a THEN ADVANCEELSE IF sym= THEN ADVANCEELSE IF sym= ( THEN BEGIN ADVANCE T; IF sym= ) THEN ADVANCE ELSE ERROR ENDELSE ERROR;PROCEDURE T;BEGINS;TEND;PROCEDURE S;IF sym= , THEN BEGIN ADVANCE S;T END;（2） 是LL（1）文法。FIRST(S)= a,( FIRST(T)= a,( FIRST(T)= , FOLLOW(S)= #, , , , ) FOLLOW(T)= ) FOLLOW(T)= ) 预测分析表如下：a, (）#SSaSS (T)TTSTTSTTSTTT ,STT 2.文法：(1)FIRST(E)=(,a,b,FIRST(E)=+,FIRST(T)=(,a,b,FIRST(T)=(,a,b,FIRST(F)=(,a,b,FIRST(F)=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#(2)考虑下列产生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T)=(,a,b,+,),#=FIRST(*F)FIRST()=*=FIRST(*F)FOLLOW(F)=*(,a,b,+,),#=FIRST(E)FIRST(a) FIRST(b) FIRST()=所以,该文法式LL(1)文法.(3)+*()ab#EETTFFP(4)procedure E;beginif sym=( or sym=a or sym=b or sym= then begin T; E end else errorendprocedure E;beginif sym=+ then begin advance; E end else if sym) and sym# then errorendprocedure T;beginif sym=( or sym=a or sym=b or sym= then begin F; T end else errorendprocedure T;beginif sym=( or sym=a or sym=b or sym= then T else if sym=* then errorendprocedure F;beginif sym=( or sym=a or sym=b or sym= then begin P; F end else errorendprocedure F;beginif sym=* then begin advance; F endendprocedure P;beginif sym=a or sym=b or sym= then advance else if sym=( thenbeginadvance; E;if sym=) then advance else errorendelse errorend;3.下面文法那些是LL（1）文法？ （1）S Abc A a| Bb| 没有左递归且FIRST 候选集不冲突且 FIRST(A)FOLLOW(A)= a, b = FIRST(B)FOLLOW(B)= b, c =所以该文法为LL（1）文法（2）S Ab A a|B| Bb|FIRST(B) b, FIRST() = 所以该文法不是LL（1）文法（3）S ABBA A a | Bb| 没有左递归且FIRST 候选集不冲突 FIRST(A)FOLLOW(A)= a, b,# = FIRST(B)FOLLOW(B)= b, b,a,# 所以该文法不是LL（1）文法(4) S aSe|B B bBe |C CcCe|d 没有左递归且FIRST 候选集不冲突 所以该文法为LL（1）文法4.Expr_Expr Expr(Expr)| Var ExprTail ExprTail_ Expr| Varid VarTail VarTail(Expr)| （1） 构造LL（1）分析表（2） 给出对句子id_ _id(id) 的分析过程解答：（1）FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(Var)=id FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) 预测分析表如下： id (）#ExprExpr_ExprExprVar ExprTailExpr(Expr)ExprTailExprTail_ ExprExprTailExprTailVarVarid VarTailVarTailVarTailVarTail(Expr)VarTail(3) 对句子id_ _(id) 的分析过程：步骤 符号栈 输入串所用产生式0Expr id_ _id(id)1# ExprTail Var id_ _id(id)ExprVar ExprTail2# ExprTail VarTail idid_ _id(id)Varid VarTail3# ExprTail VarTail_ _id(id)4# ExprTail_ _id(id)VarTail5# Expr_ _id(id) ExprTail_ Expr6# Expr_id(id)7# Expr_id(id)Expr_Expr8# Exprid(id)9# ExprTail Varid(id)ExprVar ExprTail10# ExprTail VarTail idid(id)Varid VarTail11# ExprTail VarTail(id) 12# ExprTail )Expr(id)VarTail(Expr)13# ExprTail )Expr(id)14# ExprTail ) )Expr(id)Expr(Expr)15# ExprTail ) )Exprid)16 # ExprTail ) )ExprTail Varid)ExprVar ExprTail17# ExprTail ) )ExprTail VarTail idid)Varid VarTail18# ExprTail ) )ExprTail VarTail )19# ExprTail ) )ExprTail)VarTail20# ExprTail ) )ExprTail21# ExprTail )22# ExprTail #ExprTail23# #分析成功第五章1. 短语: E+T*F, T*F,直接短语: T*F句柄: T*F2 （1）(a, ( a, a ) ) 的最左推导：S = ( T ) =( T,S ) = ( S,S ) =(a,S ) =( a,( T ) ) = ( a,( T,S ) ) = ( a,(S,S ) ) = ( a,( a ,S ) ) = ( a,( a ,a ) )最右推导：S = ( T ) =( T,S ) = ( T, (T) ) =( T, (T, S) ) =( T, (T, a) ) =( T, (S, a) ) = ( T,(S, a ) ) = ( T,( a ,a ) ) = (S,( a ,a ) ) = ( a,( a ,a ) )(a, 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 ),，S ),S ) =( ( a ,a ), ，a ),S ) =( ( a ,a ), ，a ),a )最右推导：S = ( T ) =( T,S ) =( T, a ) =( S ,a ) =( (T) , a ) =( (T, S) , a ) =( (T, ( T ) , a ) =( (T, ( a ) , a ) =( (T, S, ( a ) , a ) =( (T, , ( a ) , a ) =( (S, , ( a ) , a ) =( (T), , ( a ) , a ) =( (T,S), , ( a ) , a ) =( (T ,a), , ( a ) , a ) =( (S ,a), , ( a ) , a ) =( (a ,a), , ( a ) , a )(2) (a, a),(a),a)的规范规约及每一步的句柄为：(a, a),(a),a)a( (S ,a), , ( a ) , a )S( (T ,a), , ( a ) , a )a( (T,S), , ( a ) , a )T,S( (T), , ( a ) , a )(T)( (S, , ( a ) , a )S( (T, , ( a ) , a )( (T, S, ( a ) , a )T,S( (T, ( a ) , a )a(T,(S),a)S( (T, ( T ) , a )(T)( (T, S) , a )T,S( (T) , a )(T)( S ,a )S( T, a )a( T,S )T,S( T )(T)S步骤 符号栈 输入串 动作0#(a, a),(a),a)#预备1#( (a, a),(a),a)#进2#( (a, a),(a),a)#进3#( a, a),(a),a)#进4#(a, a),(a),a)# 进5#(S, a),(a),a)#规约 Sa6#(T, a),(a),a)#规约TS7#(T, a),(a),a)#进8#(T, a ),(a),a)#进9#(T,S ),(a),a)# 规约 Sa10#(T ),(a),a)# 规约TT,S11#(T),(a),a)#进12#(S,(a),a)#规约S(T)13#(T,(a),a)# 规约TS14#(T,(a),a)# 进15#(T,(a),a)#进16#(T,S,(a),a)#规约S17#(T,(a),a)# 规约TT,S18#(T,(a),a)# 进19#(T,(a),a)#进20#(T,(a),a)#进21#(T,(S),a)#规约Sa22#(T,(T),a)#规约TS23#(T,(T),a)#进24#(T,S),a)#规约S(T)25#(T),a)# 规约TT,S26#(T),a)#进27#(S,a)#规约S(T)28#(Ta)#规约TS29#(T,a)#进30#(T, a)#进31#(T, S)#规约Sa32#(T)# 规约TT,S33#(T)#进34#S#规约S(T)35#S#接受语法树： S 17 ( T ) 16 14 T,S 15S13a ( T ) 12（ T ）8 T , S 116T , S7( T ) 10S 5 S 9( T ) 4 a2T , S 3S a1 a其中的编号指示的结点为每一步规约所形成的语法树的根结点。3（1） FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,) (2)a(),a(=,是算符文法，并且是算符优先文法(3)优先函数a(),f44244g55523也可以最后指定f (#) ,g (#) 的值。（4）算符优先分析过程。步骤符号栈输入串动作0#(a,(a ,a)#预备1#(a,(a ,a)#进2#(a,(a ,a)#进3#(S,(a ,a)#规约Sa4#(S,(a ,a)#进5#(S,(a ,a)#进6#(S,(a ,a)#进7#(S,(S ,a)#规约Sa8#(S,(S,a)#进9#(S,(S,a)#进10#(S,(S,S)#规约Sa11#(S,(T)#规约TT,S12#(S,(T)#进13#(S,S)#规约S(T)14#(T)#规约TT,S15#(T)#进16#S#规约S(T)17#S#接受5.拓广的文法为：SS , SAS, Sb ,ASA, Aa,(1) 所有的 LR(0)项目：0.1.2.3.4.5.6.7.8.9.10.11.（2）LR(0)项目集规范族：I0 SS , SAS , Sb , ASA , AaI0 S I 1 SS , SAS , Sb , ASA, Aa , ASAA I 2 SAS, , SAS , Sb , ASA , Aaa I 3 Aab I 4 SbI 1 S I 5 ASA, ASA , Aa , SAS , SbA I 6 ASA , SAS , SAS , Sb , ASA , Aa,a (I 3)b (I 4) I 2 S I 7 SAS , ASA, ASA , Aa, SAS, Sb,A( I 2 )a (I 3 )b (I 4 )I 5 S (I 5) A (I 6) a (I 3) b (I 4)I 6 S (I 7) A (I 2 ) a (I 3) b (I 4)I 7 S (I 5) A (I 6) a (I 3) b (I 4)(3) I 1 中存在移进规约冲突SS ， Aa ， Sb 但是FOLLOW(S)#所以该冲突可以消除I 6中存在移进规约冲突：ASA ，Sb ，Aa 但是FOLLOW(A)b, a 所以该冲突不可以消除。I 7中存在移进规约冲突：SAS ，Aa ，Sb但是FOLLOW(S)a , b ,# 所以该冲突不可以消除。 所以该文法不是SLR文法。（4）I0 SS , # , SAS , # , Sb , # , ASA ,a/b , Aa ,a/bI0 S I 1 SS,# , SAS,a/b , Sb,a/b , ASA, a /b , Aa , a/b , ASA, a/bA I 2 SAS, # , SAS , #, Sb , #, ASA ,a/b , Aa, a/b a I 3 : Aa,a/b,b I 4 Sb,#I 1 S I 5 ASA, a/b , ASA , a/b , Aa , a/b , SAS , a/b , Sb, a/b A I 6 ASA,a/b , SAS , a/b , SAS , a/b , Sb , a/b , ASA , a/b , Aa, a/b a (I 3)b I7 Sb, a/b I 2 S I 8 SAS,# , ASA, a/b , ASA ,a/b , Aa, a/b , SAS, a/b, Sb, a/bA I 9 SAS , #/a/b , SAS , #/a/b , Sb ,#/ a/b , ASA , a/b , Aa, a/b a (I 3 )b I 10 Sb, #/a/b I 5 S (I 5) A (I 6) a (I 3) b (I 7)I 6 S I 11 : SAS, a/b , ASA, a/b , ASA , a/b , Aa, a/b ,A I 12 : SAS , a/b , SAS , a/b , Sb, a/b, ASA , a/b , Aa, a/b a (I 3) b (I 7)I 8 S( I 5 ) A( I 6 )a( I 3)b( I 7) I 9 S I 13 : SAS, #/a/b , ASA, a/b , ASA , a/b , Aa, a/b , SAS ,a/b , Sb , a/b A (I 9 )a (I 3 )b (I 10 )I 11 S( I 5 ) A( I 6 )a( I 3)b( I 7) I 12 S( I 11 ) A( I 12 )a( I 3)b( I 7) I 13 S( I 5 ) A( I 6 )a( I 3)b( I 7) I 6, I 11, I 13 中存在移进规约冲突，所以该文法不是LR(1)的和LALR的。(附上网络版的答案) (2)1987 S A S 11100 a