2015编译原理试题b卷答案(东北大学秦皇岛分校).doc

东 北 大 学 秦 皇 岛 分 校 课程名称： 编译原理 试卷： (B )答案 考试形式： 闭卷 授课专业： 计算机科学与技术 考试日期： 年 月 日 试卷：共 4 页 题号 一 二 三 总分 得分 阅卷人 填空题（每空1分，共15分） 1、乔姆斯基形式文法共有4种，分别是 0型或短语文法 ， 1型 或上下文有关文法 ， 2型或上下文无关文法 ， 3型或正规文法 。 2、列举4种以上的自底向上语法分析方法 简单优先 ， 算符优先 ， LR(0) SLR(1), LR(1),LALR(1) ， 。 3、程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即 静态存储分配 方案和 动态存储分配 方案。 4、你所知道的词法分析程序自动构造工具有 LEX 。 5、C语言运行时栈式内存分配的活动记录内容一般包括（列举三个）： 老SP、返回地址、参数个数、参数、局部变量、临时工作单元 。 6、表达式a:=b*c+b*d的逆波兰表示为：abc*bd*+:=。 选择题（每题1.5分，共15分） 1、哪个不是DFA的构成成分（B） A、 有穷字母表 B、初始状态集合 C、 终止状态集合 D、有限状态集合 2、词法分析器的输入是（B） ?A、单词符号串???? B、源程序 ?C、语法单位???? ??D、目标程序 3、自上而下语法分析方法的主要动作是（B） A、移进 B、推导 C、规约 D、匹配 4、设有文法G[S]：S→b|bB B→bS ，则该文法所描述的语言是（ C ） A、L（G）={bi|i≥0} B、L（G）={b2i|i≥0} C、L（G）={b2i+1|i≥0} D、L（G）={b2i+1|i≥1} 5、.设有文法G[S]: S→Ap|Bq，A→a|cA，B→b|dB ，则FIRST(Ap)为（ C ） A、{p,q} B、{b,d} C、{a,c} D、 其他 6、中间代码生成时所依据的是（ D ） A、语法规则 B、 词法规则 C、语义规则 D、等价变换规则 7、在编译程序中与生成中间代码的目的无关的是（ D ） A、便于目标代码优化 B、便于存储空间的组织 C、便于目标代码的移植 D、便于编译程序的移植 8、一个S属性文法一般采用的语法制导翻译方法（ D ）。 A. LL(1) B. 算符优先 C、LR方法 D.以上三种都可以 9、中间代码是介于源语言程序和什么之间的一种代码（ D ） A、源代码 B、机器语言 C、汇编语言 D、 目标代码 10、在一个基本块内进行的代码优化是 D 。 A.全局优化 B. 代码外提 C.循环优化 D. 局部优化 三、简答题（20分） 1、一个上下文无关文法生成句子abbaa 的推导树如下：（13分） (1)给出串abbaa 最左推导、最右推导。（4分） (2)该文法的产生式集合P ，语言可能有哪些元素？（4分） (3)找出该句子的所有短语、直接短语、句柄。（5分） (1)串abbaa 最左推导: S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa 最右推导： S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b 可能元素有：ε aa ab abbaa aaabbaa …… (3)该句子的短语有： a 是相对A 的短语 ε 是相对S 的短语 b 是相对B 的短语 εbb 是相对B 的短语 aa 是相对S 的短语 aεbbaa 是相对S 的短语 直接短语有：a ε b 句柄是：a 2、（7分）名词解释： 符号串 符号串的头 符号串的尾 符号串的固有头 符号串的固有尾 符号串的集合 符号串的闭包 四、综合题（50分） 1、构造正