编译原理总复习.doc

《编译原理总复习.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理试题整理考试题型：简答（4道）、计算（4道）、综合（3道）一、简答题：1、什么是编译程序？其分为几个阶段？编译程序：也称为编译器，能够直接将高级语言程序翻译为对应的低级语言程序。编译程序通常分为：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成5个阶段。2、文法的形式定义是什么？文法的形式定义为G=（，，P，S），其中为非终结符集，是终结符集，P是产生式集合，S是开始符号3、什么是上下文无关文法？若在文法的定义中限定文法的产生式左部只有一个非终结符，则该文法称为上下文无关文法。4、什么是文法的语言？从文

2、法G的开始符号S出发，所能推导出的句子的全体称为文法G产生的语言。5、文法的分类？乔姆斯基把文法分为0型文法（短语文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）、3型文法（正规文法）四类。这几类的差别在于对产生式施加不同的限制。6、词法分析的功能？1）按规则识别单词，输出单词本身及其类别码；（主要任务）2）滤掉程序中的无用成分；3）调用出错处理程序，识别并定位错误；4）调用符号管理程序，将识别出来的单词及其属性进行管理。7、什么是符号表？有何作用？符号表：是一种用于保存源程序中出现的标识符和常数的各种信息的数据结

3、构。作用：编译器在分析阶段收集信息放入符号表中，在综合阶段生成目标代码时使用符号表中的信息。8、什么是正规文法？若文法G=（，，P，S）中的每个产生式P的形式都是A→aB或A→a，其中A、B∈，a∈，则G是正规文法。9、语义分析的主要任务？1）对语法分析所识别出的各类语法短语进行静态语义审查；2）若无语义错误，再根据识别出的语法单位的类型进行处理，若是说明语句，则将变量的类型等属性填入符号表，若是可执行语句，则进行初步的翻译，将其翻译为中间代码。10、什么是属性文法？属性文法：包含一个上下文无关文法和一系列的语义规则，为每个文法

4、符号配备若干相关的“值”（属性）。11、什么是语法制导翻译？若遍历语法树的操作和建立语法树的操作同时进行，称为语法制导翻译。12、什么是代码优化？代码优化：指的是为了提高目标程序的质量而对源程序或中间代码进行的各种合理的等价变换，使得变换后的程序能生成更有效的目标代码。13、代码优化要遵循哪些原则？遵循如下原则：等价原则、有效原则、合算原则。14、局部优化常用哪些技术？包括：删除公共子表达式、删除无用赋值、合并已知量、对临时变量改名、对语句变换位置、代数变换等。15、循环优化常用哪些技术？包括：代码外提、强度削弱、删除归纳变量等

5、。*16、什么是短语文法？若对文法中的产生式α→β的要求是：α至少含有一个非终结符，则称该文法为短语文法。二、计算题：1）推导、画语法树、二义性的证明：5、已知表达式的文法G为：<表达式>→<项>

6、<表达式>+<项><项>→<因子>

7、<项>*<因子><因子>→(<表达式>)

8、i给出i+i+i和i+i*i的最左推导、最右推导和语法树。解答：用E表示<表达式>，T表示<项>，F表示<因子>，上述文法可以写为：E→T

9、E+TT→F

10、T*FF→(E)

11、i最左推导：E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i

12、+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、考虑文法G[S]：S→aSbS

13、bSaS

14、ε(1)试用最左推导说明此文法的

15、二义性。(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=>ab

16、ab(3)句子abab的两棵分析树：(a)(b)(4)此文法产生的语言是：在{a，b}上由相同个数的a和b组成的字符串。2）给出短语写文法：7、试构造生成下列语言的上下文无关文法：(1)={

17、n≥1,i≥0}。(6)语言={x

18、x∈{a,b,c},x是重复对称排