编译原理期末考试习题及答案(桂电)

桂 林 电 子 科 技 大 学 试 卷 2012-2013 学年第 2 学期 课号 课程名称 编译原理试题、答案和评分标准 （A卷;闭卷） 适用班级（或年级、专业） 01应本 考试时间 120 分钟 班级 学号 姓名 题 号一二三四五六七八九十成绩满 分208661510101510100得 分评卷人一、填空题|（每题4分，共20分）1. 乔母斯基定义的3型文法（线性文法）产生式形式 AàBa|a,或AàaB|a，A，BVn,a,bVt 。2.语法分析程序的输入是 单词符号，其输出是 语法单位 。3 型为 B à .aB 的LR（0）项目被称为 移进 项目，型为 B à a.B 的LR（0）项目被称为 待约 项目，4.在属性文法中文法符号的两种属性分别为 继承属性 和 综合属性 。5、运行时存贮管理方案有 静态存储分配、动态存储分配 和 堆式存储分配 和方案。 二.已知文法 G(S)(1) E à T | E+T(2) T à F | F*F(3) F à （E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分）答：（1）最右推到（2分） E => T => F => (E) => (E+T) => (E+F) => (E+i) => (T+i) => (T*F+i)(2) 语法树（2分）（3）（4分） 短语： （T*F+i） ，T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法 G(S) ： S à SaS | 是二义的。（6分）答：句子 aaa对应的两颗语法树为：因此，文法是二义文法四.给定正规文法G（S）： (1) S à Sa | Ab |b(2) A à Sa 请构造与之等价的DFA。（6分）答：对应的NFA为： （6分）状态转换表：abFSSS,AS,AS,AS五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） （2）将（1）所得的NFA确定化：（5分）ab01，301,32，32,31,32,3（5分）六. 已知文法G(S) :(1) S à | a | (T)(2) T à T,S | S试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分）答：（1）消除文法的左递归后文法 G（S）为： (1) S à | a | (T)(2) T à ST | S(3) T à ,ST | （4分） （2）（6分）firstfollowSa (# , )Ta ()T, )七. 已知文法G(S) :(1) S à SiA | A(2) A à A+B | B(3) B à A* | （试构造非终止符的firstVT和lastVT集合。（10分）答：（10分）firstVTlastVTSi , + , * , ( i , + , * , (A+ , * , (+ , * , (B* , (* , (FollowS#Ba,b,#八.已知文法G(S) :(1) S à B B(2) B à a B(3) B à b 的follow集合如表：试：（1）给出该文法的LR（0）项目集规范族划分； （2）填写相应的SLR（1）的分析表。（15分）答：（1）LR（0）项目集规范族划分(8分)I0Sà .SS à .BBB à .aBB à .b-à I1-à I2-à I3-à I4SBa bI1Sà S.I2S à B.BB à .aBB à .b-à I5-à I3-à I4Ba bI3B à a.BB à .aBB à .b-à I6-à I3-à I4Ba bI4B à b.I5S à BB.I6B à aB. (2) SLR(1)分析表（7分）状态ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九设某语言的not-then-else 语句的语法形式为：S à not E then S1 其语义解释为： 针对自上而下的语法分析器，(1) 分段产生式；（3分）(2) 写出每个产生式对应的语义动作。（7分）答：（1）分段产生式（3分）及语义动作(7分) (1) R à not E then Backpatch（$2.FC ，nxq ）;$.chain = $2.Tc (2) S à R S1 Backpatch（$2.chain ， nxq ）桂 林 电 子 科 技 大 学 试 卷 2012-2013 学年第 2 学期 课号 122239 课程名称 编译原理试题、答案和评分标准 （B卷;闭卷） 适用班级（或年级、专业） 01应本 考试时间 120 分钟 班级 学号 姓名 题 号一二三四五六七八九十成绩满 分208661510101510100得 分评卷人一、填空题|（每题4分，共20分）1. 乔母斯基定义的2型文法（上下文无关文法）产生式形式 Aà,AVn, V+。2.词法分析程序的输入是 字符串 ，其输出是 单词符号 。3 算符有限分析方法每次都是对 最左素短语 进行规约。型为 B à aB. 的LR（0）项目被称为 规约 项目。4、写出x:=b*(d-e)/(c-d)+e的逆波兰式_xbde-*cd-/e+:=_。5、常用的两种动态存贮分配办法是_栈式存储 分配 和 堆式存储_分配。 二已知文法G(S) :(1) S à | a | (T)(2) T à T,S | S 试：（1）写出句型（a,(a,a)的最左推到并画出语法树。（4分） （2）写出上述句子的短语，直接短语和句柄。（4分）答：（1）最左推到（2分） S => （T） => （T,S）=> (S,S) => (a,S) => (a,(T) => (a,(T,S) => (a,（S,S) => (a,（a,S) => (a,（a,a)(2) 语法树（2分）（3）（4分） 短语：（a,(a,a)） ，a,(a,a) ， (a,a) ， a,a , a 直接短语：a 句柄：a三证明文法 G(S) ： S à aSb | Sb | b 是二义的。（6分）答：句子 aabbbb对应的两颗语法树为： 因此，文法是二义文法四.给定正规文法G（S）： (1) S à aA (2) A à aB | bA （3）B à aA | b 请构造与之等价的DFA。（6分）答：对应的DFA为：（6分） 五. 构造识别正规语言(ab*|a)* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA （5分） （2）将（1）所得的NFA确定化：（5分）ab11,21,21,21,2 （5分）六. 已知文法G(S) :(1) S à | a | (T)(2) T à ST | S(3) T à ,ST |试：求first和follow集合，构造改文法的LL（1）分析表。（10分）答：文法相应的first 和 follow 集合 （5分）firstfollowSa (# , )Ta ()T, )其LL（1）分析表如下：七. 已知文法G(S) :(1) S à SiA | A(2) A à A+B | B(3) B à A* | （非终止符的firstVT和lastVT集合如下:firstVTlastVTSi , + , * , ( i , + , * , (A+ , * , (+ , * , (B* , (* , (试构造算符的优先关系表。（10分）答：i+()*I><<<+>><<>(>>>)<<<*>>>八已知文法G(S) :(1) S à a | aAb | b | bBa(2) A à 1A0 | (3) B à 1B0 | 求 ：该文法的LR（0）项目集规范族。（15分）答：九设某语言的DO-while 语句的语法形式为： S à do S1 while E 其语义解释为：针对自上而下的语法分析器，(1) 分段产生式；（3分）(2) 写出每个产生式对应的语义动作。（7分）答：（1）分段产生式（3分） G(S) : (1) R à do (2) U à R S1 while (3) S à U E(2) 产生式对应的语义动作(7分) (1) R à do $.loop = nxq (2) U à R S1 while $.loop = $1.loop (3) S à U E backpatch（$2.FC ， $1.loop ）； Backpatch（$2.TC ， nxq ） 9