《编译原理复习》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理复习,西安电子科技大学 软件工程研究所,刘 坚,课程内容,一、引言,二、词法分析,三、语法分析,四、语法制导翻译生成中间代码,五、运行环境,要求,牢固掌握基本概念,灵活使用基本方法,善于归纳总结（抽象能力）,2,第一章 引言,语言的翻译,不同的翻译形式：汇编、编译、转换（预编译）、逆向翻译,翻译方法：,3,编译器的基本组成,4,编译器的分析综合模式,编译器的扫描遍数与编译器的编写,5,第二章 词法分析,对于单词的识别，首先应该有单词形成的规则，称为,构词规则,，然后根据构词规则识别输入序列，称为,词法分析,。,主要内容,记号、模式与单词,记号的说明模式的形式化描述（正规式与正规集）,记号的识别有限自动机,从正规式到词法分析器,滤掉源程序中的无用成分；,处理与具体操作系统或机器有关的输入；,识别记号并交给语法分析器；,调用符号表管理器和出错处理器进行相关处理。,词法分析器是编译器与源程序打交道的唯一阶段，可以被认为是编译器的预处理阶段，它有以下几个重要作用：,6,记号、模式与单词,模式（,pattern,）：,规定单词识别的规则,记号（,token,）：,按照某模式识别出的一类单词（记号种类）,单词（,lexeme,）：,被识别出的字符串本身,词法分析器的输出：记号=记号种类+记号属性,记号的说明模式的形式化描述,正规式与正规集：,正规式与正规集的定义（,基本正规式、三个运算,）；,正规式的等价（,描述相同的集合,）；,利用正规式的等价对正规式进行化简（,正规式的代数性质,）。,用正规式对模式进行形式化描述：,如何用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等；,正规式的简化形式以及辅助定义与规则。,7,记号的识别有限自动机（,FA,）,NFA,与,DFA,的定义：,M=(S,move,s0,F),；,NFA,与,DFA,的表示：定义直接表示、状态转换图、状态转换矩阵；,NFA,与,DFA,的关键区别：,NFA,的不确定性（当前状态下，对同一字符可能有多于一个的下一状态转移）；,用,NFA,识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收、回溯带来的问题；,模拟,DFA,的算法（用,DFA,识别记号）。,从正规式到词法分析器,构造,NFA,的,Thompson,算法（与,NFA,定义的对应关系）；,模拟,NFA,的“并行”算法；,从,NFA,构造,DFA,子集法：,smove,(S,a),与,-,闭包,(,T),的计算；,DFA,的最小化可区分的概念：所有不可区分的状态看作是一个状态；,灵活运用各种方法构造,DFA,（,正规式化简、状态转换图等）,8,第三章 语法分析,语法分析是编译器中的重要阶段之一，可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义：根据一定的规则构成语言的各种结构，即,语法规则,；根据语法规则识别输入序列（记号流）中的语言结构，即,语法分析,。,语法分析的分析对象是组成语言的句子，句子具有层次结构的特征，表征该结构的最好方法是树，从而使得对语法的分析就有了,从根到叶子,和,从叶子到根,两种分析方法。,主要内容,程序设计语言与文法,有关推导的基本概念,自上而下分析,自下而上分析,9,程序设计语言与文法,正规式与正规文法：正规式与正规文法用于描述线性结构，如构成句子的记号（终结符）；识别正规语言的自动机是有限自动机，它们的特征是没有记忆能力；,上下文无关文法（,CFG=(N,T,S,P),）：,CFG,用于描述层次结构，如构成程序的句子；识别,CFL,的自动机是下推自动机，它是在有限自动机的基础上增加了一个下推栈，从而有了简单的记忆能力；,文法的分类：0型、1型、2型和3型文法,词法分析器与语法分析器（,FA,与,PDA,）,10,有关推导的基本概念,CFG,产生语言的基本方法推导：推导的基本思想是从文法的开始符号开始，反复地用产生式的右部替换句型中的非终结符。,推导的基本概念：句子、直接推导、最左推导、左句型（最右推导、右句型）；,分析树与语法树：分析树和语法树都反映了语言结构；分析树还记录了分析的过程（,含有非终结符,）；,文法的二义性：二义性的本质是在文法中缺少对文法符号优先级和结合性的限制，从而使得一个句子可以推导出多于一棵分析树。,二义性的消除：,a.,改写二义文法为非二义文法；,b.,对文法符号施加优先级与结合性的限制，使得分析的每一步有唯一选择。,11,自上而下分析,分析方法：推导，从上到下构造分析树，是一种预测的、试探的方法；,对文法的要求：没有公共左因子和左递归；,递归下降子程序方法：匹配终结符，展开非终结符（,子程序调用,）,预测分析表方法:,a.,工作方式与过程：,PDA（DPDA）,、,格局与改变格局的动作；,b.,预测分析表的构造：,FIRST,集合与,FOLLOW,集合，,FIRST,与,FOLLOW,的计算；,c.,LL(1),文法及其判别：预测分析表中没有多重定义条目（推论3.2）。,12,自下而上分析,分析方法：归约（推导的逆过程），从叶子到根构造分析树；,基本概念：短语、直接短语、句柄、归约、规范归约；,采用的方法:用移进-归约方法实现剪句柄。关键问题是如何确定栈顶已经形成句柄，当句柄形成时，如何判定采用哪个产生式进行规约；,识别活前缀的,DFA,：,活前缀,与,LR(0),项目,（,NFA,状态），拓广文法与子集法构造,DFA,；,13,自下而上分析（续）,DFA,分析输入序列：有效项目、可移进项、可规约项、移进/归约冲突、归约/归约冲突；解决冲突的方法,SLR(1),：,简单向前看一个终结符（计算归约项非终结符的,FOLLOW,，,与可移进终结符比较）；,移进-归约分析表：动作表转移表；,LR,文法与,LR,分析：,LR(0)、SLR(1)、LALR(1)、LR(1),。,14,第四章 语法制导翻译生成中间代码,本章讨论的重点是程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。,与前两章词法分析和语法分析不同的是，词法分析和语法分析的讨论侧重于理论，而本章则侧重于结合程序设计语言的实际例子讨论语言结构的具体翻译方法和一些实用的技术。,主要内容,语法制导翻译与中间代码,符号表的组织,声明语句的翻译,可执行语句的翻译,15,语法制导翻译与中间代码,语法与语义：语法和语义描述语言的不同方面、二者之间没有严格界线、语义形式化描述的困难性；,属性：用属性表示语义特征（语义值），属性的计算和属性之间的依赖关系；,语法制导翻译：为产生式配上“语义规则”并在适当的时刻执行；语义规则的两种形式；,分析方法与翻译方案：以语法分析为基础，分析树的作用；,中间代码：为什么生成中间代码，中间代码的特征，各种形式的中间代码及它们之间的关系，最常用中间代码形式。,符号表的组织,符号表的条目与信息的存储（关键字内容）；,作用域信息的保存（栈结构）。,16,声明语句的翻译,定义与声明：类型定义与变量声明，过程定义与过程声明,变量声明：符号表信息的填写,过程声明：,a.,左值与右值,b.,参数传递：参数传递的不同形式,c.,名字的作用域：静态作用域与最近嵌套原则,d.,声明中作用域信息的保存,17,可执行语句的翻译,简单算术表达式和赋值句的翻译：语法制导翻译的设计，类型转换；,数组元素的引用：,数组元素地址计算的递推公式,，地址的可变部分与不变部分，可变部分计算的语法制导翻译；,布尔表达式短路计算的翻译：为什么需要短路计算，,短路计算的控制流,，真出口与假出口，真值链与假值链；,控制语句的翻译：控制语句的分类，无条件转移与条件转移，拉链/回填技术；,18,第五章 运行环境,本章介绍程序运行时的空间组织，重点是讨论如何通过对过程的静态分析（包括符号表的利用）建立运行环境，以保证程序的正确执行。,主要内容,过程的动态特性,运行时的存储空间组织,不同的存储分配策略,栈分配策略,19,过程的动态特性,过程、活动、活动的生存期、顺序执行程序的控制流；,活动树、控制栈、活动记录；,声明的作用域与名字的绑定、变量名字的绑定与常量名字的绑定、左值与右值、“环境”与“状态”、映射的一对多特性；,20,运行时的存储空间组织,运行时内存的划分：可执行代码、静态数据区、栈、堆；,活动记录的具体内容：参数与返回或值、控制链（可选）、访问链（可选）、机器状态、局部数据、临时变量等。,存储分配策略,静态分配：简单的分配策略、对语言的限制；,栈分配：基于控制栈、可被分配数据的特点、对语言的限制、与静态分配的关系；,堆分配：可以任意动态分配和撤销数据空间、用双链表保持可用空间信息、对语言不作限制、分配策略的实现较为复杂。,21,栈分配,控制栈中活动记录的具体内容，两个重要指针,top,与,sp,；,调用序列与返回序列：调用序列和返回序列的作用、内容；调用序列与返回序列功能的划分；如何设计调用序列与返回序列，以保证控制流的正确转移和活动记录的正确切换；,控制链与访问链：控制链与访问链的作用与区别；控制链用于活动记录的正确切换，体现活动的嵌套关系；访问链用于访问非本地数据，体现过程的嵌套关系；,访问链的不同实现方法：直接用访问链访问非本地数据；用显示表访问非本地数据；访问链的维护（不同的访问链内容）；,22,关于复习,温度能使鸡蛋孵出鸡子，不能使石头孵出鸡子。,从泛泛的内容中归纳出核心和需要牢固掌握的重点不是老师的责任。,学习是不能走捷径的。,23,关于作业,作业与上机题的目的：帮助更好地理解基本概念与基本方法，在此基础上，由同学们自己归纳总结出更好的方法。,例如等价的问题：,If there is a wrong way to do something,most of people will do it every time.,提交问题的同学,刘嵩李昊刘盛华,两类问题,一教材与习题答案中的错误,二习题解答,24,一教材与习题答案中的错误,教材,23页：例2.7上边两行：将“Msi,sj,”改为“Msi,ch,”,将“.是从状态si到状态sj的边上的标记ch(或,)。”改为“.是从状态si经ch(或,)到达的下一状态sj。”,24页：倒11行：将“Msi,sj,”改为“Msi,ch,”,25页：图2.7最后一行状态“0,00,”应改为“0,12,”,34页：算法2.6方法,2、3行：将“从,si,出发”改为“从,si,出发”，将“称为,D,的初态”改为“称为,D,的初态”,45页：10行：将“N是仅出现”改为“仅N是可以出现”,70页：例3.23：将FOLLOW集合中的“”改为“,”,75页：到4行：将“文法,G3.13,”改为“文法,G3.12,”,81页：图3.22：将I0中的“T,.-F”改为“F,.-F”,25,一教材与习题答案中的错误（续1）,教材,100页：图4.2：将,A.code=(3)“(,x,:=,(2)”,改为“,(,:=,x,(2)”,129页：例4.17的中间代码：将“t3:=+,r,t4”改为“t3:=,C,+,r,t4”,133页：例4.18的中间代码：将“t5:=t3*,t4,”改为“t5:=t3*,4,”，将“,V7,”改为“,V5,”,134页：图4.16：将“,V5、V6、V7,”分别改为“,V6、V7、V5,”,136页：4.7.3上边一行：将“ptr.data,/=,x”改为“ptr.data,=,x”,138页：例4.20：将代码序列中的“L1”改为“L2”，“L2”改为“L1”,144页：例4.23上边一行：将“mklist”改为“mkchain”,习题解答,4页：2.4(1)：A1A|A0A1A0可以简化为A(1|010)A,32页：缺少3.19(1)的解答,32页：到2行：将两处“I10”均改为“I11”，将“I12”改为“I13”,越过2003,26,二习题解答2003,习题2.5 合法的日期表示