④ (/，②，③) ⑤ (－，④，d)
4. 已知文法 G[S] 为： S→dAB A→aA|a B→Bb|ε
G[S] 产生的语言是什么？
答：G[S]产生的语言是L(G[S])={danbm|n?1,m?0}。 5. 构造正规式相应的 DFA : 1(1010 * | 1(010) * 1) * 0。 解：1(1010 * | 1(010) * 1)
* 0对应的NFA为：
6. 已知文法G(S) S→a|∧|(T) T→T，S|S
写出句子((a，a)，a)的规范归约过程及每一步的句柄。 解：
句型 归约规则 句柄 ((a，a)，a) S→a a ((S，a)，a) T→S S ((T，a)，a) S→a a ((T，S)，a) T→T，S T，S ((S)，a) T→S S ((T)，a) S→S(T) (T) (S，a) T→S S (T，a) S→a a (T，S) T→T，S T，S (T) S→(T) (T) S
7. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：文法G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D
8. 设文法G(S)：
6
S→(L)|a S|a L→L，S|S (1) 消除左递归和回溯；
(2) 计算每个非终结符的FIRST和FOLLOW。 解：(1) S→(L)|aS' S'→S|ε L→SL' L'→SL'|ε (2)
FIRST)S)＝{(，a} FOLLOW(S)＝{#，，，)} FIRST(S')＝{，a,ε} FOLLOW(S')＝{#，，，)}
FIRST(L)＝{(，a} FOLLOW(L)＝{ )}
FIRST(L')＝{，，ε} FOLLOW(L'〕＝{ )} 9. 已知文法G(E) E→T|E＋T T→F|T *F F→(E)|i
(1)给出句型(T *F＋i)的最右推导； (2)给出句型(T *F＋i)的短语、素短语。
解：(1) 最右推导： E=>T->F=>(E)->(E＋T)=>(E＋F)->(E＋i)=>(T＋i)=>(T*F＋i) (2) 短语：(T*F＋i)，T*F＋i，T*F，i 素短语：T*F,i
10. While a＞0 ∨ b＜0 do Begin
X：＝X＋1；
if a＞0 then a：＝a－1 else b：＝b＋1 End；
翻译成四元式序列。 解：
(1) (j＞，a，0，5) (2) (j，－，－，3) (3) (j＜，b，0，5) (4) (j，－，－，15) (5) (＋，X，1，T1) (6) (：＝，T1，－，X) (7) (j≥，a，0，9) (8) (j，－，－，12) (9) (－，a，1，T2) (10) (：＝，T2，－，a) (11) (j，－，－，1) (12) (＋，b，1， T3) (13) (：＝，T3，－，b) (14) (j，－，－，1) (15)
11. 写出下列表达式的三地址形式的中间表示。 (1) 5+6 *(a + b);
7
(2)for j:=1 to 10 do a[j + j]:=0。 答： (1)100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2 (2)100: j:=1
101: if j>10 goto NEXT 102: i:=j+j 103: a[i]:=0
12. 设基本块p由如下语句构成： T 0 : =3.14; T 1 :=2*T 0 ; T 2 :=R+r;
A:=T l *T 2 ； B:=A;
T 3 :=2*T 0 ; T 4 :=R+r;
T 5 :=T 3 *T 4 ; T 6 :=R-r ； B:=T 5 *T 6 ；
试给出基本块p的 DAG 。
* A,T5 B * + T2,T4 - T6
1 3.14
解：基本块p的DAG图:
T0
2 6.28
T1,T3 3 R
4 r
13. 写出表达式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。 解：（1）三元式： ①（＋，a，b） ②（－，a，b） ③（/，①，②） ④（*，b，c） ⑤（＋，a，④） ⑥（－，③，⑤） （2）四元式：
①（＋，a，b，T1） ②（－，a，b，T2） ③（/，T1，T2，T3） ④（*，b，c，T4） ⑤（＋，a，T4，T5）
8
⑥（－，T3，T5，T6）
14. 写一个文法使其语言为偶数集，且每个偶数不以0开头。 解：文法G（S）： S→AB|B|A0 A→AD|C B→2|4|6|8 C→1|3|5|7|9|B D→0|C
15. 设文法 G （ S ）： S→S ＋ aF|aF| ＋ aF F→*aF|*a
（1）消除左递归和回溯；
（2）构造相应的 FIRST 和 Follow 集合。 解：（1）
S->aFS'|＋aFS' S'->＋aFS'|ε F->*aF' F'->F|ε （2）
FIRST（S）＝｛a，+｝ FOLLOW（S）＝｛＃｝ FIRST（S'）＝｛+，ε ｝ FOLLOW（S'）＝｛＃｝ FIRST（F）＝｛*｝ FOLLoW（F）＝（+，＃｝ FIRST（F'）＝｛*，ε｝ FOLLOW（+，＃｝ 16. 简要说明语义分析的基本功能。
答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。 17. 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S
消除文法的左递归及提取公共左因子。 解：消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε
提取公共左因子： S→(T) | aS′ S′→+S | ε T→ST′ T′→,ST′| ε
18. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 解： w a b + c d e 10 - / + 8 + * +
19. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： while (A if (A ≥ 1) C=C+1; else while (A ≤ D) A=A+2; }。 解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级 9 高)： 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, A) 111 (j,_,_,108) 112 (j,_,_,100) 113 20. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。 证明： 由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为： 因此，文法G[S]为二义文法。 21. 文法 G[S] 为： S->Ac|aB A->ab B->bc 写出 L(G[S]) 的全部元素。 解：S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc} 22. 构造正规式 1(0|1)*101 相应的DFA。 解：先构造NFA： 10