编译原理练习题

1一章：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、高级语言源程序经编译后产生的程序是。A、源程序B、目标程序C、函数D、过程1、扫描器的任务是从源程序中识别出一个个单词符号。2、高级语言源程序有两种执行方式，即解释和编译。判断：高级语言编写的源程序都必须通过编译，产生目标代码后才能运行。多遍扫描的编译程序的多遍是指多次重复读源程序。高级语言程序到低级语言程序的转换是基于语义的等价变换。编译程序中错误处理的任务是对检查出的错误进行修改。目标程序一定是机器语言程序。连接装配程序可把经编译程序产生的目标程序变成可执行的机器语言程序。简答题：1、请指出下列错误信息可能是编译的哪个阶段报告的？①else没有匹配的if；②数组下标越界；③使用的函数没有定义；④在数中出现了非数字信息。答：①语法分析阶段②语义分析与中间代码生成阶段③语义分析与中间代码生成阶段④词法分析阶段2、何谓源程序、中间代码和目标代码？它们三者之间有何种关系？答：所谓源程序是指用某种高级语言编写的程序，它是编译程序的加工对象。目标程序是指低级语言（机器语言或汇编语言）编写的程序，它是编译程序的加工结果。中间代码是其结构介于源程序和目标程序之间的一种机内表示形式，它是编译程序产生的中间临时结果。它们三者之间的关系是等价关系，即结构不同，但语义相同。二章：1、文法G：S-xSx|y所识别的语言是。A、xyxB、（xyx）*C、xnyxn(n≥0)D、x*yx*2、设有文法G[S]=({S,B},{b},{S-b|bB,B-bS},S),该文法所描述的语言是。A、L(G[S])={bi|i≥0}B、L(G[S])={b2i|i≥0}C、L(G[S])={b2i+1|i≥0}D、L(G[S])={b2i|≥1}3、给定文法AbA|cc，下面的符号串中为该文法句子的是。2①cc②bcbc③bcbcc④bccbcc⑤bbbcc可选项有：A、①⑤B、①③④⑤C、①④D、①④⑤4、描述语言L={ambn|n≥m≥1}的文法为。A、Z---AbbA-aA|aB-bB|bB、A-ABbA-Aa|aB-aBb|bC、Z-AbA-aAb|aD、Z-aAbA-Ab|aAb|ε1、假定G是一个文法，S是它的开始符号。如果S===〉α，则称α是一个句型，仅包含的句型称为句子。2、设有文法G[S]:S-bBB-cCBcCeC-dSS-aB，则VN={},VT={}。判断一个上下文无关文法的开始符号可以是终结符或非终结符。1型文法对规则的限制比2型文法对规则的限制要多一些。简答题：1、令文法G为：ND|NDD0|1|2|3|4|5|6|7|8|9(1)文法G定义语言是什么？(2)给出句子0127的最左推导和最右推导。答：(1)G的语言是任意的数字串：L(G)={a1a2..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|i句子iiiei的语法树如下图所示。SSiSeSiSiSiSeSiii同一句子对应两棵不同的语法树，故该文法是二义的。词法分析:1、如果两个文法产生的语言相同，则称这两个文法是等价的。2、确定的有限自动机DFA是不确定的有限自动机NFA的一个特例。33、两个等价的正规式所表示的正规集相同，高级语言的词法结构一般可以用正规文法来实现。4、一张符号表的每一项（或称入口）包含两大栏，即名字栏和信息栏。5、符号表的查找和整理技术通常有线性查找、二叉树和杂凑技术。6、设∑={a,b}，试写一正规式，其表示的正规集为“不以a开头，但以aa结尾的字符串集合”。正规式为：b(a|b)*aa1、词法分析器的输入是。A、单词符号串B、源程序C、语法单位D、目标程序2、不是NFA的成分。A、有穷字母表B、唯一的初始状态C、终止状态集合D、有限状态集合3、在词法分析阶段不能识别的是。A、标识符B、运算符C、四元式D、常数4、对编译程序所用到的符号表，涉及的操作不包括。A、填写或更新信息栏内容B、填入新名C、给定名字，访问它的有关信息D、输出token字序列判断：1、有限自动机只有一个初态。2、对任一个正规式r，都存在一个NFAM，使得L(M)=L(r)。简答题：1、设∑={0,1}，试写一正规式，其表示的正规集为：“含有子串010的所有串”。答：正规式为：(0|1)*010(0|1)*2、在实现编译程序时，常将词法分析程序从语法分析中独立出来，这样做有什么好处？答：将词法分析程序从语法分析中独立出来，这样做有以下好处：①建立高级语言时能独立地研究词法与语法两方面的特性。②词法规则简单，因此可建立特别适用于这种文法的有效分析技术，也容易实现词法分析程序生成自动化。③可以就同一个语言为每种不同的机器编写一个词法分析程序，只编写一个共同的语法分析程序，这时只要每一个词法分析程序产生相同的符号内部表示形式供该语法分析程序使用即可。综合题：1、设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。构造相应的正规式：(0|1)*1(0|1)NFA:11100确定化：012344I0I1I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}01010001语法分析：1、编译过程中，语法分析器的任务是。①分析单词是怎样构成的②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的④分析程序的结构A、②③B、②③④C、①②③D、①②③④2、在通常的语法分析方法中，特别适用于表达式的分析。A、算符优先分析法B、LR分析法C、递归下降分析法D、LL（1）分析法3、一个指明了在分析过程中的某时刻所能看到的产生是多大一部分。A、活前缀B、前缀C、项目D、项目集判断1、每个文法都能改写成LL（1）文法。2、一个LL（1）文法一定是无二义的。3、每一个算符优先文法，必定能找到一组优先函数与之对应。4、欲构造行之有效的自上而下分析器，则只需消除左递归。5、所有LR分析器的总控程序都是一样的，只是分析表各有不同。6、若B为非终结符，则Aα.Bβ为移进项目。1、语法分析最常用的两类方法是自上而下和自下而上分析法。2、语法分析器的输入是单词符号串，其输出是语法单位。3、一个文法G，若它的预测分析表M不含多重定义入口，则G是LL（1）文法。4、LL（1）文法中，第一个L表示从左到右扫描输入串，第二个L表示最左推导。5、应用算符优先分析技术分析句型时，每步被直接规约的是最左素短语，而应用LR分析技术时，每步被直接规约的是句柄。6、活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。简答题：0123451、对于文法G（S）：S（L）|as|aLL,S|SS(1)画出句型(S,(a))的语法树(2)给出句型(S,(a))的短语、直接短语、句柄和素短语。(L)L,SS(L)SA短语：S、a、(a)、S,(a)、(S,(a))直接短语：a,S句柄：S素短语：a2、考虑以下文法G：Sa|∧|(T)TT,S|S(1)消去G的左递归(2)经改写后的文法是否是LL(1)的？答：消左递归：Sa|∧|(T)TST’T’,ST’|εfisrt(S)={a,∧,(}first(T)={a,∧,(}first(T’)={,,ε}follow(S)={#,,,}}follow(T)={}}follow(T’)={}}1.文法不含左递归2.每个产生式的候选首符集两两不想交3.first(T’)∩follow(T’)=φ所以该文法是LL(1)文法。综合题：1、对下面的文法G：ETE’E’+E|εTFT’T’T|εFPF’F’*F’|εP(E)|a|b|∧(1)计算这个文法的每个非终结符的FIRST和FOLLOW。(2)证明这个文法是LL(1)的。(3)构造它的预测分析表。语义分析和中间代码生成：1、语义分析和中间代码生成时所依据的是。A、语法规则B、词法规则C、语义规则D、等价变换规则2、终结符具有属性。A、传递B、继承C、抽象D、综合3、后缀式ab+cd+/可用表达式来表示。A、a+b/c+dB、(a+b)/(c+d)C、a+b/(c+d)D、a+b+c/d4、语法制导的翻译程序能同时进行和语义分析。A、词法分析B、语法分析C、优化D、目标代码生成5、四元式之间的联系是通过实现的。A、指示器B、临时变量C、符号表D、程序变量61、语法制导的翻译是基于属性文法的，属性有两类，即综合属性和继承属性。2、在语法树中，一个结点的综合属性的值由其子结点的属性确定，而继承属性则由该结点的父结点或兄弟结点的某些属性确定。3、语义分析阶段所生成的与源程序等价的中间表示形式可以有逆波兰表示、三元式表示和四元式表示等。4、生成中间代码主要是为了使目标代码的优化容易实现。简答题：1、给出下列表达式的逆波兰式：(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、下列优化方法不是针对循环优化进行的。A、强度削弱B、删除归纳变量C、删除公共子表达式D、代码外提2、对于一个基本块来说，正确的说法是。A、只有一个入口语句和一个出口语句B、有一个入口语句和多个出口语句C、有多个入口语句和一个出口语句D、只有多个入口语句和多个出口语句判断：数组元素的地址计算与数组的存储方式有关。循环中的不变运算都可以提到循环外。根据优化设计到的程序范围，优化可分为局部优化、循环优化和全局优化三个不同的级别。局部优化是在基本块范围内进行的一种优化。在优化中，可把循环中的不变运算提到循环外去，这种方法称为代码外提。简答题1、已知三地址代码序列为：(1)i:=1(2)i:=i+1(3)j:=17(4)j:=j+1(5)k:=imodj(6)ifk≠0goto(4)(7)ifi≠jgoto(10)(8)writeI(9)writeln(10)ifi10000goto(2)(11)halt划分基本块，并画出流图2、试把以下程序划分为基本块并作出其程序流图。readCA:=0B:=1L1:A:=A+1iFB≥CgotoL2B:=B+1gotoL1L2:writeAhalt2、试构造以下基本块G的DAG(1)T0：=3.14(2)T1：=2*T0(3)T2：=R+r(4)A：=T1*T2(5)B：=A(6)T3：=2*T0(7)T4：=R+r(8T5：=T3+T4(9)T6：=R-r(10)B：=T5*T6readCA:=0B:=1L1:A:=A+1iFB≥CgotoL2B:=B+1gotoL1L2:writeAhaltN1N2N6N8N5N7N4N33.146.