编译原理第六章习题解答

真诚为您提供优质参考资料，若有不当之处，请指正。第六章 习题答案4文法G： SS;G|GGG(T)|HHa|(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, )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(FISRTVT(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;(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)均应为该文法的句子。（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）算符优先分析过程不是最右推导的逆过程，而规范归约是最右推导的逆过程。3 / 3