文档介绍：- 1- 东北大学秦皇岛分校课程名称: 编译原理试卷: (B)答案考试形式: 闭卷授课专业:计算机科学与技术考试日期:年月日试卷:共 2页题号一二三四总分得分阅卷人一、填空题(每空 2分,共 30分) 1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段,另外还有两个重要的工作是理和出错处理。表格管 2、规范规约中的可归约串是句柄, 算符优先分析中的可归约串是最左素短语。 3、语法分析方法主要可分为自顶向下和自底向上两大类。 4、 LR (0 )文法的项目集中不会出现移进- 归约冲突和归约- 归约冲突。 5 、数据空间的动态存储分配方式可分为栈式和堆式两种。 6、编译程序是指能将源语言程序翻译成目标语言程序的程序。 7 、确定有穷自动机 DFA 是 NFA 的一个特例。 8、表达式(a+b)*c 的逆波兰表示为 ab+c* 。二、选择题(每题 2分,共 20分) 1、 LR 语法分析栈中存放的状态是识别 B的 DFA 状态。 A 、前缀 B 、可归前缀 C 、项目 D 、句柄 2、D 不可能是目标代码。 A 、汇编指令代码 B 、可重定位指令代码 C 、绝对机器指令代码 D 、中间代码 3 、一个控制流程图就是具有 C 的有向图 A 、唯一入口结点 B 、唯一出口结点 C 、唯一首结点 D 、唯一尾结点 4 、设有文法 G[S] :S→ b|bB B→ bS ,则该文法所描述的语言是 C。 A、L(G) ={b i |i≥ 0}B、L(G) ={b 2i |i≥ 0} C、L(G) ={b 2i+1 |i≥ 0}D、L(G) ={b 2i+1 |i≥ 1} 5 、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。 A 、编译器 B 、汇编器 C 、解释器 D 、预处理器 6 、在目标代码生成阶段,符号表用于 D。 A 、目标代码生成 B 、语义检查 C 、语法检查 D 、预处理器地址分配 0 7 、规范归约是指 B。 A 、最左推导的逆过程 B 、最右推导的逆过程 C 、规范推导 D 、最左归约逆过程 8、使用 A 可以定义一个程序的意义。 A 、语义规则 B 、词法规则 C 、语法规则 D 、左结合规则 9、经过编译所得到的目标程序是 D。 A 、三元式序列 B 、四元式序列 C 、间接三元式 D 、机器语言程序或汇编语言程序 10 、在一个基本块内进行的代码优化是 B。 A 、全局优化 B 、局部优化 C 、循环优化 D 、代码外提三、简答题( 3小题,共 30分) 1、已知文法 G[S] :S→ Ac|aB A→ ab B→ bc 证明该文法具有二义性(本题 6分) 证明:因为该文法的句型 abc 存在如下两棵语法树: 装订线装订线内不要答题学号姓名班级- 2- 所以, 该文法具有二义性 3、若有文法 G[S] :S→ bAb A→( B|a B→ Aa)。构造该文法的简单优先关系矩阵。( 10 分) 解: 4 、构造正规表达式( a|b )*b的 DFA 并化简。( 14 分) 解:先构造其 NFA 如下: 确定化为 DFA : 将其最小化如下: 四、综合题(20分) 设有文法 G[S] :S→ BA A→ BS|d B→ aA|bS|c (1) 证明文法 G是 L