编译原理之语法分析-自下而上分析(三)

85397518 2020-05-17

  在上一篇博客中我们已经讲过如何构造LR(0)分析表,SLR构造分析表的前五个步骤是与LR(0)一样的,因此这里就不再对前五个步骤讲解。

  前五个步骤一样的原因:一个文法如果是SLR文法,则它一定是LR(0)文法,因此我们在判断它是不是SLR文法之前要先判断是不是LR(0)文法

  https://www.cnblogs.com/scm2019/p/12899757.html (前五个步骤可参考上一篇博客)

  (一)SLR分析法

    SLR分析法作用:SLR基于LR(0),通过一个前看符号,来决定是否执行归约动作或执行哪个归约动作。

    SLR分析法优点:1、有可能减少需要归约的情况   2、能够去除某些移进-归约冲突

    SLR分析法缺点:仍然有冲突出现的可能。

    

    SLR(1)解决冲突的办法

    首先看一下比较标准的解释:

    编译原理之语法分析-自下而上分析(三)

    举个例子理解上图,假如这里有一个项目集,如下图。

   编译原理之语法分析-自下而上分析(三)

       很明显这是一个s-r冲突,所以它不属于LR(0)文法,但是根据SLR(1)的解决方法,我们可以先求出产生式左侧终结符的Follow集。

     假如Follow(R) = { +, - } ,Follow(T) = { !,* }

     这时根据R和T的Follow集和移进项目圆点后的非终结符有以下三种情况

     1、当输入符号为 = 时,这时我们就把第一个产生式进行移进操作。

     2、当输入符号属于Follow(R)时(+ 或者 -),就将R->L·进行归约。

     3、当输入符号属于Follow(T)时(! 或者 *),就将T->T·进行归约。

     以上为成功消除冲突的情况

     假如Follow(R) = { =, * } ,Follow(T) = { +,* }

       1、移进项目圆点后的终结符(=)属于Follow(R),因此报错,即还是存在移进-归约冲突。因为我们还是不知道当输入符号为=时,要对S->L·=R进行移进,还是对R->L·进行归约。

     2、此外,Follow(R) ∩ Follow(T) = { * },报错,即还是存在归约-归约冲突。因为我们还是不知道当输入符号为*时,要对R->L·进行归约,还是对T->L·进行归约。

     以上为消除冲突失败的情况

     总结:如果想消除项目中的集冲突,必须满足以下两种情况(重要事情说三遍)

          总结:如果想消除项目中的集冲突,必须满足以下两种情况(重要事情说三遍)

       总结:如果想消除项目中的集冲突,必须满足以下两种情况(重要事情说三遍)

       1、移进项目圆点后的终结符(严格来说是圆点后的First集),不属于归约项目的Follow集。

       2、所有归约项目的Follow集两两相交必须为空。

    (二)构造SLR分析表

      编译原理之语法分析-自下而上分析(三),判断文法是否属于SLR文法,如果是给出SLR分析表

      1、列出文法的规范项目集

       编译原理之语法分析-自下而上分析(三)

       2、构造识别活前缀的NFA

        编译原理之语法分析-自下而上分析(三)

    3、识别或前缀的DFA

         编译原理之语法分析-自下而上分析(三)

    

       4、根据DFA判断LR(0)

      显然,在I1中面对符号E我们无法判断要进行归约还是移进,及存在S-R冲突。

      同样,在I2中面对终结符id,也存在着S-R冲突。

      因此该文法不是LR(0)文法

    5、算出Follow集,然后判断能否使用SLR的方法消除冲突,如果可以则是SLR文法        

      在I1中, Follow(S)={#} 不包含终结符+,因此I1中的S-R冲突可以消解。

      在I2中,Follow(E)={ #, ),+ },不包含终结符( ,因此I2的S-R冲突可以消解。

      综上所述,冲突能够被消除,该文法属于SLR(1)文法。

    6、画出SLR(1)分析表

         文法编号为:      

      1 : S->E

      2 : E -> id

      3 : E -> id(E)

      4 : E -> E+ id

      编译原理之语法分析-自下而上分析(三)

         构造SLR(1)方法技巧

       其实LR(0)和SLR(1)分析表雷同,SLR(1)分析表只是比LR(0)分析表少几个归约项。

       假如该文法是一个LR(0)文法,那么跟上图不一样的是3、6、7所在的行应该填满,即3所在行全填r2,6所在行全填r4,7所在行全填r3。其余的和上图一模一样。

       但是为什么SLR(1)比LR(0)分析表少几个呢?

       其实我们找到r2对应的归约产生式为E->id,而发现Follow(E)={ (,+,# },即Follow(E)中不存在id 和 ( ,因此就不需要将id 和 ( 所在列也填上r2,否则使我们发现错误不及时,造成效率低额问题。

       同理r3和r4对应归约产生式为 E -> id(E) 和  E -> E+ id,同样Follow(E)={ (,+,# }。因此id 和 ( 不需要填r3 和 r4。

    如果还没明白我们再举一个例子,有如下文法

    编译原理之语法分析-自下而上分析(三)

       该文法LR(0)分析表为

    编译原理之语法分析-自下而上分析(三)

    该文法SLR(1)分析表为

     编译原理之语法分析-自下而上分析(三)

     r1对应的归约产生式为S->BB·,r2和r3对应的归约产生式为B->aB· 和 B->b·

     在状态5所在的行,LR(0)分析表全部填写了r1,但是Follow(S)= { # },并没有a和b,所以在SLR(1)分析表中,只需要在状态5的#所在列填写r1。

     同理,我们先计算r2和r3产生式的Follow集,Follow(B)= { a,b,# },三个都有,因此在SLR(1)分析表中和LR(0)分析表中对应状态行都应该填写上。

     总结,LR(0)和SLR(0)分析表结构一样,唯一不同的就是归约项目所在的状态行,LR(0)不需要判断直接全部填写Rn,而在SLR(1)分析表中需要先判断Follow集,然后根据Follow集中已有的终结符去填SLR(1)表

       下边分别给出构造LR(0)和SLR(1)分析表比较系统的描述,可根据上述例子去理解一下:

     编译原理之语法分析-自下而上分析(三)

      编译原理之语法分析-自下而上分析(三)

     以上均为个人学习总结,如有错误或异议欢迎提出(自下而上分析法未完待续......)。

相关推荐