简答题

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 页