编译原理课件04(6)SLR(1)分析法.ppt

1、，4.5.3 SLR(1)分析法，这个条件相当苛刻，对于大多数编程语言来说，一般不能满足LR(0)语法的条件，即使是描述谓词表达式的简单语法也不是LR(0)语法。考虑算术表达式的语法：每个LR(0)项集不包含冲突项。因为LR(0)语法需要语法，所以EE T | T，TT * F | F，F (E) | ID，4.5.3 SLR (1)分析方法，它直接扩展语法和数字规则来构造，0。EE，1 .EE T，2。ET，3 .TT * F，4。TF，5。F(E)，6。Fid，I0:E，I1:EE，EE，T，I2: ET，TT*F，T，I3:TF，F，I4:(，F，T，I5: Fid，id，I6:，id，

2、*，I8:F (E)，EE，T，E，I，id，id，*，E，4.5.3 SLR(1)分析方法，不难看出I1，I2，I9既包含移动项又包含归约项，所以这个表达式的语法不是LR(0)语法。根据构造LR(0)分析表的方法，构造的LR(0)分析表在2个状态和9个状态下面对输入符号*时包含多个定义元素，如下表所示。LR(0)表达式语法分析表，以及4.5.3 SLR(1)分析方法。为了明确地分析语言句子，有必要解决并进入归约或归约冲突。我们使用期待冲突项集的输入符号的方法来解决冲突。这种分析方法称为简单线性回归分析法，即线性回归(1)分析法。4.5.3 SLR(1)分析方法，仔细分析构造LR(0)分析表的

3、方法，很容易看出分析表中多重定义的原因在于规则2，即对于每个项目集Ik中的缩减项目A，不管当前输入符号如何，ACTION表中第k行的所有元素都被设置为rj，其中J是规则A的个数，因此，4.5.3 SLR(1)分析方法， 当LR(0)项目集规范族中存在具有迁移约简冲突和约简冲突的项目集时，当在分析表的第k行遇到输入符号B时，将不可避免地出现多个定义元素。 对于冲突项集，仅根据LR(0)项本身的信息是不可能解决冲突的。您需要期待一个输入符号来检查当前环境。4.5.3 SLR(1)分析方法，对于缩减项A和B，只需调查当手柄缩减为A或B时，直接跟随A或B的终止符集，即FOLLOW(A)和FOLLOW(

4、B)，不相互交叉，也不包含移动符号B，即满足：ik=xbb，A，br，FOLLOW(A)。遵循(A)b=，4.5.3单反(1)分析方法，那么，当状态k面对输入符号A时，冲突可以按照以下规则解决：(1)如果a=b，则移入；(2)如果a遵循(a)，则使用规则a来减少。(3)如果a允许(B)，使用规则Br进行还原。(4)此外，还报告了一个错误。4.5.3 SLR(1)分析方法，一般来说，如果在LR(0)项目集I中有m个移入项目和n个减少的项目，当符号集A1、A2、AM和FOLLOW(B1)、FOLLOW(B2)、FOLLOW(Bn)相互交叉时，期待所有的移入项目。i:a11a11，a22a22，am

5、ma mm，b1r1，b2r2，bnrn，4.5.3slr (1)分析方法，假设a是当前输入字符：(1)如果aa1，a2，am，则移入。(3)此外，还报告了一个错误。(2)如果aFOLLOW(Bi)，i=1，2，n，那么Biri用于归约。用于解决分析操作冲突的方法称为SLR(1)方法。4.5.3单反(1)分析方法。现在，我们分别研究上述例子中的三个项目集I1、I2和I9中的冲突是否可以用SLR(1)方法解决。因为“跟随”(E)=$=和“接受”(EE)是一个“接受”项目，所以在I1移动的接受冲突可以通过SLR(1)解决。如果某个文法的LR(0)项集或LR(0)分析表中包含的动作冲突可以用SLR(

6、1)解决，则该文法称为SLR(1)文法。，I1=EE，EE T，4.5.3 SLR(1)分析方法，因为FOLLE(E)=，$*=，当输入字符为，$，使用规则E T执行约简，当输入字符*面对时，可移入约简冲突，I2中的约简冲突可使用SLR(1)执行。类似于I2中的情况，在其项目集中移入约简的冲突可通过SLR(1)解决。因此，语法是单反(1)语法。I2=et，TT * f，i9=ee t，TT * f，4.5.3 SLR(1)分析方法，SLR(1)分析表的结构与LR(0)分析表基本相同。只有LR(0)分析表构造算法中的规则2被修改如下：如果约简项A属于Ik，则将actionk设置为任意终止符AFL

7、OW (A)，其中A是语法的jth规则。4.5.3 SLR(1)分析方法，根据上述方法，为前面例子中的算术表达式语法构造SLR(1)分析表，如表中所示：跟随(e)=$，跟随(e)=，$，跟随(t)=，$，*，4.5例子1具有扩展语法GS，0。ss，1。s sb，2。s baa，3。ASC，4。a助理秘书长，5岁。a a a 4。5.3 SLR (1)分析方法，(1)构造DFA识别语法标准句型的主动前缀。(2)确定语法是否是单反(1)语法，如果是，构建单反(1)分析表，如果不是，请说明原因。语法的LR(0)项集规范族和转换函数如下图所示：i0:S、i1:ss、sb、b、I : b、b、i4:sb

8、aa、S、I8: A aSc、语法GSLR(0)项集和转换函数、I 93360 A ASB、S、sb、c、b、4.5.3 LR 1分析方法考虑冲突项集是否可以通过SLR(1)解决。FOUND(a)=a，FOUND(S)=b，c，$，FOUND(S)=美元，4.5.3 SLR(1)分析方法，由于FOUND(S)b=$ b=，I1的移动还原冲突可以通过SLR(1)方法解决。因为有FOUND(A)b=ab=，所以I5中的移入减少冲突可以通过SLR(1)解决。i1=ss，s sb，i5=a a，s baa，4.5.3 SLR(1)分析方法，由于以下(a)跟随(s)=ab，c，$=，i9中的归约冲突也可

9、以通过SLR(1)方法解决。所以语法是SLR(1)语法。SLR(1)的分析表如下：表：I9=A aSb，s sb，4.5.3 SLR(1)分析方法，i03360，S，i1: ss，S Sb，b，i2:I :S Sb I63360 BaA，i7:S，i8:a ASC，语法GSLR(0)项集和转换函数，i9:a，4.5.3 SLR(1)分析方法，例2下面的扩展语法G是，我们首先用SS作为初始状态集的项，然后用闭包函数和转换函数构造DFA来识别语法G的活动前缀，如下图所示。0。ss，1。s l=r，2。s r，3。l * r，4。我，5岁。4.5.3 SLR(1)分析方法，可以发现在项目集I2:中的

10、移入和减少之间存在冲突，因此不可能使用SLR(1)来解决在I2:中的移入和减少之间的冲突，sl=r * r=r，s r，I2=，sl=r，r，l，因为遵循(r)=，$=，4.5.3 SLR (1)分析方法，1。为什么单反(1)法不能解决I 2中移动和还原的矛盾？2.如何解决移入和减少I2之间的冲突？问题：4.5.3 SLR(1)分析方法，因为当使用SLR(1)方法解决动作冲突时，它仅孤立地检查约简项A，只要当前输入符号AFLow(A)面对，就确定使用规则A进行约简，而不检查符号串在标准句型中所处的环境。ii3360a，i0i1 ii，$，AAA，i0i1 ij，$A，AAA，4.5.3slr

11、(1)分析方法，因为如果堆栈中的符号串是$，则它在约简后变成$ a，并且当前读取的输入符号是A，如果语法中没有前缀为AA的规范句型，则此约简，例如，我们检查标准句型ii的SLR(1)分析过程：I0:S，I 1:I2:S L=R，R L，L，I : R，R，I4:*，I7:l * r，r，I，l，i8:rl，l，r，i9:sl=r，lr (0)识别g活前缀的DFA，4 . 5 . 3 lr(1)分析方法，不难看出当状态2出现在堆栈顶部并面向输入时。4.5.3 SLR(1)分析方法，SL=R * R=R，也就是说，在所有包含R的句型中，并非FOUND(R)中的每个元素都出现在R之后。解决这个问题的

12、方法是LR(1)分析。4.5.4 LR(1)分析方法，在分析过程中，当试图用一定的规则A对栈顶的符号串进行约简时，我们不仅要看栈中的符号串，还要向前看输入的符号A。只有当Aa确实构成了某个标准语法句型的前缀时，我们才能用这个规则进行约简。LR(1)分析方法的思想：4.5.4 lr (1)分析方法，为此，我们可以考虑原LR(0)项目集；添加更多潜在客户信息，这有助于克服行动冲突和消除无效缩减。也就是说，这个项目需要重新定义，这就是所谓的LR(1)项目。一个LR(1)项是一个二进制，一个，一个，4.5.4LR(1)的分析方法，当时，搜索者A明确指出，当一个，一个LR(1)项处于栈顶状态时，它只能用

13、一个当输入符号是一个时来约简，而不是用一个来约简FOUND(A)中的所有符号，那时，搜索算子就没有意义了。其中a是LR(0)项，每个a是终止符，称为浏览者或搜索者。4.5.4 LR(1)分析方法，构造LR(1)项集族的方法与构造LR(0)项集规范族的方法基本相同。具体构造方法如下：(1)构造LR(1)项集I的闭包函数，(1)I的任何LR(1)项都属于闭包(I)。如果条目AB、a属于闭包(1)，而BR是语法规则，那么BR和B也属于闭包(1)。重复第(二)项，直到第(一)项不再增加。4.5.4 LR(1)分析方法，对于例2中的语法G，设I=SS，$为初始集的初始项集，并求其闭包：=CLOSE(SS

14、，$)，CLOSE(I)，=SS，$ SL=R，$，L*R，$，L * R. First (a)=first (=r $)=，first (a)=first ($)=$，first (a)=first ($)=$，4.5.4LR(1)分析方法，(2)构造转换函数，如此4.5.4lr (1)分析法，GO(I0，S)=SS，$=I1，GO(I0 *，)=L*R，=/$ RL，=/$，L*R，=/$ RL，$，I3: SR，$，R，I4:*，I5: Li，=/$，I，I，*，I6:I9:SL=R，$，I11: 在LR(1)分析中，解决了I2中移入-减少的冲突。4.5.4 LR(1)分析方法，构造LR(1)分析表的方法与构造LR(0)分析表的方法基本相同，只是约简项修改如下：如果约简项A和A属于Ik，则将ACTIONK、arj设置为搜索者A。根据上述方法，我们为例2中的LR(1)项集语