资源描述：
《编译原理作业题答案080104 - 编译原理课后题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章高级语言的语法描述6、令文法G6为：N→D
2、NDD→0
3、1
4、2
5、3
6、4
7、5
8、6
9、7
10、8
11、9（1）G6的语言L（G6）是什么？（2）给出句子0127、34和568的最左推导和最右推导。解答：思路：由N→D
12、ND可得出如下推导N＝＞ND＝＞NDD＝＞…＝＞Dn（n＞=1）可以看出，N最终可以推导出1个或多个（也可以是无穷）D，而D→0
13、1
14、2
15、3
16、4
17、5
18、6
19、7
20、8
21、9可知，每个D为0～9中的任一个数字，所以，N最终推导出的就是由0～9这10个数字组成的字符串。（1）G6的语言L（G6）是由0～9这10个数字组成的字符串,或{0，1,…
22、,9}+。(2)句子0127、34和568的最左推导分别为:N＝＞ND＝＞NDD＝＞NDDD＝＞DDDD＝＞0DDD＝＞01DD＝＞012D＝＞0127N＝＞ND＝＞DD＝＞3D＝＞34N＝＞ND＝＞NDD＝＞DDD＝＞5DD＝＞56D＝＞568句子0127、34和568的最右推导分别为:N＝＞ND＝＞N7＝＞ND7＝＞N27＝＞ND27＝＞N127＝＞D127＝＞0127N＝＞ND＝＞N4＝＞D4＝＞34N＝＞ND＝＞N8＝＞ND8＝＞N68＝＞D68＝＞5687、写一个文法，使其语言是奇数集，且每个基数不以0开头。解答：G（S）：S→
23、CD
24、DD→1
25、3
26、5
27、7
28、9C→CB
29、AA→2
30、4
31、6
32、8
33、DB→A
34、0或：G（S）：S→MWN
35、NN→1
36、3
37、5
38、7
39、9M→1
40、2
41、3
42、4
43、5
44、6
45、7
46、8
47、9W→WV
48、εV→M
49、08、令文法为：E→T
50、E+T
51、E-TT→F
52、T*F
53、T/FF→（E）
54、i（1）i+i*i、i*（i+i）的最左推导和最右推导；（2）给出i+i+i、i+i*i和i-i-i的语法树。解答：（1）i+i*i、i*（i+i）的最左推导分别为：E＝＞T＝＞E+T＝＞F+T＝＞i+T＝＞i+T*F＝＞i+F*F＝＞i+i*F＝＞i+i*iE＝＞T＝＞T*F＝＞F*F＝
55、＞i*F＝＞i*（E）＝＞i*（E+T）＝＞i*（T+T）＝＞i*（F+T）＝＞i*（i+T）＝＞i*（i+F）＝＞i*（i+i）i+i*i、i*（i+i）的最右推导分别为：E＝＞T＝＞E+T＝＞E+T*F＝＞E+T*i＝＞E+F*i＝＞E+i*i＝＞T+i*i＝＞F+i*i＝＞i+i*iE＝＞T＝＞T*F＝＞T*（E+T）＝＞T*（E+F）＝＞T*（E+i）＝＞T*（T+i）＝＞T*（F+i）＝＞T*（i+i）＝＞F*（i+i）＝＞i*（i+i）（2）EEEE+TE+TE-TTT*FTT*FE-TFFFiFFiTFiiiiiFii+i+
56、Ii+i*iii-i-i9、证明下面的文法是二义的：S→iSeS
57、iS
58、i证明：思路：要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。对于句子iiiei，存在如下两个最右推导：S＝＞iSeS＝＞iSei＝＞iiSei＝＞iiieiS＝＞iS＝＞iiSeS＝＞iiSei＝＞iiiei由此，该文法是二义的。10、把下面文法改写为无二义的：S→SS
59、（S）
60、（）解答：思路：对于句子（）（）（），存在如下两棵语法树，所以该文法是二义性文法，引起SSSSSSSS（）（）SS（）（）（）（）二义性的原因在于
61、S→SS，可将其改造成等价的递归结构，消除二义性。改造后的文法为：S→TS
62、TT→（S）
63、（）11、给出下面语言的相应文法：L1={anbnci
64、n>=1,i>=0}L2={aibncn
65、n>=1,i>=0}L3={anbnambm
66、n,m>=0}L4={1n0m1m0n
67、n,m>=0}解答:分析:L1:要求a和b的个数一样多,并至少为1个,c的个数为0个以上,可用一个非终结符去生成anbn串,一个非终结符生成ci;L2同L1。L3:将anbnambm分为两段考虑,anbn和ambm,然后使用两个终结符分别产生。L4:采用从里往外扩展的方
68、式,先用一个非终结符生成中间的m个0和m个1,然后，再用另一个非终结符在该串的基础上扩充前后的n个0和n个1。L1的文法:S→ACA→aAb
69、abC→Cc
70、εL2的文法:S→ABA→Aa
71、εB→bBc
72、bcL3的文法:S→ABA→aAb
73、εB→aBb
74、εL4的文法:S→1A0
75、AA→0A1
76、ε第三章词法分析7、构造下列正规式相应的DFA：(1)1（0
77、1）*101(2)1(1010*
78、1(010)*1)*0(3)0*10*10*10*解答：210（1）第1步：根据正规式构造NFA，引入初态X和终止态Y。ε314051yx11ε（2）第2步
79、：对上NFA进行确定化，得到如下状态转化矩阵。状态I0I1XΦ{1，2，3}{1，2，3}{2，3}{2，3，4}{2，3}{2，3}{2，3，4}{2，3，4}{2，3，5}{2，3，4}{
