编译原理第六章习题解答

1、第六章 习题答案4文法g： sàs;g|ggàg(t)|hhàa|(s)tàt+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#可知：#由gàg(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) (

3、+, ;, 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)#

4、移进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）可看出，算符优先文法忽略了对单个非终结