编译原理及编译程序构造 部分课后答案(张莉 杨海燕编著)汇总

第一章 练习1 2、典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？ 典型的编译程序具有7个逻辑部分： 第二章 练习2.2 4.试：A+ =AA*=A*A 证：∵ A*=A0∪A+，A+=A1∪A2∪…∪An∪… 得：A*=A0∪A1∪A2∪…∪An∪… ∴ AA*=A（A0∪A1∪A2∪…∪An∪…） = AA0∪AA1∪AA2∪…∪A An∪… =A∪A2∪A3∪An +1∪… = A+ 同理可得： A*A =(A0∪A1∪A2∪…∪An∪…)A =A0 A∪A1A∪A2A∪…∪AnA∪… = A∪A2∪A3∪An+1∪… = A+ 因此： A+ =AA*=A*A 练习2.3 1.设G[〈标识符〉]的规则是 ： 〈标识符〉::=a|b|c| 〈标识符〉a|〈标识符〉c| 〈标识符〉0|〈标识符〉1 试写出VT和VN， 并对下列符号串a,ab0,a0c01,0a,11,aaa给出可能的一些推导。 解：VT ={a,b,c,0,1}， VN  ={〈标识符〉} (1)  不能推导出ab0,11,0a (2)〈标识符〉=>a (3)〈标识符〉=>〈标识符〉1 =>〈标识符〉01 =>〈标识符〉c01 =>〈标识符〉0c01 =>  a0c01 (4)〈标识符〉=>〈标识符〉a =>〈标识符〉aa =>aaa 2．写一文法，其语言是偶整数的集合 解：G[<偶整数>]： <偶整数>::= <符号> <偶数字>| <符号><数字串><偶数字> <符号> ::= + | — |ε <数字串>::= <数字串><数字>|<数字> <数字> ::= <偶数字>| 1 | 3 | 5 | 7 | 9 <偶数字> ::=0 | 2 | 4 | 6 | 8 4. 设文法G的规则是： 〈A〉::=b| cc 试证明：cc, bcc, bbcc, bbbcc∈L[G] 证：（1）〈A〉=>cc （2）〈A〉=>b〈A〉=>bcc （3）〈A〉=>b〈A〉=>bb〈A〉=>bbcc （4）〈A〉=>b〈A〉=>bb〈A〉=>bbb〈A〉=>bbbcc 又∵cc, bcc, bbcc, bbbcc∈Vt* ∴由语言定义，cc, bcc, bbcc, bbbcc∈L[G] 5 试对如下语言构造相应文法： （1）{ a(bn)a | n=0,1,2,3,……},其中左右圆括号为终结符。 （2） { （an）（bn） | n=1,2,3,……}  解：（1）文法[G〈S〉]： S::= a(B)a B::= bB |ε ( 2 ) 文法[G〈S〉]：--错了，两个n不等 S ::= (A)(B) A::= aA|a B::= bB|b 7.对文法G3[〈表达式〉] 〈表达式〉::=〈项〉|〈表达式〉+〈项〉|〈表达式〉-〈项〉 〈项〉::=〈因子〉|〈项〉*〈因子〉|〈项〉/〈因子〉 〈因子〉::=（〈表达式〉）| i 列出句型〈表达式〉+〈项〉*〈因子〉的所有短语和简单短语。 <表达式> => <表达式> + <项> => <表达式> + <项> * <因子> 短语有： 〈表达式〉+〈项〉*〈因子〉和〈项〉*〈因子〉 简单短语是：〈项〉*〈因子〉 8 文法V::= aaV | bc的语言是什么？ ? 解：L（G[V]）= {a2nbc | n=0,1,2,……} V ? aaV ?aaaaV ?.... ? a2nbc  (n ≥ 1) V ? bc (n=0) 练习2.4 5.已知文法G[E]： E::=ET+ | T T::=TF* |F F::=FP↑ |P P::=（E）| i 有句型TF*PP↑+， 问此句型的短语，简单短语，和句柄是什么？ 解：此句型的短语有：TF*PP↑+，TF*，PP↑，P 简单短语有：TF*，P 句柄是：TF* 8.证明下面的文法G是二义的： S::= iSeS | iS | i 证：由文法可知iiiei是该文法的句子， 又由文法可知iiiei有两棵不同的语法树。 所以该文法是二义性文法。 第三章 练习3.1 1．画出下述文法的状态图 〈Z〉::=〈B〉e 〈B〉::=〈A〉f 〈A〉::= e |〈A〉e 使用该状态图检查下列句子是否是该文法的合法句子 f，eeff，eefe 2、有下列状态图，其中S为初态，Z为终态。 （1） 写出相应的正则文法： （2） 写出该文法的V，Vn和Vt； （3） 该文法确定的语言是什么？ 解：（1） Z→A1|0    A→A0|0 （2） V={A,Z,0,1} Vn={A,Z} Vt={0,1} （3） L (G[S])= {0或0n1,n≥1} L (G[S])= {0|00*1} 练习3.2 1．令A，B，C是任意正则表达式，证明 以下关系成立： A|A=A （A*）*= A* A*=ε| AA* （AB）*A = A（BA）* （A|B）* =（A*B*）*=（A*|B*） 证明： ⑴A∣A＝｛x∣x∈L(A)或x∈L(A)｝＝｛ x∣x∈L(A)｝＝A ⑵（A*）*＝（A*）0∪（A*）1∪（A*）2∪…∪（A*）n ＝ε∪(A0∪A 1∪A2∪…∪An) ∪(A1…) ＝ε∪A0∪A 1∪A2∪…∪An ＝A* ⑶ε︱AA*所表示的语言是: {ε}∪LA·LA* ＝LA0∪LA（LA0∪LA1∪LA2∪…） ＝LA0∪LA1∪LA2∪…＝LA* 故ε︱AA*＝A* ⑷ (LALB)*LA=({ε}∪L(A)LB∪LALBLALB∪LALBLALBLALB ∪…) LA =LA∪LALBLA∪LALBLALBLA∪LALBLALBL ALB∪LA… = LA∪({ε}∪LBLA∪LBLALBLA∪…) = LA(LBLA) ∴(AB)*A=A(BA)* ⑸三个表达式所描述的语言都是LALB中 任意组合 ∴（A|B）*=(A*B*)=(A*|B*)* 2. 构造下列正则表达式相应的DFA （1） 1（0|1）*|0 （2） 1（1010*|1（010）*1）*0 4. 5. 构造一DFA，它接受Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。 第四章 练习4.2 2. 有文法G[A]:    A::= (B) | dBe B::= c | Bc 试自顶向下的语法分析程序。 解：消除左递归： A::= (B) | dBe B::= c{c} procedure B; if CLASS = 'c' then begin nextsym; while CLASS = 'c' do nextsym; end; else error; program    G; begin nextsym; A; end; procedure A; if CLASS = '(' then begin nextsym; B; if CLASS = ')' then nextsym； else error end； else if CLASS = 'd' then begin nextsym; B; if CLASS = 'e' then nextsym; else error; end; else error; 3. 有文法G[Z]:      Z::= AcB| Bd A::=AaB|c B::= aA|a (1) 试求各选择（候选式）的FIRST集合； (2) 该文法的自顶向下的语法分析程序是否要编成递归子程序？为什么？ (3) 试用递归下降分析法设计其语法分析程序。 解:  (1)  FIRST(B)={a} FIRST(A)={c} FIRST(Z)={a,c} FIRST(AcB)={c}          FIRST(Bd) ={a} FIRST(AaB)={c}          FIRST(c) ={c} FIRST(aA) ={a}            FIRST(a) ={a} (2) 要编成递归子程序，因为文法具有递归性 (3) 改写文法： Z::= AcB| Bd A::= c{aB} B::= a[A]      练习4.3 1 .  对下面的文法G[E]:        E → TE‘                E' → + E |ε T → FT' T' → T |ε F → PF' F' → * F' |ε P →(E)| a | b | ∧ (1) 计算这个文法的每个非终结符号的FIRST和FOLLOW集合 (2) 证明这个文法是LL(1)的 (3) 构造它的预测分析表 解：(1) FIRST( E ) = {(, a, b, ∧ } FOLLOW( E ) = {#, ) } FIRST( E' ) = { +,ε} FOLLOW( E' ) = {#, )} FIRST( T ) = { (, a, b, ∧} FOLLOW( T ) = { #, ),+} FIRST( T' ) = { (, a, b, ∧,ε} FOLLOW( T') = {#, ),+ } FIRST( F ) = { (, a, b, ∧} FOLLOW( F ) = { (, a, b, ∧,#, ),+} FIRST( F' ) = { *,ε} FOLLOW( F' ) = { (, a, b, ∧,#, ),+} FIRST( P ) = {(, 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(∧)= ∮