发布时间 : 星期一 文章编译原理期末复习题(含答案2011-5)更新完毕开始阅读ff1ad9a5f524ccbff1218403
⑵ 该文法的 LR(0) 分析表：
状态 0 1 2 3 4 5 6 7
ACTION a S 2 S 3 r 3 r 2 r 5 S 2 r 4 /S 3 b r 3 S 5 r 2 /S 6 r 5 r 4 # acc r 3 r 2 r 5 r 4
GOTO S 1 7 A 4 ⑶ LR(0) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态。
该文法不是 LR(0) 文法，因为存在冲突状态： I 4 和 I 7。
⑷ SLR(1) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态，冲突可用 FOLLOW 集解决。
该文法不是 SLR(1) 文法。因为 FOLLOW(S)={a,b,#} ，所以无法解决冲突。
24、对下面的文法G： S->aBc|bAB A->aAb|b B->b|ε
(1)计算这个文法的每个非终结符的FIRST和FOLLOW集合； （2）证明这个文法是LL（1）的； （3）构造它的预测分析表。
答：（1）first(B)={b, ε},first(A)={a,b},first(S)={a,b} Follow(S)={#},follow(A)={b,#},follow(B)={c,#} (2)因为只有FIRST(B)含有? , 所以只考虑： FOLLOW(B)=FIRST(c) ?FOLLOW(S)={c, #} ∴该文法的LL(1)表 (3)该文法的LL(1)分析表如下：
a b c # ? ? S aBc bAB A aAb b B b
25、设字母表∑={ a，b}，对于以aa或ab结尾的字的正规集。 （1）请写出描述该语言的正规式。
（2）构造该正规式所对应的NFA（画出转换图）； （3）将所求的NFA确定化（画出DFA的转换图）；
（4）将所求出的DFA最小化（画出极小化后的转换图）； 答： （1）正则式为：（a|b）*a(a|b）。 （1分）
（2）由正则式得到的转换系统如下图： （1分）
（3）由子集法构造的DFA如下图：
（4）DFA最小化如下图：
26、设文法G为 S ? E
E? TE | ε T ? eT | t
(1)证明它是LR(1)文法； (2)构造它的LR(1)分析表；
(3)给出输入符号串etet的分析过程。
答：(1)拓广文法G’：（1分）
(0) S' ?S (1) S ? E (2) E? TE (3) E ?ε (4) T ? eT (5) T ? t FIRST(A) = {ε, e,t}
FIRST(B) = {e, t} 构造的DFA如下:
由项目集规范族看出，不存在冲突动作。 ∴该文法是LR(1)文法。 (2)
LR(1)分析表
Action Goto 状态 e t # S E T 0 S4 S5 r3 1 2 3 1 acc 2 r1 3 S4 S5 r3 6 3 4 S4 S5 7 5 r5 r5 r5 6 r2 7 r4 r4 r4 (3)输入串abab的分析过程为：
步骤 状态栈 符号栈 当前字符 剩余字符串 动作 (1) 0 # e tet# 移进 (2) 04 #e t et# 移进 (3) 045 #et e t# 归约 T?t (4) 047 #eT e t# 归约 T?et (5) 03 #T e t# 移进 (6) 034 #Te t # 移进 (7) 0345 #TeT # 归约 T?t (8) 0347 #TeT # 归约 T?et (9) 033 #TT # 归约 E?ε (10) 0336 #TTE # 归约 E?TE (11) 036 #TE # 归约 E?TE (12) 02 # E # 归约 S?E (13) 01 #S # acc
27、对文法G(S)：
S ? S ? a T | a T | ? a T T ? ? a T | ? a
(1) 消除该文法的左递归和提取左公因子； (2) 构造各非终结符的FIRST和FOLLOW集合；
(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。 答：（1）消除左递归
S ? a T S’ | ? a T S’ S’ ? ? a T S’ | ε T ? T ? ? a T | ? a 提取左公因子
S ? a T S’ | ? a T S’ S’ ? ? a T S’ | ε T ? ? a T’ T’ ? T | ε
(2) 各非终结符的FIRST和FOLLOW集合：
FIRST(S)={a，?} FIRST(S')={ ?，ε} FIRST(T)={ ? } FIRST(T')={ ?，ε} FOLLOW(S)={#} FOLLOW(S')={#} FOLLOW(T)={?，#} FOLLOW(T')={?，#}
(3) LL(1)分析表如下(3分) ，该文法是LL(1)文法。（1分）
a ? ? # S S?aTS' S??aTS' S' S'??aTS S’?ε T T'
' T??aT' T'?ε T'?T T'?ε