福州大学软件学院 2007～2008 学年第一学期 《编译原理》课程 期末考试（A 卷） 一、 单项选择题（每小题 1 分，共 10 分） 参考答案与评分标准 2、B 1、D 二、 填空分析题（每个空格 1 分，共 10 分） 7、D 4、A 6、A 3、A 5、B 8、 D 9、A 10、D 1、可规约符号串，左部 2、从左到右进行分析，采用最右推导的逆过程即最左归约，不向前看输入字符 3、移进-规约，规约-规约 4、栈式，堆式 5、活动记录 三、 综合题（共 80 分） 1、设 M , x y a b f x y ({ , },{ , }, = ) { ( } x y f x a , , = f y a φ= ( , ) ,{ }} 为一非确定的有限自动机，其中 f 定义如下： f x b y= ( , ) { } f y b x y ( , ) { , } = 试构造相应的确定有限自动机 M'并最小化。(16 分) 解答： (1)先画出 NFA M 相应的状态图：(4 分) (2)用子集法构造状态转换矩阵：(3 分) a b b a X I 0 {x} 1 {y} 2 {x,y} Ia 2 {x,y} 2 {x,y} b Y Ib 1 {y} 2 {x,y} 2 {x,y} (3)得到 M'=({0,1,2}, {a,b}, f, 0, {1,2})，其状态转换图如下：(4 分) b a,b b b 0 a 2 1 第 1 页 共 5 页 

(4) 最小化：首先，将 M'的状态分成终态组{1,2}和非终态组{0}；考察{1,2}。由于 {1,2}a={1,2}b={2}，所以不能再划分了。(5 分) 0 a b a,b 1 2、有如下文法，给出每个产生式的 Predict 集。 P begin S end S id := E ; S | λ E n | id （8 分） 解答： Follow( S ) ={ end } (2 分) Predict( P begin S end ) = { begin } (1 分) Predict( S id := E ; S ) = { id } (1 分) Predict ( S λ ) = { end } (2 分) Predict ( E n ) = { n } (1 分) Predict ( E id )= { id } (1 分) 3、下面是产生字母表Σ = { 0, 1, 2}上数字串的一个文法： S → D S D | 2 D → 0 | 1 写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和 print(S.val) S.val = (D1.val = D2.val) and S1.val S.val = true D.val = 0 D.val = 1 从右向左读都一样时，称它为回文数）。请用 print 函数打印出 true or false。(12 分) 解答： S′ → S S → D1 S1 D2 S → 2 D → 0 D → 1 4、设有文法 G： (1) 画出文法的 LR(0) 状态机，按构造 SLR(1)分析表的算法构造文法 G 的 SLR(1)分析 表。（SLR 分析表请填写在下一页表格中） (2) 文法 G 是 SLR(1)文法吗？为什么？ （14 分） 解答： (1) 构造文法的识别规范句型活前缀的 DFA 如下图所示：(8 分) S → A a | b A c | d c | b d a A → d 第 2 页 共 5 页 

文法 SLR(1)分析表如下： 状态 (4 分) ACTION a S5 R5 S10,R5 b S3 S2 0 1 2 3 4 5 6 7 8 9 S8,R5 c S9 d S4 S7 $ R1 R3 R2 R4 A 2 3 6 GOTO S 1 ACC S’ → .S S → .A a S → .b A c S → .d c S → .b d a A → .d I0 d S → d .c A → d . I4 S A b c S’ → S . I1 S → A .a I2 S → b .A c S → b .d a A → .d I S → d c . I8 a A d S → A a . I5 S → b A .c S → b d .a A → d . I7 c a S → b A c . S → b d a . (2) 因为有两处有移进－归约冲突，所以该文法不是 SLR(1)文法。（2 分） 5、设有文法 G[S]： S → LaR | R L → bR | c R → L (1) 构造该文法的以 LR(1)项目集为状态的识别活前缀的 DFA。 (2) 构造该文法的 LR(1)分析表。 (3) 判断该文法是否为 LR(1)文法。 （14 分） 解答： (1) 该文法的以 LR(1)项目集为状态的识别活前缀的 DFA 如下图所示：（7 分） 第 3 页 共 5 页 

L 5 8 11 11 R 3 9 10 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 a R4 S7 R5 R3 B S6 S6 S12 S12 c S4 S4 S13 S13 # Acc R2 R4 R5 R5 R3 R1 R5 R4 R3 S 2 (2) 该文法的 LR(1)分析表如下所示（5 分）： (3) 因为状态机中没有冲突，所以是 LR(1)文法。（2 分） 6、设有文法 G[A]: A → iB*e 第 4 页 共 5 页 

B → SB|ε S → [eC]|·i C → eC|ε （1）判定该文法是否为 LL(1)文法？ （2）若是则给出它的 LL(1)分析表，否则说明理由。 （16 分） 解答： (1) 先计算各个产生式的 Predict 集（7 分）： Predict (A-> iB*e)={ i }; Predict (B-> SB) ={ [ , ·} Predict (B->ε ) ={ * } Predict (S->[eC]) ={ [ } Predict (S->·i) ={ · } Predict (C-> eC) ={ e } Predict (C->ε ) ={ ] } 因为 Predict 集没有冲突，所以是 LL(1)文法。 (2) LL(1)分析表如下（9 分）： A B S C i A->iB*e * A-> ε e C->eC [ B->SB S->[eC] ] C-> ε · B->SB S ->·i 第 5 页 共 5 页