西北工业大学编译原理第五章 自下而上的语法分析

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

课程内容 第一章 概论 第二章 词法分析 第三章上下文无关文法及分析(语法结构的 描 述工具) 第四章自上而下的语法分析 第五章自下而上的语法分析 第六章语义分析 第七章运行时环境(与目标代码生成有关) 第八章代码生成(主要讲解中间代码的生成) 第九章 代码优化machunyan 西北工业大学软件与微电子学院 1

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

第5章 自下而上的语法分析 5.1 自下而上的语法分析概览 5.2 LR分析概览 5.3 LR(0)项目的有穷自动机与LR(0)分析 5.4 SLR(1) 分析 5.5 一般的LR(1) 5.6 LALR(1)分析 5.7 语法分析器自动生成工具—YACC

作业machunyan 西北工业大学软件与微电子学院 2

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

5.1 自下而上的语法分析概览 自下而上语法分析方法： 从输入单词序列开始，自左至右逐步进行归

约，试图将其归约为文法的开始符号。 从输入单词序列开始，以单词做为语法树的 叶节点，自底向上地构造语法分析的结果---语法树。

machunyan

西北工业大学软件与微电子学院

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

5.1 自下而上的语法分析概览(续)例:文法G: S → cAd A → ab A→a试采用自下而上的语法分析方法识别输入串cabd是 否是该文法所定义的句子？

machunyan

西北工业大学软件与微电子学院

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

5.1 自下而上的语法分析概览(续)A S A

c a b d c a b d c a b d 自左至右规约的过程： cabd cAd cAd S 自左至右规约是规范推导的逆过程, 所以称之 为规范规约。machunyan 西北工业大学软件与微电子学院 5

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

5.1 自下而上的语法分析概览(续)对于文法G[S]:S aAcBe A b A Ab B d 建立输入串abbcde的规范推导： S aAcBe aAcde aAbcde abbcde r r r r 规范归约是规范推导的逆过程： abbcde aAbcde aAcde aAcBe S

machunyan

西北工业大学软件与微电子学院

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

5.1 自下而上的语法分析概览(续) 在自下而上语法分析工作的每一步，都是从 当前串中选择一个子串，将它归约到某个非 终结符号； 为了方便对自下而上的语法分析方法进行描 述，本章将每次规约的子串称为句柄；

machunyan

西北工业大学软件与微电子学院

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

理解句柄文法G[S] 句型α β δ 的直接短语： 若有S =>*αAδ αβ δ,α、β、δ (VN VT)* 则称β 是句型α β δ 相对于非终结符A 的直接短语; β δ 的句柄： 句型的最左直接短语(在规范推导中，最先被归约 的子串),称为该句型的句柄;

句型α

machunyan

西北工业大学软件与微电子学院

西北工业大学编译原理课件第五章 自下而上的语法分析

例5.1:已知文法G[E]:E→E+T|T T→T*F|F F→(E)|i

第5章 自下而上的语法分析

E E +T T *

TF

求句型i*i+i 的直接短语和句柄

直接短语： i1 , i2 , i3句柄： i1

F i3 i2

F i1

machunyan

西北工业大学软件与微电子学院

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

5.1 自下而上的语法分析概览(续) 总结本节内容： 自下而上的语法分析算法通常采用规范 归约，即规范推导的逆过程； 规范规约的每一步是从当前的规范句 型中将句柄归约为相应的非终结符；

machunyan

西北工业大学软件与微电子学院

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

第5章 自下而上的语法分析 5.1 自下而上的语法分析概览 5.2 LR分析概览 5.3 LR(0)项目的有穷自动机与LR(0)分析 5.4 SLR(1) 分析 5.5 一般的LR(1) 5.6 LALR(1)分析 5.7 语法分析器自动生成工具—YACC

作业machunyan 西北工业大学软件与微电子学院 11

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

5.2 LR 分析概览 LR分析法是一种有效的自下而上的语法分 析技术，它能适用于大部分上下文无关文法 的分析，一般叫LR(k)分析方法，其中 L是指自左(Left)向右分析输入单词序列， R是指分析过程都是构造最右(Right)推导的逆过 程(规范归约), 括号中的k是指在决定当前分析动作时向右看的 单词个数。

machunyan

西北工业大学软件与微电子学院

西北工业大学编译原理课件第五章 自下而上的语法分析

第5章 自下而上的语法分析

5.2 LR 分析概览(续) 有以下原因使得 LR分析法与其它语法分析方法相 比，应用更广泛，具有更强的吸引力。 应用面广：能够通过LR分析程序识 …… 此处隐藏：1207字，全部文档内容请下载后查看。喜欢就下载吧 ……