编译原理期末总结复习

1、编译原理期末总结复习篇一：一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序 。将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。2.请写出文法的形式定义？答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） 其中Vn表示非终结符号 Vt表示终结符号，VnVt=(字母表)，VnVt= S是开始符号， P是产生式，形如：(V+且至少含有一个非终结符号，V*)3.语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入

2、串是否构成语法上正确的程序。4.局部优化有哪些常用的技术？答：优化技术1删除公共子表达式优化技术2复写传播优化技术3删除无用代码优化技术4对程序进行代数恒等变换（降低运算强度）优化技术5代码外提优化技术6强度削弱优化技术7删除归纳变量优化技术简介对程序进行代数恒等变换（代数简化）优化技术简介对程序进行代数恒等变换（合并已知量）5编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。6. 什么是文法？答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划

3、无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。8.代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果9.词法分析阶段的功能是什么？答：逐个读入源程序字符并按照构词规则切分成一系列单词任务：读入源程序，输出单词符号 滤掉空格，跳过注释、换行符 追踪换行标志，指出源程序出错的行列位置 宏展开，10.什么是符号表？答：符号表在编译程

4、序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方法的好坏会直接影响编译系统的运行效率。11.什么是属性文法？答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。12.什么是基本块答：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其第一个语句，出口是其最

5、后一个语句。13.代码优化阶段的功能是什么？答：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。14.文法分哪几类？答：文法有四种:设有G=(Vn,Vt,P,S),不同类型的文法只是对产生式的要求不同：型文法(短文文法)： G的每个产生式满足：V+且中至少含有一个非终结符,V*型文法(上下文有关文法)：如果G的每个产生式均满足|=|,仅当除外，但S不得出现在任何产生式的右部型文法(上下文无关文法)：G的每个产生式为A, A是一非终结符，V*型文法(正规文法)：G的每个产生式的形式都是：AB或A，其中A,B是非终结符，是终结符串。(右线性文法)。15.循环优化常用的技术有

6、哪些？答：代码外提；强度削弱；删除归纳变量。16.什么是算符优先文法？答：算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有中的一种成立,则G为一算符优先文法。二、计算题（一）推导、最左推导、最右推导和语法树,复习表达式文法及相关例题。1. 表达式的推导例： G = (E, i, +, *, (, ) , P , E)P： E E+E | E*E | (E) | i答：表达式(i)和(i+i)*i的推导：E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*iE E*E E*i (E)* i (E + E)*i

7、 (E+ i)*i (i + i)*i(i+i)*i的最左推导过程：E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i(i+i)*i的最右推导过程：E E*E E*i (E + E)*i (E+ i)*i (i + i)*i2语法树例：对文法G = (E, i, +, *, (, ) , P , E)P： E E + E | E * E | ( E ) | i答： 句子(i+i)*i 的语法树：例： G = (E, i, +, *, (, ) , P , E)P： E E + E | E * E | ( E ) | i答：句子 ( i * i

8、 + i)的语法树：(1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i)（二）给定语言求文法（三）逆波兰式篇二：翻译程序:把一种语言程序转换成另一种语言程序，且在功能上是相同的这样的程序。 编译程序：把高级语言转换成低级语言，且在功能上是相同的这样的程序。解释程序：边解释边执行源程序的程序。区别：编译程序有中间代码，而解释程序没有。 编译过程的五个阶段：1、 词法分析 任务：对构成源程序的字符串进行扫描和分解，识别出一个个单词。2、 语法分析 任务：在词法分析的基础上，根据语言规则，把单词符号串分解成各类语法单位。3、 语义分析和中间代码产生

9、 任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。4、 优化 任务：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。5、 目标代码生成 任务：把中间代码变换成特定机器上的低级语言代码。编译程序的七个部分词法分析器，语法分析器、语义分析与中间代码产生器、优化器、目标代码生成器、表格管理和出错处理。编译程序生成的五个办法：机器语言、高级语言、移植、自编译方式和使用工具自动生成。 词法规则：指单词符号的形成规则。（也就是正规式）语法规则：规定了如何从单词符号形成更大的结构。就是语法单位的形成规则。 空字：不包含任何符号的序列。闭包：中所有的符号组成的集

10、合。上下文无关文法是指：所定义的语法范畴是完全独立于这种范畴可能出现的环境的文法。 上下文无关文法的四个组成部分：一组终结符号、一组非终结符号、一个开始符号和一组产生式。终结符号也就是不可再分的基本符号。非终结符号是用来代表语法范畴，表示一定符号串的集合。开始符号是语言中我们最感兴趣的语法范畴。产生式是定义语法范畴的书写规则。句子：文法中从开始符号推导的终结符号串。句型：从开始符号推导的符号串。语言：文法中所有句子的集合。程序语言的单词符号分为五种：关键字、标识符、常数、运算符和界符。二元式表示：（种类，属性）正规式的运算符有三种：或，连接和闭包。优先顺序是：闭包，连接，或。DFA怎么识别字：

11、若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字是a，则称a可为DFA所识别。DFA怎么识别空字：若DFA的初态结点同时又是终态结点，则空字可为DFA所识别。 NFA怎么识别字：若存在一条从某一初态结点到终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于a，则称a可为NFA识别。NFA怎么识别空字：若M的某些结点即是初态又是终态结点，或者存在一条从某个初态结点到某个终态结点的空通路，那么，空字可为M所识别。语言的语法结构是用上下文无关文法描述的。语法分析分为两类：自上而下分析法，自下而上分析法。自上而下分析法面临的问题：1.文法的左递归问题。2.回溯3.

12、成功可能是暂时的，产生虚假匹配。4.难于知道输入串中出错的确切位置。5.效率低，代价高。为什么消除左递归？因为含有左递归的文法将自上而下分析的过程陷入无限循环。 为什么消除回溯？因为回溯统一做一大堆无效的工作。自下而上分析法：从输入串开始，逐步进行归约，知道归约到文法的开始符号。 短语：符号串推导过程中某非终结符推导的部分。直接短语：符号串推导过程中某非终结符一步推导的部分。句柄：一个句型的最左直接短语。最左归约是最有推导的逆过程。中间语言形式：后缀式，三元式，四元式，间接三元式。中间语言的好处：1.便于进行与机器无关的代码优化工作。2.使编译程序改变目标机更容易。3.使编译程序的结构在逻辑上

13、更为简单，以中间语言为界面，编译前端和后端的借口更清晰。篇三：(1)程序设计语言机器语言: 由0、1代码构成，不需翻译就可直接执行其程序。汇编语言: 机器指令助记符（伪代码）形式，汇编后才可执行其程序。高级程序设计语言: 类自然语言和数学公式形式(2) 基本术语源程序(Source Program)：用源语言写的程序。源语言可以是汇编语言，也可以是高级程序设计语言。目标程序(Target Program) ：也称为“结果程序”，是源程序经翻译程序加工以后所生成的程序。目标程序可以用机器语言表示，也可以用汇编语言或其它中间语言表示。翻译程序(Translating Program)：是指把一个源

14、程序翻译成逻辑上等价的目标程序的程序。源程序为其输入，目标程序为其输出。汇编程序(Assembler)：是指把一个汇编语言写的源程序转换成等价的机器语言表示的目标程序的翻译程序。编译程序(Compiler)：若源程序是用高级程序设计语言所写，经翻译程序加工生成目标程序，则该翻译程序就称为“编译程序”，也可称为编译器。解释程序：是高级语言翻译程序的一种，他将源语言书写的源程序作为输入，解释一句后就提交计算机执行一句，并不形成目标程序，就像外语翻译中的“口译”一样，不产生全文的翻译文本。运行系统(Running System)：目标程序执行时，需要有一些子程序（如一些连接装配程序及一些连接库等）配

15、合进行工作，由这些子程序组成的一个子程序库称为运行系统。 编译系统(Compiling System)：编译程序和运行系统合称编译系统。(3) 程序的翻译除机器语言程序外，用其它语言书写的程序都必须经过翻译才能被计算机识别。这一过程由翻译程序来完成。编译方式是一种分阶段进行的方式，包括翻译和运行两部分。前一阶段：翻译后一阶段：运行，由运行系统配合完成。(4) 过程1、词法分析阶段这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号TOKEN）。某源程序片断如下：begin var sum, first, count:

16、 real; sum:=first+count*10 end.保留字 begin var real end标识符 sumfirstcountsumfirstcount界符 .逗号，逗号,冒号：分号；加号+乘号*赋值号 ：=整数10 102、语法分析阶段是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称语法单位，或语法成分，或语法范畴。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。3、语义分析阶段依据语言的语义规则，对语法分析得到的语

17、法结构分析其含义以及应进行的运算，审查源程序中有无语义错误，为代码生成阶段收集类型信息。4、中间代码生成在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源程序转变成一种内部表示形式，这种内部表示形式叫做中间代码。所谓“中间代码”是一种结构简单，含义明确的记号系统，这种记号系统可以设计为多种多样的形式。重要的设计原则：一是容易生成；二是容易将它翻译成目标代码。5、代码优化任务：对前阶段产生的中间代码系列进行变换或改造。目的是使生成的目标代码更高效，即省时间省空间。例如上例四个四元式可优化为下面两个四元式。6、目标代码生成任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的指令

18、代码或汇编指令代码。它的工作与硬件系统结构和指令含义有关。7、表格管理编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；8、出错处理如果编译过程中发现源程序有错误，编译程度应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。(5) 前端与后端参考上面的图，目的是为了在多种源语言和多种目标语言的开发过程中，可以灵活搭配组合，消除重复开发的工作量，提高编译系统的开发效率。(6) 遍所谓遍，是对源程序或

19、源程序的中间形式从头到尾扫视并完成规定任务的过程。每一遍扫视可完成一个阶段或多个阶段的功能。一遍的编译程序：以语法分析程序为核心 。多遍扫描的优点：可以减少内存容量的需求，分遍后，以遍为单位分别调用编译的各个程序，各遍程序可以相互覆盖。可使各遍的编译程序相互独立，结构清晰。能够进行充分优化，产生高质量的目标程序。可将编译程序分为前端和后端，有利于编译程序的移植。多遍扫描的缺点每遍都要读符号、送符号，增加了许多重复性的工作，降低编译效率。(7) 程序设计语言范型（从支持的计算模式）1. 强制(命令)式语言:是面向动作的，即一个计算过程看做是一系列动作，其动作是命令驱动，以语言形式表示。也称过程式

20、语言，如C,FORTRAN等;2. 函数式语言：注重程序表示的功能也称应用式语言，如ML和LISP等；3. 基于规则的语言：检查一定的使能条件，满足时执行动作也称逻辑程序设计语言，如PROLOG。4. 面向对象语言：提供抽象数据类型，支持封装性、继承性和多态性。如C+和Java等。(1) 符号和符号串1、 字母表：元素的有穷非空集合。2、 符号串：由字母表中的符号组成的任何有穷序列。3、 符号串的头尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。 如:设z=abc，那么z的头是，a, ab, abc, 除a

21、bc外，其它都是固有头；z的尾是, c, bc, abc, z的固有尾是, c, bc。4、 符号串的运算（1）符号串的连接：设x和y是符号串，x和y的连接xy是把y的符号写在x的符号后得的符号串。如：x=ST, y=abu, 则xy=STabu显然有x=x=x。（2）符号串的方幂：设x是符号串，把x自身连接n次得x的几次方幂xn。如：设x=ab则x0=x1=abx2=ababx3=ababab（3）符号串集合的乘积：设A和B为符号串集合，则A和B的乘积定义为AB=xy|xA且yB如：a=a, b, B=00, 11 则AB=a00, a11, b00, b11 显然：A=A=A（4）符号串集

22、合的方幂：设A为符号串集，则A的n次方幂An定义为:An=AAA=AAn-1=An-1A（5）符号串集合的正闭包A+：A+=A1 U A2 U U An U （6）符号串集合的闭包A*：A*=A0 U A+ = U A+如：设有正字母表=0，1 则*=0 U 1 U 2 U U n U =, 0, 1, 00,01, 10, 11, 000, 001,(2) 文法文法G定义为四元组（VN ，VT，P，S）其中:（1）VN 为非终结符号集非终结符号表示一个语言短语（或语法成分、语法单位）。 如 程序、语句、表达式等。一般用大写字母或用 括起表示非终结符号。（2）VT 为终结符号集终结符号：组成语

23、言的基本符号。是文法中不属于非终结符号集合的符号。一般用小写字母或不带 的符号表示。如程序设计语言的单词符号。设V=VN U VT，称V为文法G的字母表。（3）P 为产生式（也称规则）的集合。产生式的形式：或=，其中V+，V*（4）S 称作识别符号或开始符号，是一个非终结符号。一般表示此文法定义的最大语法短语，至少要在一条产生式 中作为左部出现。 句型、句子的定义设GS是一文法，如果符号串x是从识别符号推导出来的，即有S*x， 则称x是文法GS的句型。若x仅由终结符号组成，即S*x, xV T ，则称x为GS的句子。句型：在一棵树生长过程的任何时刻，所有那些端末结点自左至右的排列，就是一个句型

24、。语言的定义：文法G产生的语言记为L（G），它是文法G产生的全部句子的集合。 文法等价定义：若L（G1）=L（G2）则称文法G1和G2是等价的。(3) 文法的类型 N.Chomsky0型文法：定义0型语言，对应Turing机；1型文法：定义1型语言，对应线性限界自动机；箭头后面的要比前面的长或相等 2型文法：定义2型语言，对应非确定下推自动机；箭头前面的是非终结符，后面是串 3型文法：定义3型语言，对应有限自动机。非终结符可以推出一个终结符或一个终结符和一个非终结符最右推导也称为规范推导，所得句型称为规范句型。如果一个文法存在某个句型对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文

25、法中存在某个句型，它有两个不同的最左（最右）推导，则这个文法是二义的。上下文无关文法是否具有二义性是不可判定的。但有些特殊的2型文法例如LL（1）、LR（0）、LR（1）等文法是无二义性的。 一个文法兼有左递归和右递归是导致二义性的常见原因。排除文法二义性通常有两种方法:（1）在语义上加些限制（2）重新构造一个无二义性的文法(4) 句型的分析句型的分析：就是识别一个符号串是否为某文法的句型。是某个推导的构造过程。 分析方法分两大类：自上而下分析法和自下而上分析法推导与归约，最右推导是规范推导，逆过程为规范规约若S*A+（由A+得）则称是句型相对于非终结符A的短语。若S*A(由A得)则称是句型相对于A的直接短语（也称简单短语）。 一个句型的最左直接短语称为该句型的句柄。一棵子树（至少要有父子两代）的所有端末结点自左至右排列起来形成相对于子树根的短语。若子树只有父子两代，则得到直接短语。(5) 有关文法（1）有害规则 文法中含形如UU的产生式。它对描述语言没有必要，且会引起文法的二义性。（2）多余规则 文法中任何一个句子的推导都用不到的规则。（3）无用规则 文法中含形如UV的产生