编译原理总复习部门： xxx时间： xxx整理范文，仅供参考，可下载自行编辑alphabet字母表 symbol符号 string串 length长度 catenation连接power方幂 gather集合 product乘积 empty set空集 closure 闭包program程序 logic structure逻辑结构 generating产生 executing执行b5E2RGbCAPmachine language机器语言 instruction指令 function函数 assembler汇编程序p1EanqFDPwinterpreter解释程序 translator翻译程序 source language源语言 finite 有穷的DXDiTa9E3dsource program源程序 target language目标语言attribute属性 possess占有RTCrpUDGiTpreprocess预处理 compiler编译程序 break中断 Intermediate language中间语言5PCzVD7HxAdefinition定义 reconstructed重构 normal正规 character sequences 符号序列jLBHrnAILgprogramming language程序设计语言 operand操作数 instead替换 memory内存xHAQX74J0Xelement元素 high-level language高级语言 object program目标程序LDAYtRyKfEaddress地址 input输入 output输出 terminal终结符 compilation编辑Zzz6ZB2Ltkequivalence等价 nonterminal非终结符 recursion递归 deterministic确定的dvzfvkwMI1nondeterministic非确定的 Backus-Normal Form巴科斯范式 syntax语法rqyn14ZNXItree树 expression表达式 grammar文法 automata自动机 prefix前缀EmxvxOtOcosuffix后缀 infix中缀 identify识别 identifier标识符 analyses分析SixE2yXPq5predigest化简 symbol set符号集 performed执行 forecast预测 state 状态6ewMyirQFLformula产生式 conversion变换 precedence优先 simple简单 handle句柄kavU42VRUsoperator算符 terminal state终态 first state初态 optimizer优化程序y6v3ALoS89concatenation连接 word单词 alphabet字母表 lexical词法 scanner扫描器M2ub6vSTnPanalyzer分析器 syntax tree语法树 symbol table符号表 pass趟，遍0YujCfmUCwregular expression正规表达式 code generator代码生成器 backdate回溯eUts8ZQVRdderivation推导 educe推导 derivation tree推导树 path路径 ambiguous 二义性sQsAEJkW5Tsimple phrase简单短语 context-sensitive上下文有关 context-free上下文无关GMsIasNXkAright-linear 右线形phrase-structured短语结构regular grammar文法TIrRGchYzgdirect derivation直接推导 sentence句子 sentential form句型 root node根结点7EqZcWLZNXsubtree子树 semantic语义的 terminal node端末结点attribute grammar属性文法canonical derivation规范推导 top-down自上而下 bottom-up自下而上lzq7IGf02Eviable prefix活前缀nondeterminate finite automata非确定的有穷自动机zvpgeqJ1hk总复习一、基本概念：1、请简单解释编译程序的概念。
答：编译程序是现代计算机系统的基本组成部分之一。
简而言之, 编译程序就是一种语言翻译程序。
所谓翻译程序，是指这样一个程序，它能将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言> 程序。
编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。
NrpoJac3v12、请解释编译程序的前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？ (10分>答：编译程序的前端只依赖于源语言，由几乎独立于目标机器的阶段或阶段的一部分组成。
编译程序的前端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序及相关的表格管理程序和出错处理程序。
编译程序的后端是指编译器中依赖于目标机器的部分,它们一般独立于源语言，而与中间代码有关。
通常包括目标代码生成程序、代码优化程序以及相关的表格管理程序和出错处理程序。
1nowfTG4KI3、语言的语法描述方法有其三，请列举出来。
答：用自然语言描述语言的语法，用语法图描述语言的语法和用巴科斯-瑙尔范式及扩充的巴科斯-瑙尔范式 (EBNF>两种形式给出语言的语法描述。
fjnFLDa5Zo 答：根据 Chomcky文法的定义，该文法是2类文法，即上下文无关文法。
4、请写出Chomcky关于文法的定义。
答： Chomcky文法的定义：文法G定义为四元组,记为:G=(VN,VT,P,S>其中：VN—非空有限的非终结符号集VT—非空有限的终结符号集P —产生式集S —开始符号/识别符号5、已知文法：<20分）E→X|E+XX→Y|X*YY→<E）|i请判定该文法是那类文法？5、简单说明词法分析程序的主要任务。
答：词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。
tfnNhnE6e56、请简单介绍确定的有穷自动机。
答：确定的有穷自动机也称有限自动机，它是作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。
具体而言，一个确定的有穷自动机可以用一个五元组表示，即M=(K,Σ,f, S,Z>。
K是一个有穷状态集，Σ是一个有穷字母表，f是转换函数，S是初态，Z是一个终态集。
HbmVN777sL7、简单说明语法分析程序。
答：语法分析程序是编译程序的核心部分。
语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序>，目前语法分析常用的方法有自顶向下<自上而下）分析和自底向上<自下而上）分析两大类。
V7l4jRB8Hs8、请说明有关句型、句子、句柄概念？<10分）答：设G[S]是一文法，如果符号串x是从文法的识别符号推导出来的，则称符号串x是文法G[S]的句型。
若符号串x还满足仅由终结符号组成的条件，则称x为G[S]的句子。
一个句型的最左直接短语称为该句型的句柄。
83lcPA59W99、请说明有关规范句型的概念？答：最右推导，即推导的每一步都是替换当前句型最右边的非终结符，被称为规范推导，由规范推导得到的句型称为规范句型。
mZkklkzaaP10、请说明有关预测符号集的概念？答：产生式A→α预测符号集表示：在确定的自上而下的语法分析过程中，当需要替换的非终结符是A时，而当前需要匹配的终结符属于产生式A→α预测符号集中的符号，则能够采用该产生式进行推导。
当α不能推出ε时，产生式A→α预测符号集是α的首符号集；当α能推出ε时，产生式A→α预测符号集是α的首符号集与A的后跟符号集的并集，但是不包括ε。
AVktR43bpw11、简单说明LR分析器由那几部分组成？答：简单而言LR分析器由3部分组成，它们是：总控程序、分析表<ACTION表和GOTO表）和分析栈<符号栈和状态栈）。
ORjBnOwcEd12、简单说明拓广文法、活前缀和可归前缀的概念？答：拓广文法：在原文法中增加一个产生式，Ｓ′→Ｓ，得到的新文法称之为原文法的拓广文法；活前缀：在规范句型中，不包括该句型句柄右边符号的前缀称之为活前缀；可归前缀：活前缀与句柄有3种关系，：活前缀不含句柄的任何符号；：活前缀含有句柄的部分符号；：活前缀包含句柄的全部符号。
包含句柄的全部符号的活前缀称之为可归前缀。
2MiJTy0dTT13、请简单说明编译中的语义处理。
答：编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。
有时把这个工作称为静态语义分析或静态审查。
第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式<中间代码），或者将源程序翻译成目标代码。
gIiSpiue7A14、编译程序所使用的中间代码经常见的有那几种形式？答：编译程序所使用的中间代码常见的有逆波兰记号、三元式、四元式和树形表示。
15、简单说明代码优化的概念。
答：所谓代码优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。
uEh0U1Yfmh16、简单说明代码生成器的概念。
答；代码生成器是把某种高级程序设计语言编写的程序经过语法、语义分析，或再经过优化后的中间代码作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器。
IAg9qLsgBX二、应用题<每题10分，共40分）1、文法G<S）的产生式为：S→aAS,A→SbA,A→aA,A→b,S→a,请写出该文法的非终结符号集、终结符号集及文法的开始符号，根据文法画出句型aSbSbaAa的语法树，并且指出该句型的短语、直接短语和句柄？WwghWvVhPE答：该文法的非终结符号集是{S,A}、终结符号集是{a,b}及文法的开始符号是{S}句型aSbSbaAa的语法树为：该句型的短语为：aA,SbaA, SbSbaAa, aSbSbaAa,a直接短语为：aA, a句柄为：aA2、正规式为：b((ab>*|bb>ba，请根据所列正规式，画出对应的NFA的状态转换图，并且将NFA确定化，画出对应的DFA的状态转换图。
