编译原理张晶版 第六章 LR分析法.ppt

中国科大 第六章 LR分析法及分析程序自动构造 第一节 概述 本章介绍上下文无关文法的LR分析方法及分析程序的自动构造 LR：自左至右扫描,最右推导的逆过程 一、LR方法 1.基本思想 在规范归约过程中，一方面记住已移进和归约的整个符号串，另一方面根据所用的产生式推测未来可能碰到的输入符号. 第一节 概述一、LR方法 2.优缺点 优点：与其它技术相比，适应文法范围更广。能力更强，识别效率相当，尤其在自左向右扫描输入串时就能发现其中错误，并能准确指出出错位置。 缺点：若用手工构造分析程序，工作量太大，且容易出错，所以必须使用自动产生这种分析程序的产生器。 3.产生器的作用 应用产生器产生一大类上下文无关文法的LR分析程序 对二义性文法或难分析的特殊文法，施加一些限制，使之能用LR分析。 第一节 概述二、LR分析器 LR分析法通过LR分析器来实现 第一节 概述二、LR分析器 1、从逻辑上说，LR分析器包括两部分： —总控程序，或称为语法分析程序； —分析表 注：后面要学习的所有LR分析器的总控程序都相同。仅仅是它们的分析表不同 2、总控程序作用： —查分析表，根据分析表的内容做若干简单动作，如读头后移，入栈出栈等。 注：由于总控程序很简单，所以产生器的任务就是产生分析表 第一节 概述三、分析表 一个文法的LR分析器常常对应着若干不同分析表，所有分析表都恰好识别文法所产生的所有语句 本章将讨论四种不同分析表构造方法 —1.LR(0)分析表： 分析能力有限，但这是建立其它LR分析法的基础。 —2.SLR分析表： 简单LR分析表构造法，是一种容易实现又有实用价值的方法，但存在一些文法构造不出SLR分析表 第一节 概述三、分析表 3、规范LR分析表 —它能力最强，但实现代价过高，分析表尺寸太大 4、LALR分析表 —向前看LR分析表构造文法，也是一种常用方法 注：实际上，SLR和LALR分别是对LR(0)和规范LR的改进 最后，将讨论如何使用二义文法构造LR分析器并产生高效的分析技术 6.1 LR分析器一、LR分析法的基本思想 在规范归约时，当一串貌似句柄的符号串呈现于栈顶时，LR分析法根据三方面的信息找句柄： —历史：记录在栈内的符号串移进，归约的历史情况 —展望：预测句柄之后可能出现的信息； —现实：读头下的符号 注：LR分析法的基本思想是符合人的思维习惯的，但实现有困难，因为基于“历史”对未来的“展望”可能存在多种可能。当把“历史” 和“展望”材料综合在一起时复杂性就大大增加。如果简化对“展望”的要求，就可获得实际可行的分析算法。 6.1 LR分析器 6.1 LR分析器二、 LR分析器 1、下推栈： —下推栈用于存放分析输入串过程中的所有和“历史”及相应“展望”信息形成的抽象状态 —由于每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，所以LR分析器的每步动作可由栈顶状态和读头下符号唯一确定 6.1 LR分析器二、LR分析器 1、下推栈： 6.1 LR分析器二、 LR分析器 1、下推栈： 6.1 LR分析器二、LR分析器 2 .分析表 LR分析器的核心是分析表 6.1 LR分析器二、LR分析器 2 .分析表 2）动作表ACTION —ACTION[S,a]表示在当前状态S下，面临读头下的符号a所应采取的动作， —注：该动作有四种可能：移进，归约，出错，接受 3）转向表(GOTO) —GOTO[S,X]表示：若X∈VT，表示在当前状态下，读入X应转向什么状态；若X∈VN，表示当前栈顶句柄归约成X后，应转向什么状态 —注：对终结符的移进动作和转向动作可以合并在一起填在动作表中，这样，转向表可以只保留非终结符转向部分 6.1 LR分析器 注：表中符号的含义： —Sj shift j,指将读入符号a移进栈内并转到j状态，栈顶变成（j,a); —rj reduce j ,按第j号产生式进行归约； —acc accept,分析成功； —空白格 出错标志，若填入相应出错处理程序的编号，便转相应程序处理。 —分析过程 —LR分析器的动作情况也可以描述成机器内部的格局间转换，其格局用三元式表示为（状态栈，已归约的符号栈，待继续分析的输入串） 6.1 LR分析器二、LR分析器 3.总控程序的动作 1）移进 把(Sm,ai)的下一个状态S’=GOTO(Sm,ai)连同读头下符号推进栈内,栈顶成为(S’,ai),读头前进一格 2）归约 指用某产生式A b进行归约。若b的长度为g，则弹出栈顶的g个元素，使得栈顶的状态变成Sm-g,然后把 （Sm-g,A)的下一个状态S’=GOTO(Sm-g,A)连同非终结符A一起推进栈，栈顶变成（S’,A)，读头不动。