编译原理练习题库

编译原理练习题库一、填空题1.若源程序是用高级语言编写的，目标程序是______，则其翻译程序称为编译程序。

2.词法分析和语法分析本质上都是对源程序的______进行分析。

3.如果源语言(编写源程序的语言)是高级语言，而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为_____。

4.对编译程序而言，输入数据是_______,输出结果是________。

5. ______，是构成语言文法的单词，是语法成分的最小单位。

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

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

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

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

10.凡是具有某种特殊性质的客体的聚合，都可称为______。

11.如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为_______，记为φ。

12.例设 P={（1，2），（3，4），（2，2）}Q={（4，7），（2，9），（3，1）}则P·Q=____________________________13.符号串与符号组成顺序______，如符号串ab______ba，符号申001也______010。

14.假设G是一个文法，S是文法的开始符号，如果S=>*x,则称x是________。

15. 文法G产生的_______的全体是该文法描述的语言。

答案：1.机器语言程序或汇编程序2.结构3.编译程序4.源程序，目标程序。

5.终结符6.编译解释执行系统7.终结符和非终结符串8.无关9.无穷的句子集10.集合11.空集12.{（1，9），（3，7），（2，5）} 13.有关,不同于,不同于14.句型15.句子二、选择题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.正规文法_______二义性的。

a.可以是b.一定不是c.一定是8.设有文法G[S]：S::=S*S|S+S|(S)|a该文法_______二义性文法。

a.是b.不是c.无法判断9. 编译过程中扫描器的任务包括______。

①组织源程序的输入②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出⑧删除注解④删除空格及无用字符⑤行计数、列计数⑥发现并定位词法错误⑦建立符号表a．②③④⑦ b．②③④⑥⑦ c．①②③④⑥⑦ d．①②③④⑤⑥⑦10、编译过程中，语法分析器的任务是______ 。

A.分析单词是怎样构成的B.分析单词串是如何构成语句和说明的C.分析语句和说明是如何构成程序的D.分析程序的结构a.BCb.D c．BCD d．ABCD11、下列文法G[S]的句型aR／aSb／aTb／,b 的最左素短语为______。

S->aTb|，T->RR->R／S|Sa.aTbb.aSbc.Sd.R／e. ,12. 一个正规语言只能对应( )？A 一个正规文法；B 一个最小有限状态自动机；C.一个下推自动机D.一个确定的有限自动机13．文法G[A]：A→ε A→aB B→Ab B→a是( )：A 正规文法B 二型文法C.上下无关文法D. 不确定14．下面说法正确的是( )：A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法15．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( )：A 必要条件B 充分必要条件C.充分条件16、一个右线性文法G一定是（）A．LL（1）文法 C．SLR（1）文法B．LR（1）文法 D．上述三者都不是17、设A、B为任意两个集合，由所有属于集合A或属于集合B的元素组成的集合，叫做集合A与B 的_______．a.空集b. 全集c. 并集d. 交集18、在集合X上的关系R，如果合(x，y) ∈R，便必有(y，x) ∈R，则称关系R是________。

a.自反的b.对称的c.传递的d.正向的19、在状态转换图中，结点代表____，用圆圈表示。

a.输入缓冲区b.向前搜索c.状态d.字符串20、正则式的“*”读作______。

a，并且 L或者 c．连接 d．闭包21、______是编译过程的核心部分a. 语法结构b. 语法分析c. 源程序d. 单词符号22、高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____ 分析方法。

可选项有；a. 自左至右 b．自顶向下 c．自底向上 d．自右向左23、算符优先分析法每次都是对______进行归约，简单优先分析法每次都是对句柄进行归约。

a．最左短语 b.简单短语 c. 最左素短浯 d．素短语答案：1.b 2.a. 3.b 4.b 5.b 6.b 7.c 7.a 8.a 9.d 10. c 11.b 12B 13B 14 A 15A 16.A 17.c 18.b 19.c 20d 21b 22b 23d三、综合题1.“含有优化部分的编译程序的执行效率高”，这种说法正确吗？2.有人认为编译程序的五个组成部分却一不可，这种看法正确吗？3.PL／0编译程序对语法错误的处理采用哪两种办法?4. 设文法G(S)：S→(L)|a S|aL→L，S|S(1) 消除左递归和回溯；(2) 计算每个非终结符的FIRST和FOLLOW；5.设有文法G：s::=Qc|cQ::=Rb|bR::=Sa|a试求HARD(S),HARD(Q),HARD(R).6.优先函数与优先关系矩阵各有什么优缺点？7. 文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？8、给定PASCAL程序语句while a>b do if a>0 then a:=a-1 else a:=a+1;1. 将该语句翻译成逆波兰式；2. 给出编译程序扫描到then处及分号处时所得的四元式序列。

9.如何计算FIRST集？答案：1.答：含有优化功能的编译程序，其优化是指对生成的目标代码进行优化，而不是编译程序本身得到优化，它提高目标代码的效率，而不是编译程序的效率。

所以，上述说法不对。

2.答：不正确。

编译程序的五个组成部分中，词法分析，语法分析，语义分析和代码生成是必须完成的，而代码优化是为了提高目标程序的质量，它不是必需的，没有优化部分的编译程序也能生成目标代码。

3. (1)对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。

校正的方式就是补上逗号或分号。

(2)对某些错误，编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。

这样就需跳过一些后面输入的单词符号，直到读入一个。

4解： (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’〕＝{ )}HARD(Q)={S,Q,R,a,b,c}HARD(R)={S,Q,R,a,b,c}6.(1)优先函数可以节省存储空间，但不能真实反映符号间的优先关系。

利用优先函数进行语法分析时，有时不能及时发现错误，延长了分析步骤。

(2)优先关系矩阵能真实反映符号间的优先关系，但不象优先函数那样可以节省存储空间7. G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D......D8.9. 根据定义计算由FIRST集定义 FIRST (α)={a|α=>aβ， a∈，α，β∈V}若α=>ε, 则规定ε∈FIRST(α)。

①对每一文法符号X∈V，计算FIRST(X)(a) 若X∈，则FIRST(X)={X}(b) 若X∈，且有产生式X→a…，a∈，则a∈FIRST(X)(c) 若X∈，且有产生式X→ε，则ε∈FIRST(X)(d) 若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集合不再增大为止。