《《编译原理复习》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《编译原理复习》PPT课件.ppt（34页珍藏版）》请在三一办公上搜索。
1、编译原理复习,西安电子科技大学 软件工程研究所刘 坚,2,课程内容,一、引言二、词法分析三、语法分析四、语法制导翻译生成中间代码五、运行环境,要求,牢固掌握基本概念 灵活使用基本方法 善于归纳总结（抽象能力）,3,第一章 引言,语言的翻译,不同的翻译形式：汇编、编译、转换（预编译）、逆向翻译翻译方法：,4,编译器的基本组成,5,编译器的分析综合模式,编译器的扫描遍数与编译器的编写,6,第二章 词法分析,对于单词的识别，首先应该有单词形成的规则，称为构词规则，然后根据构词规则识别输入序列，称为词法分析。,主要内容 记号、模式与单词 记号的说明模式的形式化描述（正规式与正规集）记号的识别有限自动机
2、 从正规式到词法分析器,滤掉源程序中的无用成分；处理与具体操作系统或机器有关的输入；识别记号并交给语法分析器；调用符号表管理器和出错处理器进行相关处理。,词法分析器是编译器与源程序打交道的唯一阶段，可以被认为是编译器的预处理阶段，它有以下几个重要作用：,7,记号、模式与单词,模式（pattern）：规定单词识别的规则记号（token）：按照某模式识别出的一类单词（记号种类）单词（lexeme）：被识别出的字符串本身词法分析器的输出：记号=记号种类+记号属性,记号的说明模式的形式化描述,正规式与正规集：正规式与正规集的定义（基本正规式、三个运算）；正规式的等价（描述相同的集合）；利用正规式的等价
3、对正规式进行化简（正规式的代数性质）。,用正规式对模式进行形式化描述：如何用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等；正规式的简化形式以及辅助定义与规则。,8,记号的识别有限自动机（FA）,NFA与DFA的定义：M=(S,move,s0,F)；NFA与DFA的表示：定义直接表示、状态转换图、状态转换矩阵；NFA与DFA的关键区别：NFA的不确定性（当前状态下，对同一字符可能有多于一个的下一状态转移）；用NFA识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收、回溯带来的问题；模拟DFA的算法（用DFA识别记号）。,从正规式到词法分析器,构造NFA的Thomps
4、on算法（与NFA定义的对应关系）；模拟NFA的“并行”算法；从NFA构造DFA子集法：smove(S,a)与-闭包(T)的计算；DFA的最小化可区分的概念：所有不可区分的状态看作是一个状态；灵活运用各种方法构造DFA（正规式化简、状态转换图等）,9,第三章 语法分析,语法分析是编译器中的重要阶段之一，可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义：根据一定的规则构成语言的各种结构，即语法规则；根据语法规则识别输入序列（记号流）中的语言结构，即语法分析。,语法分析的分析对象是组成语言的句子，句子具有层次结构的特征，表征该结构的最好方法是树，从而使得对语法的分析就有了从根到叶子和从
5、叶子到根两种分析方法。,主要内容 程序设计语言与文法 有关推导的基本概念 自上而下分析 自下而上分析,10,程序设计语言与文法,正规式与正规文法：正规式与正规文法用于描述线性结构，如构成句子的记号（终结符）；识别正规语言的自动机是有限自动机，它们的特征是没有记忆能力；上下文无关文法（CFG=(N,T,S,P)）：CFG用于描述层次结构，如构成程序的句子；识别CFL的自动机是下推自动机，它是在有限自动机的基础上增加了一个下推栈，从而有了简单的记忆能力；文法的分类：0型、1型、2型和3型文法 词法分析器与语法分析器（FA与PDA）,11,有关推导的基本概念,CFG产生语言的基本方法推导：推导的基本
6、思想是从文法的开始符号开始，反复地用产生式的右部替换句型中的非终结符。推导的基本概念：句子、直接推导、最左推导、左句型（最右推导、右句型）；分析树与语法树：分析树和语法树都反映了语言结构；分析树还记录了分析的过程（含有非终结符）；文法的二义性：二义性的本质是在文法中缺少对文法符号优先级和结合性的限制，从而使得一个句子可以推导出多于一棵分析树。二义性的消除：a.改写二义文法为非二义文法；b.对文法符号施加优先级与结合性的限制，使得分析的每一步有唯一选择。,12,自上而下分析,分析方法：推导，从上到下构造分析树，是一种预测的、试探的方法；对文法的要求：没有公共左因子和左递归；递归下降子程序方法：匹
7、配终结符，展开非终结符（子程序调用）预测分析表方法:a.工作方式与过程：PDA（DPDA）、格局与改变格局的动作；b.预测分析表的构造：FIRST集合与FOLLOW集合，FIRST与FOLLOW的计算；c.LL(1)文法及其判别：预测分析表中没有多重定义条目（推论3.2）。,13,自下而上分析,分析方法：归约（推导的逆过程），从叶子到根构造分析树；基本概念：短语、直接短语、句柄、归约、规范归约；采用的方法:用移进-归约方法实现剪句柄。关键问题是如何确定栈顶已经形成句柄，当句柄形成时，如何判定采用哪个产生式进行规约；识别活前缀的DFA：活前缀与LR(0)项目（NFA状态），拓广文法与子集法构造D
8、FA；,14,自下而上分析（续）,DFA分析输入序列：有效项目、可移进项、可规约项、移进/归约冲突、归约/归约冲突；解决冲突的方法SLR(1)：简单向前看一个终结符（计算归约项非终结符的FOLLOW，与可移进终结符比较）；,移进-归约分析表：动作表转移表；LR文法与LR分析：LR(0)、SLR(1)、LALR(1)、LR(1)。,15,第四章 语法制导翻译生成中间代码,本章讨论的重点是程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。与前两章词法分析和语法分析不同的是，词法分析和语法分析的讨论侧重于理论，而本章则侧重于结合程序设计语言的实际例子讨论语
9、言结构的具体翻译方法和一些实用的技术。,主要内容 语法制导翻译与中间代码 符号表的组织 声明语句的翻译 可执行语句的翻译,16,语法制导翻译与中间代码,语法与语义：语法和语义描述语言的不同方面、二者之间没有严格界线、语义形式化描述的困难性；属性：用属性表示语义特征（语义值），属性的计算和属性之间的依赖关系；语法制导翻译：为产生式配上“语义规则”并在适当的时刻执行；语义规则的两种形式；分析方法与翻译方案：以语法分析为基础，分析树的作用；中间代码：为什么生成中间代码，中间代码的特征，各种形式的中间代码及它们之间的关系，最常用中间代码形式。,符号表的组织,符号表的条目与信息的存储（关键字内容）；作用
10、域信息的保存（栈结构）。,17,声明语句的翻译,定义与声明：类型定义与变量声明，过程定义与过程声明 变量声明：符号表信息的填写过程声明：a.左值与右值b.参数传递：参数传递的不同形式c.名字的作用域：静态作用域与最近嵌套原则d.声明中作用域信息的保存,18,可执行语句的翻译,简单算术表达式和赋值句的翻译：语法制导翻译的设计，类型转换；数组元素的引用：数组元素地址计算的递推公式，地址的可变部分与不变部分，可变部分计算的语法制导翻译；布尔表达式短路计算的翻译：为什么需要短路计算，短路计算的控制流，真出口与假出口，真值链与假值链；控制语句的翻译：控制语句的分类，无条件转移与条件转移，拉链/回填技术；
11、,19,第五章 运行环境,本章介绍程序运行时的空间组织，重点是讨论如何通过对过程的静态分析（包括符号表的利用）建立运行环境，以保证程序的正确执行。,主要内容 过程的动态特性 运行时的存储空间组织 不同的存储分配策略 栈分配策略,20,过程的动态特性,过程、活动、活动的生存期、顺序执行程序的控制流；活动树、控制栈、活动记录；声明的作用域与名字的绑定、变量名字的绑定与常量名字的绑定、左值与右值、“环境”与“状态”、映射的一对多特性；,21,运行时的存储空间组织,运行时内存的划分：可执行代码、静态数据区、栈、堆；活动记录的具体内容：参数与返回或值、控制链（可选）、访问链（可选）、机器状态、局部数据、
12、临时变量等。,存储分配策略,静态分配：简单的分配策略、对语言的限制；栈分配：基于控制栈、可被分配数据的特点、对语言的限制、与静态分配的关系；堆分配：可以任意动态分配和撤销数据空间、用双链表保持可用空间信息、对语言不作限制、分配策略的实现较为复杂。,22,栈分配,控制栈中活动记录的具体内容，两个重要指针top与sp；调用序列与返回序列：调用序列和返回序列的作用、内容；调用序列与返回序列功能的划分；如何设计调用序列与返回序列，以保证控制流的正确转移和活动记录的正确切换；控制链与访问链：控制链与访问链的作用与区别；控制链用于活动记录的正确切换，体现活动的嵌套关系；访问链用于访问非本地数据，体现过程的
13、嵌套关系；访问链的不同实现方法：直接用访问链访问非本地数据；用显示表访问非本地数据；访问链的维护（不同的访问链内容）；,23,关于复习,温度能使鸡蛋孵出鸡子，不能使石头孵出鸡子。从泛泛的内容中归纳出核心和需要牢固掌握的重点不是老师的责任。学习是不能走捷径的。,24,关于作业,作业与上机题的目的：帮助更好地理解基本概念与基本方法，在此基础上，由同学们自己归纳总结出更好的方法。例如等价的问题：,If there is a wrong way to do something,most of people will do it every time.,提交问题的同学刘嵩李昊刘盛华,两类问题一教材与习题
14、答案中的错误二习题解答,25,一教材与习题答案中的错误 教材,23页：例2.7上边两行：将“Msi,sj”改为“Msi,ch”将“.是从状态si到状态sj的边上的标记ch(或)。”改为“.是从状态si经ch(或)到达的下一状态sj。”24页：倒11行：将“Msi,sj”改为“Msi,ch”25页：图2.7最后一行状态“000”应改为“012”34页：算法2.6方法2、3行：将“从si出发”改为“从si出发”，将“称为D的初态”改为“称为D的初态”45页：10行：将“N是仅出现”改为“仅N是可以出现”70页：例3.23：将FOLLOW集合中的“”改为“”75页：到4行：将“文法G3.13”改为“
15、文法G3.12”81页：图3.22：将I0中的“T.-F”改为“F.-F”,26,一教材与习题答案中的错误（续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”
16、改为“L2”，“L2”改为“L1”144页：例4.23上边一行：将“mklist”改为“mkchain”,习题解答4页：2.4(1)：A1A|A0A1A0可以简化为A(1|010)A32页：缺少3.19(1)的解答32页：到2行：将两处“I10”均改为“I11”，将“I12”改为“I13”,越过2003,27,二习题解答2003,习题2.5 合法的日期表示有如下三种形式，请给出描述日期的正规式。日 月 年，如12 08 1992月/日/年，如08/12/1992,解：digit=0-9year=(digit)(digit)(digit)(digit)month=01-9|10-2day=01-
17、9|1-20-9|30-1date1=year.month.day date2=day month yeardate3=month/day/yeardate=date1|date2|date3,正规式描述的是语法，至于语义是否正确，此阶段可以不考虑。日期的语义是一个上下文有关联的复杂问题，除了已经考虑到的年的表示，还有月、日的问题。例如，如果月份是2月，则日期到底应该是28、29、还是30、31？,28,二习题解答2003（续1）,3.6 设字母表=(0,1)，设计下述语言的文法。(2)0和1个数相等的字符串;(3)0和1个数不相等的字符串；解：(2)S0S1S|1S0S|(2)(01|10|
18、00(01|10)*11|11(01|10)*00)*考虑“”，采用S0S1S|1S0S|可得分析树如下：,再考虑：(01|10|00(01|10)*11|11(01|10)*00)*用11(01|10)*00匹配得11(11100010)00 剩余的11100010没有可用的正规式。此串中存在着嵌套与先后两个关系，是正规式无法解决的,29,二习题解答2003（续2）,3.4 对所给文法G：SaSbS|bSaS|（4）设计一等价文法，但它不是二义的。解：SaEbE|EEbTaT|TT,此解无法描述G所产生的语言（看3.6(2)），原因是不递归的文法无法产生长度无限的串，另外此文法也不能正确产生
19、简单的串aabb。,30,二习题解答2004,3.19 假设所讨论的文法是非二义的，说明为什么在规范归约中，非终结符绝不会出现在句柄的右边。解：（解题思路：用反证的方法，假设在规范归约中句柄右边有非终结符，则推出矛盾）假设在规范归约中有句型“.A.”，其中是句柄，A非终结符。根据规范归约定义，A必定是由句型中相对于A的短语归约而来。而A的短语在右边（即先归约了右边的短语），与规范归约矛盾。得证。请进一步思考：为什么假设文法是非二义的？,31,关于考试,题目类型：简答题（20分）、填空题（30分）、计算题（50分）考试范围：15章讲过的内容侧重考察：基本概念与基本方法的掌握,不认真审题（题目的要
20、求理解错误：意思理解错、难题想容易、容易题想难。关键问题是基本概念不清楚）所答非所问（例如：没有要求LL分析，却将文法改为LL的）画蛇添足（例如：仅问有无冲突，却将分析表先构造出来）偷工减料（例如：有若干问，仅回答部分，或问题仅答一半）,易犯的错误,警示千万不要作弊！命运掌握在自己的手中！,32,To know how to do something well is to enjoy it.,战略上藐视敌人，战术上重视敌人。,谢 谢！,The trees that are slow to grow bear the best fruit.,33,95年夜大试题,试证明：若正规集中任何字符串的长
21、度是有限的,则识别该正规集的DFA中无环。,证明：（反证）假设DFA D中有环，不妨设此环为：ni.ni，且沿此环（从ni出发再回到ni）路径的标记为串S，显然|S|0。考察任何一个D所识别的、经过ni的串T=T1T2，其中T1是从初态到ni的路径标记，T2是从ni到终态的路径标记。,显然D也识别任何形如T1SkT2的串，其长度=|T|+k*|S|。当k时，|T|+k*|S|，与任何串长度有限矛盾。,34,中国计算机科学与技术学科教程 2002,程序设计基础 程序设计基本结构（核心）算法与问题求解（核心）基本数据结构（核心）递归（核心）事件驱动程序设计（核心）,程序设计语言 程序设计语言概论（核心）虚拟机（核心）语言翻译简介（核心）声明和类型（核心）抽象机制（核心）面向对象程序设计（核心）函数程序设计（选修）语言翻译系统（选修）程序设计语言的语义（选修）程序设计语言的设计（选修）,
