编译原理第五章 课后题.doc

第五章 1.1考虑下面表格结构文法G2 S-a|^|(T) T-T,S|S 指出(((a,a), ^,(a)),a)的规范规约及每一步规约的句柄。根据这个规范规约，给出“移进-规约”的过程，并给出它的语法树自下而上构造的过程。 答:： 规范规约 该步规约时的句柄 (((a,a), ^,(a)),a) a = (((S,a), ^,(a)) ,a) S = (((T,a), ^,(a)) ,a) a = (((T,S), ^,(a)) ,a) T,S = (((T), ^,(a)) ,a) （T） = ((S, ^,(a)) ,a) S = ((T, ^,(a)) ,a) ^ = ((T, S,(a)) ,a) T, S = ((T,(a)) ,a) a = ((T,(S)) ,a) S = ((T,(T)) ,a) (T) = ((T,S) ,a) T, S = ((T) ,a) (T) = (S,a) S = (T, a) a = (T, S) T, S = (T) (T) = S “移进-规约”的过程： 符号栈 输入串 动作 # (((a,a), ^,(a)),a) # 预备 #( ((a,a), ^,(a)),a) # 进 #(( (a,a), ^,(a)),a) # 进 #((( a,a), ^,(a)),a) # 进 #(((a ,a), ^,(a)),a) # 进 #(((S ,a), ^,(a)),a) # 归，用S-a #(((T ,a), ^,(a)),a) # 归，用T-S #(((T, a), ^,(a)),a) # 进 #(((T,a ), ^,(a)),a) # 进 #(((T,S ), ^,(a)),a) # 归，用S-a #(((T ), ^,(a)),a) # 归，T-T,S #(((T) , ^,(a)),a) # 进 #((S , ^,(a)),a) # 归，用S-(T) #((T , ^,(a)),a) # 归，用T - S #(( T, ^,(a)),a) # 进 #(( T, ^ ,(a)),a) # 进 #(( T, S ,(a)),a) # 归，用S-^ #(( T ,(a)),a) # 归，用T-T,S #(( T, (a)),a) # 进 #(( T, (