期末复习 - 简答题、分析题

分析题

有步骤的考试时按步骤给分，如果结果不对可以得步骤分

1. 将下图所示的NFA化简为DFA

状态转换表如下： I {x} {z} {x,z} {y} {x,y} {x,y,z} 重新命名新状态 I A B* C* D E 0 B C C E F 第 5 页 共 13 页

I0 {z} {x,z} {x,z} {x,y} {x,y,z} {x,y,z} I1 {x} {y} {x,y} Φ {x} {x,y} 1 A D E Φ A F* F E 状态转换图略(考试时必须画出)

2. 将下面程序划分成基本块并作出其程序控制流图 （1） Read(A,B) （2） F=1 （3） C=A*A （4） D=B*B

（5） If C

（15）If E>100 goto L2 （16）halt （17）L2:F=F-1 （18）goto L1 答案：

基本块为：（1）——（5） （6）——（10） （11）——（15） （16） （17）、（18）

第 6 页 共 13 页

控制流图

31 41 31 21 11 3. 设已构造出文法G(S)：

(1)S ? BB (2)B ? aB (3)B? b

的LR分析表如下 状态 0 1 2 3 4 5 6 7 8 9 a s3 s6 s3 r3 s6 r2 ACTION b s4 s7 s4 r3 s7 r2 # acc r1 r3 r2 S 1 GOTO B 2 5 8 9 采用LR分析、分析句子aaabab是否是该文法所描述的句子 分析过程如下： 步骤 1 2 栈中状态 0 03 栈中符号 # #a 输入符号串 aaabab# aabab# 第 7 页 共 13 页

分析动作 S3 S3 3 4 5 6 7 8 9 10 11 12 13 14

033 0333 03334 03338 0338 038 02 026 0267 0269 025 01 #aa #aaa #aaab #aaaB #aaB #aB #B #Ba #Bab #BaB #BB #S abab# bab# ab# ab# ab# ab# ab# b# # # # # S3 S4 r3(用规则③规约) r2(用规则②规约) r2(用规则②规约) r2(用规则②规约) S6 S7 r3(用规则③规约) r2(用规则②规约) r1(用规则①规约) acc 分析成功，说明aaabab是该文法所描述的句子

4. 有文法G(S)为：

S ?iEtSS’?a S’ ?eS ? ? E?b

构造其预测分析表 （1）求候选式的First集 对于S,有

FIRST(iEtSS’)={i} FIRST(a)={a} 对于S’，有 FIRST（eS）={e} FIRST(?)={? }

所以求FOLLOW(S’)={#}

对于E，有 FIRST(b)={b}

第 8 页 共 13 页