编译原理2014期末试卷及答案1

2014-2015学年第一学期期末考试答案及评分标准

《编译原理》（ A ）卷

课程代码： 22801204 适用班

计本12级 命题教师：

毛静

级：任

课教毛静

教研室主任审核(签 师：教学

主任(签

名)： 名)： 题 号 一 二 三 四 五 总分 分 值 得 分 一、选择题

（每小题2分，共20分）

1、下述编译过程，顺序正确的是： 【 C 】 A、词法分析，语义分析，语法分析，代码优化，中间代码生成，目标代码生成 B、语法分析，词法分析，语义分析，中间代码生成，代码优化目标代码生成 C、词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 D、语法分析，词法分析，语义分析，中间代码生成，目标代码生成，代码优化

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、语法分析常用的方法是： 【 B 】

可选项有：(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 】 A、同一层次的活生存期不交

B、任何时刻，处于生存期的活动构成一条从根节点到某节点的路径 C、路径上各节点的生存期是嵌套的 D、某一时刻只有一个活动处于生存期

9、关于寄存器的分配原则，下述说法错误的是： 【 B 】 A、当生成某变量的目标代码时，让变量的值尽可能保存在寄存器中 B、当到基本块的结束语句时，将变量的值保存在寄存器中 C、当到基本块的结束语句时，将变量的值保存在内存中

D、应该将一个基本块内的不常使用的的变量占用的寄存器尽早释放

10、作为目标代码生成的基本单位的是： 【 B 】 A、三地址吗 B、基本块 C、流图 D、中间代码

得 分 二、填空题

（每空1分，共10分）

1、编译程序是将_____ 高级语言________写的源程序翻译成______目标语言_____的程

序，这种翻译过程称为编译。

2、NFA识别记号的最大特点是它的____不确定性____________。 3、在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为_________最左推导___。

4、规定一个名字在什么样的范围内应该表示什么意义的规则，被称为_名字的作用域规则___。 5、活动记录中保存了两类信息，一类是__控制信息____，另一类是__访问信息________ 6、代码生成器以____中间代码___和______符号表信息___为输入，生成可以执行的 目标代码。

7、如果有一个正常数或者负常数C，使得每次X被增值C，则变量X被称为_归纳变量。。

得 分 三、判断题（正确的在题号后括号内填写“V”,错误的填写“X”） （每小题2分，共20分）

1. 编译程序与具体的机器有关，与具体的语言无关。 （ X ） 2. 词法分析是整个编译过程中唯一和源程序打交道的阶段。 （ V ） 3. 一个文法G被称为LL(1)文法，当且仅当该文法的预测分析表中不含多重定义的条

目。 （V ）

4. 如果一个句型中出现了某个产生式的右部，则此右部一定是句柄。 （ X ） 5. 继承属性的计算方法是自上而下，包含兄弟，综合属性的计算方式是自下而上，包

含自身。 （ V ）

6. 程序是动态的，活动室静态的。 （ X ） 7. 对一个变量的赋值是通过环境映射和值映射两步实现的。 （ V ） 8. 一个变量x在其下次引用链范围内总是活跃的。 （ V ） 9. 目标代码生成是编译器中唯一与目标机器特性相关的阶段。 （ V ） 10. 代码优化既可以在程序的局部范围内进行优化，也可以在全局范围内进行优化。 （ V ） 得 四、简答题

分 （第1小题7分，第2小题6分，第3 小题7分，共20分）

1、（7分）简述词法分析器的作用。 答：词法分析器的作用是：

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分）

E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i) 分析树如右图所示----------------------------------------（1分）。

（2）从分析书中可以看出：

短语：(T*F+i), -------------------------------（1分） E

T*F+i, -------------------------------（1分） T*F, ------------------------------------（1分） T i

直接短语：T*F-------------------------------（1分） F , i--------------------------------（1分） 句柄： T*F-------------------------------------

（1分）

( E )

E + T

T F

T * F i

3、（7分）写出表达式x=（a+b*c）*a-b/2+c的后缀式，三元式序列，四元式序列。

答： 后缀式：bc*a+a*b2/-c+x= ------------------------------------（1分）

三元式序列： ------------------------------------（3分）

得 分 五、论述题

（每小题15分，共30分）

1、 （15分）设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，(1)(*,b,c) (2)(+,(1),a) (3)(*,(2),a) (4)(/,b,2) (5)(-,(3),(4)) (6)(+,(5),c) (7)(=,(6),x)

四元式序列： (*,b,c,T1) (+,T1,a,T2) (*,T2,a,T3) (/,b,2,T4) (-,T3,T4,T5) (+,T5,c,T6) (=,x,T6,T7)

------------------------------------（3分） 请给出该字集对应的正规式，并构造一个识别该正规集的DFA。 答：（1）构造相应的正规式：(0|1)*1(0|1) -------------------------------（3分） （2）NFA如下图所示，其中状态0为初始状态，状态4为终态:

1 1

? ? ? ? 1 0 1 2 3 4

0 0

---------------------------------------------------（3分）

（3）确定化： I I0I1{0,1,2} {1,2} {1,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 0

0 1 2 3 4 0 1 1 1 ----------------------------------------------------（3分） （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

1 2 0 3 4 0 1

-----------------------------------(3分)

2、（15分）已知文法G[E]: E → ETE |（E）| i T→ * | +

（1） 将文法G改造成LL（1）文法（5分）；

（2） 构造文法G中每个非终结符的FIRST集合及FOLLOW集合（5分）； （3） 构造LL（1）分析表（5分）。

答：

（1）文法存在左递归，消除左递归后的文法为：

E→(E)E’ | i E’ ------------------------------------------------------------------------（2分）E’→TEE’ |ε -----------------------------------------------------------------------（2分）T→* | + -------------------------------------------------------------------------（1分）（2）FIRST(E)={(，i}

FIRST( E’)={*，+, ε} FIRST(T)={*，+} FOLLOW(E)={)，*，+，#}

FOWLLOW(E’)={)，*，+，#} FOLLOW(T)={(，i}

-------------------------------------------------------------------------------------（5分）

（3）LL(1)分析表如下表所示（表结构1分，每个空005分）： ( ) i * + # E E→(E)E’ E→iE’ E’ E’→ ε E’→TEE’ E’→TEE’ E’ →ε E’ →ε E’ →ε T T→* T→+ ----------------------------------------------------------------------------------------（3分）