编译原理第五章-课后题

第五章1.1考虑下面表格结构文法G2S-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,(a)),a)#进#((T,(a)),a)#进#((T,(S)),a)#归，用S-a#((T,(T)),a)#归，用T-S#((T,(T)),a)#进#((T,S),a)#归，用S-(T)#((T),a)#归，用T-T,S#((T),a)#进#(S,a)#归，用S-(T)#(T,a)#归，用T-S#(T,a)#进#(T,a)#进#(T,S)#归，用S-a#(T)#归，用T-T,S#(T)#进#S#归，用S-(T)接受。语法树（略）3（1）计算练习2的文法G2S-a|^|(T)T-T,S|S的FIRSTVT和LASTVT。（2）计算G2的优先关系。G2是一个算符优先文法吗？（3）给出输入串(a,(a,a))的算符优先分析过程。答：（1）(2)G[S]的算符优先关系表：a(),^#a≯≯≯(≮≮≡≮)≯≯≯,≮≮≯≯≮^≯≯≯#≮≮≮≡因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。（3）句子(a,(a,a))分析过程如下：4.对下面文法：S-AS|bA-SA|a(1)列出该文法所有的LR(0)项目。(2)构造这个文法的LR(0)项目集规范族及识别活前缀的DFA答：文法拓广：S’-SS-AS|bA-SA|aLR（0）项目：S’-．SS’-S．S-．ASS-A．SS-AS．S-．bS-b．A-．SAA-S．AA-SA．A-．aA-a．LR(0)项目集规范族及识别活前缀的DFA如下图所示：FOLLOW(S)={#,a,b}FOLLOW(A)={a,b}7.证明文法是SLR(1)的但不是LR(0)的：S-AA-Ab|bBaB-aAc|a|aAb答：(1)证明不是LR(0):因为项目集规范族的I3中，有移进和归约的冲突。所以不是LR(0)的S’-．SS-．ASS-．bA-．SAA-．aS’-S．A-S．AS-．ASS-．bA-．SAA-．aSS-A．SS-．ASS-．bA-．SAA-．aAS-b．bA-a．aS-AS．A-S．AA-．SAA-．aS-．ASS-．bSAababA-SA．S-A．SA-．SAA-．aS-．bS-．ASAA-S．AA-．SAA-．aS-．ASS-．bSabASbaSAbaAS(2)证明是SLR(1)的提示：上图继续画完，找出所有冲突的情况，根据SLR(1)解决办法可以解决，(过程略)所以为SLR(1)的或构造出SLR分析表，无多重定义入口，所以是SLR的．８．证明文法：A→BaBb|DbDaB→εD→ε是LR(1)但不是SLR(1)。（说明：书中的S为这里的A；书中的A为这里的B；书中的B为这里的D；）答：拓广文法为G′，增加产生式S′→A若产生式排序为：0S'→A1A→BaBb2A→DbDa3B→ε4D→ε由产生式知：First(S')={a,b}First(A)={a,b}First(B)={ε}First(D)={ε}Follow(S')={#}Follow(A)={#}Follow(B)={a,b}Follow(D)={a,b}G′的LR(1)项目集族及识别活前缀的DFA如下图所示：(修正:上图里左上角的I1应为:S’-A．，＃图里把向前搜索符＃漏掉了，因为是插入的图片不好修改，这里更正一下)在I0中：B→．,a和D→．，b为归约项目，但它们的搜索符不同，若当前输入符为a时用产生式B→ε归约，为b时用产生式D→ε归约，所以该文法是LR(1)文法。若不看搜索符，在I0中项目B→．和D→．为归约-归约冲突，而Follow(B)∩Follow(D)={a,b}∩{a,b}≠，冲突不能用Follow集解决，所以该文法不是SLR(1)文法。构造的LR(1)分析表如下：StateActionGotoa.b.#ABD0123456789r3r4......AccS4............S5r3r4............S8S9............r1r2123...67因为表中不含多重定义入口，所以该文法是LR(1)的.