《编译原理》西北工业大学第三版课后答案

第一章 习题解答 1. 解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻 译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。 2. 解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 3. 解： do if 述关键字在 4. 解： ， ，（）。其中， 用于语句括号； 用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。键字。逗号在 为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为 d）。 5. 略 第二章 习 题解答 1.（ 1）答： 26*26=676 （ 2）答： 26*10=260 （ 3）答： a,b,c,.,z,a0,.,a9,.,.,zz,.,共 26+26*36+26*36*36=34658 个 （ 1） n 0 解：对应文法为 G(S) = (S,a,b, S | ,S) （ 2） n,m,p 0 解：对应文法为 G(S) = (S,X,Y,a,b,c,S ,X ,Y ,S) （ 3） bn|n 0 dn|n 0 解：对应文法为 G(S) = (S,X,Y,a,b,c,d,#, S X, S Y,X ,Y ,S) （ 4） w#| w?0,1*, 解： G(S) = (S,W,R,0,1,#, S W#, W 0 ,S) （ 5）任何不是以 0打头的所有奇整数所组成的集合 解： G(S) = (S,A,B,I,J,-,0,1,2,3,4,5,6,7,8,9,S J|0B|IB|e, I J|2|4|6|8, |5|7|9,S) （ 6）所有偶数个 0和偶数个 1所组成的符号串集合 解：对应文法为 S 0A|1B|e， A 0S|1C B 0C|1S C 1A|0B （ 1） S 10a 解：本文法构成的语言集为： L(G)=(10)n, m 0。 （ 2） S 11 解： L(G)=1 1n1, ,0；且 n1, 该语言特点是：产生的句子中， 0、 1 个数相同，并且若干相接的 1后必然紧接数量相同连续的 0。 （ 3） S 111 解：本文法构成的语言集为： L(G)=1p 1,n 0 1q 1,n 0，特点是具有 1 1一步，可知其具有形式 1m 0,且 n+m0。 （ 4） S A a 解：可知， S= =n 0 该语言特点是：产生的句子中，是以 且 数相同。 （ 5） S a 解： L(G)=a(2n 1可知：奇数个 a 文法产生的语言是：以终结符 运算对象，以、为运算符，以 、 为分隔符的布尔表达式串 5. 于此文法包含以下规则： e，所以此文法是 0型文法。 （ 1）最左推导： ： T L： L： T L： L： T L： L： ； T L： L： ； ； T L： L： ； T L： L： d； ； T L： L： d； d； T L： L： d； d； ； T L： L： d； d； s； L： L： d； d； s； s 右推导： T： ： T： ： T： ： ； T： ： ； ； T： ： ； ； ； ： ： ； ； s； ： ： ； s； s； ： ： ； 说明； s； s； ： ： ； d； s； s； ： ： 明； d； s； s； ： ： d； d； s； s； ： L： d； d； s； s； L： L： d； d； s； s； 2）句子 L： L： d； d； s； s S中的句子，相应语法树是： 最右推导： S=左推导： S= 2） S中的句子 因为文法中的句子不可能以非终结符 （ 3） S中的句子 可知， S的一个句型的一部分，而不是一个句子。 （ 4） 是文法 GS中的句子 因为终结符 a，所以不可能出现 样的句子。 （ 5） 是文法 GS中的句子 由（ 1）可知： 归约为 S，由文法的产生式规则可知，终结符 S，所以不可能出现 样的句子。 归纳法于 n， n=1时，结论显然成立。设 n=于 1 2. kT*b,存在 i： i=1,2,.,k， iT*在设 1 2. k k+1T*b，因文法是前后文无关的，所以 1 2. k 可推导出 b， k+1可推导出 b(不妨称为 b k+1)。由归纳假设，对于 b，存在 i ： i=1,2,.,k， b= 1 2. k,使得 iT*外 ,我们有 k+1T*b(=b k+1） 。即 n=k+1时亦成立。证毕。 (1)用反证法。假设首符号为终结符时，的首符号为非终结符。即设： = = 且 =*。 由题意可知： = T = ，由于文法是 结符 此假设有误。得证； （ 2）同（ 1），假设：的首符号为非终结符时，首符号为终结符。即设：= = 且 = T = ，与（ 1）同理，得证。 为存在句子： 对应有两个语法树（或最右推导）： 以，本文法具有二义性。 (1) 面推导中，下划线部分为当前句型的句柄。对应的语法树为： 全部的短语： 第一个 a (句子 (产生式 A?a）的短语（直接短语）； 对于非终结符 对于非终结符 1（产生式 S?c）的短语（直接短语）； 对于非终结符 2 的短语； 注：符号的下标是为了描述方便加上去的。 （ 2）句子（ b） a（ a）（ b）的最右推导： T（ A（ b） ） T（ （ （ b） T（ a） ）（ b） T（ （ b） a（ a）（ b） 相应的语法树是： （ 3）解： i+对应的语法树略。 最右推导： E F=T T T T T T i+ i+ T i+ i+ T i+ i+ T i+ i+ 充分性：当前文法下的每一符号串仅有一个句柄和一个句柄产生式 对每一步推导都有唯一的最右推导 必要性：有唯一的语法树 对当前符号串有唯一的最左归约 （ 1）解： S c （ 2）解： S e | f （ 3）解： S （ 1）解： S 2）解： S （ 1）消除后的产生式如下： S b C b D b | 2）消除后的产生式如下： S （） |（ S） | |S A () |（ S） |S |S （ 3）消除后的产生式如下： E E+T | T*F | (E) | P F | i T T*F | (E) | P F | i F P F | (E) | i P (E) | i 第三章 习题解答 1从略 2 3 假设 W:表示载狐狸过河， G:表示载山羊过河， C:表示载白菜过河 用到的状态 1：狐狸和山羊在左岸 2：狐狸和白菜载左岸 3:羊和白菜在左岸 4:狐狸和山羊在右岸 5:狐狸和白菜在右岸 6:山羊和白菜在右岸 F:全在右岸 4 证明：只须证明文法 G:A B 或 A （ A,B 等价于 A a (a A 则 C . 所以有 A B,a,b,c 以与 2） B， 因为 是字符串，所以肯定存在着一个终结符a， 使 A 见两者等价，所以由此文法产生的语言是正规语言。 5 6 根据文法知其产生的语言是 L=m,n,i 1 可以构造如下的文法 S,A,B,C, a,b,c P= S A A B B C C c 其状态转换图如下 : 7 (1) 其对应的右线性文法是 : A 0D, B 0A,B 1C,C 1|1F,C 1|0A,F 0|0E|1A,D 0B|1C,E 1C|0B (2) 最短输入串 011 (3) 任意接受的四个串 011,0110,0011,000011 (4) 任意以 1打头的串 . 8 从略。 9 （ 2）相应的 3型文法 (i) S a| b|S aA|a S b|S a| b|S a| b| 3）用自然语言描述输入串的特征 (i) 以任意个 (包括 0)间有任意个（大于 1） a，跟一个 b,还可以有一个由 a,(以 跟任意个（包括 0） b ( 间有任意个（包括 0） b,再跟 a,最后由一个 a,的任意串结尾或者 以 间有任意个（包括 0） a,再跟 b,最后由一个 a,(任意个（包括 0） 中间跟 a,以任意个（包括 0） 间跟 括 0） b，最后由一个 a,10 （ 1） (2) S C,B ,A a S C,B ,C a （ 3）对 推导序列是： S= 文法， S= S= 文法， 推导序列是： S= 4）对串 1 文法都不能产生。 11将右线性文法化为左线性文法的算法： o （ 1）对于 产生式且 始符，将其变为 B a,否则若 B o （ 2）对于 a 的产生式 ,将其变为 S 12 (1) 状态矩阵是： 记 S=B=A B=S A=最小化和确定化后如图 （ 2）记 S=A=B S=小化和确定化后的状态转换图如下 13 （ 1）将具有 动作的 状态转换图如图： 记 1,3=(2) 记 S=Z=U R=S X=Y U R=X S U=Y U R Z=Z S=14（ 1）从略 (2)化简后 1作为一个状态， 6作为一个状态。 状态转换图如图 15从略。 16从略。 (1) r*表示的正规式集是 ,r,rr, ( |r)*表示的正规式集是 , , r,rr, = ,r,rr, |示的正规式集是 ,r,rr, (r*)*=r*= ,r,rr, 所以四者是等价的。 (2)（ * ,rs, r =r, r( 表示的正规式集是 r ,sr, = r, 所以两者等价。 18 写成方程组 S=aT+) B=cB+c(2) T=bT+) 所以 B=c*cT=b*bc*c S=a*ab*bc*c S=(1) B=cC+b(2) A=3) C=D(4) D=bB+d(5) 把（ 4）（ 5）代入（ 2），得 B c(bB+d)+b=cd+b 得 B=(cd|b),代入（ 3）得 A=b(cd|b)把它打入（ 1）得 S=a(b(cd|b)+ (cd|b) =ab(cd|b) + (cd|b) =( ab(cd|b)| (cd|b) S= (1) A=b (2) B=Bb+a(3) C=D+) D=d(5) 可得 D=dB=ab*ab|ab*ab|b)c + ab*b S=(ab*ab|b)ca+ab*=(ab*ab|b)ab*20 识别此语言的正规式是 S=d(d|,d)*; 从略。 21 从略。 22 构造 余从略。 23 下面举一个能够识别 1,2,3,10,20,100的例子，读者可以推而广之。 % #W 2 # #E 10 #0 #00 # % N; W; E; +|% ) c,i=0; 0; 2) (,r)= t sn,);); (c=)!=0) c) N: c=; c=0) i+=1; c=; c=i+=100; i+=1; W:c=; c=; c=i+=200; i+=2; i+=20; E:i+=10; /* %dn,i); 24 （ 1） 度为 2a和 此正规式的长度是 2n 用来识别 n 1个状态。 25 从略。 26（ 1）由 括住的 ,中间由任意个非 组成的字符串 , 如 ,a,等。 （ 2）匹配一行仅由一个大写字母和一个数字组成的串，如 8, （ 3）识别 r 由 和 括住的，中间由两个 或者非 和 , a,， 等等 27O0|0|(a 0000100) 280 29 参考程序如下： % # % t| +% ) c,i; 2) (,r)= t sn,);); (c=)!= c=2) i=0;i;i+) %c,i); =000; c=3) ); %s, 30 从略。 第四章 习题解答 第四章习题参考答案 (1)S (S)S (S)S (S)S11 |12 21 |23 32 |2)S 11 | |3)S (T) (T) 11 | , |, S 示第 1步，用产生式 以下同 ) .1 .1 .1 .1 不符合，改写第 5步，用 .2 .1 .1 .2 .2 .1 .1 .2 下 示 示 (1)文法没有左递归。 :P:=If f d If ; f P:=:X:=If d If ; If s X:=:Y=If ; If s (2)消去文法左递归，并记为： P A|V:= E + V I :P:=If f S f P:=:A:= f :=” f E A:=:S:= S:=:C:=If f E If f S C:=:E:= f Ep E:=p:If + f E 为是左递归文法，所以必存在左递归的非终结符 A，及形如 A |的产生式 ,且 T* 则 d) ) ,从而 ) )，即文法不满足 1）文法条件。得证。 1）文法的分析句子过程的每一步，永远只有唯一的分析动作可进行。现在，假设 )文法 存在句子 ，它有两个不同的语法树。即存在着句子 有两个不同的最左推导。从而可知，用1）方法进行句子 的分析过程中 的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即 1）分析动作存在不确定性。与1）性质矛盾。所以， L(1)文法。 (1)f的 以不是 )的。 (2)此文法具有左递归性，据第 5题结论，不是 )的。 (1)消除左递归性 ,得： S 21 消除无用产生式得： S 文法已满足 )文法的三个条件， 所以 GS: S 2) G 文法的各非终结符的 和 ： 产生式 S b a # b # b a # )分析表为： a b # S (1) 产生式 S b b #,a,c A S a b a c B a,b #,a,c (2)将 S S ,可验证，新文法是 )的。 1）为方便书写，记： 为 A， 为 B， 为 C， 为 D，原文法可以简化为： A A B | B B B C | D | (A) | 显然，文法含有左递归，消去后等价 )文法为： A A B B C D|(A)| 2)略 证：若 1）文法 G 有形如 B 及 AT*据的构造算法可知， )中一切非 加到 )中，则 a )；又因为 a 所以两集合相交非空，因此，L(1)文法；与前提矛盾，假设不成立，得证。 解： (1) S A ( a ) b S = = A = = ) b 不是简单优先文法。 (2) S R T ( ) a , S = R = T ( a , ( = , = 是简单优先文法。 o 首先消去无用产生式 Z E, Z E+T S Z T # i ( ) S Z = = T # = ( = 化简后的文法是简单优先文法 ； 解： S A / A S A = a 之间同时有关系 =和 的最左子串。由 =关系的定义，可 知 .出现在某产生式的右部中。又因 =, V= ,T=， a=消去 V，并采用分层法改写文法，得到： D;W L,i|r|n|b|c 其全部简单优先关系是： D W T L a : ; , i r|n|b|c D W = T = L = a = = i r|n|b|c 是简单优先文法。 证：设 们对 明 a 不含两个非终结符相邻情况。 n=1时， S 据定义，它不含上述情况。设 n=述结论成立，且设 归纳假设， 们再进行一步推导，得 其中， A 定义， 而 证。 证：由于 右部含有两个非终结符相邻的情况。不失一般性，设其形为 U x,y V*,由于文法不含无用产生式，则必存在含有 存在推导 ST* 文法为： E E A | A*T | A/T | T+V | i | (E) 解： （ 1）构造算符优先矩阵： - * （ ） i # - * I # * a = * =b， b 是 与 G 是算符文法矛盾，所以， 。 （ 2）的证明与（ 1）类似，略。 证：（ 1）对于 a= 句型，必有 ST*a(= ) T+ 从而 ,，与 by=矛盾，得证。 提示：根据 27 题的结论，只要证 的短语，根据 =关系的定义容易知道 的素短语。 证：与 28题的不同点只是 a0,可以是 #, 不影响结论。 证：设不能含有素短语，则只能是含有短语（不能含有终结符号），则该短语只能含有一个非终结符号，否则不符合算符文法定义，得证。 解： （ 1）算符优先矩阵： + * （ ） i # + * ( I # = a 0 do =1 :=C+1 0 do =1 :=C+1 0 do =1 :=C+1 0 do =1 :=C+1 ,) (4)(j,0,0,0); 5. 当前句 型为 do =1 :=C+1 ,) (4)(j,0,0,2); 6. 当前句型为 do =1 :=C+1 ,) (4)(j,0,0,2); 7. 当前句型为 =1 :=C+1 ,) (4)(j,0,0,2); (5)(j=,A,1,0) (6)(j,0,0,0) 8. 当前句型为 :=C+1 ,) (4)(j,0,0,2); (5)(j=,A,1,7) (6) (j,0,0,0) 9. 当前句型为 :=C+1 ,) (4)(j,0,0,2); (5)(j=,A,1,7) (6) (j,0,0,0) (7)(+.,C,1,(8)(=,C) 10. 当前句型为 ,) (4)(j,0,0,2); (5)(j=,A,1,7) (6)(j,0,0,10) (7)(+.,C,1,(8)(=,C) (9)(j,0,0,0) 11. 当前句型为 ,) (4)(j,0,0,2); (5)(j=,A,1,7) (6)(j,0,0,10) (7)(+.,C,1,(8)(=,C) (9)(j,0,0,0) (10) 12. 当前句型为 l A,) (4)(j,0,0,2); (5)(j=,A,1,7) (6)(j,0,0,10) (7)(+.,C,1,(8)(=,C) (9)(j,0,0,0) (10)(j,A,D,0) (11) (j,0,0,0) 13. 当前句型为 l :=A+2 用产生式 (1) (j,) (4)(j,0,0,2); (5)(j=,A,1,7) (6)(j,0,0,10) (7)(+.,C,1,(8)(=,C) (9)(j,0,0,0) (10)(j,A,D,12) (11) (j,0,0,0) :=A+2将赋值语句归约 A:=A+2为 (1) (j,) (4)(j,0,0,2); (5)(j=,A,1,7) (6)(j,0,0,10) (7)(+.,C,1,(8)(=,C) (9)(j,0,0,0) (10)(j,A,D,12) (11) (j,0,0,0) (12)(+,A,2,(13)(=,A) 15. 当前句型为 产生式 约，得 (1) (j,) (4)(j,0,0,2); (5)(j=,A,1,7) (6)(j,0,0,10) (7)(+.,C,1,(8)(=,C) (9)(j,0,0,0) (10)(j,A,D,12) (11) (j,0,0,0) (12)(+,A,2,(13)(=,A) (14)(j,0,0,10) 16. 当前句型为 产生式 约，得 (1) (j,) (4)(j,0,0,2); (5)(j=,A,1,7) (6)(j,0,0,10) (7)(+.,C,1,(8)(=,C) (9)(j,0,0,0) (10)(j,A,D,12) (11) (j,0,0,9) (12)(+,A,2,(13)(=,A) (14)(j,0,0,10) 17. 当前句型为 产生式 约，得 (1) (j,) (4) (j,0,0,2); (5)(j=,A,1,7) (6)(j,0,0,10) (7)(+.,C,1,(8)(=,C) (9)(j,0,0,1) (10)(j,A,D,12) (11).(j,0,0,1) (12)(+,A,2,(13)(=,A) (14)(j,0,0,10) (15)(j,0,0,1) (16) ： 1） := = ,$,2); $2); ,0, ,T);$); $ =; $j=,$,); ,$ ,1, ,$ $ ,T1,q=$T=; ,$,q+6); ,0, ,T); , , , q+7); ,T); , , ,q+7); ,1, ,T); ; ,$1); ,T,1); ;/*记录维数 */ /*下面为内情向量申请空间，并填入第一维下标信息，其中，前两个单元（下标为 0和 1）用来存放 a、 时暂不填写）， 此不必另存 。 */ $*; $=$3;/*第一维上界 */ | $; $=$1; $;/*维数加 1*/ /*下面增加向量空间，记录新一维的信息 */ $()*