第07章 自底向上LR分析法New.pptVIP

第7章　自底向上LR分析法 7.1 LR分析概述 7.2 LR(0)分析 7.3 SLR(1)分析 7.4 LR(1)分析 7.5 LALR(1)分析 华中科技大学计算机 编译原理 编译原理 主讲教师：周时阳 本章研究自底向上的LR分析法，LR分析法是一类归约法的统称，主要介绍其中最基本的LR(0)、SLR(1)、LR(1)和LALR(1)四种分析法，重点讨论可归约前缀的作用、识别活前缀DFA的构造、分析表的构造、分析法适用条件和语法分析程序结构及其分析算法。 内容摘要 7.1　LR分析概述 7.2　LR(0)分析 7.3　SLR(1)分析 7.4　LR(1)分析 7.5　LALR(1)分析 重点讲解 小结 寻找句柄是根据向右查看输入串的K个符号，结合分析所处的“状态”，确定句柄是否出现在分析栈顶部。 LR分析法也称为LR(K)分析法。这里，L表示从左到右扫描输入串，R表示最右推导之逆过程(即规范归约)，K表示向右查看输入串符号的个数。 这类自底向上的语法分析法，其总体框架可以划分为总控程序、分析栈和分析表三个组成部分，如下图所示。 目录 （符号栈） （状态栈） 分析栈S 总控程序 x · · · # a1a2 a3 a4···ai－1 ai ai+1 ··· an－1 an # 输入栈I （ACTION） q · · · q0 （GOTO） 分析表M 文法 (规则集) 假设文法G[S]和分析表M，状态0为开始状态，q为状态栈S.Q栈顶元素；a为输入栈I栈顶元素，则总控程序的算法如下： ⑴ 初始化：“0#”进栈S； ⑵ 移进：如果M.ACTION[q,a]为sj，则 将“ja”进栈S，输入栈I出栈，转到步骤⑵； ⑶ 归约：如果M.ACTION[q,a]为ri，则 (3.1) 令第i条规则为A→α。将︱α︱个状态和符号退出分析栈S； (3.2) 令q′为此刻状态栈S.Q栈顶元素。如果M.GOTO[q′,A]为状态j，将“ja”进栈S，转到步骤⑵；否则M.GOTO[q′,A]为e k，转入出错处理ERROR()； ⑷ 报错：如果M.ACTION[q,a]为e k，则 转入出错处理ERROR()； ⑸ 接受：如果M.ACTION[q,a]为acc，则 输出“OK”，结束。 例7.1 设文法G[S]定义如右，并已知分析表M见表7.1，其中表中空白出表示e k。试给出输入串abbcde的LR分析过程。 VT∪VN G[S]：⑴ S→aAcBe ⑵ A→b ⑶ A→Ab ⑷ B→d 目录 7.2.1 可归前缀和活前缀 以例7.1定义文法G[S]为例，讨论LR分析法的基本原理，同时将提出可归前缀和活前缀重要概念。 目录 G[S]：⑴ S→aAcBe ⑵ A→b ⑶ A→Ab ⑷ B→d G[S]：⑴ S→aAcBe[1] ⑵ A→b[2] ⑶ A→Ab[3] ⑷ B→d[4] S?aAcBe[1]?aAcd[4]e[1]?aAb[3]cd[4]e[1]?ab[2]b[3]cd[4]e[1] ab[2]b[3]cd[4]e[1] ?aAb[3]cd[4]e[1] ?aAcd[4]e[1] ?aAcBe[1] ? S 如果使用分析栈实现这个过程，则方法也很简单：将输入串符号移进分析栈，直到遇到“编号”为止；这时，句柄出现在分析栈顶部，令编号代表的规则是A→α，将分析栈顶部︱α︱个符号出栈，A进栈便完成一次归约。重复这些步骤，直到归约出S。 即：尾符号恰好是句柄β尾符号的文法规范句型之前缀，称为可归前缀，可归约前缀之前缀称为活前缀。 G[S]：⑴ S→aAcBe ⑵ A→b ⑶ A→Ab ⑷ B→d 例如文法G[S]，句型aAbcde的句柄为Ab，活前缀有：ε、a、aA和aAb，其中，aAb为可归前缀。 定义7.1 将符号串的任意含有头符号的子串称为前缀。特别地，空串ε为任意串的前缀。 定义7.2 设文法G[S]，如果S?αAω?αβω是句型αβω的规范推导，则αβ称为可归前缀，αβ的前缀称为活前缀。 * R R 目录 假设事先知道文法所有规范句型可归前缀，使用分析栈实现分析的具体步骤修改为： 将输入串符号移进分析栈，直到分析栈出现“可归前缀”为止；这时，句柄出现在分析栈顶部，令可归前缀编号代表的规则是A→α，将分析栈顶部︱α︱个符号出栈，A进栈便完成一次归约。重复这些步骤，直到归约