编译原理试题

《编译原理试题》由会员分享，可在线阅读，更多相关《编译原理试题（14页珍藏版）》请在装配图网上搜索。

1、编译原理题库一、选择题：1. 编译原理是对（C）。A、机器语言的执彳丁 B、汇编语言的翻译C、高级语言的翻译 D、高级语言程序的解释执行2. 编译程序是将高级语言程序翻译成D。A、汇编语言程序B、机器语言程序C、 高级语言程序D、汇编语言或机器语言程序3. 文法：G： SxSx | y 所识别的语言是（D）。A、xnyxm B、（xyx）*C、x*yx* D、xnyxm （n$0）4. 设有文法GI：II0II1II allclalblc下列符号串中是该文法的句子的有B。 ab0 a0c01 aaa bc10可选项有A、B、C、D、5. 词法分析器的输出结果是（C）。A、单词自身值B、单词在符

2、号表中的位置C、单 词的种别编码D、单词的种别编码和自身值6. 为了使编译程序能够对程序设计语言进行正确的翻译，必须采用_C_方法定义程 序设计语言。A、非形式化B、自然语言描述问题C、形式化D、自然语言和符号 体系相结合7. 若文法G定义的语言是无限集，则文法必然是（C） A.前后文无关文法B.正规文 法C.二义性文法D.递归文法8. 描述一个语言的文法是B。A、唯一的B、不唯一的C、个数有限的9. 表达式（a+b） *c 的逆波兰表示为_C_A、ab+c*B、abc+* C、a*c+b*c 10、递归下降分析法和预测分析法要求描述语言的文法是_C_A、正规文法B、LR(1)文法C、LL (

3、1)文法D、右线性文法11编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过_A_这 几步编辑编译连接 运行A、B、C、D、12、符号表的查找一般可以使用_B_:顺序查找折半查找杂凑查找排序 查找可选项有：A、B、C、D、13、语法分析的常用方法是B：自顶向下自底向上 自左向右 自右向左 可 选项有：A、B、C、D、14、LR语法分析栈中存放的状态是识别文法规范句型_A_的DFA状态。A、前缀B、 活前缀C、项目D、句柄15、一个确定的有穷自动机DFA是一个A_A、五元组(K,E, f,S,Z)B、四 元组(V , V , P, S)N TC、四元组(K, f,S, Z)D、三元

4、组(V , V , P)N T16、设有文法GE:EE+T | TTT*F | FF (E) | a句型T+T*F+a的素短语是_A_A、a B、E+T C、TD、T+T*F17递归下降分析方法属于_B_A,自左至右B,自顶向下C,自底向上D,自右向左18、文法的二义性和语言的二义性是两个_A_概念。A、不同B、相同C、无法判断19、编译过程中，词法分析阶段的任务是_B_A、识别表达式B、识别语言单词C、 识别语句D、识别程序20、无符号常数的识别和评数工作，通常都在B_阶段完成。A、词法分析B、语法 分析C、语义分析D、目标代码生成21、编译程序中安排优化的目的是为了得至LC_的目标代码A、

5、结构清晰B、较短 C、高效率D、使用存储空间最小22、代码优化的主要目标是_B_。 如何提高目标程序的运行速度 如何减少目标程序运行所需的空间。 如何协调和 如何使生成的目标代码尽可能简短可选项有：A、 B、 C、 D、23、后缀式 iii-/ f 的中缀表达式是_A_A、i f (i/(i-i) B、(i-i)/i f iC、i f (i-i) /I D、 (i-i) f i/i24字母表中的元素可以是_D_A、字母B、字母和数字C、数字D、字母、数字和 其他符号25、编译过程中，比较常见的中间语言有_D_。 波兰表示 逆波兰表示 三元式 四元式 树形表示可选项有：A、B、C、 D、26、正

6、规式(a|b) (a | b | 0 | 1)*对应的文法为_C_A、SaA I bAB、SaA | bAAaA I 1A I AaA I bA I 0A I 1AC、SaA I bAD、SaA I bAAaA I bA I 0A I 1A I AA I bA I 0A I 1A I 27、 在规则产生式中，符号“I”表示_B_A、与B、或C、非D、引导开关参数28、循环优化是对_A_中的代码进行优化。A、循环 B、函数C、基本块D、整 个程序29、设有文法GI：II0II1II allclalb下列符号串中是该文法的句子的有_B_。ab0 a0c01 aaa cb10可选项有A、B、C、D、

7、30、为了使编译程序能够对程序设计语言进行正确的翻译，必须采用_C_方法定义 程序设计语言。A、非形式化B、自然语言描述问题C、形式化D、自然语言和符号体系相结合31、无符号常数的识别和评数工作，通常都在_B_阶段完成。A、词法分析 B、语法分析C、语义分析D、目标代码生成32、递归下降分析法和预测分析法要求描述语言的文法是_C_A、正规文法 B、LR(1 )文法 C、LL (1)文法 D、右线性文法33、表达式a* (-b+c)的逆波兰表示为_AA、abc+*B、abc+*C、a b* +ac34、文法的二义性和语言的二义性是两个_A_概念。A、不同B、相同C、无法判 断35、设有文法GE:

8、EE+T | TTT*F | FF (E) | a句型T+T*F+a的素短语是_A_A、T*F B、E+TC、TD、T+T*F36字母表中的元素可以是_D_A、字母B、字母和数字C、数字D、字母、数字和 其他符号37、编译过程中，比较常见的中间语言有_D_。 波兰表示 逆波兰表示 三元式 四元式 树形表示可选项有：A、B、 C、 D、38、正规式(a|b) (a | b | 0 | 1)*对应的文法为_CA、SaA I bAB、SaA I bAAaA I 1A I AaA I bA I 0A I 1AC、SaA I bAD、SaA I bAAaA I bA I 0A I 1A I AA I b

9、A I 0A I 1A I 39、在规则产生式中，符号“一”表示_D_A、恒等于B、等于C、取决于D、定义为40、关于短语与句柄，正确的论述是：BA、短语就是句柄B、直接短语才可能是句柄C、左短语一定是句柄D、最右短语一定是句柄二、判断题（对下列叙述中正确的说法，在题后括号内打“丁”错误的打“X”）1、 编译程序是一种常用的应用软件。（X ）2、 名字就是标识符，标识符就是名字。（X ）3、 编译程序与具体的语言无关。（V ）4、 C语言的编译程序可以用C语言来编写。（V ）5、 一个语言的文法是唯一的。（X ）2、数组元素的地址计算与数组的存储方式有关。（V ）6、无左递归的文法是LLC1

10、）文法。 （X ）7、 含有优化部分的编译程序的执彳丁效率咼。（X ）8、 若两个正规式所表示的正规集相同，则认为二者是等价的。（V ）9、算符优先关系表不一定存在对应的优先函数。（X ）10、仅考虑一个基本块，不能确定一个赋值是否真是无用的。（X ）11、每个文法都能改写为LL（ 1）文法。（X ）二、填空题1、编译程序的工作过程一般主要可以划分为词法分析语法分析语义分析中间 代码生成 中间代码优化 目标代码生成。_等几个基本阶段。2、语法分析的任务是：依据语言的语法规则，逐一地分析词法分析时得到的 单词符号_,以确定它们是怎样组成说明和语句的，以及说明和语句是怎样组成_语法的。如无语法错误

11、，则给出正确的语法单位。3、代码优化是对程序进行 等价变换,提高目标程序的质量。即：使目标代码运行时所需的时间尽可能短，所占用的存储空间尽可能少4、 Chomsky定义的四种形式语言文法分别为： 0型文法（又称为短语 文法）、 1型 文法（又称为上下文有关 文法）、2 型文法（又称为上下文无关文法）、3型文法（又称为正规（或正则）文法）。5、在代码优化阶段，优化的主要方法有：局部优化、循环优化、全局优化_。6、扫描器的任务是从源程序中识别出一个个单词符号_。7、 所谓最右推导是指：_任何一步a 0都是对a中最右非终结符进行替换的8、语法分析最常用的两类方法是自上而下_和_自下而上分析法。9、一

12、个上下文无关文法所含四个组成部分是一组终结符、一组非终结符、一个开 始符号、一组产生式10、所谓语法制导翻译方法是为每个产生式配上一个翻译子程序，并在语法分析 的同时执行这些子程序。11、符号表中的信息栏中登记了每个名字的有关的性质，她类型、种属、所占单元 大小、地址_等等。12、一个过程相应的DISPLAY表的内容为 现行的活动记录的地址和所有外出最新活 动的记录地址13、常用的两种动态存贮分配办法是兰式 动态分配和 堆式 动态分配。14、产生式是用于定义_语法范畴的一种书写规则。15、一般程序语言的语法单位有： 表达式、 语句、 分程序、和 函数、 过程、程序等等。16、语法分析器的任务是

13、在词法分析识别出单词符号串的基础上，分析并判定程 序的语法结构是否符合语法规则。17、若源语言用高级语言编写的，目标程序是等价的机器语言程序或汇编程序， 则其翻译程序称为编译程序18、高级语言经过编译生成的目标程序一般是_机器语言程序 或汇编语言程序19、一个高级语言的源程序在编写形成后到正式运行前，一般要经过编辑、编译、 连接这三个阶段20、假设G是一个文法，S是文法的开始符号，如果Sn*X，则称X是句型三、名词解释：（每题5分，共20分）1. 非终结符一出现在文法产生式的左部且能派生出符号或符号串的那些符号称为 非终结符号。2. 终结符一一出现在文法产生式的右部且不能派生出符号或符号串的那

14、些符号称 为终结符号。3. 语法制导翻译语法制导翻译就是在语法分析的过程中，当进行推导或归约 时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。4. 编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言 或汇编语言的目标程序5. 扫描遍一一指编译程序对源程序或中间代码程序从头到尾扫描一次。6. 自上而下分析法就是指从文法的开始符号出发，根据文法规则正向推导出给定 句子的一种方法。7. 句柄一一给定句型中的最左简单短语就是句柄8. 上下文无关文法一一若文法G= （VN, VT，P， S）中的每一条规则的形式为A卩，其中AeVN，卩u （VNUVT），则称其为

15、上下文无关文法9. 活前缀一一规范句型的一个前缀，这种前缀不含句柄之后的任何符号。或给定文法规范句型的可归前缀的任意首部。四、简答1、何谓二义性文法？试举例说明。答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义 性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。例子：给定文法GvR:vRf vR *| vRvR|a|b辛Ib考察句子ab *，它有两棵不同的推导树，如下所示：IIIIIIab2, 设G= (VN,VT,P,vs)是上下文无关文法，产生式集合P中任意一个产生式应具 有一个什么样的形式？若G是正规文法呢？答：一般形式为vVa ,WwVN,a e

16、(VNUVT)*若G是正则文法，则一般形式 为vAa ,vB或Aa ,vA,vB eVN,a eVT(或vAvBa,vAf a)3, 编译过程的5个阶段是什么？答：编译过程的5个阶段：词法分析，语法分析，语义分析及中间代码生成，代码 优化，目标代码生成。4, 常见的存储分配策略有几种？它们都适合于什么性质的语言？答：有三种分配存储空间的方式：（1）静态分配，若在编译阶段就能确定源程序中各个数据实体的存储空间大小， 则可以采用较简单的静态存储管理。适合静态管理的语言应具备条件：数组上下界 是常数过程调用不允许递归，不允许动态建立数据实体。（2）栈式分配：适用于允许递归调用的程序设计语言。（3）堆

17、式分配：对于允许程序在运行时为变量，动态申请和释放存储空间的语言, 采用堆式分配，是最有效的解决方案。5, 设有文法GE:E-E+T E-T| TT-T*F| T| F| FF-（E）| I试证明E+T*F是它的一个句型，指出这个句型的所有短语，直接短语 和句柄。答：因为E-E+T-E+T*F,所以E+T*F是文法GE的句型。短语：E+T*F,T*F,其中T*F是直接短语，也是句柄。6, 在一个基本块内通常可以实现哪些优化？答：（1）合并已知量（2）删除公共表达式（3）删除无用代码（4）复写传播（5） 循环优化7, 设有文法GAA BCc| gDBB-bCDE| eCDaB| caDdD| e

18、EgAf| c计算该文法的每一个非终结符的FIRST集和FOLLOW集。答：文法的每一个非终结符的FIRST集和FOLLOW集如下：FIRST(A)=FIRST(BCc) U FIRST(gDB)=FIRST(B) U FIRST(C) U c U g=b U FIRST(D) U a U c,g=a,b,c,d,gFIRST(B)=FIRST(bCDE)U =b止FIRST(C)=FIRST(DaB) U FIRST(ca)=FIRST(D)UaUc=a,c,dFIRST(D)=FIRST(dD)U =d止FIRST(E)=FIRST(gAf) U c=g,cFOLLOW(A)=f, $ F

19、OLLOW(B)=a,c,d,f,g,$FOLLOW(C)=c,d,gFOLLOW(D)=a,b,c,g,f, $ FOLLOW(E)=a,c,d,f,g, $ 8,什么是活动记录？它主要由哪些内容构成？答：一个过程的一次执行所需信息的管理是通过称为活动记录的连续存储块来实现的，活动记录的主要内容有：(1) 临时变量域存放目标程序临时变量的值。(2) 局部数据域存放过程本次执行时的局部数据，简单变量及数组内情向量等。(3) 机器状态域保存在调用过程前有关机器状态的信息，包括各寄存器的当前值 及返回地址等。(4 )存取链为访问其他活动记录中所有存放的非局部数据所提供的链地址。(5) 控制链指向主调过程的活动记录。(6) 实参存放主调过程为被调用过程所提供的实参信息。(7) 返回值为主调过程存放被调过程的返回值。