《编译原理》练习题库参考答案

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

一、填空

1.若源程序是用高级语言编写的，目标程序是______，则其翻译程序称为编译程序。 2.词法分析和语法分析本质上都是对源程序的______进行分析。 3.如果源语言(编写源程序的语言)是高级语言，而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为_____。

4.对编译程序而言，输入数据是_______,输出结果是________。 5. ______，是构成语言文法的单词，是语法成分的最小单位。

6.由PL／0的EBNF可知，PL／0语言可看成是PASCAL语言的子集，它的编译程序是一个__________。

7.由于PL／0编译程序采用_________，所以语法分析过程BLOCK是整个编译过程的核心。 8.用语法图描述语法规则的优点是______、________。

9.每个非终结符是一个语法成分，在书写语言程序时并不出现，它是由_________和_________、或终结符串定义的。

10.PL／0的目标程序为假想栈式计算机的汇编语言，与具体计算机______。

11.PL／0的编译程序和目标程序的解释执行程序都是用_______书写的，因此PL／0语言可在配备_________的任何机器上实现。

12.PL／0编译程序是用PASCAL语言书写的，整个编译程序(包括主程序)是由______个嵌套及并列的过程或函数组成

13.当源程序编译正确时，PL／0编译程序自动调用__________，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。

14.由于对某些非终结符可以递归定义，这就使得_________可用有穷的文法描述。

15. ______的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。

16. PL／0编译程序的语法分析采用了____________。

17.语法分析程序除总控外主要有两大部分的功能，即_________和__________. 18.PL／0的词法分析程序GETSYM，是一个独立的过程，其功能是为_________提供单词用的， 是______的基础，它把输入的字符串形式的源程序分割成一个个单词符号。 19.每个过程应有过程首部以定义局部于它自己过程的常量、变量和过程标识符，也称_____。 20.词法分析程序GETSYM将完成的任务有:______, 识别保留字；_______,拼数,拼复合词,输出源程序.

21.如果一个PL／0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到_________，这时就说所输入的程序是正确的。

22.若要构造程序设计语言的编译程序，则首先要对程序设计语言本身有较为精确的描述。而关于程序设计语言的描述，将涉及_____、语义和______三个方面。 23.凡是具有某种特殊性质的客体的聚合，都可称为______。 24.如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为_______，记为φ。 25.设有集合A和B，如果A和B有相同的元素，则称这两个集合是_______.

26.设A、B为任意两个集合，由所有属于集合A或属于集合B的元素组成的集合，叫做集合A与B的_______．

27. 设A、B为任意两个集合，由所有用于集合A且属于集合B的元素组成的集合，称为集合A与B的_______.

28. 如果一个集合，它能包含我们所要考虑目标之内的所有元素，则称此集合为_____，记为E。

29.设A为一集合，由A的所有子集(包括空集及A本身)所组成的集合，称为A的______. 30. 由两个按一定次序排列的客体组成的序列，称为_____. 31. 设A和B为任意两个集合，若序偶的第一个成员是集合A的一个元素，第二个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的__________. 32.在集合X上的关系R，如对任意x∈X，均有(x，x) ∈R，则称关系R是______。

33.在集合X上的关系R，如果合(x，y) ∈R，便必有(y，x) ∈R，则称关系R是________。 34.在集合X上的关系R，如果合(x，y) ∈R且(y，z) ∈R，必有(x，z) ∈R，则称关系R是______。

35.例 设 P={（1，2），（3，4），（2，2）} Q={（4，7），（2，9），（3，1）} 则P·Q=____________________________

36.符号串与符号组成顺序______，如符号串ab______ba，符号申001也______010。 37.假设G是一个文法，S是文法的开始符号，如果S=>*x,则称x是________。 38. 文法G产生的_______的全体是该文法描述的语言。 39.一个文法G[Z]若存在推导序列Z=>+···Z···,

则称G(z)是______文法，这类文法所产生的句子有______个。 40.乔姆斯基把文法分成____类型.

41.四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是_______. 42.最右推导常被称为________。

43.由规范推导所得的句型称为______。

44.文法的二义性和语言的二义性是两个_________的概念。 45.对于上下文无关文法，_______是句型推导过程的几何表示。 46.直接短语也称_______.

47.每棵语法树的叶子组成一个______. 48.每棵子树的叶子组成一个______.

49. 每棵简单子树的叶子组成一个_______. 50. 最左边简单子树的叶子组成_______.

51.一个句型的最左直接短语称为该句型的_______。 52.关于句型或句子的直接推导\和推导\，实际上均可视为符号串之间关系，而且推导\为直接推导\的_________。

53. ________是语言文法的等价表示，可用它来代替BNF规则集合。

54.某条规则U→u中的左部符号U(U不是识别符号)，不在所属文法的任何其他规则右部出现，那么这条规则在推导中不起作用，即所有句子的推导始终不会用到此规则，显然这种规则是多余的。也称这种非终结符为_________.

55.从文法的某个非终结符号U推不出终结符号串，显然，所有含有U的规则是多余的。也称这种非终结符为________。

56.若L是上下文有关语言、上下文无关语言或正规语言，则L∪{ε}和L - {ε}分别是上下文有关语言、_____和正规语言。

57.设有文法G，对于其中某一非终结符号U可能作出一些不同推导U =>+ Sx，其中S叫头符号，由于推导不同，由U产生的头符号S也可能不同，这些头符号S构成的集合，称为U的推导的__________.

58.一个上下文无关文法G包括四个组成部分依次是：_____,______,_______,_______.11 59.文法所描述的语言是_______的集合。

60.词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称________。

二、选择

1.编译程序是一种常用的_________软件。 A.应用 B.系统 C.工具 D.测试 2.在使用高级语言编程时，首先可通过编译程序发现源程序的全部______错误和部分______错误。

A.语法 B.语义 C.语用 D.运行

3.编译程序生成的目标程序_____是机器语言的程序。

A.一定 B.不一定 C.某种情况下一定 D.某种情况下不一定 4.编译程序生成的目标程序_______是可执行的程序。

A.一定 B.不一定 C.某种情况下一定 D.某种情况下不一定 5.一个语言的文法是_____.

A．惟一的 B．不惟一的 C.个数有限的 D.无限的 6.巴科斯-诺尔范式(即BNF)是一种广泛采用的_____的工具。 A．描述规则 B.描述语言 C．描述文法 D．描述句子 7. 设r=(a|b|c)(x|y|z)则L（r）中元素为 个（ ） A．9 B．6 C．18 D．27

8、正则集合L={an|n≧0}相应的正则表达式是（ ） A．a* B．a+ C．aa* D．aa+

9. 编译过程中扫描器的任务包括______。 ①组织源程序的输入

②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出 ⑧删除注解

④删除空格及无用字符 ⑤行计数、列计数 ⑥发现并定位词法错误 ⑦建立符号表

A．②③④⑦ B．②③④⑥⑦ C．①②③④⑥⑦ D．①②③④⑤⑥⑦ 10、编译过程中，语法分析器的任务是______ 。 a.分析单词是怎样构成的

b.分析单词串是如何构成语句和说明的 c.分析语句和说明是如何构成程序的 d.分析程序的结构

A.bc Bd C．bcd D．abcd 11、语法分析的常用方法是________ 。

a.自顶向下 b.自底向上 c.自左向右 d.自右向左 A．abcd B．ab C．cd D．abc

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

A．表达式 B．产生式 C．单词 D．语句 13、LL(1)文法的条件是_______。

A．对形如U->Xl|X2|?|Xn的规则，要求FIRST(Xi)∩FIRST(Xj)=Φ，(i≠j)

B．对形如U->Xl|X2|?|Xn的规则，若Xi=>*ε，则要求FIRST(Xj)∩FOLLOW(U) =Φ C．A和B D．都不是

14、一个右线性文法G一定是 （ ）

A．LL（1）文法 C．SLR（1）文法 B．LR（1）文法 D．上述三者都不是 15、算符文法是指______的文法。26

①没有形如U->?VW?的规则(U，V，W∈VN)

②终结符号集VT中任意两个符号对之间至多有一种优先关系成立 ⑧没有相同的规则右部 ④没有形如U->ε的规则

A.① B．①② C．①②③ D．①②③④ 16、算符优先文法是指______的文法。

①没有形如U->?VW?的规则(U，V，W∈VN)

②终结符号集VT中任意两个符号对之间至多有一种优先关系成立 ⑧没有相同的规则右部 ④没有形如U->ε的规则

A. ①② B．①②③ C. ①②③④ D．①②④ 17、下列文法G[S]的句型aR／aSb／aTb／,b 的最左素短语 为______。 S->aTb|， T->R

R->R／S|S

A.aTb B.aSb C.S D.R／ 18、算符优先分析法每次都是对______进行归约，简单优先分析法每次都是对句柄进行归约。 A．最左短语 B.简单短语 C. 最左素短浯 D．素短语 19、xab + cde -*f/:=是赋值语句( ) 相应的后缀式 A．x:=a+b+c*d-e/f B．x:=a+(b+c)*d-e/f C．x:+a+b+c*(d-e)/f D．x:=a+b+c+(c*d)-e/f 20、LR(K)方法是______。

A．从左到右分析，每次走K步的一种编译方法 B．从左到右分析，共经过K步的一种编译方法

C．从左到右分析，每次向前预测K步的一种编译方法

D．从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法 21、下面三个文法中，为SLR(1)文法的是______。10 G1：P->PaP|b

G2：P->bPb|cPc|b|c G3：P->bPb|bPc|d

A.仅Gl B．仅G2 C．仅G3 D．G2和G3 22、有下列文法：11 S->Pa|Pb|c P->Pd|Se|f

该文法是______。

A.LL(1)文法 B.SLR(1)文法

C.a和b D.都不是

23．代码优化的主要目标是( )12 ① 如何提高目标程序的运行速度 ② 如何减少目标程序运行所需的空间 ③ 如何协调①和②

④ 如何使生成的目标代码尽可能短

A ①② B ①②③ C ①②④ D ①②③④ 24、设文法G（S为其开始符号）产生式如下：

S→aSb|ab|ε 则G是一个（ ）

A．LR（1）文法 B．SLR（1）文法 C．三型文法 D．二型文法

25 在编译程序采用的优化方法中，_____ 是在循环语句范围内进行的。12 ①合并已知常量 ②删除多余运算， ③删除归纳变量 ④强度削弱 ⑤代码外提

A ①④ B ①⑤ C ①④⑤ D ③④⑤ 26 合并表达式中常量运算的目的是_____。12 ①合并常量，使表达式中的常量尽可能少 ②合并常量，使表达式尽可能简短

③将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所有这种常量运算，使得生成的代码指令尽可能少 A ① B ② C ③ D ①②③

27 下面的程序段可以进行哪些优化_____。12 i：= 1 j：= l0 read k L：x：= x*i y：= j*i z：= x*y write j i：= i+1

if i<100 goto L halt

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

A．①④ B①⑤ C，①④⑤ D．③④⑤ 28. 属于低级语言的是（ ）

A Fortran B.Pascal C.Lisp D Masm

29.设oct是字母表{0，1，…，7}中的任何一个元素，表示C语言的八进制无符号整规表达式是（ ）。

A.(oct)8 B.(oct)* C.(oct)+ D.(oct)#

30.采用（ ）实现三地址代码时，不利于对中间代码进行优化。

56.上下文无关语言 57.头符号集合

58.终结符号，非终结符号，开始符号，产生式 59.由文法的识别符推出的所有终结符号串 60.输入缓冲区

二、选择

1.B 2.A 3.B 4.B 5.B 6.B 7.B 8.A 9.D 10.C 11.B 12.C 13.C 14.A 15.A 16.D 17.B 18. D 19.A 20.D 21.C 22.B 23.B 24.D 25.D 26.D 27.C 28.D 29.D 30.C 31.B 32.B 33.A 34.A 35.A 36.C 37.B 38.A 39.B 40.A

三、简答题

1.答：含有优化功能的编译程序，其优化是指对生成的目标代码进行优化，而不是编译程序本身得到优化，它提高目标代码的效率，而不是编译程序的效率。所以，上述说法不对。 2.答：不正确。编译程序的五个组成部分中，词法分析，语法分析，语义分析和代码生成是必须完成的，而代码优化是为了提高目标程序的质量，它不是必需的，没有优化部分的编译程序也能生成目标代码。

3.指令寄存器,程序地址寄存器,栈顶寄存器,基址寄存器

4. (1)对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。

(2)对某些错误，编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。

5. LIT：将常量值取到运行栈顶。LOD：将变量放到栈顶。STO：将栈顶的内容送入某变量单元中。CAL：调用过程的指令。INT：为被调用的过程(或主程序)在运行栈中开辟数据区。JMP：无条件转移指令。JPC：条件转移指令。OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指令 6. 句型 归约规则 句柄

((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 7. 优化：对程序进行各种等价变换，使得从变换后的程序出 发，能产生更有效的目标代码。

三种级别：局部优化、循环优化、全局优化。 8. 目标代码通常采用三种形式：机器语言，汇编语言，待装配 机器语言模块。 应着重考虑的问题：

(1)如何使生成的目标代码较短；

(2)如何充分利用寄存器，以减少访问内存次数； (3)如何充分利用指仅系统的的特点。 9. 逆波兰表示：

abc*＋ab＋/d－ 三元式序列： ① (*，b，c)

② (＋，a，①) ③ (＋，a，b) ④ (/，②，③) ⑤ (－，④，d)

10. 文法G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D

11 编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。

12 自反的 在集合X上的关系R，如对任意x∈X，均有(x，x) ∈R，则称关系R是自反的。

非自反的 在集合X上的关系R，如对任意x∈X，均有(x，x)R，则称关系R是非自反。

对称的 在集合X上的关系R，如果合(x，y) ∈R，便必有(y，x) ∈R，则称关系R是对 称的。

非对称的 在集合X上的关系R，如果有(x，y) ∈R丛x≠y，便必有(y，x)R，则称关系R是非对称的。

传递的 在集合X上的关系R，如果合(x，y) ∈R且(y，z) ∈R，必有(x，z) ∈R，则称关系R是传递的。

13. 元素的非空有穷集合。字母表中的元素。由字母表中的符号组成的任何有穷序列，惯用小写字母t、u、v、x、y…表示符号串。长度是符号串所含符号的个数。设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的联结，记为xy。 14答：从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。 15 HARD(S)={S,Q,R,a,b,c}

HARD(Q)={S,Q,R,a,b,c} HARD(R)={S,Q,R,a,b,c} 16 S::=aABb|ab A::={ab}

B::=Aa|a

17传名：a＝12 传值：a＝6 18. (1)错误 (2)正确 (3)正确 (4)正确 (5)错误 (6)错误 (7)错误

19.(1)在语义上加些限制，或者说加一些语法的非形式规定。这样做不必改变文法中原有的语法规则。

(2)把排除二义性的规则合并到原有文法中，即构造一个等价的无二义性的文法G'。这样做，需要改造原有文法。

20.只有单层分支的子树称为简单子树。

21.由某一结点及其所有分支组成的部分，成为原语法树的一棵子树。

22.句型的分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。

23.从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。 24. HARD(S)={S,Q,R,a,b,c} HARD(Q)={S,Q,R,a,b,c} HARD(R)={S,Q,R,a,b,c}

四、综合题

每题10分，3题共30分 1. 解：

(1) (j＞，a，0，5) (2) (j，－，－，3) (3) (j＜，b，0，5＝ (4) (j，－，－，15) (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)

2. 解：(1) E0→E(1)

E→E0E(2) EA→E(1) E→EAE(2)

E→i (2) E→E(1)

{BACKPATCH(E(1)·FC，NXQ)； E0·TC：＝E(1)·TC} E→E0E(2) {E·FC：＝E(2)·FC； E·TC：＝MERG(E0·TC，E(2)·TC)} EA→E(1)

{BACKPATCH(E(1)·TC，NXQ)； E0·FC：＝E(1)·FC} E→EAE(2) {E·TC：＝E(2)·TC； E·FC：＝MERG(EA·FC，E(2)·FC) E→i {E·TC：＝NXQ；E·FC：＝NXQ＋1； GEN(jn2，entry(i)，－0)； GEN(j，－，－，0)

3解： (1)

S→(L)|aS’ S’→S|ε L→SL’

L’→SL’|ε

(2)

FIRST)S)＝{(，a} FIRST(S’)＝{，a,ε} FIRST(L)＝{(，a} FIRST(L’)＝{，，ε} (3)

FOLLOW(S)＝{#，，，)} FOLLOW(S’)＝{#，，，)} FOLLOW(L)＝{ )} FOLLOW(L’〕＝{ )}

a ， ( ) ＃

S S’ L L’ S→aS’ S→(L) S’→S S’→ε S’→S S’→ε S’→ε L→SL’ L→SL’ L’→ε L’→ε 4.(1) 文法G中每个非终结符的FIRSTVT集和LASTVT集为： FIRSTVT(s')={#} FIRSTVT(P)={i,() FIRSTVT(s)={(,i) FIRSTVT(D)={i} FIRSTVT(R)={;,(,i)

(2) 文法G中每个非终结符的LASTVT集为： LASTVT(S')={#} LASTVT(P)={i,}} LASTVT(S)={}} LASTVT(D)={i} LASTVT(R)={;,},i}

5. t11 := i * 20

t12 := t11+j t13 := A-84; t14 := 4*t12

t15 := t13[t14] //A[i,j] t21 := i*20 t22 := t21+j t23 := B-84; t24 := 4*t22

t25 := t23[t24] //B[i,j] t31 := k*20 t32 := t31+l t33 := A-84 t34 := 4*t32

t35 := t33[t34] //A[k,l] t36 := 4*t35 t37 := C-4

t38 := t37[t36] //C[A[k,l]] t41 := i+j

t42 := 4*t41 t43 := D-4

t44 := t43[t42] //D[i+j] t1 := t25 +t38 t2 := t1 + t44 t23[t24] := t2

6. 解：(1) E0→E(1) E→E0E(2) EA→E(1) E→EAE(2)

E→i (2) E→E(1)

{BACKPATCH(E(1)·FC，NXQ)； E0·TC：＝E(1)·TC} E→E0E(2)

{E·FC：＝E(2)·FC；

E·TC：＝MERG(E0·TC，E(2)·TC)} EA→E(1)

{BACKPATCH(E(1)·TC，NXQ)； E0·FC：＝E(1)·FC} E→EAE(2)

{E·TC：＝E(2)·TC；

E·FC：＝MERG(EA·FC，E(2)·FC} E→i

{E·TC：＝NXQ；E·FC：＝NXQ＋1； GEN(jn2，entry(i)，－0)； GEN(j，－，－，0) 7.

8. 根据定义计算

由FIRST集定义 FIRST (α)={a|α=>aβ， a∈若α=>ε, 则规定ε∈FIRST(α)。 ① 对每一文法符号X∈V，计算FIRST(X) (a) 若X∈(b) 若X∈(c) 若X∈(d) 若X∈

，则FIRST(X)={X} ，且有产生式X→a?，a∈

，则a∈FIRST(X)

， α， β∈V}

，且有产生式X→ε，则ε∈FIRST(X) ，Y1，Y2，?Yi∈

，而有产生式X→Y1Y2?Yn。当Y1Y2?Yi-1都=>

ε时，(其中1≤i≤n)，则FIRST(Y1)-{ε}，FIRST(Y2)-{ε}，? FIRST

)-{ε}，FIRST(Yi)都包含在FIRST(X)中。

(e) 当(d)中所有Yi=>ε(i=1，2，..n),则

FIRST(X)= FIRST(Y1)∪FIRST(Y2)∪?∪FIRST(Yn) ∪{ε} 反复使用(a)-(e)步，直到每个符号的FIRST集合不再增大为止

更多课程资料请到大学课程网www.0206.cc学习

本文来源：https://www.bwwdw.com/article/wcs7.html