编译原理第七章LR分析法

《编译原理第七章LR分析法》由会员分享，可在线阅读，更多相关《编译原理第七章LR分析法（49页珍藏版）》请在金锄头文库上搜索。

1、第七章第七章 LR 分析法分析法课前索引课前索引【课前思考】 复习自顶向下和自底向上语法分析思想的区别 自底向上分析方法是一种移进-归约过程 算符优先分析法是如何确定可归约串的？ 什么是规范推导和规范归约？它们之间有什么关系？ 什么是规范句型？ 什么是规范句型的句柄？ 移进-归约过程是当分析的栈顶符号串形成句柄时就采取归约动作 自底向上分析法的关键问题是在分析过程中如何确定句柄。 如何确定一个输入符号串是否是所给文法的句子？ 【学习目标】本章将介绍自底向上分析的另一种方法，即 LR 分析法。 理解 LR 分析法的基本思想 理解可归前缀和子前缀概念 理解识别活前缀的有限自动机概念 掌握 LR 分

2、析器的构造思想和方法 对给定的文法能构造 LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器，并能判断所给 文法是四种分析器的哪几类。 对给定的输入符号串能用构造的分析器判断该输入串是否是所给文法的句子 了解某些二义性文法在 LR 分析中的应用。 【学习指南】LR 分析法的归约过程是规范推导的逆过程，所以 LR 分析过程是一种规范归约过程。 LR 分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输 入串的 K 个(K0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约， 因而也就能唯一地确定句柄。其中 LR(0)分析器是在分析过程中不需向右

3、查看输入符号， 因而它对文法的限制较大，然而，它是构造其它 LR 类分析器的基础。因此，首先应学好 LR(0)项目集规范族构造的基本原理和方法。当 K=1 时，已能满足当前绝大多数高级语言 编译程序实现的需要。SLR(1)分析是为学习 LR(1)分析做准备，LR(1)项目集族的构造是 LALR(1)分析器的构造原理和基础。LALR(1) 分析器是当前大多数高级程序设计语言编译 程序所采用的语法分析技术，也是编译程序语法分析器自动构造工具 YACC(将在第 13 章 介绍）的实现基本原理。由此，LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器的构造方法 都必须深入理解和掌握。 【难

4、 重 点】 可归前缀和子前缀概念 识别活前缀的有限自动机概念 对可归前缀为规范归约的句柄的理解 构造 LR(1)项目集族时搜索符的计算 LR 分析器的关键部分是分析表的构造 对给定的文法能构造 LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器 当一个文法能构造出不含移进-归约或归约-归约冲突时的 LR(0)/ SLR(1)/ LALR(1)/ LR(1)分析表时，称这个文法为 LR(0) / SLR(1)/ LALR(1)/ LR(1)文法。 对给定的文法能判断是四种 LR 类文法的哪几类 了解某些二义性文法在 LR 分析中的应用 【知识结构】在第 6 章中已经讨论过，自底向上分

5、析方法是一种移进-归约过程，当分析的栈顶符号 串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定 句柄。LR 分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序 查看输入串的 K 个(K0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生 式归约，因而也就能唯一地确定句柄。LR 分析法的归约过程是规范推导的逆过程，所以 LR 分析过程是一种规范归约过程。 LR(K)分析方法是 1965 年 Knuth 提出的，括号中的 K 表示向右查看输入串符号的个数。 这种方法比起自顶向下的 LL(K)分析方法和算符优先分析方法对文法的限制要少得多，

6、也 就是说对于大多数用无二义性上下文无关文法描述的语言都可以用相应的 LR 分析器进行 识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。它的主要缺点是 对于一个实用语言文法的分析器的构造工作量相当大，K 愈大构造愈复杂，实现相当困难。 目前对于真正实用的编译程序，所采用的 LR 分析器都是借助于美国 Bell 实验室 1974 年推 出的“一个编译器的编译器-YACC“来实现的。它能接受一个用 BNF 描述的满足 LALR(1)的 上下文无关文法并将自动构造 LALR(1)语法分析器。本章将主要介绍 LR 分析的基本思想和当 K1 时 LR 分析器的基本构造原理和方法。 其中

7、LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，对 绝大多数高级语言的语法分析器是不能适用的，然而，它是构造其它 LR 类分析器的基础。 当 K=1 时，已能满足当前绝大多数高级语言编译程序的需要。因此，我们将着重介绍 LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器的构造方法。其中 SLR(1)和 LALR(1)分别是 LR(0)和 LR(1)的一种改进。7.1 LR 分析概述分析概述一个 LR 分析器由 3 个部分组成：(1) 总控程序，也可以称为驱动程序。对所有的 LR 分析器总控程序都是相同的。(2) 分析表或分析函数，不同的文法分析表将不同，

8、同一个文法采用的 LR 分析器不同 时，分析表将也不同，分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分， 它们都可用二维数组表示。(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定(LR(0)分析器不需向前查看输入符号)。 LR 分析器工作过程示意图如图 7.1 所示。 图 7.1 LR 分析器工作过程示意图 f7-1-1.swf其中 SP 为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用 GOTOSi,XSj 表示，规定当栈顶状态为 Si遇到当前文法符号为 X 时应转向状态 Sj。X 为终结符或非终结

9、 符，状态的含义将在后面介绍。 ACTIONSi,a规定了栈顶状态为 Si 时遇到输入符号 a 应执行的动作。动作有 4 种可能： 移进 归约 接受 acc 报错 移进：把 Sj=GOTOSi，a移入到状态栈，把 a 移入到文法符号栈。其中 i，j 表示状态号。 归约：当在栈顶形成句柄为 时，则用 归约为相应的非终结符 A，即文法中有 A 的产 生式，若 的长度为 r(即|=r)，则从状态栈和文法符号栈中自栈顶向下去掉 r 个符号，即 栈指针 SP 减去 r。并把 A 移入文法符号栈内，Sj=GOTOSi，A移进状态栈，其中 Si为修 改指针后的栈顶状态。 接受 acc:当归约到文法符号栈中只

10、剩文法的开始符号 S 时，并且输入符号串已结束即当前输入 符是#，则为分析成功。 报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是 该文法能接受的句子。LR 分析器的关键部分是分析表的构造，后边将针对每种不同的 LR 分析器详细介绍其 构造思想及方法。回顾在第 6 章中曾给出的例 6.1 文法，现以此为例复习自底向上分析方法移进-归约过 程。 f7-1-2.swf 在步骤 3 中，用 Ab 归约在步骤 5 中，用 AAb 归约问题：何时移进？何时归约？用哪个产生式归约？是 LR 分析要解决的重要问题。7.2 LR(0)分析分析LR(0)分析表构造的思想和方法是构

11、造其它 LR 分析表的基础。我们回顾在第 6 章中曾 给出例 6.1 文法 GS为：(1) SaAcBe(2) Ab(3) AAb(4) Bd对输入串 abbcde#用自底向上归约的方法进行分析，当归约到第 5 步时栈中符号串为 #aAb，我们采用了产生式(3)进行归约而不是用产生式(2)归约，而在第 3 步归约时栈中符号 串为#ab 时却用产生式(2)归约，虽然在第 2 步和第 5 步归约前栈顶符号都为 b，但归约所 用产生式却不同，其原因在于已分析过的部分在栈中的前缀不同，也就是我们在 LR 分析 中引进的状态栈的栈顶状态不同，为了说明这个问题我们先在表 7.1 中给出例 6.1 文法 G

12、S的 LR(0)分析表，在表 7.2 给出对输入串 abbcde#的分析过程，并引进一些概念和术语。 对表 7.1 的构造原理和表 7.2 分析过程的实现思想将在下面详细介绍。 表 7.1 例 6.1 文法的 LR(0)分析表ACTIONGOTOacebd#SAB0 1 2 3 4 5 6 7 8 9S2 . . . r2 . r3 . r4 r1. . . S5 r2 . r3 . r4 r1. . . . r2 . r3 S9 r4 r1. . S4 S6 r2 . r3 . r4 r1. . . . r2 S8 r3 . r4 r1. acc . . r2 . r3 . r4 r11.

13、. 3 . . . . . 7 表 7.1 符号说明：Si：移进，将状态 i 和输入符进栈ri：归约，用第 i 个产生式归约，同时状态栈与符号栈退出相应个符号，并把 GOTO 表相应状态和第 i 个产生式的左部非终结符入栈。 表 7.2 对输入串 abbcde#的分析过程 f7-2-2.swf 总结上面 LR 分析算法为： 置 ip 指向输入串 w 的第一个符号令 Si为栈顶状态 a 是 ip 指向的符号（当前输入符号）begin (重复开始)if ACTIONSi,a=Sjthen begin PUSH j,a (进栈)ip 前进(指向下一输入符号)endelse if ACTIONSi,a

14、=rj(若第 j 条产生式 为 A) then beginpop | 项若当前栈顶状态为 Skpush GOTOSk,A 和 A(进栈)endelse if ACTIONSi,a=accthen return (成功）else errorend . (重复结束)对于上面的分析过程我们可以知道 LR 分析器的关键部分是分析表的构造,那么可提出 以下问题：一个文法的 LR 分析表是如何得到的？对于一个文法，状态集是如何确定的？为了解决这些问题引入可归前缀与活前缀概念 7.2.1 可归前缀和子前缀可归前缀和子前缀 为了在以后的 LR 分析中不致引起混淆，现对原文法进行拓广。若原文法 G 的开始符 号

15、为 S，在 G 中加产生式 SS 后得新的文法 G，则称 G为原文法 G 的拓广文法，而 S为 拓广后文法 G的开始符号。对文法进行拓广的目的是为了对某些右部含有开始符号的文法， 在归约过程中能分清是否已归约到文法的最初开始符，还是在文法右部出现的开始符号， 拓广文法的开始符号 S只在左部出现，这样确保了不会混淆。 我们可以形式地定义活前缀如下：定义定义 7.1 若 SAR R 是文法 G中的一个规范推导，G是 G 的拓广文法，符号串 是 的前缀，则称 是 G 的，也是 G的一个活前缀。实际上 是规范句型 的前缀，但它的右端不超过该句型句柄的末端（其中 A 是一产生式，VT*； 、V*） 。由

16、以上分析我们很容易理解，在 LR 分析过程中，实际上是把 的前缀列出放在符号 栈中，一旦在栈中出现 ，即句柄已经形成，则用产生式 A 进行归约。 若对例 6.1 文法 GS的每条产生式编上序号用i表示加在产生式的尾部，使产生式变 为：SaAcBe1Ab2AAb3Bd4但i不属产生式的文法符号，对输入串 abbcde 进行推导时把序号也带入，则最右推导 过程为：SaAcBe1aAcd4e1aAb3cd4e1ab2b3cd4e1所以输入串 abbcde 为该文法的句子。它的逆过程,即最左归约(规范归约)则为：ab2b3cd4e1 用产生式(2)归约aAb3cd4e1 用产生式(3)归约 aAcd4