编译原理-语法分析

FIRST
¶

$FIRST (X)$

如果 $X$ 是一个终结符号，那么 $FIRST (X) = X$
如果 $X \to ε$ 是一个产生式，那么 $ε \in FIRST (X)$
如果 $X$ 是一个非终结符号，且 $X \to Y_{1} Y_{2} \dots Y_{k}$ 是一个产生式：
- $FIRST (Y_{1}) \in FIRST (X)$
- 对于 $1 ⩽ t ⩽ k$ ，如果 $\forall 1 ⩽ s < t$ 都有 $ε \in FIRST (Y_{s})$ 成立，则 $FIRST (Y_{t}) \in FIRST (X)$

$FIRST (X_{1} X_{2} \dots X_{k})$

向 $FIRST (X_{1} X_{2} \dots X_{k})$ 加入 $FIRST (X_{1})$ 的所有非 $ε$ 符号
如果 $ε \in FIRST (X_{1})$ ，再加入 $FIRST (X_{2})$ 的所有非 $ε$ 符号；以此类推
如过 $ε \in FIRST (X_{t})$ 对 $1 ⩽ t ⩽ k$ 均成立，则将 $ε$ 加入 $FIRST (X_{1} X_{2} \dots X_{k})$ 中

HINT

$FIRST$ 集合大概就是语法分析树中，当前节点即将扩展的下一个节点的点集。

FOLLOW
¶

$S$ 是开始符号， $$$ 是输入右端的结束标记

将 $$$ 放到 $FOLLOW (S)$ 中
如果存在一个产生式 $A \to α B β$ ，将 $FIRST (β)$ 中所有的非 $ε$ 符号放入到 $FOLLOW (B)$ 中
如果存在一个产生式 $A \to α B$ 或存在一个产生式 $A \to α B β$ 且 $ε \in FIRST (β)$ ，将 $FOLLOW (A)$ 中所有符号放到 $FOLLOW (B)$ 中

HINT

$FOLLOW$ 集合大概就是语法分析树中，以当前节点为根节点的子树扩展完毕后，回溯时所即将扩展的下一个节点的点集。

自顶向下的语法分析
¶

LL(1) 文法
¶

有二义性和左递归的文法都不是 $LL (1)$ 的
一个文法是 $LL (1)$ 的，当且仅当 $G$ 的任意两个不同的产生式 $X \to α ∣ β$ 满足：
- $FIRST (α)$ 和 $FIRST (β)$ 是不相交的集合。也就是不存在左公因子。
- 如果 $ϵ \in FIRST (α)$ ，则 $FIRST (X)$ 和 $FIRST (β)$ 是不相交的集合
- 如果 $ϵ \in FIRST (β)$ ，则 $FIRST (X)$ 和 $FIRST (α)$ 是不相交的集合

预测分析表
¶

对于 $G$ 的每个产生式 $A \to α$

对于 $FIRST (α)$ 中的每个终结符号 $a$ ，将 $A \to α$ 加入到 $M [A, a]$ 中
如果 $ϵ$ 在 $F I R S T (α)$ 中：
- 那么对于 $FOLLOW (A)$ 中的每个终结符号 $b$ ，将 $A \to α$ 加入到 $M [A, b]$ 中
- 如果 $$$ 在 $FOLLOW (A)$ 中，将 $A \to α$ 加入到 $M [A, $]$ 中

自底向上的语法分析
¶

规范 LR(0) 项集族
¶

项集的闭包
¶

如果 $I$ 是文法 $G$ 的一个项集，那么 $CLOSURE (I)$ 可由下面两个规则从 $I$ 构造得到。
- 将 $I$ 中的各个项加入到 $CLOSURE (I)$ 中
- 如果 $A \to α \cdot B β$ 在 $CLOSURE (I)$ 中， $B \to γ$ 是一个产生式，并且项 $B \to \cdot γ$ 不在 $CLOSURE (I)$ 中，就将这个项加入其中。不断应用这个规则，直到没有新项加入到 $CLOSURE (I)$ 中为止

直观地讲， $CLOSURE (I)$ 中的项 $A \to α \cdot B β$ 表明在语法分析过程的某点上，我们认为接下来可能会在输入中看到一个能够从 $B β$ 推导得到的子串。

GOTO 函数
¶

$GOTO (I, X)$ ，其中 $I$ 是一个项集， $X$ 是一个文法符号。
$GOTO (I, X)$ 被定义为 $I$ 中所有形如 $[A \to α \cdot X β]$ 的项所对应的项 $[A \to α X \cdot β]$ 的集合的闭包。

直观地讲， $GOTO$ 函数用于定义一个文法的 $LR (0)$ 自动机中的转换，描述了当输入为 $X$ 时离开状态 $I$ 的转换。

构造项集族
¶

初始时， $C = I_{0} = {CLOSURE ({[S^{'} \to \cdot S]})}$
对于 $C$ 中的每个项集 $I$ ：
- 对于每个文法符号 $X$ ：
  - 如果 $GOTO (I, X)$ 非空且不在 $C$ 中，将 $GOTO (I, X)$ 加入到 $C$ 中
重复过程 2

构造 SLR 语法分析表
¶

构造 $G^{'}$ 的规范 $L R (0)$ 项集族 $C = {I_{0}, I_{1}, \dots, I_{n}}$ .
根据 $I_{i}$ 构造得到状态 $i$ 。状态 $i$ 的语法分析动作按照下面的方法决定：
- 如果 $[A \to α \cdot a β]$ 在 $I_{i}$ 中，并且 $GOTO (I_{i}, a) = I_{j}$ ，令 $ACTION [i, a] = s_{j}$ ，即移入 $j$ ；其中， $a$ 必须是终结符。
- 如果 $[A \to α \cdot]$ 在 $I_{i}$ 中，那么对于 $FOLLOW (A)$ 中的所有 $a$ ，令 $ACTION [i, a] = r_{j}$ ，即规约 $j$ ；其中， $j$ 为 产生式 $A \to α$ 的编号； $A \neq S^{'}$ .
- 如果 $[S^{'} \to S \cdot]$ 在 $I_{i}$ 中，令 $ACTION [i, $] = a c c$ ，即接受。
如果根据上面的规则生成了任何冲突动作，则这个文法不是 $SLR (1)$ 的。状态 $i$ 对于各个非终结符号 $A$ 的 $GOTO$ 转换使用下面的规则构造得到：
- 如果 $GOTO (I_{i}, A) = I_{j}$ ，那么， $GOTO [i, A] = j$ 。
规则 (2) 和规则 (3) 没有定义的条目均设为 “报错”。
语法分析器的初始状态是根据 $[S^{'} \to \cdot S]$ 所在项集构造得到的状态。

有效 LR(1) 项集族
¶

可行前缀
- 可以出现在一个移入--规约的语法分析器的栈中的最右句型前缀，称为可行前缀
$LR (1)$ 项
- 形如 $[A \to α \cdot β, a]$ 的项，称为 $LR (1)$ 项；其中 $A \to α β$ 是一个产生式， $a$ 是一个终结符或右端结束标记 $$$
- 形如 $[A \to α \cdot, a]$ 的项只有在下一个输入符号为 $a$ 时才选择 $A \to α$ 规约。
可行前缀的有效项
- $LR (1)$ 项 $[A \to α \cdot β, a]$ 对于可行前缀 $γ$ 有效的条件是：
  - 存在一个最右推导 $S \overset{*}{\underset{r m}{\Rightarrow}} δ A ω \underset{r m}{\Rightarrow} δ α β ω$ ，且
  - $γ = δ α$ ，且
  - 要么 $a$ 是 $ω$ 的第一个符号，要么 $ω = ε$ 且 $a = $$

项集的闭包
¶

如果 $[A \to α \cdot B β, a]$ 对可行前缀 $γ = δ α$ 有效，那么必然存在一个最右推导 $S \overset{*}{\underset{r m}{\Rightarrow}} δ A α x \underset{r m}{\Rightarrow} δ α B β a x$ 。假设 $β a x$ 推导出终结符号串 $b y$ ，那么对于某个形如 $B \to η$ 的产生式，有推导 $S \overset{*}{\underset{r m}{\Rightarrow}} γ B b y \underset{r m}{\Rightarrow} γ η b y$ . 因此， $[B \to \cdot η, b]$ 是 $γ$ 的有效项。其中， $b \in FIRST (β a)$ .

如果 $I$ 是文法 $G$ 的一个项集，那么 $CLOSURE (I)$ 可由下列规则从 $I$ 中构造得到。
- 对于 $I$ 中的每个项 $[A \to α \cdot B β, a]$
  - 对于 $G^{'}$ 中的每个产生式 $B \to γ$
    - 对于 $FIRST (β a)$ 中的每个终结符号 $b$
      - 将 $[B \to γ, b]$ 加入到集合 $I$ 中

Hint

本质上， $SLR$ 是利用 $LR (0)$ 自动机能够识别可行前缀这一事实构造的语法分析方案； $LR (1)$ 在此基础上考虑了对可行前缀的有效性。
$LR (1)$ 和 $LR (0)$ 构造闭包的算法的区别在于：
- 不再对于任意的 $[A \to α \cdot B β]$ 添加到闭包中了，这样做的目的是为了减少移入--规约冲突。也就是，如果 $I$ 中有产生式 $A \to α \cdot B β$ ，对于产生式 $B \to η$ ：
  - $SLR$ ：直接将 $B \to η$ 加进 $I$ 的闭包中
  - $LR (1)$ ：由于有一个向前看符号，不妨记 $A \to α \cdot B β$ 的向前看符号为 $a$ ，那么仅当满足 $a \in FIRST (β a)$ 时才能将 $B \to η$ 加进 $I$ 的闭包

GOTO 函数
¶

计算 $GOTO (I, X)$ ：

将 $J$ 初始化为空集
对于 $I$ 中的每个项 $[A \to α \cdot X β, a]$
- 将项 $[A \to α X \cdot β, a]$ 加入到集合 $J$ 中
返回 $CLOSURE (J)$

构造项集族
¶

初始时， $C = I_{0} = {CLOSURE ({[S^{'} \to \cdot S, $]})}$
- 对于 $C$ 中的每个项集 $I$
  - 对于每个文法符号 $X$
    - 如果 $GOTO (I, X)$ 非空且不在 $C$ 中
      - 将 $GOTO (I, X)$ 加入 $C$ 中

构造规范 LR(1) 语法分析表
¶

构造 $G^{'}$ 的规范 $LR (0)$ 项集族 $C = {I_{0}, I_{1}, \dots, I_{n}}$ .
根据 $I_{i}$ 构造得到状态 $i$ 。状态 $i$ 的语法分析动作按照下面的方法决定：
- 如果 $[A \to α \cdot a β, b]$ 在 $I_{i}$ 中，并且 $GOTO (I_{i}, a) = I_{j}$ ，令 $ACTION [i, a] = s_{j}$ ，即移入 $j$ ；其中， $a$ 必须是终结符。
- 如果 $[A \to α \cdot, a]$ 在 $I_{i}$ 中，且 $A \neq S^{'}$ ；那么令 $ACTION [i, a] = r_{j}$ ，即规约 $j$ ；其中， $j$ 为产生式 $A \to α$ 的编号。
- 如果 $[S^{'} \to S \cdot, $]$ 在 $I_{i}$ 中，令 $ACTION [i, $] = a c c$ ，即接受。
如果根据上面的规则生成了任何冲突动作，则这个文法不是 $L R (1)$ 的。状态 $i$ 对于各个非终结符号 $A$ 的 $GOTO$ 转换使用下面的规则构造得到：
- 如果 $GOTO (I_{i}, A) = I_{j}$ ，那么， $GOTO [i, A] = j$ 。
规则(2) 和规则(3) 没有定义的条目均设为“报错”。
语法分析器的初始状态是根据 $[S^{'} \to \cdot S, $]$ 所在项集构造得到的状态。

FIRST¶

FOLLOW¶

自顶向下的语法分析¶

LL(1) 文法¶

预测分析表¶

自底向上的语法分析¶

规范 LR(0) 项集族¶

项集的闭包¶

GOTO 函数¶

构造项集族¶

构造 SLR 语法分析表¶

有效 LR(1) 项集族¶

项集的闭包¶

GOTO 函数¶

构造项集族¶

构造规范 LR(1) 语法分析表¶

FIRST
¶

FOLLOW
¶

自顶向下的语法分析
¶

LL(1) 文法
¶

预测分析表
¶

自底向上的语法分析
¶

规范 LR(0) 项集族
¶

项集的闭包
¶

GOTO 函数
¶

构造项集族
¶

构造 SLR 语法分析表
¶

有效 LR(1) 项集族
¶

项集的闭包
¶

GOTO 函数
¶

构造项集族
¶

构造规范 LR(1) 语法分析表
¶