《编译原理复习》PPT课件.ppt
《《编译原理复习》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,可执行语句的翻译,简单算术表达式和赋值句的翻译:语法制导翻译的设计,类型转换;数组元素的引用:数组元素地址计算的递推公式,地址的可变部分与不变部分,可变部分计算的语法制导翻译;布尔表达式短路计算的翻译:为什么需要短路计算,短路计算的控制流,真出口与假出口,真值链与假值链;控制语句的翻译:控制语句的分类,无条件转移与条件转移,拉链/回填技术;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理复习 编译 原理 复习 PPT 课件
链接地址:https://www.31ppt.com/p-5569015.html