编译原理练习题

1、1、编译程序各阶段都涉及A、词法分析 B、表格管理C、语法分析D、语义分析2、 下列哪个程序不是编译程序的组成部分？ 。A、词法分析程序B、代码读入程序C、代码生成程序D、语法分析程序3、 编译程序各阶段的工作往往是 进行的。A、顺序B、并行C成批D、穿插4、 词法分析所依据的是 。A、语义规则B构词规则C语法规则D、等价变换规则5、 编译程序的语法分析器可以发现源程序中的 。C错误并校正D、语法错误。C、函数D、过程A、语义错误B、语法和语义错误6、高级语言源程序经编译后产生的程序是A、源程序B、目标程序1、扫描器的任务是从源程序中识别出一个个单词符号。2、高级语言源程序有两种执行方式，即解

2、释和编译。判断：高级语言编写的源程序都必须通过编译，产生目标代码后才能运行。 多遍扫描的编译程序的多遍是指多次重复读源程序。高级语言程序到低级语言程序的转换是基于语义的等价变换。编译程序中错误处理的任务是对检查出的错误进行修改。目标程序一定是机器语言程序。连接装配程序可把经编译程序产生的目标程序变成可执行的机器语言程序。简答题：1、请指出下列错误信息可能是编译的哪个阶段报告的？ else没有匹配的if ； 数组下标越界； 使用的函数没有定义； 在数中出现了非数字信息。答：语法分析阶段 语义分析与中间代码生成阶段语义分析与中间代码生成阶段词法分析阶段2、何谓源程序、中间代码和目标代码？它们三者之

3、间有何种关系？答：所谓源程序是指用某种高级语言编写的程序，它是编译程序的加工对象。目标程序 是指低级语言（机器语言或汇编语言）编写的程序，它是编译程序的加工结果。中间代 码是其结构介于源程序和目标程序之间的一种机内表示形式，它是编译程序产生的中间临时结果。它们三者之间的关系是等价关系，即结构不同，但语义相同。1、 文法 G: S- xSx|y 所识另U的语言是 。A、xyxB、(xyx) *C xnyx n(n 0)D、x*yx*2、 设有文法GS=(S,B,b,S- b|bB,B-bS,S)该文法所描述的语言是 。i2i2i+12iA、L(GS)=b|i 0B、L(GS)=b |i 0 C、

4、L(GS)=b |i 0 D、L(GS)=b | 13、 给定文法A bA|cc，下面的符号串中为该文法句子的是。 cc bcbc bcbcc bccbcc bbbcc可选项有：A、BC、D、4、描述语言 L=ambn|n m 1的文法为。A、Z-AbbA-aA|aB-bB|bB、A-ABbA-Aa|aB-aBb|bC、Z-AbA-aAb|aD、乙aAbA-Ab|aAb|1、 假定G是一个文法，S是它的开始符号。如果S=a，则称a是一个句型，仅包含的 句型称为句子。2、设有文法 GS:S- bBB- cC B cCeC- dS S- aB，则Vn=,Vt=。判断一个上下文无关文法的开始符号可以

5、是终结符或非终结符。1型文法对规则的限制比 2型文法对规则的限制要多一些。简答题：1、令文法G为：N D|NDD 0|1|2|3|4|5|6|7|8|9(1)文法G定义语言是什么？给出句子0127的最左推导和最右推导。答：(1)G的语言是任意的数字串：L(G)=qa2.an|ai 0,1,2,9(2)最左推导：N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127 最右推导：N=ND=N7=ND7=N27=ND27=N127=D127=01272、证明下述文法是一个二义性文法：S iSeS|iS|iiS句子iiiei的语法树如下图所示。i同一句子对应两棵不同的语法树，故该

6、文法是二义的。词法分析:1、如果两个文法产生的语言相同，则称这两个文法是等价的。2、确定的有限自动机 DFA是不确定的有限自动机 NFA的一个特例。3、 两个等价的正规式所表示的正规集相同，高级语言的词法结构一般可以用正规文法来实 现。4、一张符号表的每一项(或称入口)包含两大栏，即名字栏和信息栏。5、符号表的查找和整理技术通常有线性查找、二叉树和杂凑技术。6、设刀=a,b，试写一正规式，其表示的正规集为“不以 a开头，但以aa结尾的字符串集 合”。正规式为：b(a|b)*aa1、 词法分析器的输入是。A、单词符号串B、源程序C语法单位D、目标程序2、 不是NFA的成分。A、有穷字母表B、唯一

7、的初始状态C终止状态集合D、有限状态集合3、 在词法分析阶段不能识别的是 。A、标识符B、运算符C四元式D、常数4、 对编译程序所用到的符号表，涉及的操作不包括 。A、填写或更新信息栏内容B、填入新名C、给定名字，访问它的有关信息D、输出token字序列判断：1、有限自动机只有一个初态。2、 对任一个正规式 r,都存在一个 NFA M,使得L(M)=L(r)。简答题：1、 设刀=0,1，试写一正规式，其表示的正规集为：“含有子串010的所有串”。答：正规式为：1)*o1o(1)*2、在实现编译程序时，常将词法分析程序从语法分析中独立出来，这样做有什么好处？ 答：将词法分析程序从语法分析中独立出

8、来，这样做有以下好处： 建立高级语言时能独立地研究词法与语法两方面的特性。 词法规则简单，因此可建立特别适用于这种文法的有效分析技术，也容易实现词法分 析程序生成自动化。 可以就同一个语言为每种不同的机器编写一个词法分析程序，只编写一个共同的语法分析程序，这时只要每一个词法分析程序产生相同的符号内部表示形式供该语法分析程 序使用即可。综合题：1、设0,1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应 的正规式，并构造一个识别该正规集的DFA构造相应的正规式：(0|1)*1(0|1)NFA:1 10 0确定化:I1 0打0,1,21,21,2,31,21,2厂1,2,31,2

9、,31,2,41,2,3,41,2,41,2:1,2,3123,41,2,41,2,3,401、 编译过程中，语法分析器的任务是 。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构A、B、C、 D2、 在通常的语法分析方法中，特别适用于表达式的分析。A、算符优先分析法B LR分析法C、递归下降分析法D、LL（ 1）分析法3、 一个指明了在分析过程中的某时刻所能看到的产生是多大一部分。A、活前缀B、前缀C、项目D、项目集判断1、每个文法都能改写成 LL（ 1）文法。2、一个LL（ 1 ）文法一定是无二义的。3、每一个算符优先文法，必定能找到一组优先

10、函数与之对应。4、欲构造行之有效的自上而下分析器，则只需消除左递归。5、所有LR分析器的总控程序都是一样的，只是分析表各有不同。6、若B为非终结符，则 A a .B3为移进项目。1、语法分析最常用的两类方法是自上而下和自下而上分析法。2、语法分析器的输入是单词符号串，其输出是语法单位。3、 一个文法G,若它的预测分析表 M不含多重定义入口，则 G是LL （1）文法。4、 LL （1）文法中，第一个 L表示从左到右扫描输入串，第二个L表示最左推导。LR分析5、应用算符优先分析技术分析句型时，每步被直接规约的是最左素短语，而应用 技术时，每步被直接规约的是句柄。6、活前缀是指规范句型的一个前缀，这

11、种前缀不含句柄之后的任何符号。简答题:1、对于文法 G (S): S(L) |as|a L L,S|S画出句型(S,(a)的语法树)A短语：S a、(a)、S,(a)(S,(a)直接短语：a,S句柄：S素短语：a2、考虑以卜文法G： Sa| A |(T)TT,S|S(1)消去G的左递归(2)经改写后的文法是否是LL(1)的？答：消左递归：Sa| A|(T)T STfisrt(S)=a, A ,(first(T)=a,A ,(follow(S)=#,follow(T)=1文法不含左递归2每个产生式的候选首符集两两不想交3. first(T Qfo)ow(T)=所以该文法是LL(1)文法。T ,S

12、T dfirst(T )=, follow(T )=给出句型(S,(a)的短语、直接短语、句柄和素短语。综合题：1、对下面的文法 G: E TE E +E| d T FT T T| F PF F*F d P (E)|a|b| A(1) 计算这个文法的每个非终结符的FIRST和FOLLOW(2) 证明这个文法是 LL(1)的。(3 )构造它的预测分析表。语义分析和中间代码生成:1、 语义分析和中间代码生成时所依据的是 。A、语法规则B、词法规则C、语义规则D、等价变换规则2、 终结符具有属性。A、传递B、继承C、抽象 D、综合3、 后缀式ab+cd+/可用表达式来表示。A、a+b/c+d B (

13、a+b)/(c+d)C、a+b/(c+d) D、a+b+c/d4、 语法制导的翻译程序能同时进行和语义分析。A、词法分析B、语法分析C、优化D、目标代码生成5、 四元式之间的联系是通过 实现的。A、指示器B、临时变量C、符号表D、程序变量1、语法制导的翻译是基于属性文法的，属性有两类，即综合属性和继承属性。2、在语法树中，一个结点的综合属性的值由其子结点的属性确定，而继承属性则由该结点 的父结点或兄弟结点的某些属性确定。3、语义分析阶段所生成的与源程序等价的中间表示形式可以有逆波兰表示、三元式表示和 四元式表示等。4、生成中间代码主要是为了使目标代码的优化容易实现。简答题：1、给出下列表达式的

14、逆波兰式:(1) -a+b*(-c+d)(2) a+b*(c-d)/e-f答: (1)a-bc-d+*+(2)abcd-*e/+f-2、给出-(a+b)*(c+d)-(a+b+c)的三元式和四元式。(其中单目运算一用表示)1(+,a,b)(+,a,b,T1)2(,1,_)(,T1,_,T2)3(+,c,d)(+,c,d,T3)4(*,2,3)(*,T2,T3,T4)5(+,a,b)(+,a,b,T5)6(+,c,5)(+,T5,c,T6)7(-,4,6)(-,T4,T6,T7)优化：1、 下列优化方法不是针对循环优化进行的。D、代码外提A、强度削弱B、删除归纳变量C、删除公共子表达式2、 对于

15、一个基本块来说，正确的说法是 。A、只有一个入口语句和一个出口语句B、有一个入口语句和多个出口语句C、有多个入口语句和一个出口语句D、只有多个入口语句和多个出口语句判断：数组元素的地址计算与数组的存储方式有关。 循环中的不变运算都可以提到循环外。根据优化设计到的程序范围，优化可分为局部优化、循环优化和全局优化三个不同的级别。 局部优化是在基本块范围内进行的一种优化。在优化中，可把循环中的不变运算提到循环外去，这种方法称为代码外提。简答题1、已知三地址代码序列为：(1) i:=1(2) i:=i+1 j：=1 j:=j+1(5) k:=i mod j(6) if kz 0 goto (4) if

16、 i 工 j goto (10)(8) write I(9) writeln(10) if i C goto L2B:=B+1goto L1L2:write Ahalt2、试构造以下基本块(1) T0(2) T1(3) T2(4) A:(5) B：G 的 DAG=3.14=2*T0=R+r=T1*T2=A(6) T3： =2*T0(7) T4 : =R+r (8T5 : =T3+T4(9) T6 : =R-r(10) B : =T5*T63.14B已知如下翻译模式，用回填法给出ab or cd and ef的四元式序列，要求给出简单过程。文法及其翻译模式如下：(1)E tEi and M E

17、2 backpatch(E i.truelist,M.quad);E.truelist:= E2.truelist)E.falselist:=merge(E1.falselist,E2.falselist )(2) E tE1 or M E 2 backpatch(E 1.falselist,M.quad);E.truelist:=merge(E 1.truelist,E 2.truelist)E.falselist:=E 2.falselistE 1T id 1 relop id 2 E.truelist:= makelist( nextquad);E.falselist:=makelist

18、( nextquad+1);E.t=1OO,1O4ae c dEmit( j relop.op ,id 1.place , id 2.place , OEmit( j,-.-,0 )M T M.quad:=n extquad四兀式序列为：100(j ,a,b,0)101(j ,-,102102(j ,c ,d,104)103(j ,-,0)104(j ,e,f,0)105(j ,一,0)有文法 G（ S）：St A|BAt aAb|cBtaBb |d试构造此方法的 LR（ 0）项目集规范族。1）将文法G拓广为文法 GS-SA-cS-AB-aBbS-BB- dA-aAb2）列出 LR（ 0）的所有项目：1S-?S 5. A-?aAb 9. A-?c13. B- ?aBb17.B- ?dS-S? 6. A-a?Ab10. A-c ?14.B-a ?Bb18 B-d?S-? A 7. A-aA?b11. S- ?B15.B-aB ?bS-A? 8.A-aAb?12.S-B?16 B-aBb?3）用CLOSURE!、法构造文法 G的LR （ 0）项目集规范族：I0: S -?S