计算机编译原理 _课后答案[1-5章].pdf

发布时间：2022-06-02 发布人：admin 分类：说明书资料大小：0.15M 资料格式：pdf 举报版权申诉

qq_43440447-12384512-4744302542989746152.pdf-第1页.png

第1页 / 共22页

qq_43440447-12384512-4744302542989746152.pdf-第2页.png

第2页 / 共22页

qq_43440447-12384512-4744302542989746152.pdf-第3页.png

第3页 / 共22页

qq_43440447-12384512-4744302542989746152.pdf-第4页.png

第4页 / 共22页

qq_43440447-12384512-4744302542989746152.pdf-第5页.png

第5页 / 共22页

qq_43440447-12384512-4744302542989746152.pdf-第6页.png

第6页 / 共22页

qq_43440447-12384512-4744302542989746152.pdf-第7页.png

第7页 / 共22页

qq_43440447-12384512-4744302542989746152.pdf-第8页.png

第8页 / 共22页

文本预览

学手助霸第二章 xuebazhushou.com 习题 1 6.答:省略表示法:{1.3,1.33,1.333…};描述表示法:{1.3i|i=1,2,3…} 7.答:x+={0,12,123,1234…}; x*={,0,12,123 …} 8.答:长度为 0 的符号串个数:0 个长度为 1 的符号串个数:26 个长度为 2 的符号串个数:26*36=936 个长度为 3 的符号串个数:26*36*36=33696 个长度不大于 3 的符号串个数:26+936+33696=34658 个有代表性的符号串:a,a0,aa,a00,a0a,aa0 习题 2 3.(1)E (2)EE+TE+T+TE+T*F+FE+T*F+iE+T*T*F+i TT/FF/F(E)/F(E+T)/F(T+T)/F(F+F)/F(i+i)/i E+T*F*F+i E+T*F*i+i 助霸手学显然结论成立; xuebazhushou.com 短语:E+T 是相对于 E 的短语;F 是相对于 T 的短语;i 是相对于 F 的短语;T*F 是相对于 T 的短语;E+T+T 是相对于 E 的短语;E+T+F 是相对于 E 的短语;E+T+i 是相对于 E 的短语; E+T*F 是相对于 E 的短语;E+T*F*F 是相对于 E 的短语;E+T*F*i 是相对于 E 的短语; E+T*F*i+i 是相对于 E 的短语. 简单短语:E+T 是相对于 E 的简单短语;F 是相对于 T 的简单短语;i 是相对于 F 的简单短语;T*F 是相对于 T 的简单短语; 5.解:L(G[A])={bn-1a|n=1,2…} L(G[W])={bn-1a2|n=1,2…} 证明:当 n=1 时,WAaaaa2, 假设 n=k 时 W*bk-1a2; 则当 n=k+1 时,WAa*bbk-1aa(bka2) 综上,结论对一切 n>=1 成立,即 W*bn-1a2 在上面的规纳证明中,利用文法的一切规则且仅用了文法中的规则,因此,该文法产生的语言 L(G[W])={bn-1a2|n=1,2 …} 6.(1)Z::=aAd|aZd A::=bc|bAc (2)Z::=AB A::=ab|aAb B::=b|Bb 7. 解:题中要求文法是: Z::=1|3|5|7|9|Z1|Z3|Z5|Z7|Z9|A1|A3|A5|A7|A9 A::=2|4|6|8|A0|A2|A4|A6|A8|Z0|Z2|Z4|Z6|Z8 习题 5 2. 最左推导:S(T)(T,S)(S,S)(a,S)(a,(T))(a,(S))(a,(b)) 最右推导:S(T)(T,S)(T,(T))(T,(S))(T,(b))(S,(b))(a,(b)) 最右推导是规范分析,最右推导每一步的句柄是: 霸手助 xuebazhushou.com 学学霸助手[xuebazhushou.com]-课后答案|期末试卷|复习提纲

手助霸 ①(;②T;③(;④S;⑤b;⑥S;⑦a 4.(2)证明: xuebazhushou.com 学从上面两个语法树中可得出对于文法 G[S]:S::=iScS|iS|i 的句子 iiici 有两个不同的语法树 ,故得出该文法是二义性的. 5.(1)方法一:自顶向下手助霸 xuebazhushou.com 学最右推导: Z 方法二:自底向上 AAiBAiCAi(Bi(B+Ci(B+(i(C+(i((+(i( 手助霸 xuebazhushou.com 学学霸助手[xuebazhushou.com]-课后答案|期末试卷|复习提纲

AAiBAiCAi(Bi(B+Ci(B+(i(C+(i((+(i( 第三章手助霸最左归约: Z xuebazhushou.com 学习题 6 3.解：DFAD= （{A,B,C,D,E,F},{0,1},M,A,{E,F}） M： M(A,0)=B M(B,0)=DM(B,1)=C M(C,0)=AM(C,1)=F M(D,0)=AM(D,1)=C M(E,0)=DM(E,1)=C M(F,0)=EM(F,1)=A 对于字符串 0011011 运行 DFA D 有： M(A,0011011) =M(M(A,0),011011) =M(M(B,0),11011) =M(M(D,1),1011) =M(M(C,1),011) =M(M(F,0),11) =M(M(E,1),1) =M(C,1) =F ∴DFA D 能接受字符串 0011011 8.解：将状态转换图列表，即： xuebazhushou.com 学霸由左图可知，该状态转换图直接对应的是确定有穷状态自动机 DFA DFAD= （{0,1,2,3,4,5},{a,b},M,0,{0,1}） M:M(0,a)=1M(0,b)=2 M(1,a)=1M(1,b)=4 M(2,a)=1M(2,b)=3 M(3,a)=3M(3,b)=2 M(4,a)=0M(4,b)=5 M(5,a)=5M(5,b)=1 手助手助霸 xuebazhushou.com 学学霸助手[xuebazhushou.com]-课后答案|期末试卷|复习提纲

手助霸化简： 1.分化 ① {0,1}{2,3,4,5} ② {0,1}{2,4}{3,5} 2.合并 xuebazhushou.com 学 3.删除没有无用状态和死状态，所以化简到此结束状态最小化图：手助霸 xuebazhushou.com 学 9.(1)证明：e1|e2=e2|e1 |e1|e2|=|e1|∪|e2|=|e2|∪|e1|=|e2|e1| ∴e1|e2=e2|e1 (2)证明：(e1|e2)e3=e1e3|e2e3 |(e1|e2)e3|=|(e1|e2)||e3|=|e1|e2||e3|=(|e1|∪|e2|)|e3|=|e1||e3|∪|e2| |e3|=|e1e3|∪|e2e3|=|e1e3|e2e3| ∴(e1|e2)e3=e1e3|e2e3 10．证明：e=b|ae 当且仅当 e={a}b 证：充分性：正则表达式 e=b|ae 的值是这样一个正则集，以无数个小 a 开头，后跟一个小 b。即：e={a}b。必要性：|{a}b|=|{a}||b|=|a|*|b| ∴e=b|ae 当且仅当 e={a}b 11.(1) 从 e 构造转换系统：手助霸 xuebazhushou.com 学学霸助手[xuebazhushou.com]-课后答案|期末试卷|复习提纲

手助霸 xuebazhushou.com 学手助去ε弧及无用状态和死状态：霸 xuebazhushou.com 学由状态转换图构造 NFA： NFAA=({S,A,B,C,D,F,Z},{0,1},M,{S},{Z}) M: 由 NFA 产生 DFA: 手助霸 xuebazhushou.com 学学霸助手[xuebazhushou.com]-课后答案|期末试卷|复习提纲

手助霸 xuebazhushou.com 学分化:①{[S],[C],[A],[AD],[AF],[ABF]}{[AFZ]} ②{[S]}{[C]}{[A],[AF],[ABF]}{[AD]}{[AFZ]} 最小化: 手助 (2)由 e 构造转换系统: 霸 xuebazhushou.com 学去ε弧及无用状态和死状态: 因为现在只有一个状态,所以无需再最小化,此时就是最小化. 13.解：建立方程组如下： W=Ua+Vb ① U=Va+c ② V=Ub+c ③ 把③代入②得，U=(Ub+c)a+c =Uba+ca+c 把它改写成 U=(ca+c){ba},因此 U=(ca|c){ba} ④ 手助霸 xuebazhushou.com 学学霸助手[xuebazhushou.com]-课后答案|期末试卷|复习提纲

助把②代入③得，V=(Va+c)b+c =Vab+cb+c 把它改写成 V=(cb+c){ab},因此 V=(cb|c){ab} ⑤ 把④⑤代入①得，W=Ua+Vb=(ca|c){ba}a+(cb|c){ab}b 因此 W=(ca|c){ba}a|(cb|c){ab}b 霸手 xuebazhushou.com 学第四章手霸学助 xuebazhushou.com 6、试消去文法 G[S]： S∷=Qc|Rd|c Q∷=Rb|Se|b R∷=Sa|Qf|a 文法左递归与规则左递归。解： step1:U1=SU2=QU3=R step2:i=1,j=1:j>i-1, 不执行关于 j 的循环，且关于 U1=S 不存在规则左递归 i=2,j=1:U2=Q ∷=(Qc|Rd|c)e|Rb|b =Qce|Rde|ce|Rb|b 消去规则左递归： Q∷=RdeQ′|ceQ′|RbQ′|bQ′ Q′∷=ceQ′|ε i=3,j=1:U3=R∷=Qca|Rda|ca|Qf|a j=2:R∷=RdeQ′ca|ceQ′ca|RbQ′ca|bQ′ca|Rda|ca|RdeQ′f|cf| RbQ′f|bQ′f|a 消去规则左递归： R∷=ceQ′caR′|bQ′caR′|caR′|ceQ′fR′|bQ′fR′|aR′ R∷=deQ′caR′|bQ′caR′|daR′|deQ′fR′|bQ′fR′|ε Step3: G′[S]: S∷=Qc|Rd|c Q∷=RdeQ′|ceQ′|RbQ′|bQ′ Q′∷=ceQ′|ε R∷=ceQ′caR′|bQ′caR′|caR′|ceQ′fR′|bQ′fR′|aR′ R∷=deQ′caR′|bQ′caR′|daR′|deQ′fR′|bQ′fR′|ε 此文法没有多余规则，所以消去左递归后的文法就是 G′[S] 4、试为文法 G[P]： P∷=begin Send S ∷=A|C A∷=V:=E C∷=if Ethen S E∷=V E∷=E+V V∷=i 采用某种程序设计语言构造递归下降识别程序。解：由于文法存在左递归，进行文法等价变换，得到等价文法 G′[P]： P∷=begin Send S ∷=A|C A∷=V:=E C∷=if Ethen S E∷=VE′ E′∷=+VE′|ε V∷=i 流程图如下：霸手助 xuebazhushou.com 学学霸助手[xuebazhushou.com]-课后答案|期末试卷|复习提纲

分享到：

赞收藏

资料库

计算机编译原理 _课后答案[1-5章].pdf

相关推荐

行业

热门标签

最新资料