第4章(5)白底黑字 LR0.ppt

1、4.5 LR分析法，LR分析法是自下而上规范化的语法分析法。l表示从左到右扫描输入符号字符串。r是构成最右导数的逆过程。这种分析法对语法的限制比递归下降分析法、预测分析法、算子优先分析法少。用无意义的上下文无关语法描述的大多数语言都可以使用LR分析方法有效地进行分析。4.5 LR分析法，优点：快速准确地指出输入字符串的语法错误和错误位置。缺点：构建LR分析器的工作量相当大，很难具体实现。因此，现在正在使用用于配置LR分析器的专用工具“YACC”(请参见附录)，自动为实际的实用编译器构建LALR(1)分析器。牙齿部分介绍了LR分析的基本思想以及LR(0)、SLR(1)、LR(1)、LALR(1)

2、分析器的工作原理和配置方法。4.5 LR分析法，基本思想：LR分析法是规范归约分析法。规格减少分析的关键问题：如何确定分析堆栈顶部的符号字符串形成句柄？4.5.1 LR分析器的逻辑结构和工作流程，LR分析法确定句柄的基本思想依赖于规格减少分析。历史、前景、现实、4.5.1 LR分析器的逻辑结构和操作过程、LR分析器的逻辑结构、LR分析器的逻辑结构图表、分析堆栈、分析表和主控制程序。分析堆栈、输出、4.5.1 LR分析器的逻辑结构和操作过程，分析堆栈用于存储分析过程的历史和展望信息。LR分析方法将历史和展望信息抽象到状态，并将它们放置在分析堆栈中。也就是说，分析堆栈的各个状态概括了从分析开始到合

3、同阶段的整个分析历史和对未来的展望。1 .分析堆栈。对此，我将以简单的例子说明。对于4.5.1 LR分析器的逻辑结构和工作流程，例如语法GE:EE T | T、TT*F | F、F(E) | id，状态Sm不仅表示从分析开始到现在扫描的输入符号，还表示FOLLOW(T)，当当前读取的输入符号为或)或$时，如果语法表明在堆栈顶部形成了句柄，则必须将符号字符串ET分类为约E。如果当前读取的输入符号不是上述四个茄子符号之一，则输入字符串包含语法错误。可以看到，LR分析器的每个阶段分析操作都是由堆栈顶部状态和当前输入符号唯一确定的。4.5.1 LR分析器的逻辑结构和工作流程，都是二维数组。LR分析表是

4、LR分析器的核心部分。LR分析表包含两部分：和。状态转换表元素GOTOSi，X指定当状态Si遇到语法符号X时应传输的下一个状态。2 .LR分析表、分析任务(ACTION)表、状态切换(GOTO)表、4.5.1 LR分析器的逻辑结构和操作过程、表参考、分析任务表元素ACTIONSi、a对应于状态Si时的四个可茄子行为。移动：将状态Sj=ACTIONSi、A和输入符号A移动到分析堆栈。rj=ACTIONSi，a，即堆栈顶部的符号字符串形成句柄，语法中有rj: a的规则，其中| |=从分析堆栈顶部删除语法符号和状态，删除承包商a和状态Sj=GOTOSi-，4.5.1 LR分析器的逻辑结构和操作过程如

5、下：表，在牙齿点，分析堆栈中只有语法开始符号S和当前读取的输入符号$。也就是说，输入符号字符串已终止。，报告错误：指示输入字符串包含错误。此时，出现了不应在堆栈顶部的特定状态下遇到的输入符号。表引用，从左到右扫描输入符号字符串，1当前分析堆栈的堆栈顶部状态2当前读取的输入符号3 LR分析表元素表示的行为，3。如果主节目、4.5.1 LR分析器的逻辑结构和操作过程、主控制节目算法：输入：输入字符串W和LL、输出：W是句子，则W的自下而上分析成功。否则，将输出错误消息。算法：在初始状态S0分析堆栈顶部输入字符串W$的第一个符号，以读取为A。与4.5.1 LR分析器的逻辑结构和工作流程、4.5.1

6、LR分析器的逻辑结构和工作流程、示例1、语法G:语法对应的LR分析表如下表所示：0.ss，1.sa，2.sb，3.aaab，4.ac，5.babb，6.bd，4.5.1 LR分析器的逻辑结构和工作过程，4.5.1 LR分析器的逻辑结构和工作过程，4.5.1 LR分析器的逻辑结构和，构成LR分析表的基本思想是：直接配置DFA，以识别给定上下文无关语法中语法的所有规范文章前缀，然后将DFA转换为LR分析表。4.5.2 LR(0)分析方法需要定义一些茄子重要概念和术语，以提供构成LR分析表的算法。语法规范句型的前缀，1。字符串的前缀是指字符串的第一部分。例如，字符串abc的前缀为、a、ab和ABC。

7、2 .规格句型前置码是规格句型的前置码，不包含把手右边的符号。活动前缀可以是一个或多个标准文章模式的前缀。4.5.2 LR(0)分析、4.5.2 LR(0)分析、4.5.2 LR(0)分析、LR分析期间，堆栈中的语法符号随时都必须是特定规范语句的活动前缀。这是因为一旦在堆栈顶部形成句型句柄，就会立即签约。也就是说，如果只输入扫描的部分，输入字符串可以总结为活动前缀。4.5.2 LR(0)分析，例如，在前面的情况中，语法GS中规范文章aaAbb的句柄为aAb，堆栈中的符号字符串为aaAb，牙齿文章模式的活动前缀为a、aa a、aa、aaA、aaAb，对句柄的识别是规范句式活字前缀，4.5.2 L

8、R(0)解析法，如何识别语法规范句型的前缀？LR分析器的工作过程可以看作是逐步识别给定语法规范句子型前缀的过程。用4.5.2 LR(0)分析法可以看出，利用穷机器人可以识别给定语法的所有规范型句子的前缀。4.5.2 LR(0)分析、4.5.2 LR(0)分析和LR(0)项目，因此活动前缀和句柄之间的关系有三个茄子情况：活动前缀中已具有句柄的所有符号表示规则A的右侧符号字符串将出现在堆栈顶部，并且相应的分析操作将使用牙齿规则减少。4.5.2 LR(0)分析，活动前缀仅包含句柄的部分符号。这意味着出现在右侧子字符串1牙齿堆栈的顶部，例如规则A12，2期待在其馀输入字符串中进行一般化。活动前缀具有完

9、全没有控制柄的符号。也就是说，我们期望从规则A右侧发出的符号字符串在其馀输入字符串中可见。，4.5.2 LR(0)解析，在分析过程中，为了说明语法中一个规则右边的符号字符串识别多大部分，可以在语法的每个规则右边添加点来表示。对于以上三种茄子，用点标记的规则分别为、A、A 1 2、A。语法G右侧标有圆点的规则称为G的LR(0)项。仅null规则a，LR(0)项目a值得注意。语法G的所有LR(0)项目是构建识别语法所有规范型前缀的DFA的基础。牙齿DFA的每个状态都与一组可怜的LR(0)条目相关联。LR(0)项目表示语法规范文章前缀的各种识别状态。其他LR(0)项目在分析期间反映堆栈顶部的各种情况

10、，因此，可以根据点位置和点后是否有终结器或非终结器对语法中的所有LR(0)项目进行分类。4.5.2 LR(0)分析，直观地分析4.5.2 LR(0)，LR(0)项目按以下方式分类，转到A a等项目：其中，(VNVT)*是点后带有终止符的项目，表示期望在输入字符串中移动符号以形成控制柄。4.5.2 LR(0)分析，A B等承付款项目，其中接受(VNVT) *、B VN*、SS等项目。其中S是语法的开始符号，即语法开始符号的契约项目。只有一个规则，s在左边，是合同项目的特殊情况，表示整个句子已经分析，可以接受。4.5.2 LR(0)解析，如何构造识别语法的所有规范型前缀DFA，在牙齿项目集中，所有

11、LR(0)项目识别的前缀相同，因此可以使用闭包函数(CLOSURE)获取DFA，构成识别语法规范文章模式活动前缀DFA的每个状态为了使“接受”项目唯一，假设语法G的开始符号是S，在语法G中引入新的开始符号S，添加新的规则S，得到语法G的扩展语法G。(1)定义闭包函数，将I设置为扩展语法g的LR(0)项目集，定义和配置I的闭包克隆(I):分析4.5.2 LR(0)，I之一，(b) A B为ccl，(c)重复(b)，直到CLOSURE(I)项目不再增加。4.5.2 LR(0)分析，例如，如果为示例1的语法指定I=SS，则它将是默认项目集i0，closure (I)，SS，SA，4.5.2 LR(0

12、)分析，(2)，GO (I Go (i0，s)，=，closure (ss)，=，ss，=，i1，Go (i0，a)，=，closure，4.5.2 LR(0)分析法，(3)如何构造识别语法规范句型前缀DFA，(a)求出CLOSURESS，获得超态项目集。(b)将状态转移函数GO(I，X)应用于默认项目集或其他已配置的项目集，以获取新项目集(后续状态)。4.5.2 LR(0)分析，(D)设置切换函数GO状态之间的连接关系，对于前面的语法，配置DFA以识别语法的所有规范句型前缀，如下所示：(C)重复(B)，直到未显示新项目集(新状态)。4.5.2 LR(0)分析方法，I73360AAAB，I83360AAAB，I 93360 abb I 63360 BD，S，a，b，a，c，也就是说，输入字符串已成功分析，使用SS作为最后一份合同的状态称为接受状态。4.5.2 LR(0)解析，构成标识语法前缀的DFA状态(项目集)的整体称为牙齿语法的LR(0)项目集规范族。(4) LR(0)分析表的配置：语法G的扩展语法G的LR(0)项目集规范族的每组项目与以前的项目同时共存或多个合同项目同时共存的情况下，G被称为LR(0)语法。配置4.5.2 LR(0)分析、4.5.2 LR(0)分析和LR(