第8章LRk分析方法

LR(K)分析，本章的重点：LR分析方法的逻辑结构和分析过程LR(0)语法和LR(0)分析表结构LR(1)语法和LR(1)分析表结构SLR(1)语法和SLR(1)分析表结构，LR分析器由三部分组成：LR分析程序，也称为通用控制程序。所有LR分析仪都是一样的。分析堆栈，包括语法符号堆栈和相应的状态堆栈，都是高级的，并被推出堆栈。分析表(分析功能)。不同的语法分析表是不同的。同一语法中使用的LR分析器不同，分析表也不同。分析表可以分为两部分：动作表和转到表，两者都可以用二维数组来表示。(1)LR分析方法的逻辑结构，语法符号：X1X2Xm.XM是句型中被移入和缩小的部分。事实上，它是多余的，已经被推广到国家。状态堆栈：(S0，#)是初始状态和先前放置在堆栈中的符号。LR分析过程：在通用控制程序的控制下，从左到右扫描输入的符号串，根据分析栈中的状态和当前输入的符号，根据分析表中的内容完成相应的分析。分析表构造有四种类型：(1)LR(0)分析表构造方法(2)简单LR(SLR)分析表构造方法(3)LR(1)分析表构造方法(4)前瞻LR(LALR)分析表构造方法，2。分析表组成：(1)分析动作表动作是一个二维数组，表中有动作Si，aj，表示当前栈顶为状态Si，输入符号为aj时要执行的动作。有四种可能的动作：移入(S)、减少(R)、接受(acc)和出错。在表中，转到状态指示堆栈顶部的状态是“是”，以及遇到语法符号Xj时应该进入的下一个状态。显然：分析表定义了一个以语法符号为字母表的DFA，(2)状态转移表goto也是一个二维数组，使用三进制公式：(状态堆栈、符号堆栈、输入符号)来表示分析过程中状态堆栈、符号堆栈、输入符号的变化。初始状态S0和#被放入分析堆栈。三元公式为：(S0，#，A1A2.安#)三元公式在任何时候都是：(S0S1.Sm，# X1X2.aiAI 1.一#)分析器的下一个动作由栈顶状态SM和当前面对的输入符号AI唯一确定。LR分析过程：根据栈顶状态Sm和输入符号ai查找动作表，根据表中不同的内容完成不同的动作。如果动作Sm，ai是：移入：当前输入符号ai进入符号堆栈，下一个输入符号成为当前输入符号，动作表中指示的状态s被放入状态堆栈。三元公式变为：(S0S1.短信，# X1X2.人工智能1.一#)还原：还原是按照一定的生产公式A进行的。如果生产公式右端的长度为R，则两个堆栈顶部的R元素同时被推出堆栈。将缩减后的符号A放入符号堆栈中；根据新栈顶状态Sm-r和归约符号A，检查GOTO表，S=gotoSm-r，A进入状态栈。三元公式变为：(S0S1.SM-RS，# X1X2.AIAI 1.AN #)接受：分析成功，分析终止。三元形式不会改变。错误：报告错误信息。三元形式的改变过程终止。为了介绍LR分析过程，直接给出了语法分析表，后面将介绍如何生成语法分析表。3.举例说明了LR的具体分析过程：(1) LE，L (2) LE (3) EA (4) EB，生成公式的序号，语法设置为G L:“输入1”意味着将当前输入符号移动到堆栈，将第1个状态移动到状态堆栈。则意味着进入第I个状态，即第I个状态被放在状态堆栈上。Ri表示根据第I个生产公式减少，空白表示分析错误。根据上面的分析表，对输入串# a、b和a #的分析过程如下：1。活前缀、可约前缀、前缀和符号串的任何头，包括：前缀为：a，ab，ABC，语法GS是，S，*，r，a和871。vt *，然后a是正常前缀，或称为活动前缀。如果A是包含句柄的活前缀，并且每个句柄都是A的后端，那么A就是，如何构造LR分析表？AAabCbBBaCBbCc，例如，在句子Abacb规范的派生中的所有句柄、可约前缀和活前缀，规范派生，A、r、abcb、r、Abacb、r、Abacb、A、A、b、c、b、A、c、b、Abacb、，句柄：b、活前缀：A、ab、可约前缀：aB、Abacb、句柄：c、活前缀：aBa、aBac、aBaC、abac查找可约前缀的方法。如果aa (a VN)是文法的可约前缀，如果有规则Au，au也是文法的可约前缀。可约前缀集：语法中所有可约前缀的集合，aBCb是可约前缀，如果BBaCBbCc，ab，aBc，aBaC，aBac也是可约前缀。对于任何语法，如果有一个已知的可约前缀，所有可约前缀都可以通过以下方法获得：gaaabbbbacbBCc，它有四个对应于生产公式e e t的项目。对于语法g，生产公式的右边部分带有特殊符号“()”,它被称为LR(0)语法项目，缩写为项目、2，项目，例如，生产公式SXYZ有四个项目。0某某1某某2某某3某某生产公式A只对应一个项目：A，它可以位于生产公式右侧的任何位置；3、项目集：由几个项目组成的集合称为项目集。例如，上述产品的四个项目形成一个项目集。跟进符号有很多种，根据其项目可分为很多种：(1)跟进符号是终止符：a a ，称为移入项目；(2)下列符号为非终结符： B ，称为待约化项；(3)以下符号为空：即点在最右边的A 处，称为归约项；(4)归约项左边是语法起始符号S ，称为接受项。4.后续符号：紧接在项目中符号“”(或“)之后的符号称为项目的后续符号。后续符号表示下一时刻读取的符号。后续符号集：项目集中每个项目的后续符号集称为后续符号集。例如，以下项目集ee t，fi 的符号集是，i，7。满足以下两个条件的项目集称为兼容项目集。没有移动项和缩减项共存，没有多个缩减项共存，a a ，c a a a ，c a ，由项集组成，分为BASIC闭包和CLOSE闭包。假设相对于符号x，si是Sk的后续状态，计算BASIC(si)，basic (si)=a ax a a x sk，计算闭包(si)， basic (si)闭包(Si)， a a y 闭包(Si)，并且YVn是Yr闭包(Si)，r是符号串。(3)重复(2)直到闭合(Si)不再增加，8。状态内容，例如：G S S AA AABA C，1SA5AAAB2SA6AAAB3AAAB7AC4AAAB8AC，设置起始状态为S0，BASIC(S0)= SA ，闭包(S0)= SA，A AAB，A C，S1是S0相对于符号A的后继状态。 BASIC (S1)=S A ，CLOSION(S1)= SA，S2是S0对符号A的继承状态，BASIC (S2)=A A AB，CLOSION(S2)= AAAB，A AAB，A C，我列出所有项目(如果语法的起始符号有多条规则，将首先改为扩展语法)。 ii从起始符号项开始，计算起始状态S0的BASIC (S0)和closure (s0)。iii根据后续符号为每个状态的后续状态计算basic和closure。9.状态描述序列，例如，gSSA u BAAAB u CBaBb u d，0SS1SA2SB3AAAB4aC5bABB6bd，SS，SS，SA，SA，SB，SB，AaAb，AAAb A，AaAb，a AAB 处于一种状态的一组项目，具有相同后续符号的不同项目，后续状态是相同的，而处于不同状态的项目组是相同的。 与前一个项目相对应的几个项目具有与前一个项目相同的后续状态。构造了LR(0) analySis表。状态转移函数GO(S1，X)=Sj表示状态S1相对于语法符号X的后续状态是Sj。lr (0)分析表是根据以下规则构造的：1对于AaXBSi，GO(Si，X)=Sj，如果XVt，(移动到项目中)，动作Si，X=Sj如果XVn，(将被还原)然后转到Si，x=j，ii对于AaSi(被还原)，如果Aa是语法的第j个生成，则为所有X设置动作Si，x=rj A=S4，S4，S5，S6，1，2，3，S1，ACC，S2，SA S2(还原项)，SA是第一个生产公式，因此动作S2，A=R1动作S2，B=R1动作S2，C=R1动作S2，d=R1动作S2，=R1，R1，R1，R1，R1，a c s0，go (s0，c)=S5，c vt，所以动作s0，C d)=S6，d vt，so动作s0，d=S6，SSS0，go (s0，S)=S1，SVn，so转至s0，s=1，s a s0，go (s0，a)=S2，a VN，so转至S0，a=2，s b s0，GO(S0，b)=S3，b VN，so转至 只有当一个文法G是LR(0)文法，即G的每个状态项集是相容的时，LR(0)分析表才能用LR(0)分析方法来构造和分析。，gsseee t u TTt * f u ff (e)I，提出了一个问题，SLR(1)分析表的构造方法，si=b a ，Aa，Ca(是一个以第一个符号为终止符的符号串)，对于归约项a a ，c a ，分别跟随(a)和跟随(c ),对于移入项b a ，找出其对于项目集中的移动-缩减和缩减-缩减的冲突，采用以下解决方案：如果遵循(a);遵循(c);第一个()=，当状态1面对输入符号a时，分析表如下构造：1)如果当前输入符号a第一个()，则移入；2)如果当前输入符号a遵循(a)，则按生产公式减少；3)如果当前输入符号a遵循(b)，则按b生产公式减少；4)其他，报告错误。SLR(1)分析表的结构，状态转移函数GO(S1，X)=Sj表示状态S1相对于语法符号X的后续状态为Sj，SLR(1)分析表的结构规则：I为A A X Si，GO(S1，X)=SJ，如果XVt，(移入项)设置动作S1，X=Sj如果XVn，(待归约项)设置为S1，X=j，Ii为A A x=rj设置为任意输入符号xFollow(A)，iii如果SaSi，动作Si，#=acc(S是起始符号，归约项)，iv所有其他情况都是错误的，LR(1)分析表结构，提出一个问题，Follow(A)，Follow(c)和first()相交，也就是说，当不相容项集中的前瞻性集合与它们的相关集合相交时，它们不能用SLR(1)分析方法进行分析。gs 0s 1scbba 2aaab3aab4bc5bdb6ca7da，状态描述顺序见P213书图8-10。状态S10=s cbba ，a a ab和状态S8=c a ，d a 不兼容。follow (c)=b，a follow (d)=b，SLR(1)分析的局限性如果SLR(1)分析表仍有多个条目，则说明仅使用LR(0)项集和follow集来分析该语法是不够的。构造两个lr (1)分析表的思想是：(1) lr (1)项，在LR(0)项中放置前向搜索符号a以形成a a ，a，a follow (a)，3354，LR(1)项，(2)有效项，对于语法g s a a ，它对于活动前缀r=&a有效，只要有规范派生，s，*，r，&ay，r，&ay，y vt *， 缩减项Aa对活动前缀r=&a有效，则符号字符串A应缩减为A。移入项a a 对活动前缀r=&a有效，则句柄尚未形成，下一个操作应移入。 定义，对于