lr parser

文法介绍

文法 (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)

相关阅读

• LR-Parsing of Extended Context Free Grammars
• (Simple LR(k) grammars)[https://dl.acm.org/doi/10.1145/362619.362625]
• https://www.cs.clemson.edu/course/cpsc827/material/LRk/LR1.pdf
• https://blog.csdn.net/m0_37345402/article/details/105678216
• https://blog.csdn.net/qq_33553218/article/details/103522792
• https://blog.csdn.net/qq_35793285/article/details/94378977
• lr0 移入规约冲突
• 其他
• https://blog.csdn.net/m0_37345402/article/details/105678216