简答题
1. 已知文法G(E) E→T|E＋T T→F|T *F F→(E)|i
(1)判断符号串i+i*i是否为文法G(S)的句子，如果是画出其分析树。 (2)给出G(E)的元语言符号集、文法符号集、终结符集、非终结符集 答案：
(1)是，分析树为 (答案不唯一)
i
i
F
F
i
T
T
*
F
E
E +
T
(2)元语言符号集：→ |
文法符号集：E、T、F、+、*、(、)、i 终结符集：+、*、(、)、i 非终结符集：E、T、F
2. 画出下列有限自动机的状态转换图和状态转换矩阵
M＝({S，A，B，C}，{0，1}，f，S，{C})，其转换函数为：
f(S，0)=B f(S，1)=A f(A，0)=C f(A，1)=S
状态转换图
第 1 页 共 13 页
f(B，0)= S f(B，1)= C f(C，0)= A f(C，1)= B
1
1
S 0
0
状态转换矩阵 输 入 符 号 状 态 S A B C A 0 1 B 0 C 1 0 B C S A 1 A S C B
3. 构造下列正则表达式的非确定的有限状态自动机。
aba(a|b)*a a a ε a b 0 1 2 3 4 4. 写出下列非确定的有限自动机对应的正规式 b Y X,Y
X 第 2 页 共 13 页
ε 5 a 6 X 2 Y 1 4 Y 3 X 答案：
(X|Y)(XYY|YXX)
5. 已知文法G(S)为：
S → AB
A → aB | bS | c
B → AS | d
*
*
*
求非终结符的First和Follow集 First(S)={a，b，c} First(A)={a，b，c} First(B)={a，b，c，d} Follow(S)={﹟，a，b，c，d} Follow(A)={a，b，c，d} Follow(B)={a，b，c，d，﹟}
6. 写出表达式a=(a+b)/(a-b)-(a+b)*c的逆波兰式、三元式、间接三元式序列及四元序列。
逆波兰式：ab+ab-/ 三元式 ① ② ③ ④ ⑤ ⑥ ⑦ 间接三元式 ① ② ③ ④ ⑤ ⑥ + - / * - = a a ① ① ③ a 第 3 页 共 13 页
+ - / + * - = a a ① a ④ ③ a b b ② b c ⑤ ⑥ b b ② c ④ ⑤ ① ② ③ ① ④ ⑤ 四元式 + - / + * - =
7. 消除下列文法的直接左递归
E->E+T T->T*F|F F->(E)|id|F(id) 答案： E->E’ E’->+TE’|ε T->FT’ T’->*FT’|ε F->(E)F’|idF’ F’->(id)F’|ε
9. LASTVT 和
a a T1 a T4 T3 T6 b b T2 b c T5 T1 T2 T3 T4 T5 T6 a 计算所有非终结符的FIRSTVT 第 4 页 共 13 页