编译原理期末考试习题及答案

1、一、填空题|(每题4分，共20分)1. 乔母斯基定义的3型文法(线性文法)产生式形式ABa|a,或AaB|a,A,BVn,a,bVt。2. 语法分析程序的输入是单词符号，其输出是语法单位。3型为B.aB的LR(0)项目被称为移进项目，型为Ba.B的LR(0)项目被称为待约项目,4. 在属性文法中文法符号的两种属性分别为继承属性和综合属性。5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。二. 已知文法G(S)ET|E+TTF|F*FF(E)|i(1) 写出句型(T*F+i)的最右推到并画出语法树。(4分)(2) 写出上述句型的短语，直接短语和句柄。(4分)答：(1)最右推

2、到(2分)E=>T=>F=>(E)=>(E+T)=>(E+F)=>(E+i)=>(T+i)=>(T*F+i)(2)语法树(2分)E/K(E)/1H+T/|1下*FI(3) (4分)短语：(T*F+i)，T*F+i，T*F，i直接短语：T*F，i句柄：T*F三证明文法G(S):SSaS|£是二义的。(6分)答：句子aaa对应的两颗语法树为：sasSasSmsSassaSSase因此，文法是二义文法abFSSS,AS,AS,AS四.给定正规文法G(S):(1)SSa|Ab|bASa请构造与之等价的DFA(6分)五构造识别正规语言b*a(bb

3、*a)*b*最小的DFA(要求写出求解过程)。(15分)答：(1)对应的NFA(5分)bb（5分）(2)将(1)所得的NFA确定化：(5分)ab01,301,32,32,31,32,3六.已知文法G(S):(1) SA|a|(T)TT,S|S试：(1)消除文法的左递归；(4分)(2) 构造相应的first和follow集合。(6分)答：(1)消除文法的左递归后文法G'(S)为：(1) SA|a|(T)TST'|S(3) T',ST'|&(4分)(2)(6分)firstfollowSaA(#,)Taa()T',&)七.已知文法G（S）:SS

4、iA|AAA+B|B(3)BA*|(试构造非终止符的firstVT和lastVT集合。(10分)答：（10分）firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(八.已知文法G（S）:(1)SBBFollowBaBS#BbBa,b,#的follow集合如表：试：（1）给出该文法的LR（0）项目集规范族划分;2）填写相应的SLR（1）的分析表。（15分）答：（1）LR（0）项目集规范族划分（8分）1SIBIaIbI11S'S.12I2SB.B-B.aB-B.b-BaIbII3Ba.BB.aB-B.b-34I5BaIbII634|4Bb.I5SBB.

5、I6BaB.（2）SLR（1）分析表（7分）状态ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九.设某语言的not-then-else语句的语法形式为：SnotEthenS其语义解释为：(2) 写出每个产生式对应的语义动作。(7分)答：(1)分段产生式(3分)及语义动作(7分)(1) RnotEthenBackpatch($2.FC,nxq);$.chain=$2.Tc(2) SRS1Backpatch($2.chain，nxq)一、填空题|(每题4分，共20分1. 乔母斯基定义的2型文法(上下文无关文法)产生式形式AB,AVn,

6、V+。2. 词法分析程序的输入是字符串，其输出是单词符号o3算符有限分析方法每次都是对最左素短语进行规约。型为BaB.的LR(0)项目被称为规约项目。4、写出x:=b*(d-e)/(c-d)+e的逆波兰式xbde-*cd-/e+:=。5、常用的两种动态存贮分配办法是栈式存储分配和堆式存储分配。二已知文法G(S):(1) SA|a|(T)TT,S|S试：(1)写出句型(a,(a,a)的最左推到并画出语法树。(4分)(2) 写出上述句子的短语，直接短语和句柄。(4分)答：(1)最左推到(2分)S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T)=&g

7、t;(a,(T,S)=>(a,(S,S)=>(a,(a,S)=>(a,(a,a)(2) 语法树(2分S/|(T)/lI/ll(/T-SIIsa(3) (4分短语：(a,(a,a),a,(a,a),(a,a),a,a,a直接短语：a句柄：a三. 证明文法G（S）:SaSb|Sb|b是二义的。（6分）答：句子aabbbb对应的两颗语法树为：aAaB|bAaA|b请构造与之等价的DFA（6分）答：对应的DFA为：（6分）因此，文法是二义文法四.给定正规文法G（S）:SA（3）B（15分）五构造识别正规语言（ab*|a）*最小的DFA（要求写出求解过程）答：（1）对应的NFA（5分）

8、(5分)(2)将(1)所得的NFA确定化：(5分)ab11,21,21,21,2六.已知文法G(S):SA|a|(T)TST'|S(3) T',ST'|&试：求first和follow集合，构造改文法的LL(1)分析表。(10分)答：文法相应的first和follow集合(5分)firstfollowSaA(#,)Taa()T',£)其LL(1)分析表如下:ab(rsSaS-b(T)TT*ST'TST'$TT'-常T?STf七.已知文法G(S):(1) SSiA|AAA+B|BBA*|(非终止符的firstVT和last

9、VT集合如下:firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(试构造算符的优先关系表。(10分)答：i+()*I><<<+>><<>(>>>)<<<*>>>八已知文法G(S):Sa|aAb|b|bBaA1A0|&(3)B1B0|&求：该文法的LR(0)项目集规范族。(15分)答：九.设某语言的DO-while语句的语法形式为:SdoS1whileE其语义解释为：S的代码E的代码二二二|ETC针对自上而下的语法分析器，(1) 分段产生式；(3分)(2) 写出每个产生式对应的语义动作。(7分)答：(1)分段产生式(3分