当前位置：文档之家 › 南京邮电大学 编译原理 课后习题答案和讲解2

南京邮电大学 编译原理 课后习题答案和讲解2

  • 格式：doc
  • 大小：644.50 KB
  • 文档页数：23

《编译原理》习题解答P38-39 8、设有文法G[S]：S∷＝aAbA∷＝BcA | BB∷＝idt |ε试问下列符号串（1）aidtcBcAb （3）ab （5）aidtcidtcidtb 是否为该文法的句型或句子。

（1）S⇒aAb⇒aBcAb⇒aidtcAb⇒aidtcBcAb 句型但不是句子；（3）S⇒aAb⇒aBb⇒aεb⇒ab 是句型也是句子；（5）S⇒aAb⇒aBcAb⇒aidtcAb⇒aidtcBcAb⇒aidtcidtcBb⇒aidtcidtcidtb句型也是句子。

P39 10、给定文法：S∷＝aB | bAA∷＝aS | bAA | aB∷＝bS |aBB|b 该文法所描述的语言是什么？L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。

P39 11、试分别描述下列文法所产生的语言（文法开始符号为S）：（1）S∷＝0S | 01（2）S∷＝aaS | bc（3）S:: =aSd | aAdA:: =aAc | bc（4）S:: =ABA:: =aAb | abB:: =cBd | ε（1）L(G)＝{0n1| n≥1}；（2）L(G)＝{a2n bc | n≥0}；１（3）L(G)＝{a i bc j d k | i, j, k≥1, i=j+k-1}；或者L(G)＝{a j+k-1bc j d k | j, k≥1}；（4）L(G)＝{a n b n c m d m | m≥0, n≥1}。

P39 15. 设文法G规则为：S：：=ABB：：=a|SbA：：=Aa|bB对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。

（2）baabaab（2）SA BA a S bb B Aa b B aa句型baabaab的短语a, ba, baa, baab, baabaab，简单短语a，句柄 aP40 19. 证明下述文法是二义的1) S::=iSeS|iS|i3) S::=A|BA::=aCbA|aB::=BCC|a２C::=ba (最简单的就是a为句型)1)对于句子iiieii可构造两棵不同的语法树，所以证明该文法是二义的。

P41 24. 下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？1.S::=aB B::= cB B::=b C::=c2.S::=aB B::=bC C::=c C::=ε3.S::=aAb aA::=aB aA::=aaA B::=b A::=a4.S::=aCd aC::=B aC::=aaA B::=b5.S::=AB A::=a B::=bC B::=b C::=c6. S::=AB A::=a B::=bC C::=c C::=ε7. S::=aA S::= ε A::=aA A::=aB A::=a B::=b8. S::=aA S::= ε A::=bAb A::=a正规文法 1 2 7上下文无关文法 5 6 8上下文有关文法 3短语结构文法 4P42 29. 用扩充的BNF表示以下文法规则：1．Z::=AB|AC|A2．A::=BC|BCD|AXZ|AXY3．S::=aABb|ab３4．A::=Aab|ε解:1．Z::=A（B|C|ε）::=A[B|C]2．A::=BC（ε|D）{X（Z|Y）}::= BC[D] {X（Z|Y）}3．A::=a((AB|ε)b) ::= a[AB]b4．A::={ab}P74 4. 画出下列文法的状态图：Z：：=BeB：：=AfA：：=e|Ae 并使用该状态图检查下列句子是否该文法的合法句子：f, eeff, eefe。

由状态图可知只有eefe是该文法的合法句子。

P74 5. 设右线性文法G=({S, A, B}, {a, b}, S, P)，其中P组成如下：S：：=bA A：：=bB A：：=aA A：：=b B：：=a画出该文法的状态转换图。

４P74 8. 设(NFA) M = ( {A, B}, {a, b}, M, {A}, {B} )，其中M定义如下：M (A, a) = {A, B} M (A, b) = {B} M (B, a) = ø M (B, b) = {A, B}请构造相应确定有穷自动机(DFA) M’。

解：构造一个如下的自动机(DFA) M’，(DFA) M’={K’, {a, b}, M’, S’, Z’} K’的元素是[A] [B] [A, B]由于M（A, a）={A, B}，故有M’（[A], a）=[A, B]同样M’（[A]，b）=[B]M’（[B]，a）=øM’（[B]，b）=[A，B]由于M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U ø= {A，B}故M’（[A，B]，a）= [A，B]由于M（{A，B}，b）= M（A，b）U M（B，b）={B}U {A，B} = {A，B}故M’（[A，B]，b）= [A，B]S’=[A]，终态集Z’={[A，B]，[B]}重新定义：令0=[A] 1=[B] 2=[A, B]，则DFA如下所示：５P74 10. 已知正规文法G = ({S, B, C}, {a, b, c}, P, S)，其中P内包含如下产生式：S::=aS | aB ……①B::=bB | bC ……②C::=cC | c ……③请构造一个等价的有穷自动机。

解：M=({S, B, C, T}, {a, b, c}, M, {S}, {T})M (S, a)=S M (S, a)=B M (S, b)=øM (S, c)=øM (B, a)=øM (B, b)=B M (B, b)=C M (B, c)=øM (C, a)=øM (C, b)=øM (C, c)=T M (C, c)=CP74 11. 构造下列正规式相应的DFA：（1）1(0|1)*101解：先构造该正规式的转换系统：７由上述转换系统可得状态转换集K={S, 1, 2, 3, 4, 5, Z}，状态子集转换矩阵如下表所示：其对应的DFA 状态转换图为：现在对该DFA 进行化简，最终得到下列化简后的状态转换图（先将其分成两组——终态组{5}和非终态组{0, 1, 2, 3, 4}，P74 12. 将图3.24非确定有穷自动机NFA 确定化和最少化。

a图3.24 NFA 状态转换图８解：设(DFA)M = {K, V T , M, S, Z}，其中，K={[0], [0, 1], [1]}，V T ={a, b}，M ： M ([1], a) =[0] M ([1], b) =Ф M ([0, 1], a) =[0, 1] M ([0, 1], b) =[1] M ([0], a) =[0, 1] M ([0], b) =[1] S=[1]，Z={[0], [0, 1]}令[0, 1]=2，则其相应的状态转换图为： 现在对该DFA 进行化简，先把状态分为两组： 终态组 {0, 2} 和非终态组 {1}，易于发现P74 18.根据下面正规文法构造等价的正规表达式：S::=cC | a ……① A::=cA | aB ……② B::=aB | c ……③C::=aS | aA | bB | cC | a ……④ 解：由③式可得 B= aB + c → B=a*c 由②式可得 A= cA + aB → A= c*aa*c 由①式可得 S= cC + a由④式可得 C= aS + aA + bB + cC + a → C= c*( aS + aA + bB + a) →C= c*( aS + ac*aa*c + ba*c + a) → S= cc*( aS + ac*aa*c + ba*c + a) + a = cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a) = (cc*a)*( cc*( ac*aa*c | ba*c | a) | a)P142 1. 试分别消除下列文法的直接左递归（采用两种方法——重复法和改写法） （1）G[E]:E::=T | EAT ……①T::=F | TMF ……②F::=(E) | i ……③A::=+ | - ……④M::=* | / ……⑤解：先采用“重复法”：再采用“改写法”：E::=T{AT} E::=TE’T::=F{MF} E’::= ATE’ | εF::=(E) | i T::=FT’A::=+ | - T’::=MFT’ | εM::=* | / F::=(E) | iA::=+ | -M::=* | /（4）G[Z]:Z::=V1……①V1::=V2 | V1iV2……②V2::=V3 | V2+V3……③V3::=)V1*| ( ……④解：先采用“重复法”：再采用“改写法”：Z::=V1Z::=V1V1::=V2 {iV2} V1::=V2 V1’V2::=V3 {+V3} V1’::=i V2 V1’ | εV3::=)V1*| ( V2::=V3 V2’V2’::=+V3 V2’ | εV3::=)V1*| (P142 2. 试分别消除下列文法的间接左递归（2）G[Z]:Z::=AZ| b ……①９A::=Z A | a ……②解(一)：将②式代入①式可得，Z::=ZAZ| aZ | b 消除左递归后得到：Z::=(aZ | b)Z’Z’::=AZZ’ | εA::=ZA| a解(二)：将①式代入②式可得，A::= AZA| bA | a 消除左递归后得到：Z::= AZ| bA::=bAA’ | aA’A’::=ZAA’|εP143 5. 对下面的文法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）构造它的LL（1）分析表并分析符号串a*b+b;解:（1）构造FIRST集：FIRST(E’)={+, ε}FIRST(F’)={*, ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧}FIRST(T’)={ (，a，b, ε，∧}构造FOLLOW 集：规则一１０＃∈FOLLOW(E) FOLLOW(E)={#}规则二)∈FOLLOW(E) FOLLOE(E)={ )，#}FIRST(E’)-{ε}FOLLOW(T) FOLLOW(T)={+}FIRST(T’)-{ε}FOLLOW(F) FOLLOW(F)={ (，a，b，∧}FIRST(F’)-{ε}FOLLOW(P) FOLLOW(P)={*}规则三FOLLOW(E) FOLLOW(E’) FOLLOW(E’)={#，)}FOLLOW(E) FOLLOW(T) FOLLOW(T)={＋，＃，）}FOLLOW(T) FOLLOW(T’) FOLLOW(T’)= {＋，＃，）}FOLLOW(T) FOLLOW(F) FOLLOW(F)={ (，)，a，b，＋，＃，∧} FOLLOW(F) FOLLOW(F’) FOLLOW(F’)= { (，)，a，b，＋，＃，∧} FOLLOW(F) FOLLOW(P) FOLLOW(P)= { (，)，a，b，＋，＃，∧,*} 最后结果为：FIRST(E’)={+, ε}FIRST(F’)={*, ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧}FIRST(T’)={ (，a，b, ε，∧)FOLLOE(E)={ ), ＃}FOLLOW(E’)={＃，)}FOLLOW(T)={＋，＃，）}FOLLOW(T’)= {＋，＃，）}FOLLOW(F)={ (，)，a，b，＋，＃，∧}FOLLOW(F’)={ (，)，a，b，＋，＃，∧}FOLLOW(P)= { (，)，a，b，＋，＃，∧,*}（2）证明该文法是LL（1）文法：证明：对于规则E’::=+E |ε，T’::=T |ε，F’::=*F’ |ε（仅有一边能推出空串）有FIRST(+E)={+}∩FIRST(ε)= ø，FIRST(T)={(, a, b, ∧}∩FIRST(ε)= øFIRST(*F’)={*}∩FIRST(ε)= ø，FIRST(+E)={+}∩FOLLOW(E’)= {#, )}=øFIRST(T)={(, a, b, ∧}∩FOLLOW(T’)= {+, #, )}=øFIRST(*F’)={*}∩FOLLOW(F’)= { (，)，a，b，＋，＃，∧}=ø所以该文法是LL（1）文法。

合集下载

编译原理_第三版_课后答案

编译原理_第三版_课后答案


{2,3,5,7,9,10} {2,4,5,7,8,10} {2,4,5,7,8,10} {11} {6} ห้องสมุดไป่ตู้ {2,5,7,8,10} φ φ
{2,3,5,7,10} {2,3,5,7,9,10} φ φ
{11} {11} φ φ S
{6} {6} φ φ
3: 5: 6: S a b S S A a b A a A S b A
文法： (1) 最左推导: 最右推导: (2) (((a,a),^,(a)),a) (((S,a),^,(a)),a) (((T,a),^,(a)),a) (((T,S),^,(a)),a) (((T),^,(a)),a)
((S,^,(a)),a) ((T,^,(a)),a) ((T,S,(a)),a) ((T,(a)),a) ((T,(S)),a) ((T,(T)),a) ((T,S),a) ((T),a) (S,a) (T,S) (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)# 归 6 #(((T ,a),^,(a)),a)# 归 7 #(((T, a),^,(a)),a)# 进 8 #(((T,a ),^,(a)),a)# 进 9 #(((T,S ),^,(a)),a)# 归 10 #(((T ),^,(a)),a)# 归 11 #(((T) ,^,(a)),a)# 进 12 #((S ,^,(a)),a)# 归 13 #((T ,^,(a)),a)# 归 14 #((T, ^,(a)),a)# 进 15 #((T,^ ,(a)),a)# 进 16 #((T,S ,(a)),a)# 归 17 #((T ,(a)),a)# 归 18 #((T, (a)),a)# 进 19 #((T,( a)),a)# 进 20 #((T,(a )),a)# 进 21 #((T,(S )),a)# 归 22 #((T,(T )),a)# 归
编译原理及实现课后习题答案

编译原理及实现课后习题答案

编译原理及实现课后习题解答2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*.x0=(aaa)0=ε| x0|=0xx=aaaaaa |xx|=6x5=aaaaaaaaaaaaaaa | x5|=15A+ =A1∪A2∪…. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…}A* = A0 ∪A1 ∪A2∪…. ∪ A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…}2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3xy=abcb |xy|=4xyz=abcbaab |xyz|=7(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=122.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。

S => SS* => Sa* => SS+a* => Sa+a* => aa+a*2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。

Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z01=>U001=>1001Z=>V1=>Z01=>V101=>01012.5 已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。

A∷=aA︱ε描述的语言: {a n|n>=0}B∷=bBc︱bc描述的语言：{b n c n|n>=1}L(G[S])={a n b m c m|n>=0,m>=1}2.6 已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。

编译原理课后习题答案+清华大学出版社第二版

编译原理课后习题答案+清华大学出版社第二版

也称基地址。 SL： 静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，
用以引用非局部（包围它的过程）变量时，寻找该变量的地址。 DL： 动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放
数据空间时，恢复调用该过程前运行栈的状态。 RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地
编译程序大致有哪几种开发技术？
答案：
（1）自编译：用某一高级语言书写其本身的编译程序。 （2）交叉编译：A 机器上的编译程序能产生 B 机器上的目标代码。 （3）自展：首先确定一个非常简单的核心语言 L0，用机器语言或汇编语言书写出它的编
译程序 T0，再把语言 L0 扩充到 L1，此时 L0⊂ L1 ,并用 L0 编写 L1 的编译程序 T1，再把语 言 L1 扩充为 L2，有 L1 ⊂ L2 ,并用 L1 编写 L2 的编译程序 T2，……，如此逐步扩展下 去， 好似滚雪球一样，直到我们所要求的编译程序。 （4）移植：将 A 机器上的某高级语言的编译程序搬到 B 机器上运行。
(main).
答案： 程序执行到赋值语句 b∶=10 时运行栈的布局示意图为：
1
《编译原理》课后习题答案第二章
第 3题 写出题 2 中当程序编译到 r 的过程体时的名字表 table 的内 容。
name
kind
level/val
adr
size
答案：
题 2 中当程序编译到 r 的过程体时的名字表 table 的内容为：
盛威网（）专业的计算机学习网站
2
《编译原理》课后习题答案第一章
合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行 中间代码程序，最后得到运行结果。
编译原理习题参考答案

编译原理习题参考答案

程序设计语言与编译——语言的设计与实现（第2版）习题4答案4-5 解：上下文有关文法（1型文法），产生的语言L（G）{=a i b i c i | i≥1,i为整数} 4-6 解：3型文法，L（G）={a i | i≥1,i为奇数}4-7 解：2型文法，L（G）={a i b i | i≥1,i为整数}4-8 解：1型文法，L（G）={a i b i c i | i≥1,i为整数}4-9 解：1. 最左推导最右推导S⇒ (A) ⇒ (B) ⇒(SdB) S⇒ (A) ⇒ (B) ⇒ (SdB)⇒ ((A)dB) ⇒ ((B)dB) ⇒ (SdS) ⇒ (Sda)⇒ ((S)dB) ⇒ ((b)dB) ⇒ ((A)da ⇒ ((B)da)⇒ ((b)dS) ⇒ ((b)da) ⇒ ((s)da⇒ ((b)da)2. 语法树4-10解：1. 因为存在推导S ⇒ SbF ⇒ SbP ⇒ Sbc ⇒ Fbc ⇒ FaPbc所以FaPbc是文法G (S) 的一个句型。

2. 语法树4-11解：因为串aaabaa可有下列两棵不同的语法树所以文法G (S)是二义文法。

因为串i(*可有下列两棵不同的语法树9-2解：（1）消除文法G的②产生式直接左递归。

A→SeA' | fA' ③A'→dA' | ε④（2）消除间接左递归：按S.A排序，将S的①产生式代入③有A→AaeA' | AbeA' | ceA' | fA' ⑤（3）消除⑤的直接左递归有A→ceA'A" | fA'A" ⑥A"→aeA'A" | beA'A" | ε⑦（4）对S的①产生式提公因子有S→AB | c ⑧B→| a | b ⑨（5）最后，文法G提取公因子，消除左递归后的产生式由⑧, ⑨, ⑥, ⑦和④组成，无多余的产生式。