《编译第六章》ppt课件

《《编译第六章》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章LR分析法及分析程序自动构造第六章LR分析法及分析程序自动构造（1）第一节概述本章介绍上下文无关文法的LR分析方法及分析程序的自动构造LR：自左至右扫描,最右推导的逆过程一、LR方法1.基本思想在规范归约过程中，一方面记住已移进和归约的整个符号串，另一方面根据当前所用的产生式推测未来可能碰到的输入符号.第六章LR分析法及分析程序自动构造（2）第一节概述一、LR方法2.优缺点优点：与其它技术相比，适应文法范围更广。能力更强，识别效率相当，尤其在自左向右扫描输入串时就能发现其中错误，并能准确指出出错位置。缺点：若用手工构造分析程序，工作量太大，且容易出错，所以必须使用

2、自动产生这种分析程序的产生器。3.产生器的作用应用产生器产生一大类上下文无关文法的LR分析程序对二义性文法或难分析的特殊文法，施加一些限制，使之能用LR分析。第六章LR分析法及分析程序自动构造（3）LR分析法通过LR分析器来实现总控程序分析表输出带第一节概述二、LR分析器输入带下推栈第六章LR分析法及分析程序自动构造（4）1、从逻辑上说，LR分析器包括两部分：—总控程序，或称为语法分析程序；—分析表注：后面要学习的所有LR分析器的总控程序都相同。仅仅是它们的分析表不同2、总控程序作用：—查分析表，根据分析表的内容做若干简单动作，如读头后移，入栈出栈等。注：由于总控程序

3、很简单，所以产生器的任务就是产生分析表第一节概述二、LR分析器第六章LR分析法及分析程序自动构造（5）一个文法的LR分析器常常对应着若干不同分析表，所有分析表都恰好识别文法所产生的所有语句本章将讨论四种不同分析表构造方法—1.LR(0)分析表：分析能力有限，但这是建立其它LR分析法的基础。—2.SLR分析表：简单LR分析表构造法，是一种容易实现又有实用价值的方法，但存在一些文法构造不出SLR分析表第一节概述三、分析表第六章LR分析法及分析程序自动构造（6）3、规范LR分析表—它能力最强，但实现代价过高，分析表尺寸太大4、LALR分析表—向前看LR分析表构造文法，也是

4、一种常用方法注：实际上，SLR和LALR分别是对LR(0)和规范LR的改进最后，将讨论如何使用二义文法构造LR分析器并产生高效的分析技术第一节概述三、分析表第六章LR分析法及分析程序自动构造（7）6.1LR分析器一、LR分析法的基本思想在规范归约时，当一串貌似句柄的符号串呈现于栈顶时，LR分析法根据三方面的信息找句柄：—历史：记录在栈内的符号串移进，归约的历史情况—展望：预测句柄之后可能出现的信息；—现实：读头下的符号注：LR分析法的基本思想是符号人的思维习惯的，但实现有困难，因为基于“历史”对未来的“展望”可能存在多种可能。当把“历史”和“展望”材料综合在一起时复

5、杂性就大大增加。如果简化对“展望”的要求，就可获得实际可行的分析算法。第六章LR分析法及分析程序自动构造（8）6.1LR分析器总控程序分析表输出带输入带下推栈二、LR分析器一个LR分析器实际上是带有下推栈的确定的有限状态自动机。可将一个“历史”与这个“历史”下的展望信息综合为抽象的一个状态第六章LR分析法及分析程序自动构造（9）1、下推栈：—下推栈用于存放分析输入串过程中的所有和“历史”及相应“展望”信息形成的抽象状态—由于每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，所以LR分析器的每步动作可由栈顶状态和读头下符号唯一确定6.1LR分析器二、LR

6、分析器第六章LR分析法及分析程序自动构造（10）1、下推栈：6.1LR分析器二、LR分析器sms0xm#……状态栈符号栈下推栈栈顶指针—把一个“历史”和这个“历史”下的“展望”信息综合为抽象的一个状态，下推栈用于存放在对输入串进行分析的过程中这些状态，由于每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，所以栈顶的状态就可用于决定当前的动作第六章LR分析法及分析程序自动构造（11）1、下推栈：6.1LR分析器二、LR分析器sms0xm#……状态栈符号栈下推栈栈顶指针—为了便于了解栈顶状态对正规分析过程的作用，我们把栈分为两栏：状态栏和符号栏。符号栈仅

7、用于记录迄今移进---归约所得到的文法符号，由于它们已经被概括在“状态”里了，所以对语法分析不起作用。—初始时，状态栈放S0（初态），符号栈放“#”（栈底符）；栈顶Sm代表符号栈内的符号串XmXm-1…X1及其展望信息第六章LR分析法及分析程序自动构造（12）6.1LR分析器二、LR分析器2.分析表LR分析器的核心是分析表a1a2……ana1a2…anA1A2…AnS0..Sk这张分析表包含两部分：动作表（Action)和转向表(GoTo)，它们都是二维数组Si表示状态，ai表示终结符，Ai表示非终结符Actiongoto第六章LR分析