《编译原理自测题2014.doc》由会员分享，可在线阅读，更多相关《编译原理自测题2014.doc（7页珍藏版）》请在金锄头文库上搜索。
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、编译过程的几个阶段的输入输出及相关技术进行解答。产生式翻译方案（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.lexe
