网络编程 第7章.ppt

1、1.第7章，LR分析，2，学习目的，本章将介绍另一种自下而上的分析方法，即LR分析理解LR分析的基本思想，理解可约前缀和活前缀的概念，理解用于识别活前缀的有限自动机的概念，并掌握LR分析器的构造思想和方法，对于给定的语法，LR分析器可以构造LR(0)、SLR(1)、LALR(1)和LR(1)四种分析器，并可以判断给定的语法属于哪四种分析器。对于给定的输入符号串，构造的分析器可以判断输入串是否是给定语法的句子，并理解一些二进制语法在LR分析中的应用。3.学习指南，LR分析过程是一个规范的简化过程。LR分析方法可以根据当前分析堆栈中的符号串(通常由状态表示)和按顺序向右看的输入串的k (K0)符号

2、，唯一地确定分析器的动作是否被移入或减少，以及哪个产品被用于减少，也就是说，它可以唯一地确定句子句柄。其中，K=0是LR(0)分析器，它对语法有很大的限制，但它是构造其他LR类分析器的基础。因此，我们应该掌握构造LR(0)项集规范族的基本原则和方法。4，学习指南，当K=1时，它可以满足当前大多数高级语言编译器的实际需要。本章介绍了三种：单反(1)分析是为学习单反(1)分析做准备；LR(1)项集族的构建是LALR(1)分析器的构建原则和基础。LALR(1)解析器是目前大多数高级编程语言采用的语法分析技术，也是实现YACC(将在第13章中介绍)的基本原理，这是一个编译解析器的自移动构造工具。5.简

3、历1960年，他毕业于凯斯理工学院，并于1963年获得加州理工学院数学博士学位。他在学校一直呆到1968年，然后转到斯坦福大学教书。1992年，他光荣地从斯坦福大学退休，并为计算机编程艺术TEX排版软件和METAFONT字体设计软件乌托邦84“小创造”作出了贡献：算法X代表非终止符；a代表终结者。在状态转换表gotoi中，x gotoi，x=j3360，当状态堆栈的顶部是I，符号堆栈的顶部是非终结符x时，转到状态j，12，移动到Shift:以指示：动作I，a=Sj动作3360，状态j和输入符号a分别进入状态堆栈和符号堆栈，并且输入字符串前进一个字符。j，a，reduced reduce:表示：

4、ACTIONi，a=rk，其中： k表示kth生产公式。动作：让第k个产品的右边部分长度为m，左边的非终止符为a，状态堆栈顶部的m个状态位置为P1。从符号栈和状态栈中分别弹出m个符号；2.非终结符进入符号堆栈；3.GOTOp，A=q进入状态堆栈。q，A，13，accept意味着：ACTIONi，a=acc action :在符号堆栈中只有#和语法开始符号s，并且输入字符串只有#，因此分析结束。错误意味着：操作I，a=空白操作：错误，终止分析，并转移到错误处理程序。14，移入，0进入状态堆栈；#进入符号堆栈；Ip指向w#的第一个符号。LR驱动程序算法流，开始，让我们成为状态堆栈的顶部；a是ip所

5、指向的符号；执行ACTIONs，a、接收、报告错误、减少、直到(ip指向输入字符串#的末尾，符号堆栈的顶部是E)；初始化，一个进入符号堆栈；将状态j输入状态堆栈；使ip指向下一个符号；| |符号从符号堆栈中弹出；从状态堆栈中弹出| |符号；让我们成为状态堆栈的顶部；a .进入符号堆栈；转到，a进入状态堆栈；产量公式a；错误()；/*调整误差函数*/，返回；注：在分析过程中，符号栈的内容只是连接其余输入字符串的一个句型。a、b、b、c、d、e、a、a、b、s、a、b、b、c、d、e、b、b、a、d、abbcde、aabcde、aacde、aacbe、s、3 024 #ab bcde# reduc

6、ed (Ab)，4 023 #aA bcde#移入，5 0236 #aAb cde# reduced (AAb)，6 023 #aA cde#移入，7 0235 #aAc de#移入，8 02358 # AAcd e # reduced(BD 10 023579 # AAcbe # reduction(SaaCBe)，11 01 #S #验收，语法GS:(1)SaaCBe(2)Ab(3)AAB(4)BDe适用于LR(0)语法的语法LR(0)的语法能力最弱。从理论上讲，最重要的是FA如何识别活动前缀，以及DFA如何识别活动前缀。LR(0)分析表结构，17，可返回前缀：如果一个句型的某个前缀的后缀

7、是该句型的句子句柄，那么这个前缀被称为该句型的可返回前缀。活前缀：S Aw w，wVT* r是前缀，那么r是g的活前缀。也就是说，一个标准句型的前缀。如果句柄后不包含任何符号，则称为句型的活前缀。* RM，abbcde，aacde，aaCBE，s，a，aa，AAC，aacb，a，ab，a，aa，aab，a，aa，AAC，aacd，s，右句类型活前缀，例如语法GS P14，18，1。活动前缀不包含句柄的任何符号，并且期望从输入字符串中看到从A的右边部分推导出的符号字符串。2.活动前缀只包含句柄的一些符号，表示A12的右子串1已经出现在堆栈的顶部，预计将会看到从输入字符串2推导出的符号。3.活动前

8、缀已经包含句柄的所有符号，表示生产公式A的右边部分已经出现在堆栈的顶部。例如，正确的句型aAbcde的活前缀，a，aA，aAb，其中：a不包含任何句柄符号；AA仅包含手柄符号的一部分；aAb包含手柄的所有符号。活动前缀和句柄之间的关系：约定：是句子模式的句柄，相应的生成公式是A，=12，19，这表示如果确定了句子模式，句柄将相应地被确定，也就是说，最左边的简单短语确定可用语法具有无限数量的活动前缀。因为语法有无限的句型，所以可以构造一个有限自动机来识别特定语法的所有活动前缀。根据DFA，可以构建LR(0)分析器的一个重要部分。20.拓宽语法：引入一个新的非终结符作为语法的新发起者，并添加一个新

9、的公式：SS 3360 s是新的发起者，S是最初的初始符号。扩展语法的目的是使语法只有一个以识别符号为左部的产物，从而使构造的分析器具有唯一的接受状态。21，介绍了用点标记的生成公式，表示在分析过程中已经识别出(出现在栈顶)多少个汉语语法G的生成公式的正确符号。定义：在语法的每一个产生式的右边加一个点，叫做g的LR(0)项。点是表示一个项的标记。用项目表达分析的过程。功能：圆点表示通过识别产品的正确符号所达到的位置。可以从点的左边部分推导出的符号串已经从输入串中看到，并且希望看到从点的右边部分推导出的符号串。也就是说，在生产公式的右边部分添加一个点来划分获取的内容和要获取的内容：构成一个句柄。

10、二。LR(0)项目，22，例如，如果有一个生产SaAcBe，有以下六个项目：特别是：A、A、B、BVN待减、A、A、aVT移入项目、A减项目、S，这是S S初步验收项目，上述项目称为LR(0)项目。根据点的位置以及点后是终止符还是非终止符或者空，项目可分为以下几类：saacbe、saacbe、saacbe、saacbe、saacbe、23、活动前缀和句柄，以及LR(0)项目、移入项目或待缩减项目A。描述堆栈顶部没有句柄的任何符号，并期望此时将A的右边部分推出。活动前缀不包含句柄的任何符号。移入项或待缩减项A1.2描述了A12的右子串1已经出现在堆栈的顶部，期望看到从输入字符串推导出的符号2。活

11、动前缀仅包含手柄符号的一部分。缩减项a描述了生产公式a的右边部分出现在堆栈的顶部。活动前缀已经包含句柄的所有符号。24，3。构造一个确定的有限自动机来识别活动前缀。构建状态2。定义后续状态3。构造一个转换函数，25，1。构造一个状态，定义：让我成为文法G的LR(0)项集，并构造闭包(1)作为DFA的状态。结束是一个项目闭包(I)中的每个项目都是等价的，也就是说，从预期缩减的角度来看是相同的；内核：除了SS，圆点不是产品最左边的项目。初始状态：让项SS成为初始状态集的核心，并获得闭包(SS)作为初始状态项集，26，举例(0)SE(扩展语法)(1)E AA(2)E BB(3)A CA(4)A D(

12、5)B CB(6)B D，SE，E AA，E 2。连续状态定义，(1)连续项定义使项A.X成为项集合中对应于某个状态U的项，则项AX是项A.X的后继项，其中X是语法符号字母表中的任何符号(2)连续状态定义闭包(AX)是状态U的后继状态，3)构造一个转换函数，并定义(转换函数)如果I是，I:AX，J:AX，X，用状态转移图表示为：28，定义：标识状态的整个DFA项集合(状态)解决方案：1)初始状态：闭包(SS) 2)找到一个新的状态，转到(1，X)=闭包(J)，其中1是已求解的状态3)重复2)直到没有新的状态集出现。1.LR(0)项集规格族的计算；4.lr (0)分析表的构造；29.(0)SE(

13、扩展语法)(1)e aa(2)e bb(3)a ca(4)a d(5)b CB(6)b d、b、E，B，E，bB，B，cB，B，d，c，A，c，A，c A，A，d，c，A d，d，d，I1，I2，I3，I5，I6，B，cB，B，cB，B，d，I8，E，bB，I7，B，d，I9，B，cB，I11，c，d，A c A，I10，A，B，c，A，E aA，I4，d，DFA，p36，30，LR(0)语法活动前缀的项集被识别。该算法构造了一个离散傅立叶变换。状态图的描述：(1)每个DFA的状态是一个称为LR(0)项集的项集，整个状态集称为LR(0)项集规范族；(2)在DFA的任何项目集合中，每个项目都是等

14、价的，这意味着从期望缩减的角度来看是相同的；(3)有一个唯一的初始状态和几个最终状态，用几种活动前缀表示识别状态；(4)主动前缀的解决方案：从初始状态开始，沿着可达状态标记路径。(5)状态反映了手柄的识别。31，LR(0)项目集规范系列(DFA标识g的活动前缀):I0: SE I1: SE I 2: EAa EAa . ca eBa AD I: eBa I43360 EAa I5: Ac。A BCb ACa Bd A . d I6: Ad I73360 eBB I83360 BcB Bd I9333 60 Bd I10: ACa I11: BcB，32，一个项目集我不能有下列情况：(A)移入和

15、减少项目同时存在，所以我有移位/减少冲突；(二)减少和减少物品同时存在，所以我有减少/减少冲突；如果没有移动-减少冲突，则构造LR(0(0)。显然，LR(0)语法的每个项集不包含任何冲突项。LR(0)语法很弱，甚至表达式语法也不属于LR(0)。33，示例(0)SE(扩展语法)(1)E Y；E (2) E Y (3) Y (4) Y i:t，I0，S E，E Y；E，E，Y，Y，E，Y；e，e y .se，e，I，y i:t，i1，I2，i3，y，y i:t，非LR(0)语法，34，2。构造lr (0)分析表，假设语法是LR(0输出动作子表并转到：G分析表的子表。方法：1 .用C=I0，I1，I2，In，G构造LR(0)项集规范族，即带有活动前缀的DFA。2.状态k的分析动作(在分析表中，我们用项集Ik的下标k来表示相应的状态)如下：(a)如果aa属于Ik并且GO(Ik，a)=Ij，a是最终符号，那么集actionk，a=SJ (shift j)，ij:闭包(Aa)，a，ik3330。A)=Ij，A是非终端符号，然后设置gotok，a=j，ik3360 A，ij:closure (aa)，A，ik:aa，(d)如果SS属于ik，设置动作k，# acc(接受)(e)，它不能用分析表中的上述规则填写信息，(b)如果A属于Ik，设置所