编译原理自测题2014

1、注：1、章节不完全按照陈意云教材的章节；2、不公布标准答案；3、题目中标注的页码如P6图1.3均为陈意云教材的页码。第一章一填空题1编译程序的工作过程一般可以划分为_、_、_、_和_等几个基本阶段，同时还伴有_和_。2若源程序是用高级语言编写的，目标程序是_或_，则其翻译程序称为编译程序。3编译方式与解释方式的根本区别在于_。4_是这样一种程序，它能将用甲种语言书写的程序转换成与其等价的乙种语言书写的程序。5对编译程序而言，输入数据是_，输出结果是_。6运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称_。7当把编译程序划分成编译前端和编译后端时，_主要由与_有关但与目标机无关

2、的部分组成，编译后端包括编译程序中与目标机有关的部分，编译后端不依赖于源语言而仅仅依赖于_。8描述词法规则的有效工具是_，通常使用_来描述语法规则，使用_描述语义规则。二 简答题1什么是编译程序2. 什么是解释程序3. 什么是翻译程序4. 以上3种程序的区别三 综合题1、编译过程的几个阶段的输入输出及相关技术（P6图1.3）第二章一 综合题1构造与正规式(a|b)*a(a|b)等价的状态最少的确定有限自动机。2构造与正规式(0|1)*0(0|1)等价的状态最少的确定有限自动机。3构造与正规式(a|ba)*等价的状态最少的确定有穷自动机。4构造与正规式(a|b)* aa等价的状态最少的确定有穷自

3、动机。5构造与正规式a (a|b)*b等价的状态最少的确定有穷自动机。注意：以上4题要分别写出构造NFA、NFA确定化为DFA（子集法）、DFA的最小化过程二 简答题1、当给出有限自动机的状态转换图时，写出有限自动机的五元式定义，并判断它能识别何种字符串。第三章一填空题1上下文无关文法包括以下四个组成部分：一组_符号，一组_符号，一个_符号，以及一组_。2如果一个文法存在某个句子对应两棵不同的语法树，则这个文法是_文法。3消除文法的二义性的方法主要有：_二义文法为非二义文法；为文法符号规定_和_。二 简答题1有文法G：EE+EE*E(E)id（1）给出(id* id)+ id的最左推导；（2）

4、并给出该推导过程中的所有句型；（3）给出该文法的2个句子；（4）这个文法产生的是什么语言。2. 有文法G：SaSbSbSaS（1）为句子abab构造最左推导；（2）给出该推导过程中的所有句型；（3）证明该文法是二义文法；（4）这个文法产生的是什么语言。3. 什么是LL（1）文法。4. 预测分析器模型由哪些部分组成。5. LR分析器模型由哪些部分组成。第四章一填空题1自上而下语法分析中存在的主要问题是由左递归引起的 问题和左公共因子引起的 问题。2LL（1）文法是即不含左递归，也没有左公共因子的文法。要避免回溯，第一，需要文法中每一个非终结符A的各个产生式的候选首符集两两不相交，即，若Aa1|a

5、2|an，则 f，(ij)；第二，若A存在某个候选首符集包含e，则 =f，i=1,2,.,n。3自上而下语法分析的基本思想是，对任何输入串，从文法的 符号，即根结点出发，自上而下地为输入串建立一颗语法树。递归下降分析器采用的是自上而下语法分析方法，非递归的预测分析器采用的是 语法分析方法，LR分析器采用的是 语法分析方法。4预测分析器模型是由输入、输出、 ， 和 组成。5自下而上语法分析的基本思想是，从 开始，逐步进行 ，直至规约到文法的开始符号，即从语法树的 开始，步步向上规约，直到 。6LR分析器模型包括输入、输出、 、 和含有 与 两部分的分析表。二、简答题1将以下文法G（S）改写成LL

6、(1)文法，该文法能识别哪一类语言。S (L)aL L，SS2将以下表达式文法G（E）改写成LL(1)（无左递归的）文法，该文法能识别哪一类语言。EE+TTTT*FFF (E)id3将以下表达式文法G（L）改写成LL(1)（无左递归的）的文法，该文法能识别哪一类语言。LE：LEE+TE-TTTT*FT/FT mod FFF (E)idnum4将以下文法G(S)改写成LL(1)（无左公共因子的）文法，该文法能识别哪一类语言。S iCtS | iCtSeS | aC b三、综合题一完成分析以下文法G的LL（1）预测分析器（语法分析器）的构造。（1）L E;L| （2）E TE （3）E +TE|-

7、TE|（4）T FT （5）T *FT|/FT|mod FT|（6）F (E)|id|num 1给出或画出预测分析器模型的组成；2构造预测分析表，FIRST（A）和FOLLOW（A）如下：FIRST(F) = ( id numFIRST(T) = * / mod FIRST(T) = ( id numFIRST(E) = + - FIRST(E) = ( id numFIRST(L) = ( id num FOLLOW(L) = # FOLL0W(E) = ) ; FOLLOW(E) = ) ; FOLLOW(T) = + - ; ) FOLLOW(T) = + - ; ) FOLLOW(F)

8、 = + - * / mod ) ; 3给出驱动器算法的伪代码，令ip指向#中的第一个终结符，top指向文法开始符号S;4填表给出用此分析器分析句子id+id*id; #的过程。5填表给出用此分析器分析句子id+id*;#的过程。第三章&第五章一、综合题一有文法G： （1）EE+T （2）ET （3）TT*F （4）TF （5）F(E) （6）Fi 表1是LR分析表，以下程序是驱动器算法，loop s := top; a := ip; case actions，a is shift s: push(a); push(s); next(ip); reduce by A: pop(2*|); s

9、:= top; push(A); push(goto(s，A); accept: return; others: error; end case;end loop1完成表2中LR分析器利用LR分析表和驱动器对输入串i*i+i进行分析的过程：写出栈中的内容和动作类型（移进或归约，若为移进请指出转向状态，若为归约请指出归约采用的产生式），如步骤1步骤3；2若在语法分析同时进行语义分析，请在有语义翻译动作的步骤中标出，无语义翻译动作的步骤中空白，如步骤1步骤3。表1 文法G的LR分析表ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s482

10、35r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5解答：表2步骤栈内容当前输入移进-规约动作翻译动作1#0i*i+i#移进：s52#0i5*i+i#规约：r6（Fi）有语义动作3#0F3*i+i#规约：r4（TF）有语义动作4567891011121314第六章一填空题1、属性文法是在上下文无关文法的基础上，为每个文法符号配备若干相关的“值”，称为属性，属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程，对文法的每个产生式配备的一组属性的计算规则，叫_，语义分析和中间代码的产生就是根据该规则进行的，在自上而下或

11、自下而上语法分析过程中，在适当的时候进行属性的_或其它语义动作（如查填符号表、_、发布出错信息）就可进行语法制导翻译得到中间代码，这就是_的基本思想。2、文法符号的属性分为两类，_属性用于“自下而上”传递信息，_属性用于“自上而下”传递信息。二 简答题1、简述语法制导翻译的基本思想第七章二、简答题一把下面表达式翻译成（a）语法树（b）有向无环图DAG （c）后缀表达式（d）三地址代码（1）-(a+b)*(b+c)（2）a*(b-c)+ (b-c)*d（3）(a+b)*(c+d)-(a+b+c)二请根据以下翻译方案写出id1*id2+id3的三地址代码。结合第1章，综合题的1、编译过程的几个阶段

12、的输入输出及相关技术进行解答。产生式翻译方案（1）Aid:=E p=lookup(id.lexeme);if(p!=nil) emit(p,=, E.place);else error;（2）EE1+E2E.place=newtemp( );emit(E.place, = ，E1. place, +，E2. place；)（3）EE1*E2 E.place=newtemp( );emit(E.place, = ，E1. place, *，E2. place；)（4）Eidp=lookup(id.lexeme);if(p!=nil) E.place=p;else error;第八章-第九章一填空

13、题1、不同的编译程序关于数据空间的存储分配策略会有所不同，_分配策略在编译是对所有数据对象分配固定的存储单元，且在运行是始终保持不变；另外还可采用的分配策略是_分配策略和_分配策略。2、过程一次执行所需局部信息用一块连续的存储区来管理，这块存储区叫_，它由临时数据、局部数据、机器状态、访问链、控制链、参数和返回值等域构成，不同的语言及同一语言的不同编译器使用的域可能不同，这些域在其中的布局也可能不同，另外_往往可以取代它们中的一个或多个域。3、编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息，这些信息通常记录在一张或几张_中。二、简答题：1、C语言的编译系统应该采用哪种存储分配策略，并简述理由。1、Pascal语言的编译系统应该采用哪种存储分配策略，并简述理由。2、编译系统常见的存储分配策略有几种？它们都适合于什么性质的语言？三、综合题P172例6.4第十章-第十三章一填空题1、代码优化可在编译的各阶段进行，其中主要的一类是在_代码之前生成的，这类优化不依赖于具体的计算机。2、代码优化可在编译的各阶