合肥工业大学编译原理期末复习

编译原理基础题

一、选择题

1、在使用高级语言编程时，首先可通过编译程序发现源程序的全部（ A ）错误和部分语义错误。

A、语法 B、语义 C、语用 D、运行 2、编译过程中，语法分析器的任务是（ B ）。

(1)分析单词是怎样构成的； (2)分析单词串是如何构成语句和说明的； (3)分析语句和说明是如何构成程序的；(4)分析程序的结构

A、(2)(3) B、(2)(3)(4) C、(1)(2)(3) D、(1)(2)(3)(4) 3．生成能被5整除的正整数的文法G[Z]是_ C____。 A. G[Z]: Z→AC,A→BA|B,B→0|1|2|?|9,C→0|5 B. G[Z]: Z→AC,A→BA|ε,B→0|1|2|?|9,C→0|5 C. G[Z]：Z→DA0|A5，A→BA|ε，B→0|D，D→1|2|?|9 D. G[Z]：Z→AC|C,A→BA|B,B→0|1|2|?|9,C→0|5

4、编译程序中的语法分析器接受以（ C ）为单位的输入，并产生有关信息供以后各阶段使用。

A、表达式 B、产生式 C、单词 D、语句 5、算符优先分析法每次都是对（ D ）进行归约。 A、直接短语 B、句柄 C、素短语 D、最左素短语 6、过程调用时，参数的传递方法通常有（ C ）。 (1)传值；(2)传地址；(3)传结果；(4)传名

A、(1)(2) B、(1)(2)(3) C、(1)(2)(4) D、(1)(2)(3)(4) 7、在编译方法中，动态存储分配的含义是（ A ）。 A、在运行阶段对源程序中的量进行分配 B、在编译阶段对源程序中的量进行分配

C、在编译阶段对源程序中的量进行分配，在运行时这些量的地址可以根据需要改变 D、以上都不对

8、a:= a+b*c↑(d/e)/f的逆波兰记号表示是（ ）。

A、aabc*+↑de/f/:= B、aabcde↑/*f/:= C、aabcde/↑*f/+:= D、以上都不对。

9．算符文法是指 A 的文法。

①没有形如U→...VW...的规则（U，V，W?VN） ②VT中任意两个符号之间至多存在一种算符优先关系

③没有相同右部的规则 ④没有形如U→ε的规则

A. ① B. ①和② C. ①、②和③ D. ①、②、③和④

10、编译程序绝大多数时间花在 D 上。

a．出错处理 b．词法分析 c．目标代码生成 d．管理表格

11．下述语句类中，_____A_ _____在编译阶段通常不产生可执行代码。

A. 变量说明语句 B. 流程控制语句 C. 输入输出语句 D. 赋值语句

12、词法分析器的输入是 B 。

a．单词符号串 b．源程序 c．语法单位 d．目标程序

13．在编译程序采用的优化方法中， D 是在循环语句范围内进行的。

①合并已知常量 ②删除多余运算 ③删除归纳变量 ④运算强度削弱 ⑤代码外提

A. ①④ B. ①⑤ C. ①④⑤ D. ③④⑤

14．程序的基本块是指__ D____。

A. 不含无条件转移语句的程序段 B. 不含条件转移语句的程序段 C. 不含停机的语句程序段

D. 仅含有一个入口语句和一个出口语句的顺序程序段

15、文法G描述的语言L(G)是指 A 。

a. L(G)={α|S+ VT*} ?α , α∈

*α, α∈b. L(G)={α|S?VT*}

*α,α∈c. L(G)={α|S?(VT∪VN*)} d. L(G)={α|S+ (VT∪VN*)} ?α, α∈

16、如果文法G是无二义的，则它的任何句子α A 。

a. 最左推导和最右推导对应的语法树必定相同

b. 最左推导和最右推导对应的语法树可能不同 c. 最左推导和最右推导必定相同

d. 可能存在两个不同的最左推导，但它们对应的语法树相同

17、文法G：E→E+T|T

T→T*P|P P→(E)|I

则句型P+T+i的句柄和最左素短语为 B 。 a.P+T和i b. P和P+T c. i和P+T+i d.P和T 18、产生正规语言的文法为 D 。

a. 0型 b. 1型 c. 2型 19、有文法G：E→E*T|T

T→T+i|i

d. 3型

句子1+2*8+6按该文法G归约，其值为 B 。 a. 23 B. 42 c. 30 d. 17 20、若a为终结符，则A→α·aβ为 B 项目 a.归约 b.移进 c.接受 d.待约 21、就文法的描述能力来说，有 C 。

a. SLR（1）?LR（0） b. LR（1）?LR（0）c. SLR（1）?LR（1）d.无二义文法?LR（1）

22、一个 A 指明了在分析过程中的某时刻所能看到产生式多大一部分。

a.活前缀 b.前缀 c.项目 d.项目集 23、四元式之间的联系是通过 B 实现的。

a.指示器 b.临时变量 c.符号表 d.程序变量 24、表达式（┓A∨B）∧（C∨D）的逆波兰表示为 B 。

a. ┓AB∨∧CD∨ b. A┓B∨CD∨∧ c. AB∨┓CD∨∧ d. A┓B∨∧CD∨

25、终结符具有 D 属性。

a.传递 b.继承 c.抽象 d.综合

26、在编译方法中，动态存储分配的含义是 A 。

a. 在运行阶段对源程序中的数组、变量、参数等进行分配 b. 在编译阶段对源程序中的数组、变量、参数进行分配

c. 在编译阶段对源程序中的数组、变量、参数等进行分配，在运行时这些数组、变量、参数的地址可根据需要改变 d. 以上都不正确

27、栈式动态分配与管理在过程返回时应做的工作有 。

a. 保护SP b. 恢复SP c.保护TOP d. 恢复TOP 28、下列 C 优化方法不是针对循优化进行的。

a．强度削弱 b．删除归纳变量 c．删除多余运算 d．代码外提 29、对一个基本块来说， A 是正确的。

a．只有一个入口语句和一个出口语句 b．有一个入口语句和多个出口语句

c．有多个入口语句和一个出口语句 d．有多个入口语句和多个出口语句

二、填空题

1、编译方式与解释方式的根本区别在于（ 是否生成目标代码 ）。

2、自顶向下语法分析方法会遇到的主要问题有（ 回溯 ）和（ 左递归带来的无限循环 ）。 3、自上而下语法分析方法的基本思想是：从（识别符号或开始符号）出发，不断建立（ 直接推导 ），试图构造一个推导序列，最终由它推导出与输入符号相同的（ 符号串 ）。

4、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 5、文法符号的属性有（ 继承属性 ）和（ 综合属性 ）两种。

6．已知文法G[A]：A→(B)| a |ε，B→B，A | A，该文法的开始符号是_A__ ，非终结符号

集合为___{A,B}___，终结符号集合为__{(,),a}_____。

7．已知文法G[S]：S→AB,A→ aAb | c,B→ aBb| d，则对于非终结符A，FOLLOW(A)=__ {a,b,d}____。

8、Chomsky定义的四种形式语言文法分别为： 0型文法--又称短语文法，1型文法--又称上下文有关文法，2型 文法--又称（上下文无关 ）文法，3型文法--又称（ 正规 ）文法。 9、在PASCAL中，由于允许用户动态申请与释放内存空间，所以必须采用（ 堆 ）存储分配方式。

10、局部优化是局限于一个（ 基本块 ）范围内的一种优化。 11、编译程序的工作过程还会伴有（ 表格处理 ）和（ 出错处理 ）。

12．有这样一个推导过程，其每一步推导都是对符号串中最右的非终结符进行替换， 我们把这种推导过程称为__最右推导（或规范推导）_______ 。

三、判断题

1、一个有限状态自动机中，有且仅有一个唯一终态。 （ F ） 2、自动机M和M′的状态数不同，则二者必不等价。 （ F ） 3、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 （ T ） 4、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。 （ T ） 5．在形式语言中，最右推导的逆过程称为规范归约。 （ T ） 6．句型的每个直接短语都是某规则的右部。 （ T ） 7．任何正规文法都是上下文无关文法。 （ T ） 8. 计算机高级语言翻译成低级语言只有解释一种方式。 （ F ） 9．自底而上语法分析方法的主要问题是候选式的选择。 （ F ）

10．“用高级语言写的源程序都必须通过编译, 产生目标代码后才能投入运行”这种说法。( F) 11．一个句型的句柄一定是文法某产生式的右部。 ( T )

12．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 ( ) 13．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。( )

14．综合属性是用于 “ 自上而下 ” 传递信息。 ( F ) 15．使用语法制导翻译方法的编译程序能同时进行语法分析和语义分析。( T ) 16. 终结符既可以有综合属性，又可以有继承属性。（ F ） 17. 逆波兰表示法表示表达式时无须使用括号。（ T ）

18. 由于C语言的函数允许递归调用，因此对C程序中的所有变量的单元分配一律采用动态分配方式。（ F ）

19. DISPLAY表用来记录每层过程的最新活动记录地址，因此它的大小运行时确定。（ ） 20. 最左素短语一定是短语。（ T ）

21. LR分析中的活前缀一定包含某句型的句柄的一部分或全部。（ T ） 22. 自下而上分析的“下”指的是被分析的源程序串。（ T ）