编译原理及实现课后答案.pdf

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

douglasren-4117469-编译原理及实现课后习题答案.pdf-第1页.png

第1页 / 共33页

douglasren-4117469-编译原理及实现课后习题答案.pdf-第2页.png

第2页 / 共33页

douglasren-4117469-编译原理及实现课后习题答案.pdf-第3页.png

第3页 / 共33页

douglasren-4117469-编译原理及实现课后习题答案.pdf-第4页.png

第4页 / 共33页

douglasren-4117469-编译原理及实现课后习题答案.pdf-第5页.png

第5页 / 共33页

douglasren-4117469-编译原理及实现课后习题答案.pdf-第6页.png

第6页 / 共33页

douglasren-4117469-编译原理及实现课后习题答案.pdf-第7页.png

第7页 / 共33页

douglasren-4117469-编译原理及实现课后习题答案.pdf-第8页.png

第8页 / 共33页

文本预览

2.1 设字母表 A={a}，符号串 x=aaa，写出下列符号串及其长度：x0,xx,x5 以及 A+和 A*. x0=(aaa)0=ε | x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =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）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3 设有文法 G[S]：S∷=SS*|SS+|a，写出符号串 aa+a*规范推导，并构造语法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

S S S * S S + a a a 2.4 已知文法 G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5 已知文法 G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε 描述的语言: {an|n>=0} B∷=bBc︱bc 描述的语言：{bncn|n>=1} L(G[S])={anbmcm|n>=0,m>=1} 2.6 已知文法 E∷=T∣E+T∣E-T 、 T∷=F∣T*F∣T/F 、 F∷=(E)∣i，写出该文法的开始符号、终结符号集合 VT、非终结符号集合 VN。开始符号：E Vt={+, - , * , / ,（ , ）, i} Vn={E , F , T}

2.7 对 2.6 题的文法，写出句型 T+T*F+i 的短语、简单短语以及句柄。短语：T+T*F+i T+T*F i i T T*F 简单短语：i T*F T 句柄：T E + T E + T F T * F i E T 2.8 设有文法 G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？ S S S * S S + S S + S a a S * S a a a a 根据所给文法推导出句子 a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。 2.9 写一文法，使其语言是奇正整数集合。 A::=1|3|5|7|9|NA N::=0|1|2|3|4|5|6|7|8|9 2.10 给出语言{anbm|n,m≥1}的文法。 G[S]: S::=AB A::=aA|a

B::=bB|b 3.1 有正则文法 G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a ，画出该文法的状态图，并检查句子 abba 是否合法。解：该文法的状态图如下： S a V b b a U b a Z 句子 abba 合法。 3.2 状态图如图 3.35 所示，S 为开始状态，Z 为终止状态。写出相应的正则文法以及 V，Vn 和 Vt。 a A b S b a Z 图3-35状态图

解：左线性文法 G[Z]: 右线性文法 G’[S]: Z::=Ab|b A::=Aa|a V={Z,A,a,b} Vn={Z,A} Vt={a,b} S::=aA|b A::=aA|b V={S,A,a,b} Vn={S,A} Vt={a,b} 3.3 构造下列正则表达式相应的 NFA： 1(1|0)*|0 1(1010*|1(010)*1)*0 解：正则表达式：1(1|0)*|0 1、 2、 3、 S S 1(1|0)*|0 0 1(1|0)* Z Z

S q0 4、 1 1 0 0 A 1 0 0,1 q2 ε Z q1 正则表达式：1(1010*|1(010)*1)*0 1 0 1 1 1 ε 5 0 3 1 0 4 1 6 0 0 7 8 1 0 2 3.4 将图 3.36 的 NFA M 确定化 a 0 a,b a 图3.36 状态图 1

b {1} {1} Φ a {0,1} {0,1} {0} a q1 a b 解： q0={0} q1={0,1} q2={1} DFA: q0 a b q2 3.5 将图 3.37 的 DFA 化简。 0 a 1 a b a a b 2 4 b b b b 图3.37 DFA状态图 a a 3 5

解：划分 {0,1} a {1} b {2,4} {2,3,4,5} {1,0,3,5} {3,5,2,4} 划分 {0,1} {2,4} {3,5} a {1} {0,1} {3,5} q0={0,1} q1={2,4} q2={3,5} 化简后的 DFA： a q0 b a q1 b {2,4} {3,5} {2,4} b b q2 a

分享到：

赞收藏

资料库

编译原理及实现课后答案.pdf

相关推荐

课程资源

热门标签

最新资料