本文更新于2024-05-28 20:23:46

1. $LR(0)$分析#

1.1 可归前缀和活前缀#

定义$1.1.1$ 如果文法$G$的拓广文法$G'$有正规推导$S' \mathop{\Rightarrow}\limits^* \alpha A\omega \mathop{\Rightarrow}\limits_R \alpha \beta \omega$，且若$\gamma$是串$\alpha \beta$的一个前缀，则$\gamma$是文法$G'$和$G$的一个活前缀。$\gamma$是规范句型$\alpha \beta \omega$的前缀，但是它不会超过$\alpha \beta \omega$的句柄的右端。

如果$\gamma = \alpha\beta$则$\gamma$是文法$G$的一个可归前缀。

TIP

$LR(0)$分析方法实际上就是在不断列出$\alpha \beta$的前缀，一旦出现$\alpha\beta$也就是出现了可归前缀，就立刻使用$A\to \beta$归约句柄。

1.2 求解活前缀与可归前缀#

如果$G$是一个上下文无关文法，$G'$是其拓广文法，对每一个非终结符$A$，定义$LC(A)$运算。

TIP

$LC(A)$运算的结果是所有包含有$A$的正规句型中$A$左边的符号串。

通过$LC(A)$就能找出所有不包含句柄的活前缀。

定理$1.1.1$ 若有产生式$B \to \alpha A \omega$，则$LC(A) \supseteq LC(B) \times \{\alpha\}$

通过该定理，依次列方程求$LC(A)$:

$LC(A)$只求出了非终结符$A$在未被替换时左部可能产生的串，还未能形成句柄。定义产生式$A \to \beta$的$LR(0)CONTEXT(A\to\beta)$运算：

得到的串就都是可归前缀。

以每一个产生式$A\to \beta$的$LR(0)CONTEXT(A\to \beta)$构造一个$NFA$，终态为可归前缀。接着从开始状态$X$连空弧向每一个$NFA$，得到一个大$NFA$，该$NFA$