编译原理复习文档.docx

1、编译原理复习文档编译原理复习总结 题型：填空、选择、简答题、综合题第一章 编译器概述复习要点： 1、编译程序的总框架，编译程序工作的大致过程。 2、理解一下概念：编译、解释、翻译、编译前端、后端、遍 计算机执行用高级语言编写的程序主要有两种途径：解释和编译 编译：专指由高级语言转换为低级语言 编译和解释的区别： 是否产生目标程序 编译程序的五个阶段：词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成 此外还包括：表格处理和出错处理 第二章 词法分析复习要点： 1、了解词法分析器的任务 2、掌握状态转换图 3、正规式：与正规集的转换，判断等价 4、有限自动机：NFA确定化、DFA最简

2、化、正规式到DFA的转换 词法分析器（扫描器）的任务：从源程序中识别出一个个具有独立含义的最小语法单位。 扫描器的输出格式：二元式序列（单词种别，单词符号的属性值） 状态转换图：结点代表状态，用圆圈表示。状态之间用箭弧连结，弧上的标记指明在射出弧的结点状态下可能出现的输入字符 初始状态 接受状态 正规式和有限自动机 正规式和正规集的转换 给出正规式，要求写出相应的NFA、DFA 给出正规集，要求写出相应的NFA、DFA 1、正规式和正规集 三种运算： “”读为“或”， “ ”读为“连接” “*”读为“闭包” 转换 正规式等价： 两个正规式所表示的正规集相同，则称两个正规式等价令是一个有限字母表

3、，则上的正规式及其表示的集合递归定义如下:1. 和都是上正规式，它们表示的正规集为和2. 若a是上的字符，则a是正规式，它表示的正规集为a3. 若r和s都是上的正规式，他们表示的正规集记为L(r)和L(s)，则（a） r|s是正规式，表示集合L(r)L(s)，（b） rs是正规式，表示集合L(r)L(s)，（c） r*是正规式，表示集合(L(r)*，（d）(r)是正规式，表示的集合仍然是L(r)。（加括弧改变优先级、结合性） 有限自动机1、确定的有限自动机 M=(S，S0，F) 其中:1. S 有穷状态集2. 输入字母表3. 映射函数(也称状态转换函数) SS (s,a)=S , S, S S

4、, a4. s0 唯一的初始状态 s0 S5. F终止状态集 ZS2、不确定的有限自动机 M= (S, ,S0, F) 其中:1. S 有限状态集（非终极符集合）；2. 输入字母表（终极符集合）；3. 转换函数S () P(S)， 即S *到S的幂集(2S)的一种映射；4. S0 唯一的初始状态集合 （非空）S0S5. F终止状态集合 FSDFA是NFA的特例，对于每个NFA M存在一个DFA M”，使L(M)=L(M”)。 NFA的确定化 ：子集法 具有转移的NFA确定化 DFA的化简：分割法 一个有穷自动机是化简的 它没有多余状态并且它的状态中没有两个是互相等价的。对于任一个DFA，存在一

5、个唯一的状态最少的等价的DFA不含弧的NFA确定化举例例：把右图确定化I0 = 0 (I0,a) = 0,1 = I1(I0,b) = 1 = I2(I1,a) = 0,1 = I1 (I1,b) = 1 = I2 (I2,a) = 0 = I0 (I2,b) = 例：化简下图，使其最小化。 从正规式到有限自动机1、从正规式构造NFA 2、把NFA变成DFA 3、将DFA化简 正规式分裂规则：第三章 语法分析（自上而下） 语法分析器的任务： 按照语言的语法构成规则，识别输入的符号串能否构成一个句子 语法分析的理论基础 上下文无关文法和下推自动机文法：描述语言语法结构的形式规则。乔姆斯基（Cho

6、msky）对文法的分类： 0型文法 1型文法 2型文法 3型文法文法 G = (VT , VN, S, P) 0型文法： ， , (VN VT)*, | | 1 1型文法：| | | |，但S 可以例外 2型文法：A ，AVN , (VN VT)* 3型文法：A aB或A a，A, BVN , a VT 短语文法、上下文有关文法、上下文无关文法、正规文法 分析树：表示语言的句子结构，推导的图形表示（1）子树：除叶子结点之外的任意结点连同它的所有子孙结点构成子树。（2）句型：在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。（3）短语：子树的末端符号自左到右连成串，相对于子

7、树树根而言称为短语。 简单短语（直接短语）：若短语事某子树根经过1步推导得到的，则称之为该子树根的简单短语。 （4）句柄：句型中的最左简单短语。 注：句柄是最左归约时要寻找的简单短语。 自上而下：消除左递归： 消除直接左递归： P Pa| 消除后：P P P P| 消除间接左递归： 自上而下语法分析包括：递归下降分析程序和预测分析程序预测分析程序：预测分析表是一矩阵MA,a，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素MA,a是存放A的一个侯选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。 求首符集（First集）假定是文

8、法G的一个符号串， V* ，则First()a| a,a VT 注：1)若 ,那么 First()。 2)First()集合是的所有可能推导出的开头终结符或所组成的集合。 求随符集（Follow集）假定S是文法G的开始符号，对于G的任何非终结符A，Follow(A)a|S Aa,a VT 注：1)若 SA,则规定：# Follow(A)。 2)Follow(A)集合是指在所有句型中紧跟A之后的终结符或#所组成的集合。 LL(1)文法：若文法G的预测分析表M中不含有多重定义项，则称G为LL (1)文法。注：1)LL(1)文法是无二义的，二义文法一定不是LL(1)文法。 2) LL的含义是从左到右

9、扫描输入串，采用最左推导分析句子。 3)数字1表示分析句子时需向前看一个输入符号。证明定理 文法G是LL(1)文法当且仅当对于G的每个非终结符A的任何两个不同产生式A |有： 1）First() First()= 2）若 First() ，则First() Follow(A)= 第四章 自下而上语法分析 分析过程思想：是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到达到文法的开始符号为止的过程。 LR：自左至右扫描，最右推导的逆过程。 LR分析法寻找可归约句柄的依据 历史： 记录在栈内的符号串移进、归约的历史情况 展望： 预测句柄之后可能出现的信息； 现实： 读头下的符号。

10、 LR分析法通过LR分析器来实现。 LR分析器包括两部分：总控程序和分析表；分析表LR分析器的核心 分析表构成： 动作表(ACTION) 、转向表(GOTO) 注：Si表示状态， ai表示终结符，Ai表示非终结符。 动作表ACTION ACTIONS,a表示在当前状态S下，面临读头下的符号a所应采取的动作。 注：该动作有四种可能：移进、归约、出错、 接受 转向表GOTO GOTOS,X：若X VT ，表示在当前状态下，读入X应转向什么状态；若X VN ，表示当前栈顶句柄归约成X后，应转向什么状态。 注：表中符号的含义： Sj ： Shift j，指将读入符号a移进栈内并转到j状态，栈顶变成（j

11、,a）； rj ： Reduce j,按第j号产生式进行归约； acc ： accept , 分析成功； 空白格 ：出错标志，若填入相应出错处理程序的编号，便转到相应程序处理。 构造LR(0)分析表的基本思想： 只根据历史信息识别呈现于栈顶的句柄。 注：LR(0)分析表构造的思想和方法是构造其它LR分析表的基础。 构造LR(0)分析表的基本策略： 构造文法G的一个有限自动机，它能识别文法中的所有活前缀。 活前缀的概念： 指规范句型的一个前缀，这种前缀不含句柄之后的任何符号活前缀有两种类型： 1）归态活前缀： 活前缀的尾部正好是句柄之 尾，这时可以进行归约。归约之后又成为另一句型的活前缀。 2）

12、非归态活前缀：句柄尚未形成，需要继续移进若干符号之后才能形成句柄。 构造自动机识别活前缀 对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀。 由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，此“状态”称为“项目”。这些自动机的全体就是能识别所有活前缀的有限自动机。项目: 在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目（简称项目）。注：圆点在产生式中的位置不同则是不同项目。 （1）可以把圆点理解为栈

13、内外的分界线。 （2）产生式右部符号串的长度为n，则可以分解为n+1个项目。 （3）产生式A只有一个项目A。 LR(0)分析表的构造算法 构造LR(0)分析表 设C=I0,I1,In,以各项目集Ik(k0，,n)的k作为状态序号，并以包含SS的项目集作为初始状态，同时将G文法的产生式进行编号。然后按下列步骤填写ACTION表和GOTO表： 1)若项目Aa属于Ik状态且GO(Ik,a)= Ij,a为终结符，则置ACTIONk,a=Sj; 即：移进a，并转向Ij状态。 2)若项目AIk,则对任何终结符a(包括语句结束符),置ACTIONk,a=rj; 其中，j为产生式A 的编号，即根据j号产生式进

14、行归约。 3)若项目S S属于Ik, 则置ACTIONk,=accept,简写为acc; 4)若GO(Ik ，A)= Ij,A是非终结符，则置GOTOk,A=j; 5)分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。 LR(0)文法定义：若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是LR(0)文法。SLR分析表SLR是LR(0)的一种改进，它在归约 时除了考虑历史情况之外还考虑了一点现实。 构造SLR分析表的算法 设C=I0,I1,In,以各项目集Ik(k0，,n)的k作为状态序号，并以包含S S的项目集作为初始状态，同时将产生式进行编号。然后按下列步骤填写A

15、CTION表和GOTO表： 1)若项目Aa属于Ik状态且GO(Ik,a)= Ij,a为终结符，则置ACTIONk,a=Sj; 即：移进a，并转向Ij状态。 2)若项目A Ik,则对任何终结符a Follow(A),置ACTIONk,a=rj；其中j为产生式A的编号，即根据j号产生式A进行归约。 3)若项目S S属于Ik, 则置ACTIONk,=acc; 4)若GO(Ik ，A)=Ij,A是非终结符，则置GOTOk,A=j; 5)分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。注：1）若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是SLR文法。 2)二义文法决不是

16、LR文法。 3) SLR分析法包含的展望信息是体现在利用了Follow(A)信息，可以解决“归约-归约”冲突 4) SLR分析法没有包含足够的展望信息，不能完全解决“移进-归约”冲突，需要改进。语法制导翻译和中间代码生成 中间代码四种形式 逆波兰式 四元式：最常用的形式 三元式 树形表示法后缀表示式(逆波兰表达式) Operand1 Operand2 Operator四元式形式: (Operator,Operand1,Operand2,Result)控制语句中布尔式E翻译成的四元式为以下三种： (jnz,A1,_,P) If A1 then goto P (j,A1, A2,P) If A1A

17、2 then goto P (j, _, _ ,P) Goto P 注：这些四元式都是转移四元式，其中P为出口的四元式序号。与E的真假值相对应的分别为“真出口”和“假出口”两类四元式。 例如：把语句if ABD then S1 else S2 翻译成四元式 解: (1)(jnz,A,_,(5) ;真出口；若A为真，执行S1代码 (2)(j,_,(3) ;若A为假，看右边的表达式值 (3)(j目标语言编译：专指由高级语言转换为低级语言。程序设计语言编译程序机器语言解释：接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。特点：1编译器：工作效率高，即

18、时间快、空间省；交互性与动态特性差、可移植性差。大多数PL采用此种方法翻译2解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Java等。基本功能：二者相同所采用的技术：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。1.1 词法分析任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。 单词：是高级语言中有实在意义的最小语法单位，它由字符构成。词法分析依照词法规则，识别出正确的单词，转换成统一规格，备用。转换对基本字、运算符、界限符的转换 标识符的转换 常数的转换 转换完成后的格式：（单词种别，单词符号的属性值）二元式表

19、示 （单词种别，单词符号的属性值） 描述词法规则的有效工具是正规式和有限自动机。1.2 语法分析任务：根据语言的语法规则，把单词流组成各类语法单位，如：短语、句子、过程、程序语法规则：语言的规则，又称为文法；规定单词如何构成短语、语句、过程和程序。 语法规则通常用上下文无关文法描述。position := initial + rate * 60;表达式的语法特征： 任何一个标识符都是表达式； 任何一个数都是表达式； 如果e1和e2都是表达式，那么 e1 + e2 e1 * e2 (e1)也都是表达式 语法分析有两种方法：推导(Derive)和规约(Reduce) 语法分析过程也可以用一棵倒着的

20、树来表示，这棵树叫做分析树1.3 语义分析 任务：检查程序的语义正确性，以保证程序各部分能有意义的结合在一起，为以后的代码生成阶段收集类型信息 语义分析阶段的重要工作：类型检查1.4 中间代码生成 任务：根据语义规则产生一种介于源语言与目标代码之间的一种中间代码。中间代码是不依赖于机器但是又便于生成依赖于机器的目标代码的一种结构简单、含义明确的记号系统 中间代码形式：逆波兰式、 四元式、三元式1.5 代码优化任务：对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码。原则：等价变换 主要方面：公共子表达式的提取、合并已知量、删除无用语句、循环优化等。 1.6 目标代码生成任

21、务：把经过优化的中间代码转化成特定 机器上的低级语言代码 目标代码的形式 绝对指令代码:可立即执行的目标代码。 汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行。 可重定位指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。1.7 符号表管理表格作用：用来记录源程序的各种信息以及编译过程中的各种状况。与编译前四阶段有关的表格有： 符号表、常数表、标号表、分程序入口表、中间代码表等。 符号表：用来登记源程序中的常量名、变量名、数组名、过程名等，记录它们的性质、定义和引用情况。 1.8 错误诊断和报告任务：如果源程序有错误，编译程序应

22、设法发现错误，并报告给用户。完成：由专门的出错处理程序来完成 错误类型： 语法错误:在词法分析和语法分析阶段检测出来。 语义错误：一般在语义分析阶段检测。1.9 阶段的分组编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。注：遍与阶段的含义毫无关系。要在某机器上为某种语言构造一个编译程序，必须掌握下面三个方面的内容：源语言，目标语言，编译方法。 本章小结：基

23、本概念：翻译器、编译器、解释器、源语言、目标语言、前端、后端、遍。编译过程分哪些阶段？各个阶段完成的主要功能和采用的主要方法。第二章 词法分析 词法分析器：实现词法分析的程序 词法分析的任务：从左至右扫描源程序的字符串，按照词法规则识别出源程序中具有独立含义的最小语法单位单词。 和用户接口的其他任务： -滤掉注释和（由空格、制表符等引起的）空白 -其他预处理工作 词法分析器作为一个独立的子程序2.1 单词及属性2.1.1 词法记号、模式、词法单元 词法记号：按照某个模式（或规则）识别出的元素（一组）。 如：关键字、算符、标识符、常数、标点符号、字符串词法单元：被识别出的元素，又称单词，源程序中

24、具有独立含义的最小语法单位。模式：产生和识别元素的规则。词法记号 词法单元举例 模式的非形式描述 var var var for for for relation , = , = , 或 0）例1：例如 x=ST，y=abu，则它们的连接xy=STabu，看出x=2，y=3，xy=5例2：符号串自身连接n次得到的符号串 an 定义为 aaaa n个a a1=a, a2=aa且a0=例3：若x=AB 则：x0 = ，x1 =AB，x2 = ABAB，x3 = ABABAB，xn = xxn-1 = xn-1x (n0) 语言的运算-合并：L M = s | s L 或 s M -连接：LM =

25、st | s L 且 t M-指数：L0是 ，Li是Li -1L -闭包：L = L0 L1 L2 -正闭包： L+ = L1 L2 例：若 L=a, b, M=c, d则 LM=ac, bc, ad, bd， L*=, a, b, aa, bb, ab, ba, aaa, .，L+= a, b, aa, bb, ab, ba, aaa, .。2.2.2 正规式正规式：又称正规表达式，是描述单词构造方法的一种形式化工具，每个正规式r表示一个语言L(r)，正规式表示的语言叫正规集。 下面是正规式和它所表示的正规集的递归定义。令是一个有限字母表，则上的正规式及其表示的集合递归定义如下: 1. 和都是上正规式，它们表示的正规集为