资源描述：
《编译原理课后答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1）优先顺序（从高至低）为+，*和↑，同级优先采用左结合。（2）优先顺序为↑，+，*，同级优先采用右结合。解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16（2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法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的最左推导和最右推导。解：（1）L（G6）=｛a
12、
13、a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N＝＞ND＝＞NDD＝＞NDDD＝＞DDDD＝＞0DDD＝＞01DD＝＞012D＝＞0127N＝＞ND＝＞N7＝＞ND7＝＞N27＝＞ND27＝＞N127＝＞D127＝＞0127N＝＞ND＝＞DD＝＞3D＝＞34N＝＞ND＝＞N4＝＞D4＝＞34N＝＞ND＝＞NDD＝＞DDD＝＞5DD＝＞56D＝＞568N＝＞ND＝＞N8＝＞ND8＝＞N68＝＞D68＝＞5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。解：A→SN,S→+
14、-
15、∑,N→D
16、MDD→1
17、3
18、5
19、7
20、9,M→MB
21、1
22、2
23、3
24、
25、4
26、5
27、6
28、7
29、8
30、9B→0
31、1
32、2
33、3
34、4
35、5
36、6
37、7
38、8
39、98.文法：最左推导:最右推导:语法树：/*************************************************/9．证明下面的文法是二义的：S→iSeS
40、iS
41、I解：因为iiiiei有两种最左推导，所以此文法是二义的。10．把下面文法改写为无二义的：S→SS
42、(S)
43、()解：S→ST
44、T,T→(S)
45、()11．给出下面语言的相应文法L1=｛anbnci
46、n≥1,i≥0｝L2=｛aibncn
47、n≥1,i≥0｝L3=｛anbnambm
48、n,m≥0｝L4=｛1n0m1m0n
49、n,
50、m≥0｝解：（1）S→AB
51、AA→aAb
52、abB→c
53、cB(2)S→AB
54、BA→a
55、aAB→bBc
56、bc(3)S→AB
57、A
58、B
59、∑A→aAb
60、abB→aBb
61、ab(4)S→1S0
62、0A1A→0A1
63、01第三章词法分析7.构造下列正规式的相应的DFA1(0
64、1)*1011(1010*
65、1(010)*1)*00*10*10*10*(00
66、11)*((01
67、10)(00
68、11)*(01
69、10)(00
70、11)*)*解答：（1）1(0
71、1)*101II0I1{X}Ф{A,B,C}{A,B,C}{B,C}{B,C,D}{B,C}{B,C}{B,C,D}{B,C,D}{B,C,E
72、}{B,C,D}{B,C,E}{B,C}{B,C,D,y}{B,C,D,y}{B,C,E}{B,C,D}S01ABBCDCCDDEDECFFED(2)1(1010*
73、1(010)*1)*0II0I1{X}Ф{A,B,C}{A,B,C}{y}{D,H,I,L}{y}ФФ{D,H,I,L}{E,J}{B,C}{E,J}Ф{B,C,F,G,K}{B,C}{y}{D,H,I,L}{B,C,F,G,K}{B,C,G,I,L,y}{D,H,I,L}{B,C,G,I,L,y}{B,C,G,J,y}{B,C,D,H,I,L}{B,C,G,J,y}{B,C,G,y}{D,H,I,L}
74、{D,H,I,K,L}{E,I,J,L}{B,C}{E,J,y}Ф{B,C,F,G,K}{E,I,J,L}{J}{B,C,F,G,K}{J}Ф{K}{K}{I,L}Ф{I,L}{J}{B,C}8.给出下面正规表达式（1）以01结尾的二进制数串（2）能被5整除的十进制整数（3）包含奇数个1或者奇数个0的二进制数串（4）英文字母组成的所有符号串，要求符号串中的字母按照字典序排列。（7）不包含子串abb的由a和b组成的符号串的全体。解答：（1）（0
75、1）*01（2）(1
76、2
77、…
78、9)(0
79、1
80、2
81、…
82、9)*(0
83、5)
84、0
85、5（3）0*1(0*10*10*)*（4）A*B*
86、…Z*(7)b*(a
87、ab)*9.对下面的情况给出DFA以及正规表达式。（1）{0，1}上的含有子串010的所有串。（2）{0，1}上不含子串010的所有串。解答：（1）（0
88、1）*010（0
89、1）*（2）1*(0
90、1*
91、1)*1*12将图3.8的（a）和(b)分别确定化和最少化。解：1确定化ab｛0｝｛0,1｝｛1｝｛0,1｝｛0,1｝｛1｝｛1｝｛0｝__令A=｛0｝B=｛0，1｝C=｛1｝则状态转换图为：2最少化首先，所有状态可分为终态集{AB}非终态集{C}其次，考察{AB}，由于{AB}由a到{B}，由b到{C}，所以不可分，令A={AB}则最少化后的
