5、Sb
6、b，试证明文法G[S]为二义文法。A答案1答：语义分析的基本功能包括:确定类型、类型检查、语义处理和某些静态语义检查。2解：消除文法G[S]的左递归：S→(T)
7、
8、a+S
9、aT→ST′T′→,ST′
10、ε提取公共左因子：S→(T)
11、aS′S′→+S
12、εT→ST′T′→,ST′
13、ε3答：wab+cde10-/+8+*+4答：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)：100(j<,A,C,102)101(j,_,_,113)102(j<,B,D,104)103(j,_,_,113)104(j=,A,1,106)105(j,_,_,108)106(+,C,1,C)107(j,_,_,112)108(j≤,A,D,110)109(j,_,_,112)110(+,A,2,
14、A)111(j,_,_,108)112(j,_,_,100)1135答：证明： 由文法G[S]：S→aSb
15、Sb
16、b，对句子aabbbb对应的两棵语法树为： 因此，文法G[S]为二义文法。 编译原理B1.什么是句子？什么是语言?2.写一文法，使其语言是偶正整数的集合,要求： (1)允许0打头； (2)不允许0打头。3.已知文法G[E]为： E→T
17、E+T
18、E-T T→F
19、T*F
20、T/F F→（E）
21、i①该文法的开始符号（识别符号）是什么？②请给出该文法的终结符号集合VT和非终结符号集合VN。③找出句型T+T*F+i的所有短语、简
22、单短语和句柄。4.构造正规式相应的NFA:1(0
23、1)*101。5.写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列。B卷答案1答：(1)设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈VT*),则称x是文法的一个句子。(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*}。2解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:S->PD
24、DP->NP
25、ND->0
26、2
27、4
28、6
29、8N->0
30、1
31、2
32、3
33、4
34、5
35、6
36、7
37、8
38、9(2)G[S]=({S,P,R,D,N,Q}
39、,{0,1,2,…,9},P,S)P:S->PD
40、P0
41、DP->NR
42、NR->QR
43、QD->2
44、4
45、6
46、8N->1
47、2
48、3
49、4
50、5
51、6
52、7
53、8
54、9Q->0
55、1
56、2
57、3
58、4
59、5
60、6
61、7
62、8
63、93解：①该文法的开始符号（识别符号）是E。②该文法的终结符号集合VT={+、-、*、/、（、）、i}。非终结符号集合VN={E、T、F}。③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;简单短语为i、T*F、第一个T;句柄为第一个T。4解：1(0
64、1)*101对应的NFA为5解：逆波兰表示： abc*＋ab＋/d－ 三元式序列：
65、①(*，b，c) ②(＋，a，①) ③(＋，a，b) ④(/，②，③) ⑤(－，④，d)编译原理C1．(10分)对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。（1）else没有匹配的if（2）数组下标越界（3）使用的函数没有定义（4）在数中出现非数字字符（5）函数调用时实参与形参类型不一致。2．(15分)构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式3．(10分)为下面的语言设计文法：（1）{ambn,其中m³n}（2）{w
66、
67、wÎ{a,b}*，w的长度为奇数}证明E+T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。5．(15分)给定文法：E→E+T
68、E-T
69、TT→T*F
70、T/F
71、FF→(E)
72、idC卷答案1答案：（每小题2分）（1）语法分析（2）语法分析（3）语义分析（4）词法分析（5）语义分析2答案：按题意相应的正规表达式是(0*10)*0*，或0*(0
73、10)*0*，构造相应的DFA。3答案：（每小题10分）（1）考虑在先产生同样数目的a,b，然后再生成多余的a。以下是一种解法：S→aSb
74、aS
75、ε（2）A→aB
76、bBB→aA
77、bA
78、ε5证明E+T*（id）是
