Skip to main content

lr parser

· 3 min read

文法介绍​

文法 (Grammar) 由四部分组成:$(V_f , V_n , P , S)$

$V_f$: 描述的是终结符

$V_n$: 描述的是非终结符

P : 产生式

S : 开始的产生式

lr(0)​

right : terminal and notermial left : noterminal procduction: left and right configuration: production whith dot successor: set of configuration

build configure set​

the problem is that how to build the configure set :

the configure set is combine with two set : basic set and closure set

  • basic set ：$\lbrace A \rightarrow \omega S.\omega' | A \rightarrow \omega .S\omega' \in P \rbrace$

  • closure set ：$\lbrace A \rightarrow .\omega | A \rightarrow \omega \in P \quad AND \quad B \rightarrow \phi.A\phi' \in Configure \rbrace$

 The basis set consists of all configurations in S having a marker before an s, but with the
marker moved to follow the s;

closure set : {A -> .w | A->w is production}

lr(0)​

lr(0) 特别在于状态机：

  • reduce state : 转换函数的transition 要么 （一个底部 + 0到1个非终结符）
  • read state ： 转换函数的transition 都是终结符

lr(0) 算法​

lr(0) 描述的需要注意以下几个内容：

  • stack : stack 存了两个内容.一个是state 还有一个是$V$ 也就是终结符和非终结符的并集

冲突​

移入-规约冲突

  • 原因: 存在产生式P1和P2 , P1右部是产生式P2右部的前缀

规约-规约冲突:

  • 原因: 存在产生式P1和P2,P1 右部和P2右部有公共后缀

如何解决冲突​

移入-规约冲突解决: FOLLOW(P)没有交集

规约-规约冲突解决: FIRST(t) 没有交集

  • 举例
S->E
E->E+T | T
T->T*F | F
F->(E) | id

这里

E-> T.      (1)
T->T.*F     (2)

这两个移入规约冲突

产生式1 是产生式2的前缀

为了解决冲突,我们引入了slr(1),改进了lr(0)的遇到冲突的时候无法解决的问题

SLR(1)​

相关阅读​