内容发布更新时间 : 2024/10/22 10:59:27星期一 下面是文章的全部内容请认真阅读。
2018-2018学年第一学期期末考试答案及评分标准
《编译原理》< A）卷
课程代码：命题教师：
22801204 毛静
b5E2RGbCAP
教研室主任审核(签
名>：
适用班计本12级 级：任课教毛静 教 案主任(签 师：
名>：题 号 分 值 得 分 一 二 三 四 五 总分 一、选择题 <每小题2分，共20分） 1、下述编译过程，顺序正确的是： 【 C】 A、词法分析，语义分析，语法分析，代码优化，中间代码生成，目标代码生成B、语法分析，词法分析，语义分析，中间代码生成，代码优化目标代码生成
p1EanqFDPw C、词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成D、语法分析，词法分析，语义分析，中间代码生成，目标代码生成，代码优化
DXDiTa9E3d 2、编译程序是对：【D 】 A、高级语言程序的执行 B、汇编语言的翻译 C、机器语言的执行D、高级语言的翻译 3、词法分析的输入和输出分别是：【 C 】
A、汇编指令，目标代码B、源程序，中间代码 C、源程序，记号流D、源程序，语法树
4、正规式M1和M2等价的条件是： 【 C 】 A、M1和M2的状态数相同 B、M1和M2的有向边相同
C、M1和M2所表示的语言集相同 D、M1和M2状态数和有向边都相同
5、语法分析常用的方法是：
可选项有：(1>自上而下 (2>自左向右 (3>自底向上 (4>自右向左 A、<1）<2） B、<1）<3） C、<1）<4） D、<2）<3）
6、若b为终结符，则A -> B.bC称为：【 A 】 A、可移进工程
B、可归约工程 C、可接受工程 D、待约工程
7、参数的传递方式主要有： 【 D 】 可选项：<1）值传递 <2）地址传递 <3）复写恢复 <4）换名调用 A、<1）<2） B、<1）<2）<3） C、<2）<3）<4） D、<1）<2）<3）<4）
8、下述关于顺序执行的程序的活动树上各节点之间的关系错误的说法是： 【 D 】RTCrpUDGiT A、同一层次的活生存期不交
B、任何时刻，处于生存期的活动构成一条从根节点到某节点的路径 C、路径上各节点的生存期是嵌套的 D、某一时刻只有一个活动处于生存期
9、关于寄存器的分配原则，下述说法错误的是： 【 B 】 A、当生成某变量的目标代码时，让变量的值尽可能保存在寄存器中 B、当到基本块的结束语句时，将变量的值保存在寄存器中 C、当到基本块的结束语句时，将变量的值保存在内存中
D、应该将一个基本块内的不常使用的的变量占用的寄存器尽早释放 10、作为目标代码生成的基本单位的是： 【 B 】 A、三地址吗 B、基本块 C、流图 D、中间代码 得 分
<每空1分，共10分）
填空题二、
5PCzVD7HxA 【 B 】
1、编译程序是将_____高级语言________写的源程序翻译成______目标语言_____的程序，这种翻译过程称为编译。jLBHrnAILg 2、NFA识别记号的最大特点是它的____不确定性____________。
3、在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为_________最左推导___。xHAQX74J0X 4、规定一个名字在什么样的范围内应该表示什么意义的规则，被称为_名字的作用域规则___。
5、活动记录中保存了两类信息，一类是__控制信息____，另一类是__访问信息________
6、代码生成器以____中间代码___和______符号表信息___为输入，生成可以执行的目标代码。
7、如果有一个正常数或者负常数C，使得每次X被增值C，则变量X被称为_归纳变1 / 3
量。。
得 分 <正确的在题号后括号内填写“V”,错误的填写判断题三、 “X”）<每小题2分，共20分）
LDAYtRyKfE 1.编译程序与具体的机器有关，与具体的语言无关。< X ） 2.词法分析是整个编译过程中唯一和源程序打交道的阶段。 答：词法分析器的作用是： 1) 滤掉源程序中的无用成分，如注释、空格、回车等<2分） 2) 处理与具体平台有关的输入<如文件结束符的不同表示等）<1分） 3) 识别记号，并交给语法分析器。根据模式识别记号<2分） 4) 调用符号表管理器或出错处理器，进行相关处理<2分） 2、(6分>对于文法G(E>:E?T|E+T T?F|T*F F?(E>|i 1>.写出句型 (T*F+i> 的最右推导并画出分析树<3分）。 2>.写出上述句型的短语，直接短语、句柄<3分）。 答：<1）句型 (T*F+i> 的最右推导：-------------------------------<2分）EmxvxOtOco E?T?F?(E> ?(E+T> ?(E+F> ?(E+i> ?(T+i> ?(T*F+i> 分析树如右图所示----------------------------------------<1分）。SixE2yXPq5 <2）从分析书中可以看出： 短语：(T*F+i>, -------------------------------<1分） E T F T*F+i, -------------------------------<1分） T*F, ------------------------------------<1分） i 直接短语：T*F-------------------------------<1分） , i--------------------------------<1分） 句柄：T*F-------------------------------------<1分） 3、<7分）写出表达式x= (*,T2,a,T3> (/,b,2,T4> (-,T3,T4,T5> (+,T5,c,T6> (=,x,T6,T7> 得 分 五、论述题 <每小题15分，共30分） 1、 <15分）设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请 给出该字集对应的正规式，并构造一个识别该正规集的DFA。M2ub6vSTnP 答：<1）构造相应的正规式：(0|1>*1(0|1>-------------------------------<3分）0YujCfmUCw <2）NFA如下图所示，其中状态0为初始状态，状态4为终态: 1 1 ????1 0 1 2 3 4 0 0 ---------------------------------------------------<3分）eUts8ZQVRd <3）确定化： I {0,1,2} {1,2} {1,2,3} 2 / 3 {1,2} {1,2} {1,2,3} {1,2,3} {1,2,4} {1,2,3,4} {1,2,4} {1,2} {1,2,3} {1,2,3,4} {1,2,4} {1,2,3,4} 0 1 0 1 0 0sQsAEJkW5T 0 1 2 3 4 0 1 1 1 ----------------------------------------------------<3分）GMsIasNXkA <4）最小化DFA 初始划分结果<{0,1,2}，{3,4}） Move(0,0>= 1 Move(1,0>=1 Move(2,0>=3 第二次划分<{0,1}，{2}，{3,4}） Move(0,1>=2 Move(1,1>=2 所以状态0和状态1不可区分 Move(3,0>=1 Move(4,0>=3 状态3和状态4可区分 ------------------------------------<3分） 第三次划分<{0,1}，{2}，{3}，{4}）用1状态代替{0,1}状态得到最小DFA如下图所示 0 1 1 0 0 1 2 3 4 0 1 -----------------------------------(3分> 2、<15分）已知文法G[E]: E → ETE | （1） 将文法G改造成LL<1）文法<5分）； （2） 构造文法G中每个非终结符的FIRST集合及FOLLOW集合<5分）； （3） 构造LL<1）分析表<5分）。 答： <1）文法存在左递归，消除左递归后的文法为： E→(E>E’|i E’------------------------------------------------------------------------<2分） TIrRGchYzg E’→TEE’|ε-----------------------------------------------------------------------<2分） 7EqZcWLZNX 3 / 3 T→*|+ -------------------------------------------------------------------------<1分） lzq7IGf02E <2）FIRST(E>={(，i} FIRST( E’>={*，+, ε} FIRST(T>={*，+} FOLLOW(E>={>，*，+，#} FOWLLOW(E’>={>，*，+，#} FOLLOW(T>={(，i} -------------------------------------------------------------------------------------<5 分） zvpgeqJ1hk <3）LL(1>分析表如下表所示<表结构1分，每个空005分）： ( > i * + # E E→(E>E’ E→iE’ E’ E’→ε E’→TEE’ E’→TEE’ E’→ε E’→ε E’→εT T→* T→+ 分） ----------------------------------------------------------------------------------------<3NrpoJac3v1