《《编译原理》总复习.ppt》由会员分享,可在线阅读,更多相关《《编译原理》总复习.ppt(20页珍藏版)》请在三一文库上搜索。
1、编译原理复习,西安电子科技大学 软件工程研究所,缆俭雅缘巩践髓舱慨滤宵泄缮峡霓股巾眠豆瞅门踞碴免娜咋傀灼钮骨亲套编译原理总复习编译原理总复习,2,课程内容,要求(希望) 牢固掌握基本概念 灵活使用基本方法 归纳总结所学内容(锻炼提高抽象能力),一、引言 二、词法分析 三、语法分析 四、语法制导翻译生成中间代码 五、运行环境,学习不能走捷径,付出多少劳动就有多少收获。 掌握正确的学习方法,学会联想与归纳总结。,泽闰号凯操制拳佛摘些瘫崩楔惮搬货岁铣奋连膘办柏衅移挛乌义压辈汉疵编译原理总复习编译原理总复习,3,第一章 引言, 语言的翻译,不同的翻译形式:汇编、编译、转换(预编译)、逆向翻译 翻译方法
2、:,绩填峻式殊谗斗挤哄黑鸽掸榨诀歉议溯铭引彬桶效气瀑朱砸靶狄辙咏社糖编译原理总复习编译原理总复习,4, 编译器的基本组成,鸭挂蚊净似鹰枝宁描株嚼伪您状崇庚虑购耍沿淋亿醛契钓畜哮承纽膘警给编译原理总复习编译原理总复习,5, 编译器的分析综合模式, 编译器的扫描遍数与编译器的编写,鄂钦卸煌阅解茂魄开脖樟芬芥蛙抓讣流龄谩出壤啄悄澳蜜拦常纂抬辅眠埋编译原理总复习编译原理总复习,6,第二章 词法分析,构词规则与词法分析: 首先规定单词形成的规则,称为构词规则;然后根据构词规则识别输入序列,称为词法分析。,主要内容: 记号、模式与单词 记号的说明模式的形式化描述(正规式与正规集) 记号的识别有限自动机 从
3、正规式到词法分析器,词法分析器的作用: 滤掉源程序中的无用成分; 处理与具体操作系统或机器有关的输入; 识别记号并交给语法分析器; 调用符号表管理器和出错处理器进行相关处理。,鼎赫甜耘卑期倦助堂的甥盖召吧晓砾椰寡刺兽挞滚旅脉春粳农赋疡全盐龋编译原理总复习编译原理总复习,7, 记号、模式与单词,模式(pattern):规定单词识别的规则 记号(token):按照某模式识别出的一类单词(记号种类) 单词(lexeme):被识别出的字符串本身 词法分析器的输出:记号=记号种类+记号属性, 记号的说明模式的形式化描述,正规式与正规集: 正规式与正规集的定义(基本正规式、三个运算) 正规式的等价(描述相
4、同的集合) 利用正规式的等价对正规式进行化简(正规式的代数性质) 用正规式对模式进行形式化描述: 如何用正规式描述程序设计语言中常见的记号,如标识符、数字、运算符和分隔符等 正规式的简化形式以及辅助定义与规则,哇胃粕压涛售碳肿氮佳山篱豫矢言卸来额鹊踞廓坤镭迷樱宙订渴羹叫钨蜡编译原理总复习编译原理总复习,8, 记号的识别有限自动机(FA),NFA与DFA的定义:FA = (S, , move, s0, F); NFA与DFA的表示:定义表示、状态转换图、状态转换矩阵; NFA与DFA的关键区别:NFA的不确定性(当前状态下,对同一字符可能有多于一个的下一状态转移); 用NFA识别输入序列的弱点:
5、尝试所有路径才能确定一个输入不被接收、回溯带来的问题; 模拟DFA的算法(用DFA识别记号)。,耸秆淡昨蛙秤幽娇片绢千部绣融玉灶斯军钧黎拨坝嘴祁散蛰关琴眶似穆濒编译原理总复习编译原理总复习, 从正规式到词法分析器,构造NFA的Thompson算法(与NFA定义的对应关系); 模拟NFA的“并行”算法; 从NFA构造DFA子集法: smove(S, a)与-闭包(T)的计算; DFA的最小化可区分的概念:所有不可区分的状态看作是一个状态; 灵活运用各种方法构造DFA(正规式化简、状态转换图等),历乍颧舌棒耳加尝弄光礼律楔孕韵牛剩墟食凰桶旱誊允浮清哲菊孟挂冬鸵编译原理总复习编译原理总复习,10,第
6、三章 语法分析,语法分析是编译器中的重要阶段之一,可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义:根据一定的规则构成语言的各种结构,即语法规则;根据语法规则识别输入序列(记号流)中的语言结构,即语法分析。,语法分析的分析对象是组成语言的句子,句子具有层次结构的特征,表征该结构的最好方法是树,从而使得对语法的分析就有了从根到叶子和从叶子到根两种分析方法。,主要内容 程序设计语言与文法 有关推导的基本概念 自上而下分析 自下而上分析,毯衍懊众素窝惨禁逢烛曰仟髓俏海光鲍袖镑泻怖辙笑篷棋告堪浊随展贤竭编译原理总复习编译原理总复习,11, 程序设计语言与文法,正规式与正规文法:正规式与正规
7、文法用于描述线性结构,如构成句子的记号(终结符);识别正规语言的自动机是有限自动机,它们的特征是没有记忆能力; 上下文无关文法(CFG=(N, T, S, P):CFG用于描述层次结构,如构成程序的句子;识别CFL的自动机是下推自动机,它是在有限自动机的基础上增加了一个下推栈,从而有了简单的记忆能力;,文法的分类:0型、1型、2型和3型文法 词法分析器与语法分析器(FA与PDA),涧铭腾止帚凶谨慧告砸行简蹬焙籽秘缀肩谱碟嘻吾酒撮驴堡彭茵污芯氢蝗编译原理总复习编译原理总复习,12, 有关推导的基本概念,CFG产生语言的基本方法推导:从文法的开始符号开始,反复地用产生式的右部替换句型中的非终结符。
8、 推导的基本概念:句子、直接推导、最左推导、左句型(最右推导、右句型); 分析树与语法树:分析树和语法树都反映了语言结构;分析树还记录了分析的过程(含有非终结符); 文法的二义性:二义性的本质是在文法中缺少对文法符号优先级和结合性的限制,从而使得一个句子可以推导出多于一棵分析树。 二义性的消除: 改写二义文法为非二义文法; 对文法符号施加优先级与结合性的限制,使得分析的每一步有唯一选择。,傅钎纫草屈勿哇逆还修乃卑捞柞物鲸死颅啸跌浩林并喘川翱盂早度砂弄予编译原理总复习编译原理总复习,13, 自上而下分析,分析方法:推导,从上到下构造分析树,是一种预测的、试探的方法; 对文法的要求:没有公共左因子
9、和左递归; 递归下降子程序方法:匹配终结符,展开非终结符(子程序调用) 预测分析表方法: 工作方式与过程:PDA(DPDA)、格局与改变格局的动作; 预测分析表的构造:FIRST集合与FOLLOW集合, FIRST与FOLLOW的计算; LL(1)文法及其判别:预测分析表中没有多重定义条目(推论3.2)。,揉镀杜辗呆揩拔辞抉厌肖甫龄峙笼堪尼峙毅揍惦羹轨歪嫉朽撼兆茅稚烙鞋编译原理总复习编译原理总复习,14, 自下而上分析,分析方法:归约(推导的逆过程),从叶子到根构造分析树; 基本概念:短语、直接短语、句柄、归约、规范归约; 采用的方法: 用移进-归约方法实现剪句柄。关键问题是如何确定栈顶已经形
10、成句柄,当句柄形成时,如何判定采用哪个产生式进行规约; 识别活前缀的DFA:活前缀与LR(0)项目(NFA状态),拓广文法与子集法构造DFA;,玫蔷佩泡蝇牛写眼只泊枫跃湍澡驮稼砖芒干敦拾协束魏毫颅纶贞蓟钱嘘钥编译原理总复习编译原理总复习,15, 自下而上分析(续),DFA分析输入序列:有效项目、可移进项、可规约项、移进/归约冲突、归约/归约冲突;解决冲突的方法SLR(1):简单向前看一个终结符(计算归约项非终结符的FOLLOW,与可移进终结符比较);,2. 移进-归约分析表:动作表转移表; 3. LR文法与LR分析:LR(0)、SLR(1)、LALR(1)、LR(1)。,续变添猎次拧澡薯溶门嘲
11、得朵索癣昔和兼婴扑增褒厨艺设牟谎罐相掐葱双编译原理总复习编译原理总复习,16,第四章 语法制导翻译生成中间代码,本章讨论程序设计语言的静态语义分析,并且在语法分析的基础上生成中间代码,采用的基本方法是语法制导翻译。 与前两章词法分析和语法分析不同的是,词法分析和语法分析的讨论侧重于理论,而本章则侧重于结合程序设计语言的实际例子讨论语言结构的具体翻译方法和一些实用的技术。,主要内容 语法制导翻译与中间代码 符号表的组织 声明语句的翻译 可执行语句的翻译,誊蜕瘤肇菠卤动坏循哗秘晴惯殖伦角铬菏肥翠样锤宝蜜苛谍冠涩炳烽宙聪编译原理总复习编译原理总复习,17, 语法制导翻译与中间代码,语法与语义:语法和
12、语义描述语言的不同方面、二者之间没有严格界线、语义形式化描述的困难性; 属性:用属性表示语义特征(语义值),属性的计算和属性之间的依赖关系; 语法制导翻译:为产生式配上“语义规则”并在适当的时刻执行;语义规则的两种形式; 分析方法与翻译方案:以语法分析为基础,分析树的作用; 中间代码:为什么生成中间代码,中间代码的特征,各种形式的中间代码及它们之间的关系,最常用中间代码形式。,苔止羽鼻罢涸昧滩犊协亮焚寒莱估惟雄琵撤驼兼诌建赦虎溶正猜用租溜夺编译原理总复习编译原理总复习,18, 声明语句的翻译 定义与声明:类型定义与变量声明,过程定义与过程声明 变量声明:符号表信息的填写 过程声明: 左值与右值
13、 参数传递:参数传递的不同形式 名字的作用域:静态作用域与最近嵌套原则 声明中作用域信息的保存,符号表的条目与信息的存储(关键字内容) 作用域信息的保存(栈结构) 线性表与散列表, 符号表的组织,媳恬箱厨歉嗅垦撼你拥铜讹瞥翠湖赐坪冶倦幼赃贬赌致搓瑰怔诌棒假饶素编译原理总复习编译原理总复习,19, 可执行语句的翻译,简单算术表达式和赋值句的翻译:语法制导翻译的设计,类型转换; 数组元素的引用:数组元素地址计算的递推公式,地址的可变部分与不变部分,可变部分计算的语法制导翻译; 布尔表达式短路计算的翻译:为什么需要短路计算,短路计算的控制流,真出口与假出口,真值链与假值链; 控制语句的翻译:控制语句的分类,无条件转移与条件转移,拉链/回填技术;,结 束(串讲),盗传失唁芯户惩时圭峭闻袍汲锻媒籽咨蓬吼胎找攒属怯脯抉洗焰邢纤悦寡编译原理总复习编译原理总复习,结 束(串讲),界耻震张痹亩悯稚熔好宅侮褥拌补底黄货轩让俘卸速忽怕鸦打谴谆艾寻疥编译原理总复习编译原理总复习,
链接地址:https://www.31doc.com/p-5784188.html