《编译原理总复习.doc》由会员分享，可在线阅读，更多相关《编译原理总复习.doc（7页珍藏版）》请在金锄头文库上搜索。
1、编译原理总复习编译原理试题整理考试题型：简答（4道）、计算（4道）、综合（3道）一、简答题：1、什么是编译程序？其分为几个阶段？编译程序：也称为编译器，能够直接将高级语言程序翻译为对应的低级语言程序。编译程序通常分为：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成5个阶段。2、文法的形式定义是什么？文法的形式定义为G=（，P，S），其中为非终结符集，是终结符集， P是产生式集合，S是开始符号3、什么是上下文无关文法？若在文法的定义中限定文法的产生式左部只有一个非终结符，则该文法称为上下文无关文法。4、什么是文法的语言？从文法G的开始符号S出发，所能推导出的句子的全体称为文法
2、G产生的语言。5、文法的分类？乔姆斯基把文法分为0型文法（短语文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）、3型文法（正规文法）四类。这几类的差别在于对产生式施加不同的限制。6、词法分析的功能？1）按规则识别单词，输出单词本身及其类别码；（主要任务）2）滤掉程序中的无用成分；3）调用出错处理程序，识别并定位错误；4）调用符号管理程序，将识别出来的单词及其属性进行管理。7、什么是符号表？有何作用？符号表：是一种用于保存源程序中出现的标识符和常数的各种信息的数据结构。作用：编译器在分析阶段收集信息放入符号表中，在综合阶段生成目标代码时使用符号表中的信息。8、什么是正规文法？若文法
3、G=（，P，S）中的每个产生式P的形式都是AaB或Aa，其中A、B，a，则G是正规文法。9、语义分析的主要任务？1）对语法分析所识别出的各类语法短语进行静态语义审查；2）若无语义错误，再根据识别出的语法单位的类型进行处理，若是说明语句，则将变量的类型等属性填入符号表，若是可执行语句，则进行初步的翻译，将其翻译为中间代码。10、什么是属性文法？属性文法：包含一个上下文无关文法和一系列的语义规则，为每个文法符号配备若干相关的“值”（属性）。11、什么是语法制导翻译？若遍历语法树的操作和建立语法树的操作同时进行，称为语法制导翻译。12、什么是代码优化？代码优化：指的是为了提高目标程序的质量而对源程序
4、或中间代码进行的各种合理的等价变换，使得变换后的程序能生成更有效的目标代码。13、代码优化要遵循哪些原则？遵循如下原则：等价原则、有效原则、合算原则。14、局部优化常用哪些技术？包括：删除公共子表达式、删除无用赋值、合并已知量、对临时变量改名、对语句变换位置、代数变换等。15、循环优化常用哪些技术？包括：代码外提、强度削弱、删除归纳变量等。*16、什么是短语文法？若对文法中的产生式的要求是：至少含有一个非终结符，则称该文法为短语文法。二、计算题：1）推导、画语法树、二义性的证明：5、已知表达式的文法G为：|+|*()| i给出i+i+i和i+i*i的最左推导、最右推导和语法树。解答：用E表示，
5、T表示，F表示，上述文法可以写为： E T | E+T T F | T*F F (E) | i最左推导：E=E+T=E+T+T=T+T+T=F+T+T=i+T+T=i+F+T=i+i+T=i+i+F=i+i+iE=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i最右推导：E=E+T=E+F=E+i=E+T+i=E+F+i=E+i+i=T+i+i=F+i+i=i+i+iE=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i =i+i*ii+i+i和i+i*i的语法树如下图所示。i+i+i、i+i*i的语法树8、考虑文法GS：SaSbS|b
6、SaS|(1)试用最左推导说明此文法的二义性。(2)对于句子abab构造两个相应的最右推导。(3)对于句子abab构造两棵相应的分析树。(4)此文法所产生的语言是什么？解答：(1) 句子abab有如下两个不同的最左推导：S = aSbS = abS =abaSbS = ababS = abab S = aSbS = abSaSbS = abaSbS = ababS = abab 所以此文法是二义性的。(2) 句子abab的两个相应的最右推导： S = aSbS = aSbaSbS = aSbaSb = aSbab = abab S = aSbS = aSb = abSaSb = abSab =
7、 abab(3) 句子abab的两棵分析树： (a)(b)(4) 此文法产生的语言是：在a，b上由相同个数的a和b组成的字符串。2）给出短语写文法：7、试构造生成下列语言的上下文无关文法：(1)=|n1,i0。(6)语言=x|xa,b,c,x是重复对称排列的(aabcbaa，aabbaa等)解答：(1) 把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S ABA aAb|abB cB|e(6) GS：SaSa | bSb | cSc | a | b | c |e3）短语、素短语、最左素短语、firstVT、lastVT：例4.19（P92）、例4.
8、20（P93）12、已知文法GE：（拆成两道大题出）ET|E+TTF|T*FF(E)|i(1)给出句型（T*F+i）的最右推导，并画出语法树；(2)给出句型（T*F+i）的短语、素短语和最左素短语；(3)证明E+T*F是文法的一个句型，指出这个句型的所有短语、直接短语和句柄。解答： 最右推导：E=T=F=(E)=(ET)=(EF)=(Ei)= (Ti)=(T*Fi)语法树：图4.1 句型(T*Fi)的语法树 短语：(T*Fi)，T*Fi，T*F，i 素短语：T*F，i最左素短语：T*F 由于E =E+T =E+T*F，故E+T*F为该文法的句型 短语：T*F、E+T*F 直接短语： T*F 句
9、柄： T*F13、给定文法GS，其产生式如下：S(T)|aTT,S|S(1)给出输入串(a,(a,a)的最左和最右推导过程；(2)计算该文法各非终结符的FirstVT集和LastVT集。解答：最左推导：S= (T) = (T,S) = (S,S) = (a,S) = (a,(T) = (a,(T,S) = (a,(S,S) = (a,(a,S) = (a,(a,a)最右推导：S= (T) = (T,S) = (T,(T) = (T,(T,S) = (T,(T,a) = (T,(T,a) = (T,(a,a) = (S,(a,a) = (a,(a,a)文法中S和T的FirstVT和LastVT集
10、为：FirstVT(S)=a,( FirstVT(T)=,a, ( lastVT(S)=a, ） lastVT(T)=,a,)4）给语句写四元式序列（四选一）：例5.12（P156）11、将下面的语句翻译为四元式序列：(1)if (AC) and (BD) thenif A=1 then c:=c+1else if A=D then A:=A+2；(4)for i:=b*2 to 100 do x:=(a+b)*(c+d)-(a+b+c)；解答：(1) 四元式序列为： 1（j,A,C,3）8.(:=,T,-,C) 2.(j,-,-,14)9.(j,-,-,14) 3.(j, i,t1,15)7
11、. (+, a, b, t3 )8. (+, c, d, t4 )9. (*,t3, t4, t5) 10. (+, a, b, t6 )11. (+, t6 c, t7 )12. ( -, t5, t7, t8) 13. ( :=, t8, , x )14. (j, , , 4)15.三、综合题：1）NFADFA：例3.9（P44）2）自上而下分析（四选一）：例4.12（P79）8、已知文法GS，其产生式如下：S(L)|aLL,S|S从GS中消除左递归，并为之构造一个非递归预测分析器LL(1)分析表，并说明对输入符号串（a,(a,a)）的分析过程。解答：消除所给文法的左递归，得G：S (L)
12、|a L SLL ,SL |e 实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G有：First(S) = ( , a )Follow(S) = ) , , , #First(L) = ( , a )Follow(L) = ) First(L) = ,Follow(L) = ) 按以上结果，构造预测分析表M如下：文法G是LL(1)的，因为它的LL(1)分析表不含多重定义入口。预测分析器对输入符号串(a,(a,a)做出的分析动作如下：步骤栈剩余输入串输出1#S(a,(a,a)#2#)L(a,(a,a)#S (L)3#)La,(a,a)#4#)LSa,(a,a)#L SL5#)Laa,(a,a)#S a6#)L,(a,a)#7#)LS,(a,a)#L ,SL8#)LS(a,a)#9#)L)L(a,a)#S (L)10#)L)La,a)#11#)L)LSa,a)#L SL12#)L)Laa,a)#S a13#)L)L,a)#14#)L)LS,a)#L ,SL15#)L)LSa
