MENU

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

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

概述

LR(0)找出句柄前缀,构造分析表,然后根据输入符号进行规约。见到First集就移进,见到终态就归约

LR(0)分析表的构造

两个函数

  • goto转移函数:就是在产生式C的状态上,后面接符号x后产生新的自动机状态的过程。
  • closure闭包函数:参数是goto()产生的集合。简而言之,如果下一个期待输入的是非终结符B,那么把该非终结符的产生式也并入到集合当中。

LR(0)分析表构造算法

C0 = closure (S’ -> ● S $) // the init closure
SET = {C0} // 标记已经计算过的状态
Q = enQueue(C0) // a queue
while (Q is not empty)
  C = deQueue(Q)
  foreach(x ∈ (N∪T) )
    D = goto(C, x)
    if (x ∈ T)
      ACTION[C, x] = D
    else
      GOTO[C, x] = D
    if (D not ∈ SET)
      SET ∪= {D}
      enQueue(D)

案例

案例:

0: S'-> S$
1: S -> x x T
2: T -> y

LR(0)分析表

动作(ACTION)转移(GOTO)
状态符号xy$ST
s1s2g6
s2s3
s3s4g5
s4r2r2r2
s5r1r1r1
s6accept
  • s2(shift 2),改变到自动机的状态s2
  • g5(goto 5),转移到自动机的状态s5
  • r2(reduce 2),归约到文法上的编号2

分析过程

xxy$为例

步骤状态栈S符号栈/分析栈输入符号下一步动作
1s1$xxy$s2
2s1s2$xxy$s3
3s1s2s3$xxy$s4
4s1s2s3s4$xxy$r2(T -> y)
5s1s2s3$xxT$g5
6s1s2s5$xxT$r1(S -> x x T)
7s1$S$g6
8s6$$accept
分析成功

goto和closure算法

goto(C, x):
  temp = {} // a set
  foreach (C’s item i: A -> β ● x γ )
    temp ∪= {A -> β x ● γ }
  return closure(temp)
// goto转移函数,就是在产生式C的状态上,后面接符号x后产生新的自动机状态的过程。
closure(C):
  while(C is still changing)
      foreach (C’s item i: A -> β ● B γ )
            C ∪= {B -> …}
  return C;
// closure闭包函数,参数是goto()产生的集合。简而言之,如果下一个期待输入的是非终结符B,那么把该非终结符的产生式也并入到集合当中。

LR(0)分析算法问题分析

对每一个形如X -> α ● 的项目:

  1. 直接把 α 归约成 X, 紧跟一个 “goto”,尽管不会漏掉错误,但会延迟错误发现时机。
  2. LR(0)分析表中可能包含 移进-归约冲突 与 归约-归约冲突 。

问题1:错误定位

FOLLOW(S) = { $}, 如果输入的是● x x y x到状态3的时候是x x y ● x下一个输入是x,而非$,此时应该就该抛出异常,而实际上他会一直归约到状态4后再报错。这就是错误定位

问题2:冲突

而事实上FOLLOW(E) = {$} ,+号并不是FOLLOW集里的,所以并不应该执行第2个(归约)操作,而应该是第1个(移进)操作。

因为E的FOLLOW集不包含+,所以假如此时进行归约,归约后,E后面跟着的输入此时是+,直接就报错了。

解决

解决错误定位&冲突问题 → SLR算法

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