MENU

【编译原理】LR(1)分析算法

June 2, 2020 • Read: 131 • 编程之路,编译原理

LR(1)分析算法

概念

LR(1) 在每个项目中增加搜索符,例如有$A → α·Bβ$,则还需将$B$的规则也加入。

  • [X -> α ● β, a] 的含义是:

    • α在栈顶上
    • 剩余的输入能够匹配 βa
  • 当归约 X -> αβ时, a是前看符号

    • 把 reduce by X -> αβ ,填入ACTION[s, a]
  • 构造方法,其他和LR(0)相同,仅闭包的计算不同:

    • 对项目[X -> α ● Y β , a] ,添加[Y -> ● γ , b]到项目集,其中b∈FIRST_S(βa) 。

修改后的构造:

以状态0为例,根据产生式S' -> ● S ,$

  • 计算S闭包。即S -> ● L = R ,$S -> ● R ,$
  • 第一步得出的栈顶符号是非终结符L和R,所以继续计算 L 和 R 的闭包。即L -> ● * R ,=,$L -> ● id ,=,$R -> ● L ,$
  • L已经计算过,不再计算。
  • 前看符号是上一个产生式的FIRST_S(βa)

优化

LALR分析算法 把类似的项目集进行合并(比如上述的5和11,8和10),修改ACTION表和GOTO表以反映合并的效果。

特点:不会产生“移进-归约”冲突 ,但会产生“归约-归约”冲突

- - - 结束 - - -
  • 文章标题:【编译原理】LR(1)分析算法
  • 文章链接:https://blog.canye365.cn/archives/338.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021