LR(1)分析法

叁歲伎倆 2022-01-27 12:59 258阅读 0赞

SLR(1)分析法只是简单地考察下一个输入符号`b`是否属于与归约项目 A → α A\\rightarrowα A→α相关联的`FOLLOW(A)`，但 b ∈ F O L L O W ( A ) b\\in FOLLOW(A) b∈FOLLOW(A) 只是归约的一个必要条件，而非充分条件。

假设栈内的符号串为 $ $ \\delta\\alpha $ ，规约之后变为 $ $\\delta A$ ，当前读到的输入为`a`，若文法中不存在以 $ $\\delta a $ 为前缀的规范举行，那么这种规约就无效了。**并不是FOLLOW(A)中的每个元素在A的所有举行中都会出现在A的后面。**

# LR(1)分析法的思想 #

当师徒用某一规则 A → α A \\rightarrow\{\\alpha\} A→α规约栈顶的符号 α \\alpha α时，不仅应该查看栈中符号串 δ α \\delta \\alpha δα，还应向前扫视一个输入符号`a`，只有当 δ A a \\delta Aa δAa确实构成文法某一规范句型的前缀时，才能用此规则进行规约。

因此，可以考虑在原来LR(0)项目集中增加更多的展望信息，这些信息有助于克服动作冲突和排除无效规约，也就是需要重新定义称之为\*\*LR(1)\*\*的项目。

# LR(1)项目 #

一个LR(1)项目是一个**二元组**\[ A → α ⋅ β ， a A \\rightarrow\{\\alpha·\\beta，a\} A→α⋅β，a\]，其中 A → α ⋅ β A \\rightarrow\{\\alpha·\\beta\} A→α⋅β是一个LR(0)项目，每个`a`是终结符，称它为**展望符或搜索符**。

当$\\beta \\not= \\epsilon $时，搜索是无意义的。

当 β = ϵ \\beta = \\epsilon β=ϵ时，搜索符`a`明确指出当\[ A → α ⋅ β ， a A \\rightarrow\{\\alpha·\\beta，a\} A→α⋅β，a\]是栈顶状态的一个LR(1)项目时，**仅在输入符号是`a`时才能用 A → α A \\rightarrow\{\\alpha\} A→α** 规约，**而不是对FOLLOW(A)** 中的所有符号都用 A → α A\\rightarrow\{\\alpha\} A→α规约。

## LR(1)项目集族构造方法 ##

### 构造LR(1)项目集`I`的闭包函数 ###

1.  `I`的任何项目都属于`CLOSURE(I)`
2.  若项目 \[ A → α ⋅ B β a ， a \] \[A \\rightarrow\{\\alpha·B\\beta\}a，a\] \[A→α⋅Bβa，a\]属于`CLOSURE(I)`， B → r B \\rightarrow\{r\} B→r是文法中的一条规则， b ∈ F I R S T ( β a ) b\\in FIRST(\\beta a) b∈FIRST(βa)，则 \[ B → ⋅ r ， b \] \[B \\rightarrow\{·r\}，b\] \[B→⋅r，b\]也属于`CLOSURE(I)`
3.  重复第二步直到`CLOSURE(I)`不再增大为止

### 转换函数构造 ###

令`I`是一个LR(1)项目集，`X`是一个文法符号，函数  
 G O ( I , X ) = C L O S U R E ( J ) J = \{ \[ A → α X ⋅ β ， a \] ∣ \[ A → α ⋅ X β ， a \] ∈ I \} GO(I,X) = CLOSURE(J) \\\\ J = \\\{\[A \\rightarrow\{\\alpha X·\\beta\}，a\] | \[A \\rightarrow\{\\alpha ·X\\beta\}，a\] \\in I\\\} GO(I,X)=CLOSURE(J)J=\{ \[A→αX⋅β，a\]∣\[A→α⋅Xβ，a\]∈I\}

# 总结 #

多数情况下同一个文法的LR(1)项目集的个数比LR(0)项目集的个数要多，**这是因为对同一个LR(0)项目集由于搜索符的不同而对应着多个LR(1)项目集**。

当一个文法是LR(0)文法，则一定是一个SLR(1)文法，也是LR(1)文法。反之却不一定成立。