步骤 1 2 3 4 5 6 7 8 9 # #( #(a #(S #(L 栈 输 入 (a, ((a, a), (a, a)))# a, ((a, a), (a, a)))# , ((a, a), (a, a)))# , ((a, a), (a, a)))# , ((a, a), (a, a)))# ((a, a), (a, a)))# (a, a), (a, a)))# a, a), (a, a)))# , a), (a, a)))# , a), (a, a)))# , a), (a, a)))# a), (a, a)))# ), (a, a)))# ), (a, a)))# , (a, a)))# , (a, a)))# (a, a)))# a, a)))# , a)))# , a)))# , a)))# a)))# )))# 动 作 移进 移进 归约，S?a 归约，L?S 移进 移进 移进 移进 归约，S?a 归约，L?S 移进 移进 归约，S?a 移进 归约，L?S 移进 移进 移进 归约，S?a 归约，L?S 移进 移进 归约，S?a #(L, #(L, ( #(L, (( #(L, ((a 10 #(L, ((S 11 #(L, ((L 12 #(L, ((L, 13 #(L, ((L, a 14 #(L, ((L, S 15 #(L, ((L 16 #(L, ((L) 17 #(L, (S 18 #(L, (L 19 #(L, (L, 20 #(L, (L, ( 21 #(L, (L, (a 22 #(L, (L, (S 23 #(L, (L, (L 24 #(L, (L, (L, 25 #(L, (L, (L, a 26 #(L, (L, (L, S 27 #(L, (L, (L 28 #(L, (L, (L) 29 #(L, (L, S 30 #(L, (L 31 #(L, (L) 32 #(L, S 33 #(L ), (a, a)))# 归约，L?L, S , (a, a)))# 归约，S?(L) )))# 归约，L?L, S )))# 移进 ))# 归约，S?(L) ))# 归约，L?L, S ))# 移进 )# 归约，S?(L) )# 归约，L?L, S )# 移进 34 #(L) 35 #S # 归约，S?(L) # 接受 2、已知文法G[S]为： S?a|^|(T) T?T,S|S (1)计算G[S]的FIRSTVT和LASTVT。
(2)构造G[S]的算符优先关系表并说明G[S]是否未算符优先文法。
(3)计算G[S]的优先函数。
(4)给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。
[答案]
(1) FIRSTVT和LASTVT
S T FIRSTVT a、^、（ ，、a、^、（ LASTVT a、^、） ，、a、^、) (2) 算符优先关系
a ( ) , ^ # a ≯ ≯ ≯ ( ≮ ≮ ≡ ≮ ) ≯ ≯ ≯ , ≮ ≮ ≯ ≯ ≮ ^ ≯ ≯ ≯ # ≮ ≮ ≮ (3) 对应的算符优先函数为： S T a 2 3 ( 1 3 ) 2 1 , 2 1 ^ 2 3 # 1 1 (4) 句子(a,a)#分析过程如下： 步骤 栈 1 2 3 4 5 # #( #(a #(F #(F, 优先关系 #≮( (≮a a≯, (≮, ,≮a 当前符号 剩余输入串 ( a , , A a,a)# ,a)# a)# a)# )# 移进或归约 移进 移进 归约 移进 移进 6 7 8 9 10 #(F,a #(F,F #(F #(F) #F A≯) ,≯) (≡) )≯# #≡# ) ) ) # # # # # 归约 归约 移进 归约 接受
句子(a, (a, a))分析过程如下：
步骤 栈 优先关系 当剩余输入串 移进或前归约 符号 ( a , , ( a , , a ) ) ) ) ) # # a,(a,a))# , (a,a))# (a,a))# (a,a))# a,a))# ,a))# a))# a))# ))# )# )# )# # # 移进 移进 归约 移进 移进 移进 归约 移进 移进 归约 归约 移进 归约 归约 移进 归约 接受 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 # #( #(a #(F #(F, #(F,( #(F,(a #(F,(F #(F,(F, #(F,(F,a #(F,(F,F #(F,(F #(F,(F) #(F,F #(F #(F) #F #≮( (≮a a≯, (≮, ,≮( (≮a a≯, (≮, ,≮a a≯) ,≯) (≡) )≯) ,≯) (≡) )≯# #≡# ） # 3、对题2的G[S] (1)给出(a,(a,a))和(a,a)的最右推导和规范归约过程。
(2)将(1)和题2中的(4)进行比较给出算符优先归约和规范归约的区别。
[答案]
(1) (a,(a,a))的最右推导过程：
S => ( T ) => (T, S) => (T, (T)) => (T, (T, S)) => (T, (T,a)) => (T, (S, a))=> (T, (a, a)) => (S, (a, a))
(注：句柄下面有下划线)
(a,a))的最右推导过程： S => ( T ) => (T, S) => (T, a) => (S, a)=> (a, (a, a)) (注：句柄下面有下划线)
(2) (a,(a,a))的规范归约过程。 步骤 1 2 3 4 5 6 7 8 9 栈 # #( #(a #(S #(T #(T, #(T, ( #(T, (a #(T, (S 输 入 (a, (a, a))# a, (a, a))# , (a, a))# , (a, a))# , (a, a))# (a, a))# a, a))# , a))# , a))# , a))# a))# ))# ))# ))# )# )# # # # 动 作 移进 移进 归约，S?a 归约，L?S 移进 移进 移进 归约，S?a 归约，T?S 移进 移进 归约，S?a 归约，T?T, S 移进 归约，S?(T) 移进 归约，T?T, S 归约，S?(T) 接受 10 #(T, (T 11 #(T, (T, 12 #(T, (T,a 13 #(T, (T, S 14 #(T, (T 15 #(T, (T) 16 #(T, S 17 #(T, S) 18 #(T) 19 #S (a,a)的规范归约过程。 步骤 1 2 3 栈 # # ( # (a 输 入 (a, a)# a, a)# , a)# 动 作 移进 移进 归约，S?a 4 5 6 7 8 9 #(S #(T #(T, #(T, a #(T, S #(T , a)# , a)# a)# )# )# )# # # 归约，T?S 移进 移进 归约，S?a 归约，T?T, S 移进 归约，S?(T) 接受 10 #(T) 11 # S (2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与非终结符无关，只需知道把当前可归
约串归约为某一个非终结符，不必知道该非终结符的名字是什么，因此去掉了单非终结符的归约。 规范归约的可归约串是句柄，并且必4、有文法G[S]： S?V V?T|ViT T?F|T+F F?)V*|( (1) 给出(+(i(的规范推导。
(2) 指出句型F+Fi(的短语，句柄，素短语。
(3) G[S]是否为OPG？若是，给出(1)中句子的分析过程。 [答案]
(1) S=>V=>ViT=>ViF=>Vi(=>T i(=>T+F i(=>T+( i(=>F+( i(=>(+( i(
(2)句型F+Fi(的语法树：
短语：F，F+F，(，F+Fi( 句柄：F 素短语：(
(3) FIRSTVT和LASTVT S V T F FIRSTVT i,+,),( i,+,),( +,),( ),(, LASTVT i,+,*,( i,+,*,( +,(,* *,( (2)算符优先关系 i + * ( ) #