编译原理总结

(1)程序设计语言•机器语言:由0、1代码构成，不需翻译就可直接执行其程序。•汇编语言:机器指令助记符（伪代码）形式，汇编后才可执行其程序。•高级程序设计语言:类自然语言和数学公式形式(2)基本术语•源程序(SourceProgram)：用源语言写的程序。源语言可以是汇编语言，也可以是高级程序设计语言。•目标程序(TargetProgram)：也称为“结果程序”，是源程序经翻译程序加工以后所生成的程序。目标程序可以用机器语言表示，也可以用汇编语言或其它中间语言表示。•翻译程序(TranslatingProgram)：是指把一个源程序翻译成逻辑上等价的目标程序的程序。源程序为其输入，目标程序为其输出。•汇编程序(Assembler)：是指把一个汇编语言写的源程序转换成等价的机器语言表示的目标程序的翻译程序。•编译程序(Compiler)：若源程序是用高级程序设计语言所写，经翻译程序加工生成目标程序，则该翻译程序就称为“编译程序”，也可称为编译器。•解释程序：是高级语言翻译程序的一种，他将源语言书写的源程序作为输入，解释一句后就提交计算机执行一句，并不形成目标程序，就像外语翻译中的“口译”一样，不产生全文的翻译文本。•运行系统(RunningSystem)：目标程序执行时，需要有一些子程序（如一些连接装配程序及一些连接库等）配合进行工作，由这些子程序组成的一个子程序库称为运行系统。•编译系统(CompilingSystem)：编译程序和运行系统合称编译系统。(3)程序的翻译•除机器语言程序外，用其它语言书写的程序都必须经过翻译才能被计算机识别。这一过程由翻译程序来完成。•编译方式是一种分阶段进行的方式，包括翻译和运行两部分。•前一阶段：翻译•后一阶段：运行，由运行系统配合完成。(4)过程1、词法分析阶段这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号TOKEN）。某源程序片断如下：beginvarsum,first,count:real;sum:=first+count*10end.保留字beginvarrealend标识符sumfirstcountsumfirstcount界符.逗号，逗号,冒号：分号；加号+乘号*赋值号：=整数10102、语法分析阶段是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称语法单位，或语法成分，或语法范畴。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。3、语义分析阶段依据语言的语义规则，对语法分析得到的语法结构分析其含义以及应进行的运算，审查源程序中有无语义错误，为代码生成阶段收集类型信息。4、中间代码生成在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源程序转变成一种内部表示形式，这种内部表示形式叫做中间代码。所谓“中间代码”是一种结构简单，含义明确的记号系统，这种记号系统可以设计为多种多样的形式。重要的设计原则：一是容易生成；二是容易将它翻译成目标代码。5、代码优化任务：对前阶段产生的中间代码系列进行变换或改造。目的是使生成的目标代码更高效，即省时间省空间。例如上例四个四元式可优化为下面两个四元式。6、目标代码生成任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。它的工作与硬件系统结构和指令含义有关。7、表格管理编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；8、出错处理如果编译过程中发现源程序有错误，编译程度应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。(5)前端与后端参考上面的图，目的是为了在多种源语言和多种目标语言的开发过程中，可以灵活搭配组合，消除重复开发的工作量，提高编译系统的开发效率。(6)遍所谓遍，是对源程序或源程序的中间形式从头到尾扫视并完成规定任务的过程。每一遍扫视可完成一个阶段或多个阶段的功能。一遍的编译程序：以语法分析程序为核心。多遍扫描的优点：可以减少内存容量的需求，分遍后，以遍为单位分别调用编译的各个程序，各遍程序可以相互覆盖。可使各遍的编译程序相互独立，结构清晰。能够进行充分优化，产生高质量的目标程序。可将编译程序分为前端和后端，有利于编译程序的移植。多遍扫描的缺点每遍都要读符号、送符号，增加了许多重复性的工作，降低编译效率。(7)程序设计语言范型（从支持的计算模式）1.强制(命令)式语言:是面向动作的，即一个计算过程看做是一系列动作，其动作是命令驱动，以语言形式表示。也称过程式语言，如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,除abc外，其它都是固有头；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|xA且yB}如：a={a,b},B={00,11}则AB={a00,a11,b00,b11}显然：{}A=A{}=A（4）符号串集合的方幂：设A为符号串集，则A的n次方幂An定义为:An=AA……A=AAn-1=An-1A（5）符号串集合的正闭包A+：A+=A1UA2U…UAnU…（6）符号串集合的闭包A*：A*=A0UA+={}UA+如：设有正字母表={0，1}则*=0U1U2U…UnU…={,0,1,00,01,10,11,000,001,……}(2)文法文法G定义为四元组（VN，VT，P，S）其中:（1）VN为非终结符号集非终结符号表示一个语言短语（或语法成分、语法单位）。如程序、语句、表达式等。一般用大写字母或用〈〉括起表示非终结符号。（2）VT为终结符号集终结符号：组成语言的基本符号。是文法中不属于非终结符号集合的符号。一般用小写字母或不带〈〉的符号表示。如程序设计语言的单词符号。设V=VNUVT，称V为文法G的字母表。（3）P为产生式（也称规则）的集合。产生式的形式：→或∷=，其中∈V+，∈V*（4）S称作识别符号或开始符号，是一个非终结符号。一般表示此文法定义的最大语法短语，至少要在一条产生式中作为左部出现。句型、句子的定义设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有S*x，则称x是文法G[S]的句型。若x仅由终结符号组成，即S*x,xVT，则称x为G[S]的句子。句型：在一棵树生长过程的任何时刻，所有那些端末结点自左至右的排列，就是一个句型。语言的定义：文法G产生的语言记为L（G），它是文法G产生的全部句子的集合。文法等价定义：若L（G1）=L（G2）则称文法G1和G2是等价的。(3)文法的类型N.Chomsky0型文法：定义0型语言，对应Turing机；1型文法：定义1型语言，对应线性限界自动机；箭头后面的要比前面的长或相等2型文法：定义2型语言，对应非确定下推自动机；箭头前面的是非终结符，后面是串3型文法：定义3型语言，对应有限自动机。非终结符可以推出一个终结符或一个终结符和一个非终结符最右推导也称为规范推导，所得句型称为规范句型。如果一个文法存在某个句型对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中存在某个句型，它有两个不同的最左（最右）推导，则这个文法是二义的。上下文无关文法是否具有二义性是不可判定的。但有些特殊的2型文法[例如LL（1）、LR（0）、LR（1）等文法]是无二义性的。一个文法兼有左递归和右递归是导致二义性的常见原因。排除文法二义性通常有两种方法:（1）在语义上加些限制（2）重新构造一个无二义性的文法(4)句型的分析句型的分析：就是识别一个符号串是否为某文法的句型。是某个推导的构造过程。分析方法分两大类：自上而下分析法和自下而上分析法推导与归约，最右推导是规范推导，逆过程为规范规约若S*A+（由A+得）则称是句型相对于非终结符A的短语。若S*A(由A→得)则称是句型相对于A→的直接短语（也称简单短语）。一个句型的最左直接短语称为该句型的句柄。一棵子树（至少要有父子两代）的所有端末结点自左至右排列起来形成相对于子树根的短语。若子树只有父子两代，则得到直接短语。(5)有关文法（1）有害规则文法中含形如U→U的产生式。它对描述语言没有必要，且会引起文法的二义性。（2）多余规则文法中任何一个句子的推导都用不到的规则。（3）无用规则文法中含形如U→V的产生式，即单产生式。为保证文法G的任一非终结符A在句子推导中出现，必须满足如下两个条件：（1）A必须在某句型中出现，A。（2）必须能够从A推导出终结符号串t。有关文法的化简和改造，包括以下几项工作：（１）无用符号和无用产生式的删除。（２）－产生式的消除。（３）单产生式的消除。（４）左递归的消除。(1)词法分析输出单词符号（TOKEN)是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分成下列5种：1．基本字，也称关键字，如PASCAL语言中的begin，end，if，while和var等。2．标识符，用来表示各种名字，如常量名、变量名和过程名等。3．常数，各种类型的常数，如25，3.1415，TRUE和ABC等。4．运算符，如+，*，=等。5．界符，如逗点，分号，括号等。词法分析程序所输出的单词符号常常采用下二元式表示：（单词种别，单词自身的值）可用整数码或助记符等表示。(2)单词的描述工具程序设计语言中的单词(TOKEN)是基本语法符号。单词符号的语法可以用有效的工具加以描述。正规式和它所表示的正规集的递归定义如下。设字母表为∑，辅助字母表∑={|,·,*,(,)}定义（正规式和它所表示的正规集）：设字母表为Σ，辅助字母表Σ`={Φ，ε，|，·，*，(，}。②ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和{}；②任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；③假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1|e2,e1·e2,e1*也都是正规式,它们所表示的正规集分别为L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))*。④仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。(3)有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。确定的有穷自动机（DFA）：定义：一确定的有穷自动机（DFA）M是一个五元组：M=（K，∑，f,S,Z）其中1．K