（2）预测分析表：（3分） S S’ P P’ a aPS’ b f fS’ q PS’ qP’ # ? bP ? ? ? (15分)写出下列文法中各候选式的FIRST集和各非终结符的FOLLOW集,构造该文法的LL（1）分析表，并说明它是否为LL（1）文法。（2011年重修卷A出过） S → aA|BA A→ cB|? B → bB|? 各候选式的FIRST集 (4分) FIRST（aA）={a} FIRST（BA）={ b，c，? } FIRST（cB）={c} FIRST（?）={?} FIRST（bB）={ b } FIRST（?）={?} 各非终结符的FOLLOW集 (4分) FOLLOW(S)= {#} FOLLOW(A)= {#} FOLLOW(B)= { c，#} LL（1）分析表 (5分) a b c # S S → aA S → BA S → BA S → BA A A→ cB A → ? B B → bB B → ? B → ? 说明它是否为LL（1）文法 (2分) 判断1分，理由1分 因为LL（1）分析表无冲突，所以该文法是LL（1）文法。 2. 设文法G(S): S→^ | a | (T) T→T,S | S
⑴ 消除左递归；
⑵ 构造相应的FIRST和FOLLOW集合； ⑶ 构造预测分析表
解：(1)消除左递，文法变为G’[S]： S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε
此文法无左公共左因子。
(2)构造相应的FIRST和FOLLOW集合： FIRST(S)={a, ^, (}， FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ，FOLLOW(T)={}} FIRST(T’)={,, ε} ，FOLLOW(F)={)} (3)构造预测分析表： S T T’ a S→a T→ST’ ^ S→^ T→ST’ ( S→(T)' T→ST’ ) T’→ε , T’→,ST’ # 第七章重点：1. 识别活前缀的有限自动机的构造，判断某个文法是否是LR(0)文法，或SLR（1）文法或LR（1）文法，若不是，请说明理由，若是，构造相应的LR分析表。 2. 查LR分析表，进行句子的识别。 典型例题：文法G[S]及其LR分析表如下，请给出串baba#的LR分析过程。 (1) S → DbB (2) D → d (3) D → ε (4) B → a (5) B → Bba (6) B → ε LR分析表 状态 0 1 2 3 4 5 6 7 8 ACTION b r3 S4 r2 r6 r4 S7 r5 D s3 a S5 S8 # acc r6 r4 r1 r5 S 1 GOTO B 6 D 2 (注：答案格式为 步骤
答案：
状态栈 符号栈 输入串 ACTION GOTO) 步骤 状态
0 1 2 3 4 5 6 7 8
0 02 024 0245 0246 02467 024678 0246 01
符号 输入串 ACTION GOTO
baba# r3 2 baba# S4 aba# S5
ba# r4 6 ba# S7 a# S8
# r5 6 # r1 1 # acc
#
#D #Db #Dba #DbB #DbBb #DbBba #DbB #S
2. （8分） 已知拓广文法G[S’]：S’→S S→AS∣ε A→aA∣b
（1）试构造以LR（1）项目集为状态的识别活前缀的有穷自动机；
I5 I1 [S'→S．，#] I2 S [S→AS．，#] A S I0 A b I4 b I3 [A→b．，a/b/#] a a b [A→a．A，a/b/#] [A→．aA，a/b/#] [A→．b，a/b/#] a A I6
（2）试判断文法是否是LR(1)文法，并说明理由。 ( 1 ) I0: I2: I6: [S'→．S，#] [S→．AS，#] [S→．，#] [A→．aA，a/b/#] [A→．b，a/b/#] [S→A．S，#] [S→．AS，#] [S→．，#] [A→．aA，a/b/#] [A→．b，a/b/#] [A→aA．，a/b/#] （2）有穷自动机所有的状态都不含有“移进－归约”、“归约－归约”冲突，因
而该文法是LR(1)文法。
练习：. (20 分 ) 给定文法 G[S] ： S → SaA|a A → AbS|b
⑴ (8 分 ) 请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵ (4 分 ) 请构造该文法的 LR(0) 分析表。
⑶ (4 分 ) 什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷ (4 分 ) 什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？ 答：⑴拓广文法 1 分
G[S ′ ]: S ′→ S ⑴ S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA ：
⑵ 该文法的 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,#} ，所以无法解决冲突 。 其它练习可以直接做书本上我们布置的作业！
第八章：1.给出代码，写成代码对应的四元式(三地址码形式！) 重点：（1）. 赋值语句 （2）. For语句
（3）.if …then语句 （4）数组赋值 （5）.while语句
例：写出下面语句经语法制导翻译后所生成的四元式代码序列。 （共10分） if x
解：假设初始为100，则四元式代码序列为
100 if x
（10分）试完成下列语句翻译的四元式序列。（2010年出过） while (A>B) do
if(C>D) then X:=Y*Z else X:=Y+Z; (1) if A>B goto (3) (2) goto (11) (3) _________ (4) goto (8) (5) _________ (6)X:=T1
(7) _________ (8)T2:=Y+Z (9)X:=T2
(10) _________ (11)
答：(3) if C 练习：已知源程序如下： prod:=0; i:=1;