西交11春《编译原理》考前模拟题 （免费）

久爱奥鹏晓林

西交《编译原理》考前模拟题
一、 选择题
1. 描述一个语言的文法是（B ）
A.唯一的 B.不唯一的 C.可能唯一，也可能不唯一
2. 若文法G定义的语言是无限集，则文法必然是（D ）
A.前后文无关文法 B.正规文法 C.二义性文法 D.递归文法
3. 数组的内情向量中肯定不含数组的（B ）信息
A.维数 B.类型 C.各维的上下界 D.各维的界差
4. 简单优先分析每次归约的是（C ）
A. 最左直接短语 B.直接短语 C.最左素短语 D.控制结点
5. 最适合动态建立数据实体的内存分配方式是（B ）
A. 栈式分配 B.堆式分配 C.编译时预先分配 D.以上三种均可
6. 文法 G 产生的 ( D )的全体是该文法描述的语言。
A ．句型 B. 终结符集 C. 非终结符集 D. 句子
7．若文法 G 定义的语言是无限集，则文法必然是 ( A ) ：
A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的
8． Chomsky 定义的四种形式语言文法中， 0 型文法又称为 （ A ）文法； 1 型文法又称为 （ C ） 文法； 2 型语言可由 （ G ） 识别。
A ．短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法
E 图灵机 F 有限自动机 G 下推自动机
9．一个文法所描述的语言是 （ A ） ；描述一个语言的文法是 （ B ） 。
A ．唯一的 B 不唯一的 C 可能唯一，好可能不唯一
10． 数组的内情向量中肯定不含有数组的 （ A ） 的信息
A．维数 B.类型 C.维上下界 D.各维的界差
11．在下述的编译方法中，自底向上的方法有 （ F ） ，自顶向下的分析方法有 （ A ） 。
①简单优先分析 ②算符优先分析 ③递归下降分析 ④预测分析技术 ⑤LR（K）分析
⑥ SLR（k）分析 ⑦ LL（k）分析 ⑧LALR（K）分析
A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦
E.①②⑤⑥⑦ F. ①②⑤⑥⑧
12. 下推自动机识别的语言是（ C ）
A.0型语言                 B. 1型语言
C. 2型语言                C. 3型语言
13. 常见的中间代码形式不含（  D ）
A.三元式                        B.四元式
C.逆波兰式                        D.语法树
14. 语言是（ A ）的集合
A.句子                        B.产生式
C.符号串                D.句型
15. 扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即（  B ）
A.字符                B.单词                C.句子                D.句型
16. 代码优化的目的是（  C ）
A.节省时间                        B.节省空间
C.节省时间和空间        D.把编译程序进行等价交换
代码生成阶段的主要任务是（  C ）
A.把高级语言翻译成汇编语言
B.把高级语言翻译成机器语言
C.把中间代码变换成依赖具体机器的目标代码
D.把汇编语言翻译成机器语言

二、判断正误
1、算符优先关系表不一定存在对应的优先函数。 √
2、数组元素的地址计算与数组的存储方式有关。√
3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。√
4、每个文法都能改写为LL(1)文法。×
5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。×
三、填空题
1、从功能上说，程序语言的语句大体可分为_______语句和______语句两大类。
(执行性、 说明性)
2、扫描器的任务是从________中识别出一个个_______。 (源程序、 单词符号)
4、语法分析最常用的两类方法是________和_________分析法。(自上而下、 自下而上)
5、一个上下文无关文法所含四个组成部分是_______________。 (一组终结符号，一组非终结符号、一个开始符号、一组产生式)
6、所谓语法制导翻译方法是_____________________。 (为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序)

四、简答题
1、什么是 遍 (指编译程序对源程序或中间代码程序从头到尾扫描一次)
2、什么是语法分析 （按文法的产生式识别输入的符号串是否为一个句子的分析过程）
3、什么是后缀式 （一种把运算量写在前面，把算符写在后面的表示表达式的方法）
4、编译程序与解释程序有何区别？
答：二者的工作方法不同，后者是边解释边执行，解释所得的代码并不保存；前者是先将高级语言翻译感情上标代码，将其保存到指定的空间中，待需要时再执行 之，甚至可以在案一个机器上编译，而在另一台机器上执行。
5、何谓素短语？
答：素短语是满足下述条件的短语：（1）它至少含有一个终结符号（2）满足条件（1）的“最小”短语
6、过程调用时，主调程序与被调程序之间的信息传递有哪些方式？
答：形式参数与实在参数结合方式传递（简称参数传递）、返回值传递、共享数据区传递。
7、 何谓语法制导翻译？
答：语法制导翻译是对前后文无关文法的扩充，即对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推 导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序，完成相应的语义分析和翻译工作。
8、何谓算符文法？
答：当一个文法的所有产生式的右部均不出现两个非终结符号相邻的情况时，该就被称为算符文法。
9、常见的存储分配策略有几种？它们都适合于什么性质的语言？
有三种分配存储空间的方式：（ 1 ） 静态分配 若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。 适合 静态管理 的语言应具备条件： 数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。 （ 2） 栈式分配 适用于允许递归调用的程序设计语言 ；（ 3 ） 堆式分配 对于允许程序在运行时为变量 动态申请和释放存储空间 的语言 ， 采用 堆式分配 是最有效的解决方案 。
10、常见循环优化都有哪些项目？
不变运算外提；运算强度削弱；消除归纳变量；下标变量地址计算优化。
11、什么是活动记录？它主要由哪些内容构成？
一个过程的一次执行所需信息的管理，是通过称为 活动记录 的连续存储块来实现的。活动记录的主要内容有：（ 1） 临时变量域 存放目标程序临时变量的值；（ 2 ）局部数据域 存放过程本次执行时的局部数据、简单变量及数组内情向量等；（ 3 ）机器状态域 保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；（ 4 ）存取链 为访问其它活动记录中所存放的非局部数据所提供的链地址；（ 5 ）控制链 指向主调过程的活动记录；（ 6 ）实参 存放主调过程为被调用过程所提供的实参信息；（ 6 ）返回值 为主调过程存放被调过程的返回值
12、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？
答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。
　　　　应着重考虑的问题：
　　　　(1)如何使生成的目标代码较短；
　　　　(2)如何充分利用寄存器，以减少访问内存次数；
　　 　 (3)如何充分利用指仅系统的的特点。　　　　
13、何谓二义性文法？试举一例说明。
答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。
        例子：给定文法G[<R>]：
<R>→<R>*|<R><R>|a|b
考察句子ab*，它有两棵不同的推导树，如下所示：

14、在一个基本块内通常可实现哪些优化？
答：①合并已知量
②删除公共子表达式
③删除无用代码
④复写传播
15、设G=（VN，VT，P，<S>）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？
答：一般形式为<v>→&#61537;，<v>&#61646;VN，&#61537;&#61646;(VN∪VT)*。
        若G是正则文法，则一般形式为<A>→a<B>或<A>→a，<A>、<B>&#61646;VN，a&#61646;VT（或<A>→<B>a，<A>→a）。

五、综合题
1、考虑下面程序
　　 Var a：integer；
　　 Procedure S(X)；
　　　 Var X：integer；
　　　 Begin
　　　　 a：＝a＋1；
　　　　 X：＝a＋X
　　　 End；
　　 Begin
　　　　 a：＝5；
　　　　 S(a)；
　　　　 Print(a)
　　 End．
试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？
答：传名：a＝12　　
　　 传值：a＝6
2、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。
答：逆波兰表示：
　　　　　abc*＋ab＋/d－　
　　　 三元式序列：
　　　　　 ① (*，b，c)
　　　　　 ② (＋，a，①)
　　　　　 ③ (＋，a，b)
　　　　　 ④ (/，②，③)
　　　　　 ⑤ (－，④，d)
3、已知文法G(S)
　　 S→a|∧|(T)
　　 T→T，S|S
　　 写出句子((a，a)，a)的规范归约过程及每一步的句柄。
答： 句型　　　　　归约规则　　　　　句柄
　　　((a，a)，a)　　S→a　　　　　　　a
　　　((S，a)，a)　　T→S　　　　　　　S
　　　((T，a)，a)　　S→a　　　　　　　a
　　　((T，S)，a)　　T→T，S　　　　　 T，S
　　　((S)，a)　　　 T→S　　　　　　　S
　　　((T)，a)　　　 S→S(T)　　　 　　(T)
　　　(S，a)　　　 　T→S　　　　　　　S
　　　(T，a)　　　 　S→a　　　　　　　a
　　　(T，S)　　　 　T→T，S　　　　　 T，S
　　　(T)　　　 　　 S→(T)　　　　　　(T)
　　 　S　　　　　　　　　　　　　　　　　　
4、设 L í {a,b,c}* 是满足下述条件的符号串构成的语言：
(1)若出现 a ，则其后至少紧跟两个 c ；
(2)若出现 b ，其后至少紧跟一个 c 。
试构造识别 L 的最小化的 DFA ，并给出描述 L 的正规表达式。
DFA 如图所示。相应的正规式为 (c|acc|bc)* 。

5、将下面的条件语句表示成四元式序列：
if a>b then x:=a+b*c else x:=b-a;
四元式：
(1) ( j>, a, b, (3))
(2) ( j, , , (7) )
(3) ( *, b, c, T1)
(4) ( +, a, T1, T2)
(5) ( :=, T2, , x)
(6) ( j, , , (9))
(7) ( -, b, a, T3)
(8) ( :=, T3, , x)
(9) ( … … )
6、写一个文法，使其语言是奇数集，且每个奇数不以0开头。
解：文法G(N)：
　　　　　 N→AB|B
　　　　　 A→AC|D
　　　　　 B→1|3|5|7|9
　　　　　 D→B|2|4|6|8
　　　　　 C→0|D　　　　
7、设文法G(S)：
　　 S→(L)|a S|a
　　 L→L，S|S
　　 (1)消除左递归和回溯；
　　 (2)计算每个非终结符的FIRST和FOLLOW；
解1)
　　　　　 S→(L)|aS'
　　　　　 S'→S|ε
　　　　　 L→SL'
　　　　　 L'→SL'|ε
　(2)
　　　　　　 FIRST)S)＝{(，a}　　　　FOLLOW(S)＝{#，，，)}
　　　　　　 FIRST(S')＝{，a,ε}　　FOLLOW(S')＝{#，，，)}
　　　　　　 FIRST(L)＝{(，a}　　　　FOLLOW(L)＝{ )}
　　　　　　 FIRST(L')＝{，，ε}　　FOLLOW(L'〕＝{ )}
8、While　a＞0 ∨b＜0　do
　　 Begin
　　　　 X：＝X＋1；
　　　　 if a＞0 then a：＝a－1
　　　　　　　　 else b：＝b＋1
　　 End；
　　 翻译成四元式序列。
解：
　　　(1) (j＞，a，0，5)
　　　(2) (j，－，－，3)
　　　(5) (＋，×，1，T1)
　　　(6) (：＝，T1，－，×)
　　　(7) (j≥，a，0，9)
　　　(8) (j，－，－，12)
　　　(9) (－，a，1，T2)
　　　(10) (：＝，T2，－，a)
　　　(11) (j，－，－，1)
　　　(12) (＋，b，1， T3)
　　　(13) (：＝，T3，－，b)
　　　(14) (j，－，－，1)
　　　(15)
9、已知文法G(E)
　　 E→T|E＋T
　　 T→F|T *F
　　 F→(E)|i
　　 (1)给出句型(T *F＋i)的最右推导及画出语法树；
　　 (2)给出句型(T *F＋i)的短语、素短语。
解：(1) 最右推导：
　　　　　　　 ETF(E)(E＋T)(E＋F)(E＋i)
　　　　　 　 (T＋i)(T*F＋i)
(2) 短语：(T*F＋i)，T*F＋i，T*F，i　
　 素短语：T*F,i 　

久爱奥鹏网;www.92open.com