编译原理练习题

1、选择题1、汇编程序是将 a翻译成b，编译程序是将 c 翻译成d .a.汇编语言程序 b.机器语言程序c.高级语言程序d. a 或者 b e. a或者c f. b或者c2、下面关于解释程序的描述正确的是b .(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于 COBOL和FORTRAN语言(3) 解释程序是为打开编译程序技术的僵局而开发的a. (1)(2)b. (1)c. (1)(2)(3)d.(2)(3)3、高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少(1)e 和 (1)b . 其中，(1)e的目的是使最后阶段产生的目标代码更为高

2、效.与编译系统相比，解释系统d .解释程序处理语言时，大多数采用的是b方法.(4)a就是一种典型的解释型语言.(1)： a.优化中间代码生成b.目标代码生成C.词法分析 d.语法分析e.代码(2): a.b.比较简单，可移植性好，执行速度快比较复杂，可移植性好，执行速度快c.d.比较简单，可移植性差，执行速度慢 比较简单，可移植性好，执行速度慢(3)： a.源程序命令被逐个直接解释执行b.先将源程序转化为之间代码，再解释执行c.先将源程序解释转化为目标程序，在执行 d.以上方法都可以：a. BASIC b. C c. FORTRAN d. PASCAL4、用高级语言编写的程序经编译后产生的程序

3、叫b .用不同语言编写的程序产生_b 后，可用连接在一起生成机器可执行的程序.在机器中真正执行的是a.源程序b.目标程序c.函数d.过程e.机器指令代码f.模块h.程序库5、要在某一台机器上为某种语言构造一个编译程序g.连接程序，必须掌握下述三方面的内容 ：_cd_ C_a.汇编语言b.高级语言c.源语言d. 目标语言e.程序设计方法f.编译方法测试方法h.机器语言g.6、由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成(1)d，诸阶段的工作往往是(2)d 进行的.(1) a. 过程b.程序 c.批量d.遍a. 顺序7、编译过程中b.并行 c.成批d.穿插,语法分析器的任

4、务就是和说明的(3)分析语句和说明是如何构成程序的8、编写一个计算机高级语言的源程序后编译 (3)连接(1)编辑9、编译程序必须完成的工作有a(4)分析程序的结构,到正式上机运行之前，一般要经过_b_这几步.运行(1)词法分析(4)代码生成语法分析之间代码生成(3)语义分析代码优化a.b. (1)(2)(3)(4)(5)c. (1)(2)(3)(4)(5)(6)d. (1)(2)(3)(4)(6)e. (1)(2)(3)(5)(6)10、编译程序是一种A.汇编程序B.翻译程序C.解释程序D.目标程序11、按逻辑上划分,A.语义分析编译程序第二步工作是词法分析B.C.语法分析D.代码优化12、通

5、常一个编译程序中，不仅包含词法分析, 代码生成等五个部分，还应包括 A.模拟执行器B.解释器语法分析，中间代码生成,代码优化，目标13、文法G所描述的语言是CC.表格处理和出错处理D.符号执行器的集合。A. 文法G的字母表V中所有符号组成的符号串B. 文法G的字母表V的闭包V*中的所有符号串C.由文法的开始符号推出的所有终极符串D.由文法的开始符号推出的所有符号串14、乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、是 BA.短语文法B. 正则文法 C.上下文有关文法D.15、文法 GN= (b , N, B, N, N b| bB,A. L(GN)=b IB. L(GN)=b2i

6、+1C. L(GN)=b16、一个句型中的最左可选项有:A.短语 B.2型、3型。其中3型文法上下文无关文法Bt bN)，该文法所描述的语言是D. L(GN)=b称为该句型的句柄。2i+1简单短语C. 素短语D.17、设G是一个给定的文法，S是文法的开始符号, 的一个B_ O如果终结符号Qx(其中x V),则称x是文法GA.候选式 B. 句型 C.单词D.产生式18、一个上下文无关文法 G包括四个组成部分，它们是：一组非终结符号，一组终结符号, 一个开始符号，以及一组D OA.句子 B. 句型 C.单词D.产生式19、文法GE:该文法句型 ( E+ T)可选项有：a 1( E)E+ F * (

7、E + T)的简单短语是下列符号串中的E+ TF F *(E + T)20、A)和若一个文法是递归的，则它所产生的语言的句子A.是无穷多个B.是有穷多个C.是可枚举的B) 和 C) 和D)D.个数是常量21、词法分析器用于识别C 。A.句子 B.句型 C.单词D.产生式22、在语法分析处理中,A.非终极符集first集合、B.终极符集FOLLOW!合、select集 合均是字母表C.D.状态集23、编译程序中语法分析器接收以A为单位的输入。24、25、26、27、29、30、A.单词B.表达式C.产生式 D.句子在自底向上的语法分析方法中，分析的关键是A.寻找句柄B.寻找句型C.B.消除递归D

8、.选择候选式在LR分析法中，分析栈中存放的状态是识别规范句型A.句柄B.前缀C.活前缀DFA状态。D. LR(0)项目词法分析的任务是(A识别单词代码优分的目的是(A.节省时间A)B.分析句子的含义C.识别句子D.生成目代码C)B.节省空间C.节省时间和空间D.把编译程序进行等价交换代码生成阶段的主要任务是(C)A.把高级语言翻译成汇编语言B.把高级语言翻译成机器语言C.把中间代码变换成依赖具体机器的目标代码D.把汇编语言翻译成机器语言在LR分析法中，分析栈中存放的状态是识别规范句型A.句柄B.前缀C.活前缀的DFA状态。D. LR(0)项目一个上下文无关文法G包括四个组成部分,它们是：一组非

9、终结符号，一组终结符号，一个开始符号，以及一组A.句子B.句型C.单词D.产生式是非判断题1、正规文法产生的语言都可以用上下文无关文法来描述。(V)2、如果一个文法是递归的，则其产生的语言的句子是无穷个。(V)3、文法的二义性和语言的二义性是两个不同的概念。4、一个LL( I)文法一定是无二乂的。(V)5、在规范规约中用最左素短语来刻划可归约串。6、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(V)7、编译程序是对汇编程序的翻译。(X)8、计算机高级语言翻译成低级语言只有解释一种方式。9、在编译中进行语法检查的目的是为了发现程序中所有错误。10、甲机上的某编译程序在乙机上能直接使用

10、的必要条件是甲机和乙机的操作系统功能完(X)11、正则文法其产生式为 A a, A Bb, A,B S, a、b V12、 每个文法都能改写为LL(1)文法。13、递归下降法允许任一非终极符是直接左递归的。全相同。(V)(X)14、算符优先关系表不一定存在对应的优先函数。(X)(V)15、自底而上语法分析方法的主要问题是候选式的选择。16、LR法是自顶向下语法分析方法。(X)(V)18、若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。19、一个句型的句柄一定是文法某产生式的右部。20、在程序中标识符的出现仅为使用性的。21、在程序中标识符的出现仅为使用性的。名词解释题1、扫描遍:

11、指编译程序对源程序或中间代码程序从头到尾扫描一次。2、短语：设GZ是给定文法，w=xuy V+为该文法的句型，如果满足下面两个条件 Z马xUy ; U左U ;则称句型xuy中的子串U是句型xuy的短语。3、简单短语：设GZ是给定文法，w=xuy V+为该文法的句型，如果满足下面两个条件 Z刍xUy ; U = u ;则称句型xuy中的子串U是句型xuy的简单短语(或直接短语)。4、句柄：一个句型中的最左简单短语称为该句型的句柄。5、语法分析:按文法的产生式识别输入的符号串是否为一个句子的分析过程。6、活前缀：若SaA诵 3是文法G中的一个规范推导，G是 G的拓广文法，符号串丫是a B的前缀，则

12、称丫是G的，也是G的一个活前缀。其中S为文法开 始符号。或：可归前缀的任意首部。7、可归前缀:是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。LR(0)项目：把产生式右部某位置上标有圆点的产生式称为相应文法的一个LR(O)项目。9、语义规则:对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。10、翻译方案：将属性文法中的语义规则用花括号 括起来，插在产生式右部的合适地方，指明语义规则的计算次序，陈述一些细节，得到一种语义动作与语法分析交错的表示方法，以表述语义动作在语法分析过程中的执行时刻，称之为翻译方案。11、后缀式：一种把运算量(操作数)写在前面把算符写在后面(后缀)的

13、表示法。即一个表达式E的后缀形式可以如下定义:(1)(3)12、过程活动:如果E是一个变量或常量，则 E的后缀式是E自身。如果E是 E1 opE2形式的表达式，这里op是任何二元操作符，则 巳op,这里B和E2分别为E和E2的后缀式。如果E( E1)形式的表达式，贝y E1的后缀式就是E的后缀式。E的后缀式为Ei产生该过程这样一个连续的存一个过程的活动指的是该过程的一次执行。就是说，每次执行一个过程体, 体的一个活动。13、活动记录:为了管理过程在一次执行中所需要的信息，使用一个连续的存储块,储块称为活动记录。14、活动的生存期:指的是从执行某过程体第一步操作到最后一步操作之间的操作序，包括执

14、行过程时调用 其它过程花费的时间。15、基本块的DAG一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG(1) 图的叶结点(没有后继的结点)以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr (A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。（2）图的内部结点 （有后继的结点） 以一运算符作为标记， 表示该结点代表应用该运算 符对其后继结点所代表的值进行运算的结果。（3）图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的 值。16、 S-属性文法：？什么是 L-

15、属性文法？它们之间有什么关系？S-属性文法是只含有综合属性的属性文法。17、L- 属性文法：L-属性文法要求对于每个产生式A X1X2 Xn,其每个语义规则中的每个属性或者是综合属性，或者是 Xj 的一个继承属性，且该属性仅依赖于：（1）产生式Xj的左边符号X1,X2, Xj-1的属性；（2）A的继承属性。18、语法制导翻译：语法制导翻译是对前后文无关文法的扩充,即对文法中的每个产生式都附加一个语义动 作或语义子程序, 且在语法分析过程中, 每当需要使用一个产生式进行推导或归约时, 语法 分析程序除执行相应的语法分析动作外,还要执行相应的语义动作或调用相应的语义子程 序,完成相应的语义分析和翻

16、译工作。19、词法分析按照记法规则从构成源程序的词法分析的主要任务是从左向右扫描每行源程序的符号, 字符串中识别出一个个具有独立意义的最小语法单位, 并转换成统一的内部表示, 送给语法 分析程序。四、 简答计算题1、已知文法 GE 为：EtT|E+T|E-TTtF|T*F|T/FFt（ E）|i 该文法的开始符号（识别符号）是什么？请给出该文法的终结符号集合Vt和非终结符号集合Vn。 找出句型 T+T*F+i 的所有短语、简单短语和句柄。E。答：该文法的开始符号（识别符号）是 I 该文法的终结符号集合VT=+、-、*、/ 、（、）、 i 。非终结符号集合 VN=E、T、F 。 句型 T+T*F

17、+I的短语为i、T*F、第一个 T、T+T*F+i; 简单短语为i、T*F、第一个T;句柄为第一个To2、已知文法 GS 为：StdABaA|aBt Bb| GS 产生的语言是什么？GS能否改写为等价的正规文法？答： GS产生的语言是 L(GS)=da nbm | n 1,m 0。GS能改写为等价的正规文法，其改写后的等价的正规文法GS / 为:S J dAA 7 aA|aB|aB 7 bB|b3、简述DFA与 NFA有何区别答：DFA与NFA的区别表现为两个方面：一是NFA可以若干个开始状态，而 DFA仅只一个开 始状态。另一方面， DFA的映象M是从KX刀到K,而NFA的映象M是从KX刀到

18、K的子集, 即映象M将产生一个状态集合(可能为空集)，而不是单个状态。4、试给出非确定自动机的定义。2, S, P ）。答：一个非确定的有穷自动机(NFA) M是一个五元组：M=( K,其中：1. K是一个有穷集，它的每个元素称为一个状态；所以也称2为输入符号表;2. 2是一个有穷字母表， 它的每个元素称为一个输入符号，3. S ( K是一个非空初态集；P: K X 2 *72K ;表明在4. P是状态转换函数，是在KX 2 *7 K的子集的映射，即，某状态下对于某输入符号可能有多个后继状态。5、为正规式(a|b ) *a(a|b)构造一个等价的确定的有限自动机。答：a,b将其转换为确定的自动

19、机。d6、给定下列自动机,答：消除边,得到NFAd十注：带+号的结点为初始状态;十带一号的结点为终止状态+ CGHdddAd确定化，得到DFABCEBCE+一d+SAAABCEGABCEGBCEBCEDGGHDGDHHHDHDH注：带+号的结点为初始状态;d(2)此DFA的正则表达式为：4-13.消除下列文法 GE的左递归。带一号的结点为终止状态(aab|b)(b或 a b (blab)。Tt T/F IFt ( E )答：消除文法GE的左递归后得到:Et teEt -T EI Tt ftTt /ft I ft (E) I i8、在LL(1)分析法中丄L分别代表什么含义？答：第一个L代表从左到

20、右的扫描，第二个L代表每次进行最左推导。9、自顶向下分析思想是什么？如果全部匹配答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。因此判定给定终结符号串是正确句子。成功，则表示开始符号可推导出给定的终结符串。10、自顶向下的缺点是什么？答：在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产生式， 直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。11、LL (1)文法的定义是什么？答：一个上下文无关文法是 LL(1)文法的充分必要条件是每个非终结符A的两个不同产生式，At a ,At 3 ；满足 SELECT(A t a ) A

21、 SELECT(A t 3 )=。其中，a、3 不能同时马 。12、什么是文法的左递归？ 答：一个文法含有下列形式的产生式之一时:1)AtA3 , A VN B V*2)AtB3 , BtAa , A、B VN, a、3 V* 则称该文法是左递归的。13、递归下降法的主要思想是什么?因为文法递归相应子程序也答：对每个非终结符按其产生式结构写出相应语法分析子程序。递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归 下降法。14、自底向上分析法的原理是什么?答：在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当前句型的句柄(最左简单短

22、语)，并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。15、给定文法 GZ:1.Z t C S2.C t if Ethen3.St a =E4.E t e VA5.E t a6.A t i其中：Z、C、S A、E Vn ；if、then、=、V、 i Vta)构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFAACTIONGOTO0ifthe n=Vi#ZCSEA0S3121OK2S6453S784r 15S966r 6r 6r 67S10S118r 5r 5r 59S12810211S1312S11r 3134r4r

23、4Follow(A)则可构造= = ,# , V ,then SLR (1)分析表为：b)构造其SLR( 1 )分析表。答：1首先拓广文法：在 G中加入产生式0. Z 7Z,识别全部活前缀的 DFA然后得到新的文法G,再求G的l0： Z 7 . ZZ 7. C SC 7 if E . thenC7. if E then li： Z 7 乙 12: Z 7 c . sS7.A= El9：E7 e . V AS7 A = . EE7 . E V AE7 . AA 7. i13： C7if . E thenE 7. E V A110：111：A7 . iC7 if E then .E 7. AA 7

24、. i|4： Z7c s.|5： S7A. = EI 12：I 13：2. Follow(Z)= #Follow(C)= iFollow(S)=#Follow(E)=#, V ,thenA7 . i S7 A = E.E7 e . V AE7 e V A.ACA112VAthenifAliol816、设有文法GS:St a aA t AbA t b求识别该文法所有活前缀的DFA答:(1).首先拓广文法：在G中加入产生式0.S t S,然后得到新的文法0.S t S1.S t aA2.A t Ab(2).再求G的识别全部活前缀的 DFA17、语法制导翻译方法的基本思想是什么G :答：在语法分析过

25、程中，每当使用一条产生式进行推导或归约时，就执行该产生式所对应的语义动作进行属性计算，完成对输入符号串的翻译。18、在一个属性文法中， 对应于每个产生式 At a都有一套与之相关联的语义规则，每条规则的形式为b:= f (c1,c2 , , ck)，其中对于b的要求是什么？答：语义规则中的左部属性变量 b被规定为只能是下述两种变量: 对应产生式左部符号的综合属性变量; 对应产生式右部符号的继承属性变量。19、对于文法G(E):PT|E+TJ F|T*FJ(E)|i1) 写出句型(T*F+i)的最右推导并画出语法树。2) 写出上述句型的短语，直接短语和句柄。答：1.)匕 BF=(E) =(E+T

26、) =(E+F)=(E+i)=(T+i)=(T*F+i)2）短语：（T*F+i）, T*F+i, T*F, i 直接短语：T*F, i句柄：T*F20、构造下面文法的 LL(1)分析表。S T a B S | b A S | 名A T b A A | aB T a B B | b答：FirstFollowSa, b, z$Aa, ba, b, $Ba, ba, b, $开始符号集合和后继符号集合ab$SS T a B SS T b A SS T ZAA T aA T b A ABB T a B BB T bLL(1)分析表五、综合题1、通过构造识别活前缀的 DFA和构造分析表，来证明文法 答：先给出接受该文法活前缀的 DFA如下：E T E + id | id 是 SLR(1)文法。再构造SLR分析表如下:状态动作转移id+$E0s211s3acc2r2r23s44r1r1表中没有多重定义的条目，因此该文法是SLR(1)的。2、为下面文法构造规范LR(1)分析表，画出像教材上图3.20这样的状态转换图就可以了。S T V = E | EV T * E | idE T V合并同心项目集后是否会出现动作冲突?(2)上述状态转换图有同心项目集吗? 答：(1) 状态转换图如下：SJ S T S