期末复习——简答题、分析题 下载本文

简答题

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 页