编译原理模拟试题和答案编译原理模拟试题和答案 d

【题型】简答题 1题干】

现有文法G[S]：

B?idt|?请问aidtccb是句型还是句子，为什么？

S?aAb

A?BcA|B

【答案】

S ?aAb ?aBcAb ?aidtcAb ?aidtcBcAb ?aidtc ?cAb ? aidtccAb?aidtccBb ?aidtcc ?b ? aidtccb 是句型，也是句子。 【题型】简答题 2题干】

设有文法G1[S]： →

→|

试写出028的最左推导过程。 【答案】

028的最左推导：=>=>=>=>=>0=>02=>028。 3题型】填空题 【题干】

递归下降法不允许任一非终结符是直接_______________递归的。 【答案】 左;

4题型】填空题 【题干】

在使用高级语言编程时，首先可通过编译程序发现源程序的全部_______________错误和部分语义错误。 【答案】 语法;

5题型】填空题 【题干】

把汇编语言程序翻译成机器可执行的目标程序的工作是由_______________完成的。 【答案】 汇编器;

6题型】填空题 【题干】

语法分析器的输出是_______________。 【答案】 语法单位;

7题干】

循环优化的三种重要技术包括删除归纳变量、代码外提和_______________。 【答案】 强度消弱; 8题干】

写出表达式(a+b)/(a-b)-a(a+b*c)的三元式序列及四元式序列。 【答案】

三元式： ⑴.(+,a,b) ⑵.(-,a,b) ⑶.(/,⑴,⑵) ⑷.(*,b,c) ⑸.(+,a,⑷) ⑹.(-,⑶,⑸) 四元式： ⑴.(+,a,b,T1) ⑵.(-,a,b,T2) ⑶.(/,T1,T2,T3) ⑷.(*,b,c,T4) ⑸.(+,a,T4,T5) ⑹.(-,T3,T5,T6)

9题干】

什么是句子？什么是语言？ 【答案】

(1)设G是一个给定的文法，S是文法的开始符号，如果S→x(其中x∈VT*),则称x是文法的一个句子。(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S→x,x∈VT*}。 10型】简答题 【题干】

为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。 【答案】

w a b + c d e 10 - / + 8 + * + 11干】

现有文法G[S]： S?aAb

A?BcA|B B?idt|?

请问aidtcBcAb是句型还是句子，为什么？ 【答案】

S?aAb?aBcAb?aidtcAb?aidtcBcAb 是句型但不是句子。 12干】

构造正规式相应的NFA : 1(0|1)*101。 【答案】

1(0|1)* 101对应的NFA为

【题型】简答题

13干】

简述DFA与NFA有何区别？ 【答案】

DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。 14简答题 【题干】

试写出VT＝{0，1}上下述集合的正则表达式：集合：所有以1开始和结束的符号串。 【答案】 1(0|1)*1|1

15【题型】简答题 【题干】

现有文法G[S]： S?aAb A?BcA|B B?idt|?

请问ab是句型还是句子，为什么？ 【答案】

S ?aAb ?aBb ?a ?b=ab 是句型，是句子。 【题型】简答题 16干】

写一个文法，使其语言是奇数集，且每个奇数不以0开头。

【答案】 文法G(N)： N→AB|B A→AC|D

B→1|3|5|7|9 D→B|2|4|6|8 C→0|D

【题型】简答题 17干】

常见的存储分配策略有几种？它们都适合于什么性质的语言？ 【答案】

有三种分配存储空间的方式：

（1）静态分配：若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。适合静态管理的语言应具备条件：数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。

（2）栈式分配：适用于允许递归调用的程序设计语言；

（3）堆式分配：对于允许程序在运行时为变量 动态申请和释放存储空间的语言，采用堆式分配是最有效的解决方案。

18

何谓优化？按所涉及的程序范围可分为哪几级优化？ 【答案】

优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化。 19【题型】填空题 【题干】

扫描器的任务是从源程序中识别出一个个_______________。 【答案】 单词符号; 20型】填空题 【题干】

若源程序是用高级语言编写的，_______________是机器语言程序或汇编程序。 【答案】 目标程序;

【题型】填空题 21干】

若源程序是用高级语言编写的，则其翻译程序称为_______________。 【答案】 编译程序; 22干】

编译方式与解释方式的根本区别在于_______________。 【答案】

是否生成目标代码; 23

对编译程序而言，输入数据是_______________。 【答案】 源程序; 24干】

产生式是用于定义_______________的一种书写规则。 【答案】 语法成分; 25干】

对编译程序而言，输出结果是_______________。 【答案】 目标程序; 26【题干】

语法分析最常用的两类方法是自上而下和_______________分析法。 【答案】 自下而上; 27干】

语法分析器可以发现源程序中的 ____ 。 语法错误;