《编译原理》练习测试题库

5.解释说明指令LIT? LOD? STO? CAL? INT? JMP? JPC? OPR?5 6. 已知文法G(S) S→a|∧|(T) T→T，S|S

写出句子((a，a)，a)的规范归约过程及每一步的句柄。 7. 何谓优化？按所涉及的程序范围可分为哪几级优化？

8. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？ 9. 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。 10. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。 11.编译程序的结构是什么? 12. 关系有哪些基本性质？

13.解释字母表, 符号, 符号串,符号串的长度,符号串联结？ 14. 自下而上分析算法的基本思想是什么？ 15.设有文法G： s::=Qc|c Q::=Rb|b R::=Sa|a

试求HARD(S),HARD(Q),HARD(R).

16. 用扩充的BNF范式表示下述文法以消去ε规则： S::=aABb|ab A::=Aab|ε B::=Aa|a

17. 考虑下面程序 …………

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的值是什么？ 18.设有文法G[I]:8 I->I1/I0/Ia/Ic/a/b/c

判断下面符号串中哪些是该文法的句子. (1) ab0 (2)a0c01 (3)aaa (4)bc10

(5)aabc (6)bbca

19.为了正确地对源程序进行编译，不允许文法有二义性，那么怎样才能排除文法的二义性呢?9

20.什么是简单子树？ 21.什么是子树？

22.什么是句型的分析？

23.自下而上分析算法的基本思想是什么？ 24.设有文法G： s::=Qc|c Q::=Rb|b R::=Sa|a

试求HARD(S),HARD(Q),HARD(R). 25．编译程序和高级语言有什么区别? 26．编译程序的工作分为那几个阶段? 27．简述自下而上的分析方法。

28．简述代码优化的目的和意义。

六、综合题

1. While a＞0 ∨ b＜0 do Begin

X：＝X＋1；

if a＞0 then a：＝a－1 else b：＝b＋1 End；

翻译成四元式序列。 2. 设布尔表达式的文法为

(1)(2)

E → E∨E

(1)(2)

E → E∧ E E → i

假定它们将用于条件控制语句中，请

(1) 改写文法，使之适合进行语法制导翻译和实现回填； (2) 写出改写后的短个产生式的语义动作。 3. 设文法G(S)： S→(L)|a S|a L→L，S|S

(1) 消除左递归和回溯；

(2) 计算每个非终结符的FIRST和FOLLOW； 4. 对下列文法G: 26 S'->#S# S->D(R) R->R; P|p P->S|i

D->i

计算文法中每个非终结符的FIRSTVT集和LASTVT集 。

5. 将下列赋值语句译成三地址代码。 A[i,j] :=B[i,j] + C[A[k,l]] + D[i+j] 6、设布尔表达式的文法为

E →E(1)∨E(2)

E →E(1)∧E(2)

E →i

假定它们将用于条件控制语句中，请

(1)改写文法，使之适合进行语法制导翻译和实现回填；

(2)写出改写后的短个产生式的语义动作。 7、 （8分）给定PASCAL程序语句

while a>b do if a>0 then a:=a-1 else a:=a+1; 1. 将该语句翻译成逆波兰式；

2. 给出编译程序扫描到then处及分号处时所得的四元式序列。 8.如何计算FIRST集？ 9．证明下述文法G：

S?aSbS|aS|d

是二义性文法。 10．对于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短语、直接短语和句柄？ 句型baSb的语法树如图五(2)所示。

S

A B

b B S b

a 图五(2) 句型baSb的的语法树

11．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中：

? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和

状态转换图。

华中师范大学网络教育学院 《编译原理》练习测试题库参考答案

一、填空

1.机器语言程序或汇编程序 2.结构 3.编译程序

4.源程序，目标程序。 5.终结符

6.编译解释执行系统 7.一趟扫描方法 8.直观、易读

9.终结符和非终结符串 10.无关

11.PASCAL语言 12.18

13.解释执行程序 14.无穷的句子集 15.语法分析

16.自顶向下的递归子程序法

17.说明部分的处理,程序体部分的处理 18.语法分析,语法分析 19局部量

20滤空格,识别标识符,输出源程序 21程序结束符 22.语法,语用 23.集合 24.空集 25.相等的 26.并集 27.交集 28.全集 29.幂集 30.序偶

31.笛卡尔乘积 32.自反的 33.对称的 34.传递的 35.{（1，9），（3，7），（2，5）}