2023年编译原理期末试卷及答案

2023-2023学年第一学期期末考试答案及评分标准。A、汇编指令，目的代码。B、源程序，中间代码

《编译原理》（A）卷。C、源程序，记号流。D、源程序，语法树

课程代码:22801204合用班计本12级

4、正规式Ml和M2等价的条件是：。【C】

命题教师:毛静坂课教毛静

A、M1和M2的状态数相同，

教研室主任审核（署痂学主任T鲁

名）：名）：B、M1和M2的有向边相同

题号w~r五总分。C、M1和M2所表达的语言集相同。

分值

D、Ml和M2状态数和有向边都相同

।得分।一、选择题

5、语法分析常用的方法是：【B

（每小题2分，共20分）

LJ可选项有：（1）自上而下（2）自左向右（3）自底向上（4）自右向左

A、（1）（2）。

B,（1）（3）

1、下述编译过程，顺序对的的是：

•C、（1）（4）•。

[C]

D、（2）（3）

A、词法分析，语义分析，语法分析，代码优化，中间代码生成，目的代码生成

B、语法分析，词法分析，语义分析，中间代码生成，代码优化目的代码生成6、若b为终结符，则A->B.bC称为：【A

，C、词法分析，语法分析，语义分析，中间代码生成，代码优化，目的代码生成。D、A、可移进项目。。

语法分析，词法分析，语义分析，中间代码生成，目的代码生成，代码优化B、可归约项目

。C、可接受项目

2、编译程序是对：

D、待约项目

[D1

。A、高级语言程序的执行。B、汇编语言的翻译7、参数的传递方式重要有：。【D】

。C、机器语言的执行。D、高级语言的翻译可选项：（1）值传递（2）地址传递（3）复写恢复（4）换名调用

A、（1）（2）。

3、词法分析的输入和输出分别是：[C]

B、⑴(2)(3)二、填空题

。C、(2)(3)(4)。(每空1分，共10分)

D、⑴(2)(3)(4)

1、编译程序是将高级语言写的源程序翻择成目的语言的

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

8、下述关于顺序执行的程序的活动树上各节点之间的关系错误的说法是:

2、NFA辨认记号的最大特点是它的不拟定性_____________o

[D]

3、在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为

。A、同一层次的活生存期不交

最左推导。

B、任何时刻，处在生存期的活动构成一条从根节点到某节点的途径

4、规定一个名字在什么样的范围内应当表达什么意义的规则.被称为名字的作用域规

C、途径上各节点的生存期是嵌套的

D、某一时刻只有一个活动处在生存期

5、活动记录中保存了两类信息，一类是控制信息，另一类是访问信息

9、关于寄存器的分派原则，下述说法错误的是：[B]

。A、当生成某变量的目的代码时，让变量的值尽也许保存在寄存器中6、代码生成器以中间代码和符号表信息为输入.生成可以执行的

。B、当到基本块的结束语句时，将变量的值保存在寄存器中目的代码。

C、当到基本块的结束语句时，将变量的值保存在内存中。。7、假如有一个正常数或者负常数C,使得每次X被增值C,则变量X被称为归纳变

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

10、作为目的代码生成的基本单位的是；[B]

A、三地址吗。

B、基本块三、判断题(对的的在题号后括号内填写“V”，错误的填写“X”)

。C、流图(每小题2分，共20分)

D、中间代码

1.编译程序与具体的机器有关，与具体的语言无关。

H(X)

2.词法分析是整个编译过程中唯一和源程序打交道的阶段。

(V)

3.一个文法G被称为LL（1）文法，当且仅当该文法的预测分析表中不含多重定义的条答:词法分析器的作用是：

目。1）滤掉源程序中的无用成分，如注释、空格、回车等（2分）

（V）2）解决与具体平台有关的输入（如文献结束符的不同表达等）（1分）

4.假如一个句型中出现了某个产生式的右部，则此右部一定是句柄。3）辨认记号，并交给语法分析器。根据模式辨认记号（2分）

（X）4）调用符号表管理器或犯错解决器,进行相关解决（2分）

5.继承属性的计算方法是自上而下，包含兄弟，综合属性的计算方式是自下而上,

包含自身。2、（6分）对于文法G（E）:

（V）EfT|E+T

6.程序是动态的，活动室静态的。T->F|T*F

（X）Ff（E）|i

7.对一个变量的赋值是通过环境映射和值映射两步实现的。1）.写出句型（T*F+i）的最右推导并画出分析树（3分）。

（V）2）.写出上述句型的短语，直接短语、句柄（3分）。

8.一个变量x在其下次引用链范围内总是活跃的。

答：（1）句型（T*F+i）的最右推导：---———--------------——---——（2

（V）

分）

9.目的代码生成是编译器中唯一与目的机器特性相关的阶段。

EnT=F=>(E)=(E+T)n(E+F)n(E+i)n(T+i)n(T*F+i)

（V）

分析树如右图所示------

10.代码优化既可以在程序的局部范围内进行优化，也可以在全局范围内进行优化。

（1分）。

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

F.

吾：(T*F+i),--———..............-......———"(1分)

T

T*F+i,------———--"—————"----卜I分)

四,简答题

（第1小题7分，第2小题6分，第3小

题7分，共20分）

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

TF

,i-------------―--------------(1分)(+,Tl,a,T2)

____—————___一(1(*,T2,a,T3)

(/,b,2,T4)

(一，T3,T4,T5)

(+,T5,c,T6)

(=,x,T6,T7)

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

列。

后^^5^：be*a+a*b2/-c+x=———-————---————

-----(1分)

三元式序列：___—___----------..---

--(3分)

(1)(*,b,c)

(2)(+,(l),a)

(3)(*,(2),a)

五、论述题

(4)(/,b,2)（每小题15分，共30分）

(5)(-,(3),(4))

1、（15分）设£={0,1}上的正规集S由倒数第二个字符为1的所有字符串组成，请

(6)(十,(5),c)

给出该字集相应的正规式,并构造一个辨认该正规集的DFAo

(7)(二,(6),x)

四元式序歹U：-------------------—--------(3分)

答：（1）构造相应的正规式：（0|1）*1（0|1）

(*,b,c,Tl)

-(3分)初始划分结果({0,1,2},{3,4})

(2)NFA如下图所示，其中状态0为初始状态，状态4为终态:Move(0,0)=1Move(1,0)=1Move(2,0)=3

第二次划分({0,1),{2},{3,4})

Move(0,1)=2Move(l,l)=2所以状态0和状态1不可区分

Move⑶0)=1Move(4,0)=3状态3和状态4可区分

------(3分)

第三次划分([0,1},{2},{3},{4})用1状态代替{0}1}状态得到最小DFA

如下图所示

----——(3分)

(3)拟定化:

1，o

(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|

{124}{1,2}{123}

(1,2,3,4){124}(1,2,3,4)

(3分)

2、(15分)已知文法G[E]:

1

E-ETE|(E)Ii

-——————(3，分)

T-**

(4)最小化DFA