《编译原理 第六章 习题解答》由会员分享，可在线阅读，更多相关《编译原理 第六章 习题解答（3页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 习题答案习题答案4文法 G： SS;G|G GG(T)|H Ha|(S) TT+S|S （1）该文法是算符文法，且不包含 产生式。 计算每个非终结符的 FIRSTVT 集合：FIRSTVT(S) = FIRSTVT(S);FIRSTVT(G)= ;, a, ( FIRSTVT(G) = FIRSTVT(G)(FIRSTVT(H)= a, ( FIRSTVT(H) = a, (= a, (FIRSTVT(T) = FIRSTVT(T)+FIRSTVT(S)= +, ;, a, ( 计算每个非终结符的 LASTVT 集合：LASTVT(S) = ;LASTVT(G)= ;, a, )
2、 LASTVT(G) = )LASTVT(H)= a, ) LASTVT(H) = a, )= a, )LASTVT(T) = +LASTVT(S)= +, ;, a, ) 关系 由#S#可知：# 由 GG(T)|H 可知：() 关系S#LASTVT(S)# ;, a, )# S;LASTVT(S); ;, a, ); G(LASTVT(G)( a, )( T)LASTVT(T) +, ;, a, ) S)LASTVT(S) ;, a, ) T+LASTVT(T)+ +, ;, a, )+ 关系#S#FISRTVT(S) #;, a, ( ;G;FISRTVT(G) ;a, ( (T(FISR
3、TVT(T) (+, ;, a, ( (S(FISRTVT(S) (;, a, ( +S+FISRTVT(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 ，H，(S) 句柄：a 素短语：a，T+S，(S) 最左素短语：a（3） 对 a;(a+a)进行算符优先分析步骤如下：步骤符号栈当前符号剩余符号串移进或归约1#a;(a+a)#移进2#a;(a+a)#归约3#N;(a+a)#移进4#N
4、;(a+a)#移进5#N; (a+a)#移进6#N; (a+a)#归约7#N; (N+a)#移进8#N; (N+a)#移进9#N; (N+a)#归约10#N; (N+N)#归约11#N; (N)#移进12#N; (N)#归约13#N; N#归约14#N#分析成功对(a+a)进行算符优先分析步骤如下：步骤符号栈当前符号剩余符号串移进或归约1#(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#分析成功采用算符优先分析方法进行分析，可知：a;(a+a)和(a+a)均应为该文法的句子。S ; GS ; GH( S )HG ( T )T + SHaS（4） 句子 a;(a+a)的最右推导为：S=S;G=S;H= S;(S)= （无法推出句子 a;(a+a)） 句子(a+a)的最右推导为：S=G=H= (S)=（无法推出句子(a+a)） 由以上推导过程可知：a;(a+a)和(a+a)均不是该文法的句子。 （5）由（3）和（4）可看出，算符优先文法忽略了对单个非终结符的归约过程，不是规范 归约，因此无法避免把错误的句子得到正确的归约。 （6）算符优先分析过程不是最右推导的逆过程，而规范归约是最右推导的逆过程。
