编译原理总复习 (2).doc

《编译原理总复习 (2).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、总复习一、基本概念：1、请简单解释编译程序的概念。答：编译程序是现代计算机系统的基本组成部分之一。简而言之,编译程序就是一种语言翻译程序。所谓翻译程序，是指这样一个程序，它能将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。2、请解释编译程序的前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？(10分)答：编译程序的前端只依赖于源语言

2、，由几乎独立于目标机器的阶段或阶段的一部分组成。编译程序的前端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序及相关的表格管理程序和出错处理程序。编译程序的后端是指编译器中依赖于目标机器的部分,它们一般独立于源语言，而与中间代码有关。通常包括目标代码生成程序、代码优化程序以及相关的表格管理程序和出错处理程序。3、语言的语法描述方法有其三，请列举出来。答：用自然语言描述语言的语法，用语法图描述语言的语法和用巴科斯-瑙尔范式及扩充的巴科斯-瑙尔范式(EBNF)两种形式给出语言的语法描述。答：根据Ch

3、omcky文法的定义，该文法是2类文法，即上下文无关文法。4、请写出Chomcky关于文法的定义。答：Chomcky文法的定义：文法G定义为四元组,记为:G=(VN,VT,P,S)其中：VN—非空有限的非终结符号集VT—非空有限的终结符号集P—产生式集S—开始符号/识别符号5、已知文法：（20分）E→X

4、E+XX→Y

5、X*YY→（E）

6、i请判定该文法是那类文法？5、简单说明词法分析程序的主要任务。答：词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。6、请简

7、单介绍确定的有穷自动机。答：确定的有穷自动机也称有限自动机，它是作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。具体而言，一个确定的有穷自动机可以用一个五元组表示，即M=(K,Σ,f,S,Z)。K是一个有穷状态集，Σ是一个有穷字母表，f是转换函数，S是初态，Z是一个终态集。7、简单说明语法分析程序。答：语法分析程序是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上

8、（自下而上）分析两大类。8、请说明有关句型、句子、句柄概念？（10分）答：设G[S]是一文法，如果符号串x是从文法的识别符号推导出来的，则称符号串x是文法G[S]的句型。若符号串x还满足仅由终结符号组成的条件，则称x为G[S]的句子。一个句型的最左直接短语称为该句型的句柄。9、请说明有关规范句型的概念？答：最右推导，即推导的每一步都是替换当前句型最右边的非终结符，被称为规范推导，由规范推导得到的句型称为规范句型。10、请说明有关预测符号集的概念？答：产生式A→α预测符号集表示：在确定的自上而下的语法分析过程中，当

9、需要替换的非终结符是A时，而当前需要匹配的终结符属于产生式A→α预测符号集中的符号，则能够采用该产生式进行推导。当α不能推出ε时，产生式A→α预测符号集是α的首符号集；当α能推出ε时，产生式A→α预测符号集是α的首符号集与A的后跟符号集的并集，但是不包括ε。11、简单说明LR分析器由那几部分组成？答：简单而言LR分析器由3部分组成，它们是：总控程序、分析表（ACTION表和GOTO表）和分析栈（符号栈和状态栈）。12、简单说明拓广文法、活前缀和可归前缀的概念？答：拓广文法：在原文法中增加一个产生式，Ｓ′→Ｓ，得到

10、的新文法称之为原文法的拓广文法；活前缀：在规范句型中，不包括该句型句柄右边符号的前缀称之为活前缀；可归前缀：活前缀与句柄有3种关系，：活前缀不含句柄的任何符号；：活前缀含有句柄的部分符号；：活前缀包含句柄的全部符号。包含句柄的全部符号的活前缀称之为可归前缀。13、请简单说明编译中的语义处理。答：编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程

11、序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。14、编译程序所使用的中间代码经常见的有那几种形式？答：编译程序所使用的中间代码常见的有逆波兰记号、三元式、四元式和树形表示。15、简单说明代码优化的概念。答：所谓代码优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。16、简单说明代