4) S’->b
5) A’-> aA’ |ξ
第六章
1
S ? a | ∧ | ( T ) T ? T , S | S
解：(1) 增加辅助产生式 S’?＃S＃ 求 FIRSTVT集 FIRSTVT（S’）＝ {#}
FIRSTVT（S）＝ {a ∧ ( }＝ { a ∧ ( }
FIRSTVT (T) ＝ {,} ∪ FIRSTVT( S ) = { , a ∧ ( } 求 LASTVT集 LASTVT（S’）＝ { # } LASTVT（S）＝ { a ∧ )} LASTVT (T) ＝ { , a ∧ )} (2)
算符优先关系表 a ∧ ( ) , # a ·> ·> ·> ∧ ·> ·> ·> ( <· <· <· =· <· ) ·> ·> ·> , <· <· <· ·> ·> # <· <· <· =· 因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法 (3)
a ∧ ( ) , F 1 1 1 1 1 1 g 1 1 1 1 1 1
f 2 2 1 3 2 1
g 2 2 2 1 2 1 f 3 3 1 3 3 1
g 4 4 4 1 2 1 f 3 3 1 3 3 1
g 4 4 4 1 2 1
(4)
栈 优先关系 当前符号 剩余输入串 移进或规约 ＃ <· ( a,a)# 移进
16
#
＃( <· a ,a)# 移进 # (a ·> , a)# 规约 ＃(T <· , a)# 移进 ＃(T， <· a )# 移进 ＃(T,a ·> ) # 规约 ＃(T,T ·> ) # 规约 ＃(T =· ) # 移进 ＃(T) ·> ＃ 规约 ＃T =· ＃ 接受 4. 扩展后的文法
S’?#S# S?S;G S?G G?G(T) G?H H?a H?(S) T?T+S T?S （1）
FIRSTVT(S)={;}∪FIRSTVT(G) = {; , a , ( } FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( } FIRSTCT(H)={a , ( }
FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , ; , a , ( }
LASTVT(S) = {;} ∪LASTVT(G) = { ; , a , )} LASTVT(G) = { )} ∪ LASTVT(H) = { a , )} LASTVT(H) = {a, )}
LASTVT(T) = {+ } ∪LASTVT(S) = {+ , ; , a , ) }
构造算符优先关系表
； ( ) a + # ; ·> <· ·> ·> <· <· ( <· <· ·> ·> <· <· ) ·> ＝· ·> ·> ·> a <· <· <· <· + ·> <· ·> ·> ·> # ·> ·> ·> ＝· 因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法 （2）
句型a(T+S);H;(S)的
短语有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H 直接短语有: a T+S H (S) 句柄： a
素短语：a T+S (S) 最左素短语：a (3)
分析a；（a＋a）
栈
优先关系 当前符号 剩余输入串 移进或规约 17
＃ ＃a ＃T ＃T； ＃T；（ ＃T；（a ＃T；（T ＃T；（T＋ ＃T；（T＋a ＃T；（T＋T ＃T；（T ＃T；（T） ＃T；T ＃T
分析a；（a＋a） 栈 ＃ ＃（ ＃（a ＃（T ＃（T＋ ＃（T＋a ＃（T＋T ＃（T ＃（T） ＃T <· ·> <· <· <· ·> <· <· ·> ·> ＝· ·> ·> ＝· a ； ； （ a ＋ ＋ a ） ） ） ＃ ＃ ＃ ；（a＋a）＃ （a＋a）＃ （a＋a）＃ a＋a）＃ ＋a）＃ a）＃ a）＃ ）＃ ＃ ＃ ＃ 移进 规约 移进 移进 移进 规约 移进 移进 规约 规约 移进 规约 规约 接受 优先关系 <· <· ·> <· <· ·> ·> ＝· ·> ＝· 当前符号 ( a ＋ ＋ a ） ） ） ＃ ＃ 剩余输入串 a＋a）＃ ＋a）＃ a）＃ a）＃ ）＃ ＃ ＃ ＃ 移进或规约 移进 移进 规约 移进 移进 规约 规约 移进 规约 接受 （4）
不能用最右推导推导出上面的两个句子。
第七章
1、已知文法：
A → aAd|aAb|ξ
判断该文法是否是SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。 解：(0) A’→ A
(1) A → aAd (2) A → aAb (3) A → ξ
构造该文法的活前缀DFA：
18
I0： A’ →·A a I2： A I3： A →aA·d A →·aAd A →·aAb A →· A I1：A’ →A· A →a·Ad A →a·Ab A →·aAd A →·aAb a A →· Follow(A)∩{a}=∮ d I4： A →aAd· A →aA·b b I5：A →aAb·
由上图可知该文法是SLR（1）文法。 构造SLR（1）的分析表： 状态 a 0 1 2 3 4 5 步骤 1 2 3 4 5 S2 S2 状态栈 0 02 023 0235 01 # #a #aA #aAb #A d R3 R3 S4 R1 R2 符号栈 ACTION b R3 R3 S5 R1 R2 输入串 ab# b# b# # # # R3 acc R3 R1 R2 ACTION S2 R3 S5 R2 acc GOTO A 1 3 GOTO 3 1 输入串ab#的分析过程：
3、考虑文法：
S →AS|b A→SA|a (1) 列出这个文法的所有LR（0）项目 (2) 按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA
的所有状态全体构成这个文法的LR（0）规范族。
(3) 这个文法是SLR的吗？若是，构造出它的SLR分析表。 (4) 这个文法是LALR或LR（1）的吗？ 解：（0）S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a (1)列出所有LR（0）项目：
S’→·S S→·b A→·a S’→ S· S→b· A→a· S →·AS A→·SA S →A·S A→S·A S →AS· A→SA·
(3)构造该文法的活前缀NFA：
19
b b b b I6： I7： a S →b· A →a· a a a a b I0： S I1： A I3： I5： S’→·S S’→ S· A →SA· S S →AS· S →·AS A →S·A S →A·S A →S·A S →·b A →·SA S →·AS A →·SA A →·SA A →·a S →·b A A →·a A →·a A S →·AS S A →·SA S →·AS S →·b A →·a S →·b A A I2： IS S 4： a S →A·S A →S·A S →·AS A A →·SA S b S →·b A →·a A →·SA S →·AS A →·a S →·b 由上可知：I1 I3 I5 中存在着移进和归约冲突
在I1中含项目：S’→ S· 归约项 Follow(S’)={#}
A →·a 移进项 Follow(S’)∩{a}=∮ S →·b 移进项 Follow(S’)∩{b}=∮
在I3中含项目：A →SA· 归约项 Follow(A)={a,b}
S →·b 移进项 Follow(A) ∩ {b}≠∮ A →·a 移进项 Follow(A) ∩ {a}≠∮
在I5中含项目：S →AS· 归约项 Follow(S)={#,a,b}
A →·a 移进项 Follow(S) ∩ {a}≠∮ S →·b 移进项 Follow(S) ∩ {b}≠∮
由此可知，I3、I5的移进与归约冲突不能解决，所以这个文法不是SLR（1）文法。 （4）做LR（1）项目集规范族
I0： I1： I2：
S’→·S ，# S’→ S· ,# S →A·S ,a/b/#
S →·AS ，a/b/# A →S·A ,a/b S →·AS ,a/b/#
S →·b ,a/b/# A →·SA ,a/b S →·b ,a/b/#
A →·SA ,a/b A →·a ,a/b A →·SA ,a/b A →·a ,a/b S →·AS ,a/b A →·a ,a/b
S →·b ,a/b
20