语法分析

FIRST

计算方法

$FIRST(X)$

如果 $X$ 是一个终结符号，那么 $FIRST(X) = X$
如果 $X \rightarrow \varepsilon$ 是一个产生式，那么 $\varepsilon \in FIRST(X)$
如果 $X$ 是一个非终结符号，且 $X \rightarrow Y_1Y_2\cdots Y_k$ 是一个产生式：
- $FIRST(Y_1) \in FIRST(X)$
- 对于 $1 \leqslant t \leqslant k$，如果 $\varepsilon \in FIRST(Y_s)$, $1\leqslant s < t$ 成立，则 $FIRST(Y_t) \in FRIST(X)$。

$FIRST(X_1X_2\cdots X_k)$

向 $FIRST(X_1X_2\cdots X_k)$ 加入 $FIRST(X_1)$ 的所有非 $\varepsilon$ 符号
如果 $\varepsilon \in FIRST(X_1)$，再加入 $FIRST(X_2)$ 的所有非 $\varepsilon$ 符号；以此类推
如过 $\varepsilon \in FIRST(X_t)$ 对 $1 \leqslant t\leqslant k$ 均成立，则将 $\varepsilon$ 加入 FIRST($X_1X_2\cdots X_k$) 中

Hint

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

FOLLOW

计算方法

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

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

Hint

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

自顶向下的语法分析

LL(1) 文法

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

预测分析表

对于 $G$ 的每个产生式 $A \rightarrow \alpha$

对于 $FIRST(\alpha)$ 中的每个终结符号 $a$，将 $A \rightarrow \alpha$ 加入到 $M[A,a]$中
如果 $\epsilon$ 在 $FIRST(\alpha)$ 中：
- 那么对于 $FOLLOW(A)$ 中的每个终结符号 $b$，将 $A \rightarrow \alpha$ 加入到 $M[A,b]$ 中
- 如果 $ 在 $FOLLOW(A)$ 中，将 $A \rightarrow \alpha$ 加入到 $M[A,$]$ 中

自底向上的语法分析

规范 LR(0) 项集族

项集的闭包

如果 $I$ 是文法 $G$ 的一个项集，那么 $CLOSURE(I)$ 可由下面两个规则从 $I$ 构造得到。
- 将 $I$ 中的各个项加入到 $CLOSURE(I)$ 中；
- 如果 $A \rightarrow \alpha \cdot B\beta$ 在 $CLOSURE(I)$ 中， $B \rightarrow \gamma$ 是一个产生式，并且项 $B \rightarrow \cdot ~\gamma$ 不在 $CLOSURE(I)$ 中，就将这个项加入其中。不断应用这个规则，直到没有新项加入到 $CLOSURE(I)$ 中为止。
直观地讲，CLOSURE$(I)$ 中的项 $A \rightarrow \alpha \cdot B\beta$ 表明在语法分析过程的某点上，
我们认为接下来可能会在输入中看到一个能够从 $B\beta$ 推导得到的子串。

GOTO 函数

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

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

构造项集族

初始时，$C=I_0=\Big\lbrace CLOSURE\big( \big\lbrace \big[ S’ \rightarrow \cdot S \big] \big\rbrace \big)\Big\rbrace$
对于 $C$ 中的每个项集 $I$： - 对于每个文法符号 $X$：
- 如果 $GOTO(I,X)$ 非空且不在 $C$ 中，将 $GOTO(I,X)$ 加入到 $C$ 中
重复过程 2

构造 SLR 语法分析表

构造 $G’$ 的规范 $LR(0)$ 项集族 $C=\lbrace I_0,I_1,\cdots,I_n \rbrace$。
根据 $I_i$ 构造得到状态 $i$。状态 $i$ 的语法分析动作按照下面的方法决定： - 如果 $[A \rightarrow \alpha \cdot a\beta]$ 在 $I_i$ 中，并且 $GOTO(I_i,a)=I_j$，令 $ACTION[i,a]=s_j$，即移入 $j$；其中，$a$ 必须是终结符。 - 如果 $[A \rightarrow \alpha \cdot]$ 在 $I_i$ 中，那么对于 $FOLLOW(A)$ 中的所有 $a$，令 $ACTION[i,a]=r_j$，即规约 $j$；其中，**$j$ 为产生式 $A \rightarrow \alpha$ 的编号**；$A \neq S’$。 - 如果 $[S’ \rightarrow S \cdot]$ 在 $I_i$ 中，令 $ACTION[i,$]=acc$，即接受。
如果根据上面的规则生成了任何冲突动作，则这个文法不是 $SLR(1)$ 的。
状态 $i$ 对于各个非终结符号 $A$ 的 $GOTO$ 转换使用下面的规则构造得到：
- 如果 $GOTO(I_i,A)=I_j$，那么，$GOTO[i,A]=j$。
规则(2)和规则(3) 没有定义的条目均设为“报错”。
语法分析器的初始状态是根据 $[S’ \rightarrow \cdot S]$ 所在项集构造得到的状态。

有效 LR(1) 项集族

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

项集的闭包

如果 $\big[ A \rightarrow \alpha \cdot B\beta, a \big]$ 对可行前缀 $\gamma=\delta\alpha$ 有效，那么必然存在一个最右推导 $S \overset{*}{\underset{rm}{\Rightarrow}} \delta A\alpha x \underset{rm}\Rightarrow \delta\alpha B\beta ax$。假设 $\beta ax$ 推导出终结符号串 $by$，那么对于某个形如 $B \rightarrow \eta$ 的产生式，有推导 $S \overset{*}{\underset{rm}{\Rightarrow}} \gamma Bby \underset{rm}\Rightarrow \gamma\eta by$。
因此，$\big[ B \rightarrow \cdot\eta, b \big]$ 是 $\gamma$ 的有效项。其中，$b \in FIRST(\beta a)$。

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

Hint

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

GOTO 函数

计算 $GOTO(I,X)$
- 将 $J$ 初始化为空集
- 对于 $I$ 中的每个项 $\big[ A \rightarrow \alpha\cdot X\beta,a \big]$
  - 将项 $\big[ A \rightarrow \alpha X\cdot \beta,a \big]$ 加入到集合 $J$ 中
- 返回 $CLOSURE(J)$

构造项集族

初始时， $C=I_0=\Big\lbrace CLOSURE\big( \big\lbrace \big[ S’ \rightarrow \cdot S,$ \big] \big\rbrace \big)\Big\rbrace$
- 对于 $C$ 中的每个项集 $I$
  - 对于每个文法符号 $X$
    - 如果 $GOTO(I,X)$ 非空且不在 $C$ 中
      - 将 $GOTO(I,X)$ 加入 $C$ 中

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

构造 $G’$ 的规范 $LR(0)$ 项集族 $C=\lbrace I_0,I_1,\cdots,I_n \rbrace$。
根据 $I_i$ 构造得到状态 $i$。状态 $i$ 的语法分析动作按照下面的方法决定： - 如果 $[A \rightarrow \alpha \cdot a\beta, b]$ 在 $I_i$ 中，并且 $GOTO(I_i,a)=I_j$，令 $ACTION[i,a]=s_j$，即移入 $j$；其中，$a$ 必须是终结符。 - 如果 $[A \rightarrow \alpha \cdot, a]$ 在 $I_i$ 中，且 $A \neq S’$；那么令 $ACTION[i,a]=r_j$，即规约 $j$；其中，**$j$ 为产生式 $A \rightarrow \alpha$ 的编号**。 - 如果 $[S’ \rightarrow S \cdot, $]$ 在 $I_i$ 中，令 $ACTION[i,$]=acc$，即接受。
如果根据上面的规则生成了任何冲突动作，则这个文法不是 $LR(1)$ 的。
状态 $i$ 对于各个非终结符号 $A$ 的 $GOTO$ 转换使用下面的规则构造得到：
- 如果 $GOTO(I_i,A)=I_j$，那么，$GOTO[i,A]=j$。
规则(2)和规则(3) 没有定义的条目均设为“报错”。
语法分析器的初始状态是根据 $[S’ \rightarrow \cdot S, $]$ 所在项集构造得到的状态。