聊城大学计算机学院11—12学年第2学期期末考试《编译原理》试题(闭卷A卷).docVIP

聊城大学计算机学院1—12学年第学期期末考试本《编译原理》试题（闭卷A卷） 题号 一 二 三 四 总分 复核人 得分 一、填空题（共题，每空1分，共15分） 得分 阅卷人 自而采用、归约、错误处理、等四种操作。对编译程序而言，输入数据是，输出结果是。 后缀式abc-/所代表的表达式是。如果的任何一个产生式的右部都不包含连续的非终结符，那么则称之为G是一个给定的文法，S是文法的开始符号，如果Sx( 其中 x∈VT*), 则称 x是文法的一个 。 递归下降法不允许任一非终极符是直接 递归的。 对于文法G[E]：E→T|E+T T→F|T*F F→PF|P P→(E)|i，句型T+T*F+i的产生 由最右推导由此得到的句型称为句型。二、选择题（共10题，每题2分，共20分） 得分 阅卷人 题号 1 2 3 4 5 6 7 8 9 10 答案 正规式 M 1 和 M 2 等价是指_____。? 　A．M1和M2的状态数相等 ? 　 　?????? B． M1和M2的有向边条数相等C．M1和M2所识别的语言集相等 　　 D． M1和M2状态数和有向边条数相等 文法G：S→xSx|y所识别的语言是_____。 A． xyx? 　 B．(xyx)* C．xnyxn(n≥0) ??? D．x*yx* 如果文法G是无二义的，则它的任何句子α _____。 A．最左推导和最右推导对应的语法树必定相同 　　B．最左推导和最右推导对应的语法树可能不同 　　 C．最左推导和最右推导必定相同 ? 　　　D．可能存在两个不同的最左推导，但它们对应的语法树相同 四元式之间的联系是通过_____实现的。 A．指示器 ???? 　　B．临时变量 　C．符号表 ??????????? D．程序变量编译程序前三个阶段完成的工作是_____ A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 对应Chomsky四种文法的四种语言之间的关系是_____ A．L0(L1(L2(L3 B．L3(L2(L1(L0C．L3=L2(L1(L0 D．L0(L1(L2=L3_____。 A．是无穷多个 B．是有穷多个 C．是可枚举的 D．个数是常量 高级语言编译程序常用的语法分析方法中，LL分析法属于______分析方法。 A．自左至右 B．自顶向下 C．自底向上 D．自右至左 若a为终结符，则A→α·aβ为 项目。 A． 归约 B． 待约 C． 接受 D．移进 LR 分析法中，分析栈中存放的状态是识别规范句型_____的 DFA 状态。 A．B． C．D．LR(0) 三、简答题（共5题，共分） 得分 阅卷人 字母表Σ={a, b}，试写出Σ上所有以a为首的组成的正规集相对应的正规式 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。 （6分）已知文法G(S)及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 请问：对输入串acab经过上述翻译后的输出结果是什么？并写出分析过程。 （8分） 已知文法 G[E] 为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 请问：① 请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。 ② 找出句型 T+T*F+i 的短语、直接短语和句柄。 （8分）已知文法 A→ aAd| aAb|ε 试判断该文法是否SLR（1）文法，并说明之。 、（共题，共分） 得分 阅卷人 1、G(S)： S→(L)|a S|a L→L，S|S ①（4分）消除左递归和回溯。 ②（4分）计算每个非终结符的FIRST和FOLLOW。 ③（5分）构造预测分析表。 2、(1分)已知文法G[S]：S→aB|ε B→bC|bD C→cB|c D→d 试构造一个与之等价的NFA，并将上述NFA确定化为DFA。 已知文法GS→S S→AS|b A→SA|a ① （5分）试求Closure({(S→(S#)})。 ② （5分）试求GO(closure({(S→(S#)})，S)。 学院 专业 姓名 ?学号 级 班 ··