《编译原理》课后习答案第六章 第6章自底向上优先分析 第1题 已知文法GS为： T-T.S/S (山)计算GS的FIRSTVT和LASTVT。 (②)构造GS的算符优先关系表并说明GS是否为算符优先文法。 3)计算GS的优先函数。 (4)给出输入串(a,a)#和(a,(a,)的算符优先分析过程。 答案： 文法展开为： S-a S-A S-T) T-T.S T→S (I)FIRSTVT-LASTVT表： 非终结符 FIRSTVT集 LASTVT集 s (a( (aA)3 T {aA(,) {aA),} (2)算符优先关系表： 盛咸网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 1 第 6 章 自底向上优先分析 第 1 题 已知文法 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))#的算符优先分析过程。 答案： 文法展开为： S→a S→∧ S→(T) T→T,S T→S (1) FIRSTVT - LASTVT 表： (2) 算符优先关系表：
《编译原理》课后习题答案第六章 a # 8 ( 表中无多重人口所以是算符优先(OPG)文法。 友情提示：记得增加拓广文法S一#S#,所以#《FIRSTVT(S),LASTVT(S)之#。 (3)对应的算符优先函数为： a # ； 1 (4)对输入串(a.a)#的算符优先分析过程为 栈(STACK)当前输入字符(CHAR)剩余输入串(INPUT_STRING)动作(ACTION) a.a)Move in ,a)#Move in al4 Reduce:s◆a a)Move in Move in #(N.a #Reduce:S一a #(N.N Reduce::T-→T,S #N #Move in Reduce:S-(T) Success! 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 2 表中无多重人口所以是算符优先（OPG）文法。 友情提示：记得增加拓广文法 S`→#S#，所以# FIRSTVT(S)，LASTVT(S) #。 (3)对应的算符优先函数为： a ( ) , ^ # f 2 1 2 2 2 1 g 3 3 1 1 3 1 （4）对输入串（a,a）#的算符优先分析过程为 栈（STACK） 当前输入字符（CHAR） 剩余输入串（INPUT_STRING） 动作（ACTION） # #( #(a #(N #(N, #(N,a #(N,N #(N #(N) #N ( a , , a ) ) ) # # a,a)#. ,a)#. a)#. a)#. )#. #. #. #. Move in Move in Reduce: S→a Move in Move in Reduce: S→a Reduce: T→T,S Move in Reduce: S→(T) Success!
《编译原理》课后习题答案第六章 对输入串(a(a,a)#的算符优先分析过程为： 刷金输入串 栈(STACK)当前字符(CHAR (INPUT_STRING) 动作(ACTION) a,(a,a))#Move in (aa)#Move in (aa)#Reduce:S-→a (a,a)片 Move in aa) Move in #N,( a))#Move in #ON (a a)l Reduce Sa #N.(N a)#Move in #QN.(N a ))#Move in #N,N, #Reduce:S→g #(N.(N.N ) )#Reduce:T→T.S #(N.(N #Move in #(N.(N) Reduce:ST) )))# #Reduce::T→T,S Move in #(N) Reduce:S-(T) N 第2题 已知文法GS为 s-→aAiT T→T.ss (山)给出(a,(a,a)和(a,a)的最右推导，和规范归约过程。 (②)将(1)和题1中的(4)进行比较给出算符优先归约和规范归约的区别。 答案： （1)(aa)的最右推导过程为 S=(T) →T,S) 三Ta) →S.a →(a,a) (a(aa)的最右推导过程为： S(T) →T,S) →T,T) 盛咸网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 3 对输入串（a,(a,a)）# 的算符优先分析过程为： 栈（STACK）当前字符（CHAR） 剩余输入串 （INPUT_STRING） 动作（ACTION） # #( #(a #(N #(N, #(N,( #(N,(a #(N,(N #(N,(N #(N,(N,a #(N,(N,N #(N,(N #(N,(N) #(N,N #(N #(N) #N ( a , , ( a , , a ) ) ) ) ) ) # # a,(a,a))#. ,(a,a))#. (a,a))#. (a,a))#. a,a))#. ,a))#. a))#. a))#. ))#. )#. )#. )#. #. #. #. Move in Move in Reduce: S→a Move in Move in Move in Reduce: S→a Move in Move in Reduce: S→a Reduce: T→T,S Move in Reduce: S→(T) Reduce: T→T,S Move in Reduce: S→(T) Success! 第 2 题 已知文法 G[S]为： S→a| |(T) ∧ T→T,S|S (1) 给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。 (2) 将(1)和题 1 中的(4)进行比较给出算符优先归约和规范归约的区别。 答案： （１）(a,a)的最右推导过程为： S (T) (T,S) (T,a) (S,a) (a,a) （a,(a,a)）的最右推导过程为： S (T) (T,S) (T,(T))
《编译原理》课后习题答案第六章 →T.T.S) →TTa →T,s,a) (T(aa)) →(S.(a.a) 5(aaa】 (a,(aa)的规范归约过程 步骤 栈 输入 动 1# (a.(a.a)# 移进 2 a.(a.a)) 移进 3 (aa)# 白的.g3a 4#(S .(a a))# 归约，L→S 5#T ,(a,a) 移进 6#(工 (a,a) 移进 7#T( a.a)# 移进 T.(a .a) 归约，S)a 9#T(S 归约，TS 10#0 移进 11#T(工 a)片 移进 12 #(T,(T.a 归约，S→a 13#T,(工，S 归约，T)工S 14#TT 移进 15#T.①m 归的.s3Tn 16 (.S 移进 17 #T,S) 归约，T今TS 18#荆① 归约，$（① 19#S 接受 (a,a)的规范归约过程 步骤 栈 输入 动作 1# (aa)话 移进 2#( a al# 移讲 3 #(a a) 归约，S)a 4#S 归约，T)S 6 #(工 a)话 移进 7#a 归约，S→a 8 #T,S 归约，T→工S 移进 10#T 归约，S→① # 接受 盛威网(ww.snwei.com)专业的计算机学习同站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 4 (T,(T,S)) (T,(T,a)) (T,(S,a)) (T,(a,a)) (S,(a,a)) (a,(a,a)) (a,(a,a))的规范归约过程： 步骤 栈 输 入 动 作 1 # (a, (a, a))# 移进 2 #( a, (a, a))# 移进 3 #(a , (a, a))# 归约，SÆa 4 #(S , (a, a))# 归约，LÆS 5 #(T , (a, a))# 移进 6 #(T, (a, a))# 移进 7 #(T, ( a, a))# 移进 8 #(T, (a , a))# 归约，SÆa 9 #(T, (S , a))# 归约，TÆS 10 #(T, (T , a))# 移进 11 #(T, (T, a))# 移进 12 #(T, (T,a ))# 归约，SÆa 13 #(T, (T, S ))# 归约，TÆT, S 14 #(T, (T ))# 移进 15 #(T, (T) )# 归约，SÆ(T) 16 #(T, S )# 移进 17 #(T, S) # 归约，TÆT, S 18 #(T) # 归约，SÆ(T) 19 #S # 接受 (a,a)的规范归约过程： 步骤 栈 输 入 动 作 1 # (a, a)# 移进 2 # ( a, a)# 移进 3 # (a , a)# 归约，SÆa 4 #(S , a)# 归约，TÆS 5 #(T , a)# 移进 6 #(T, a)# 移进 7 #(T, a )# 归约，SÆa 8 #(T, S )# 归约，TÆT, S 9 #(T )# 移进 10 #(T) # 归约，SÆ(T) 11 # S # 接受
《编译原理》课后习思答案第六章 (②)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与 非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名 字是什么，因此去掉了单非终结符的归约 规范归约的可归约串是句柄，并且必须准确写出可归约串归约为哪个非终结符 第3题： 有文法GS: S→y VTT F→N )）给出(+（的规范推导。 (②)指出句型F+F(的短语，句柄，素短语。 (③)GS是否为OPG?若是，给出(I)中句子的分析过程。 答案： (l)S=>V=>ViT->ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=(+(i (2)句型F+F(的语法树 短语：F,F+F,(,F+Fi( 句柄：F 素短语：( (3)FIRSTV"T和LASTVT FIRSTVT I LASTVT + +,1 . 算符优先关系 因为该文法是OP,同时任意两个终结符的优先关系唯一，所以该文法为OG (+(G(的分析过程 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 5 (2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与 非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名 字是什么，因此去掉了单非终结符的归约。 规范归约的可归约串是句柄，并且必须准确写出可归约串归约为哪个非终结符。 第３题： 有文法 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 FIRSTVT LASTVT S i,+,),( i,+,*,( V i,+,),( i,+,*,( T +,),( +,(,* F ),(, *,( 算符优先关系 i + * ( ) # i ≯ ≮ ≯ ≮ ≮ ≯ + ≯ ≯ ≯ ≮ ≮ ≯ * ≯ ≯ ≯ ≯ ( ≯ ≯ ≯ ≯ ) ≮ ≮ ≮ ≮ # ≮ ≮ ≮ ≮ ≡ 因为该文法是 OP，同时任意两个终结符的优先关系唯一，所以该文法为 OPG。 (+(i(的分析过程 S V V i T T F T + F ( F
《编译原理》课后习题答案第六章 步骤 优先关系 当前符号 剩余输入串☐移进或归约 + （1# 归约 #大+ + (i(# 移进 #F+ +本( i是 移进 #EL (为i 进 归约 6 #F+F +1 归约 移过 #Fi 末( # 移进 9 #Fi( 中# 归约 10 F证 为世 # 归约 11 F 持▣共 # 接受 盛成网(www.snwei.com)专业的计算机学习网站 6
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 6 步骤 栈 优先关系 当前符号 剩余输入串 移进或归约 1 # #≮( ( (+(i(# 移进 2 #( (≯+ + (i(# 归约 3 #F #≮+ + (i(# 移进 4 #F+ +≮( ( i(# 移进 5 #F+( (≯i i (# 归约 6 #F+F +≯i i (# 归约 7 #F #≮i i (# 移进 8 #Fi i≮( ( # 移进 9 #Fi( (≯# # 归约 10 #FiF i≯# # 归约 11 #F #≡# # 接受
《编译原理》课后习答案第六章 第4题 文法G[s]为： S-S:GIG G-G(T)IH +8|(S) T-→1+s|S (1)构造G[S]的算符优先关系表，并判断G[S]是否为算符优先文法。 (2)给出句型a(TS):H:S)的短语、句柄、素短语和最左素短语。 (3)给出a:(a+a)和(a+a)的分析过程，说明它们是香G[S]的句子。 (4)给出(3)中输入串的最右推导，分别说明两输入串是否为G[S]的句子。 (5)由(3)和(4)说明了算符优先分析的哪些缺点。 (6)算符优先分析过程和规范归约过程都是最右推导的逆过程吗？ 答案： (1)构造文法G[S]的算符优先关系矩阵： > ·> . > 在上表中可看出终结符之间的优先关系是唯一的，或称G[S]的算符优先关系矩阵不含 多重入口，因此，G[S]是一个算符优先文法。 盛咸网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 7 第４题 文法G［S］为： S→S;G｜G G→G(T)｜H H→a｜(S) T→T+S｜S （１） 构造G［S］的算符优先关系表，并判断G［S］是否为算符优先文法。 （２） 给出句型a(T+S);H;(S)的短语、句柄、素短语和最左素短语。 （３） 给出a;(a+a)和(a+a)的分析过程，说明它们是否为G［S］的句子。 （４） 给出（３）中输入串的最右推导，分别说明两输入串是否为G[S]的句子。 （５） 由（３）和（４）说明了算符优先分析的哪些缺点。 （６） 算符优先分析过程和规范归约过程都是最右推导的逆过程吗？ 答案： （1）构造文法G［S］的算符优先关系矩阵： ; ( ) a + # ; ( ) a + # ·＞ ＜· ·＞ ·＞ ＜· ＜· ＜· ＜· ·＞ ·＞ ＜· ＜· ·＞ =· ·＞ ·＞ ·＞ ＜· ＜· ＜· ＜· ·＞ ＜· ·＞ ·＞ ·＞ ·＞ ·＞ ·＞ =· 在上表中可看出终结符之间的优先关系是唯一的，或称G［S］的算符优先关系矩阵不含 多重入口，因此，G［S］是一个算符优先文法
《编译原理》课后习题答案第六章 (2) 短语： a相对H、G T+S相对T a(T+S)相对G、S H相对G a(T+S);H相对S (S)相对H、G a(T+S);H;(S)相对S 句柄：a 素短语：T+S、(S) 最左素短语：T+S (3)对输入串(a+a)#的分析过程如下： 步骤 当前符号 剩余输入串 移进或归约 (1 ( a+a)# 移进 (2) 8+ 4a)# 移进 (4) a)s (5) #0N a 移进 (6) #0N+a 共 归约 (7) #(N+N 归约 (8) ) # (9) # (10) N 分析成功 说明是它的句子。 (4)试用规范推导 S→G-H=(S)由此往下S不可能推导出a+a,所以(a+a)不是G[s]的句子。 (5)结果说明：由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中， 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 8 （２） （3）对输入串(a+a)＃的分析过程如下： 步骤 栈 当前符号 剩余输入串 移进或归约 （1） # ( a+a)# 移进 （2） #( a +a)# 移进 （3） #(a + a)# 归约 （4） #(N + a)# 移进 （5） #(N+ a )# 移进 （6） #(N+a ) # 归约 （7） #(N+N ) # 归约 （8） #(N ) # 移进 （9） #(N) # 归约 （10） #N # 分析成功 说明是它的句子。 （４）试用规范推导： S⇒ G⇒H⇒（S）由此往下S 不可能推导出a+a，所以 (a+a)不是G［S］的句子。 （5）结果说明：由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中
《编译原理》课后习题答案第六章 当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。 (6)算符优先分析过程不是最右推导的逆过程，规范归约过程是最右推导的逆过程 盛咸网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 9 当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。 （６）算符优先分析过程不是最右推导的逆过程。规范归约过程是最右推导的逆过程
《编译原理》课后习题答案第六章 附加题 问题1： 对于文法s→(L川 L→LS1S (1)给出句子a(a,以（焦，）的一个最右推导，并指出右句型的句柄： (2)核照(1)的最右推导，说明移进一归约分析器的工作步骤。 答案： (I)S=(L)(LS)=(L.(L))=>(L,(LS))=>(L(L (L))=>(L(L,(LS))>(L,(L,(L a》 =>L(L,(Sa》=>(L,L,(鱼a)=>(L,(S(aa》=>(L,(,(a,a)=>(L,(L.S,(aa》) =>L,(La,(a,a=>L,(Sa,(aa)=>(L,(aa,(a,a》=>(S(aa,(aa》=>(鱼(aa (a,a》 (注：句柄下面有下划线) 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第六章 盛威网（www.snwei.com）专业的计算机学习网站 10 附加题 问题 1： 对于文法 S Æ ( L ) | a L Æ L, S | S (1)给出句子(a, ((a, a), (a, a)))的一个最右推导，并指出右句型的句柄； (2)按照(1)的最右推导，说明移进－归约分析器的工作步骤。 答案： (1)S => ( L ) => (L, S) => (L, (L)) => (L, (L, S)) => (L, (L, (L))) => (L, (L, (L, S)))=> (L, (L, (L, a))) =>(L,(L,(S, a))) => (L, (L, (a, a))) => (L, (S, (a, a))) => (L, ((L), (a, a))) => (L, ((L, S), (a, a))) =>(L,((L,a), (a,a)))=> (L, ((S, a), (a, a))) => (L, ((a, a), (a, a))) => (S, ((a, a), (a, a))) => (a, ((a, a), (a, a))) (注：句柄下面有下划线)