2022年COM-.编译原理A卷 .pdf

1 课程编号： COM08010 北京理工大学 20132014学年第二学期2011 级软件学院编译原理期末试题A 卷(2014.06) 班级学号姓名成绩题号一二三四五六七八总分成绩* 注意：一二四题必须答在试卷上，其它的题目写在答题纸上。一判断题（在下面答题表中填上“”或“”）。（10 分）题号1 2 3 4 5 6 7 8 9 10 答案1、 语法分析中自上而下和自下而上分析方法的扫描模式都是相同的，仅是分析模式不同。2、 LR(1)到 LALR(1) 同心项目集的合并不会产生归约归约冲突。3、 PL/0 编译器的语法分析方法采用的是自上而下分析方法。4、 LL(1) 文法不能直接处理左递归文法。5、 编译程序处理的5 个阶段词法分析、语法分析、语义处理以及中间代码生成、代码优化、目标代码生成都是有序的。6、 由于素短语是通过终结符之间的优先关系所确定的，所以素短语中不含非终结符。7、 最小化的 DFA 就是状态数最少的 DFA。8、 三元式表示法不便于优化，而间接三元式和四元式表示法便于优化。9、 正则表达式可以表示的集合一定是正则语言。10、构造基本块的 DAG 是做基本块优化前的控制流分析和数据流分析。二单项选择或填空题。（40分）1、补充完整下面的T 型图组合。A P O M B 【】【】【】【】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 2 2、基本块优化中设计的优化技术有【】 、 【】和【】 。3、 设 语 言L= ambicj|mi+j 0 ， 满 足L(G)=L的 文 法G的 四 元 式 描 述 为【 ， ， 】 。4、自下而上语法分析中主要的分析动作是【_】和【_】 。5、右图所示为某一程序段的流图。根据流图变量 t 在 d6 点的 ud链为【】 。6、右图为某基本块的DAG 图，则基本块优化后的四元式为 (每个四元式用分号结束 ) 【_ _ _ _】 。7、需要使用“拉链返填”技术的编译器情况：【_ _ 】和【_ _ 】 。8、 构 成 LR 语 法 分 析 器 的 核 心 构 件 是 【 _ _ _】 、分 析 栈 和【_ 】 。9、对下图所示的 DFA，按状态之间的状态等价关系进行划分，状态集合0,1,2,3,4,5 划分为【 _】 。d2： m=t+k d3： t=k+m d1：t=2 d4：j=t+k d5：t=j+m d6：n=t*m 3.14 n1n2n3A B0C，* D bbbbaaa035412名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 3 10、设有算符先文法G：S0S1| 1S001填写该文法优先关系表的如下表项：0 1 1 11、下面对引入中间代码的目的描述不正确的是：【】A) 便于生成目标代码B) 便于移植C) 便于优化D) 便于语义分析12、单词是语言中具有独立意义的：【】A)最小语法单位B) 最小词法单位C)语法单位D) 词法单位13、对于文法 GS：SABAAa|bBBa|Sb，句型 baSb的句柄是：A) baSbB) baC) a D)Sb14、下面对 LR 分析方法描述错误的是：【】A) LR 分析模式是规范归约B) LR(0)项目与活前缀无关C) LR 分析中归约的串是通过识别活前缀来识别的D) LR(1)项目中的向前搜索符仅仅在归约项目时使用。15、关于流图结点之间的必经结点二元关系，下列叙述不正确的是：【】A)满足自反性B)满足传递性C)满 77 称性D)满足反对称性三解答题（10 分）设字母表 =a,b,c，给出 上的正规式： R= a(b|ca)*|a)。1、构造 NFA M，使得 L(M)=L(R) ，要求给出构造的过程；2、将上面的 NFA M 确定化为 DFA M ，使得 L(M)=L(M)，要求给出确定化的过程。四 解答题（8 分）设有下面类 C 语言程序片段。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 4 注： Ex1,Ex2, E1, E2, E3, S1,S2, S3 皆为类 C 语言的合法语句； if 语句和 for 语句的语义与 C 语言相同。在下表中给出该程序片段的目标代码结构。其中：Ex1,Ex2, E1, E2, E3, S1,S2, S3语句的中间代码可简写为Exi.code, Ei.code, Si.code ；JF表示为假值跳转； JT表示为真值跳转。Addr Code (类四元式形式表示同讲义) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 五. 解答题（8分）设文法 G(P)：if (Ex1) for(E1; E2; E3) S1; else if (Ex2) S2; S3; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 5 P( B)| PaBbaR|RBbb|a1、将上述文法修改为LL(1) 文法；2、构造出 LL(1) 分析表。六. 解答题（8 分）给出如下程序流图，其中首结点为结点0：1、 求出流图中每个结点的必经结点集。2、 求出流图中的回边与循环。七. 解答题1. 设有文法 G(S)：S PP P aB | b B c |判断文法 G(S)是 LR(1)文法还是 LALR(1) 文法。要求给出判断的过程。八. 解答题（8 分）设有如下程序代码：1: k=0; 2: i=0; 3: if(i20)goto (12); 4: a=b+c; 5: b=d*c; 0 1 2 3 4 5 6 7 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 6 6: if(b=0)goto (9); 7: 8: printf(b); exit 9: i=i+1; 10: 11: printf( i); goto (13); 12: k = k + 1; 13: if(k=100) goto (2); 14: exit 给出该程序对应的控制流图。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -