《编译原理实践及应用》第4章(2)自下而上语法分析

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

第四章( ) 第四章(2)自下而上语法分析方法

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

本章要求 主要内容 自下而上语法分析的概念，规 主要内容：自下而上语法分析的概念， 自下而上语法分析的概念 范归约，算符优先分析方法及其相关概念。 范归约，算符优先分析方法及其相关概念。 重点掌握：掌握自下而上分析的基本思想， 重点掌握：掌握自下而上分析的基本思想， 基本概念，算符优先文法、 基本概念，算符优先文法、算符优先关系 的判定，最左素短语、句柄、 的判定，最左素短语、句柄、活前缀的定 义与判定， 义与判定，求FirstVT集,LastVT集,构造算 集 集 构造算 符优先关系表,能用算符优先分析法进行 符优先关系表 能用算符优先分析法进行 表达式分析

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

例：判定输入串(i+i)*i是否是下述文法的句子？ G = ({E}, {i, +, *, (, ) } , P , E) P: E → E + E : E→ E*E E→ (E) E→i 使用最左推导：E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i 自上而下语法分析采用最左推导，每一步推 自上而下语法分析 结论：自上而下语法分析 导使用哪个产生式要视当前非终结符匹配输入字符串 中的哪个符号来确定。 自下而上语法分析是最左推导的逆过程，由输入符号 自下而上语法分析 串反向推导到文法的开始符号。

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

自下而上的语法分析 实现思想：“移进-归约”方法 实现思想： 移进-归约” –设置一个栈，将输入符号逐个移进 移进栈中，栈 移进 顶形成某产生式的右部时，就用左部去代替， 称为归约 归约。重复这一过程，直到栈中只剩下 归约 文法的开始符号，就确认输入串是文法的句 子，分析成功，否则出错。 –语法树：从树叶开始，逐步向上归约构造分 析树，直到形成根结。是推导的逆过程。 核心 – 寻找句柄 这是关键 寻找句柄(这是关键 这是关键)进行规约。用不同的方法 寻找句柄，就可获得不同的分析方法。

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

最左推导(Left-most Derive)– 每次推导都替换当前句型的最左边的非终结符。— —与最右归约对应

最右推导 最右推导(Right-most Derive)– 每次推导都替换当前句型的最右边的非终结符。— —与最左归约(规范归约)对应，得规范句型 例：设有文法G[S]: (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 使用最右推导： ( 2 ) (1 ) (4 ) (3 ) 因为S aAcBe aAcde aAbcde abbcde,所以 rm rm rm rm abbcde是文法G的句子。

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

最左归约过程是最右推导的逆过程， 对输入串abbcde 的归约过程如下： 2 3 4 5 6 7 8 9 10 步骤 1 移 移 归 移 归 移 移 归 移 归 进 进 约 进 约 进 进 约 进 约 动作 a b 2 b 3 c d 4 e 1 e d b a A a b A A a a c A a B c c A A a a B c A a S

(1)S →aAcBe (2)A →b (3)A →Ab (4)B →

d

a

该分析过程反复执行“移进” 该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。 归约”两个动作，直到栈中只有开始符号为止。

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

这种分析过程具有如下特点： – 从输入串的开始依次读入单词(移进 移进栈中) 。 移进 – 一旦发现可归约串 可归约串(某个产生式的右端)就立即 可归约串 归约。 归约 – 归约 归约就是将栈顶的一串符号用文法产生式的左 部代替，归约可能重复多次 重复多次，然后继续移进。 重复多次 – 若最终能归约成文法的开始符号，则分析成功。 – 由于总是将句型的最左边的可归约串替换成非 终结符，该方法与最右推导对应。 关键是如何判断可归约串？

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

语法分析树的生成演示S S→aAcBe A A→Ab A A→b B B→d (1)S → aAcBe (2)A → b (3)A → Ab (4)B → d

a

b

b

c

d

e

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

问题的提出：① 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 ② 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 通过不同的自底向上的分析算法来解释，不同 的算法对可归约串的定义是不同的，但分析过程 边移进边归约。 都有一个共同的特点：边移进边归约 边移进边归约 规范归约：使用句柄 句柄来定义可归约串。 句柄 算符优先：使用最左素短语 最左素短语来定义可归约串 最左素短语

《编译原理实践及应用》(黄贤英 王柯柯编著)电子教案

规范归约的概念* 有文法G,开始符号为S, 如果有S=>xβy,则xβy 是文法G的句型，x,y是任意的符号串 * + 如果有S=>xAy, 且有A=>β,则β是句型xβy相对 于非终结符A的短语 * 如果有S=>xAy, 且有A->β,则β是句型xβy相对 于A->β的直接短语 位于一个 一个句型最左边的直接短语称为句柄. 一个 注意: 每次归约的部分必须是句柄 (最右推导)。 句柄 关键的问题是如何识别句柄 如何识别句柄

《编译原理实践及应用》(黄 …… 此处隐藏：1915字，全部文档内容请下载后查看。喜欢就下载吧 ……