资源描述：
《编译原理第五章-课后题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章1.1考虑下面表格结构文法G2S->a
2、^
3、(T)T->T,S
4、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=>((
5、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),^,(
6、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)
7、#进#((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
8、^
9、(T)T->T,S
10、S的FIRSTVT和LASTVT。（2）计算G2的优先关系。G2是一个算符优先文法吗？（3）给出输入串(a,(a,a))的算符优先分析过程。答：（1）(2)G[S]的算符优先关系表： a(),^#a ≯≯ ≯(≮≮≡ ≮
11、 ) ≯≯ ≯,≮≮≯≯≮ ^ ≯≯ ≯#≮≮ ≮≡ 因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。（3）句子(a,(a,a))分析过程如下：4.对下面文法：S->AS
12、bA->SA
13、a(1)列出该文法所有的LR(0)项目。(2)构造这个文法的LR(0)项目集规范族及识别活前缀的DFA答：文法拓广：S’->SS->AS
14、bA->SA
15、aLR（0）项目：S’->．S S’->S．S->．AS S->A．S S->AS．S->．b S->b．A->．SA A->S．A A->SA．A->．a A->a．LR(0)项目集规范族及识别活前
16、缀的DFA如下图所示：FOLLOW(S)={#,a,b}FOLLOW(A)={a,b}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->．bSabASbaSAbaAS7.证明文法是SLR(1)的但不是LR(0)的：S->AA-
17、>Ab
18、bBaB->aAc
19、a
20、aAb答：(1)证明不是LR(0):因为项目集规范族的I3中，有移进和归约的冲突。所以不是LR(0)的(2)证明是SLR(1)的提示：上图继续画完，找出所有冲突的情况，根据SLR(1)解决办法可以解决，(过程略)所以为SLR(1)的或构造出SLR分析表，无多重定义入口，所以是SLR的．８．证明文法： A→BaBb
21、DbDa B→ε D→ε是LR(1)但不是SLR(1)。（说明：书中的S为这里的A；书中的A为这里的B；书中的B为这里的D；）答：
