3. LR 分析¶

3.1. LR 分析¶

3.1.1. LR(k) 分析器¶

LL(k) 分析器很简单，但能力不强。它无法识别很多语言。

LR(k) 功能更强，但也更复杂！

是一个移进-归约（shift-reduce）分析器：把终结符移进栈中，直到重写规则的右端可以被归约为该规则的左端为止。
是一个自底向上（bottom-up）分析器：从输入串开始，反复用重写规则的左端替换右端，直到得到起始符号为止。（因此这与 LL 分析器相反，LL 分析器是从起始符号"自顶向下" 到串。）
L 表示：从左到右读取输入
R 表示：产生最右推导（LL 是最左推导）
$k$：向前看符号的个数

备注

我们只考察 LR(1) 文法

回想一下，LL(1) 分析例程是通过把 CFG 转换为 PDA 来构造的。

3.1.2. LR 分析过程¶

将 CFG 转换为 PDA（与 LL 过程使用不同的转换过程）
使用 PDA 和向前看符号（与 LL 过程使用不同的分析例程）

将 CFG 转换为 PDA

想法：要用 CFG 及以上最右推导的方式推导一个串，从起始符号开始，每一步反复应用产生式，替换最右边的变量。为了用 NPDA 模拟这个过程，我们反向模拟这个过程：从输入串开始，反向使用产生式（用产生式的左端替换其右端），并推导出起始符号。因此，NPDA 先把输入串的符号移进栈中。每当栈顶的几个符号与一条产生式的右端匹配时，就弹出右端（可能有几个符号）并在栈上替换（或压入）左端。如果替换后栈上只剩下起始符号，那么输入串就属于该文法的语言。要看 NPDA 实际模拟的最右推导，从起始符号开始，按 NPDA 中应用的相反顺序应用这些产生式。

构造出的 NPDA：

三个状态： $s, q, f$

在状态 $s$ 开始，把栈底标记 $z$ 压入栈中
状态 $s$ 中有所有重写规则，方向相反

这些规则先弹出右端，然后压入左端

$(s, \mbox{lhs}) \in \delta(s, \lambda, \mbox{rhs})$

注意：我们假定栈可以一次弹出多个符号。

这被称为归约（reduce）操作。
$s$ 中识别终结符的附加规则

对每个 $x \in \Sigma, g \in \Gamma, (s,xg) \in \delta(s,x,g)$

这被称为移进（shift）操作。
从栈中弹出 $S$ 并进入状态 $q$
从栈中弹出 $z$ ，进入 $f$ ，接受。

PDA 是非确定的！使用向前看符号来决定采用哪条转移。

3.1.3. LR 分析动作¶

移进（Shift）

把向前看符号转移（transfer）到栈上
归约（Reduce）

对于 $X \rightarrow w$ ，在栈上用 $X$ 替换 $w$
接受（Accept）

输入串属于该语言
错误（Error）

输入串不属于该语言

我们希望把所有这些信息保存到一张表中。

3.1.4. LR(1) 分析表¶

列：

终结符、 $\$$ 和变量（ $\$$ 是串结束标记）

终结符和 $\$$ 被用作向前看符号。

变量在某种程度上也被用作向前看符号。
行：

状态号：表示推导中的模式

LR(1) 分析表示例

1) $S \rightarrow aSb$

2) $S \rightarrow b$

\[\begin{split}\begin{array}{|r||c|c|c|c|} \hline &a & b & \$ & S \\ \hline \hline 0 & s2 & s3 & & 1 \\ \hline 1 & & &acc & \\ \hline 2&s2&s3&&4 \\ \hline 3&&r2&r2& \\ \hline 4&&s5&& \\ \hline 5&&r1&r1& \\ \hline \end{array}\end{split}\]

表项的定义：

$sN$：把该列的终结符移进（或压入）栈中，并转移到状态（或行号）N。
$N$：转移到状态（或行号）N。
$rN$：按规则号 N 归约。该规则的右端在栈顶。把它弹出，并用规则的左端替换。
$acc$：接受输入串。
空：错误。

备注

识别每种操作

我们将创建一个模拟栈内容的 DFA。当栈顶是某个右端时就归约，我们处于终结状态。

栈上的状态号只是我们来自何处的轨迹。

LR(1) 分析例程

"entry" 是一个包含四个部分的记录：state、action、rule.rhs、rule.lhs:

state = 0 push(state) read(symbol)                                 获取向前看符号 entry = T[state,symbol]                      T 是 LR 分析表 while entry.action <> accept do
   if entry.action == shift then
      push(symbol) state = entry.state push(state) read(symbol)
   else if entry.action == reduce then
      do 2*size_rhs times { pop() }         弹出 entry.rule.rhs 和状态 state := top-of-stack()               不要弹出！push(entry.rule.lhs) state = T[state,entry.rule.lhs] push(state)
   else if entry.action == blank then
      error
   entry = T[state, symbol]
end while if symbol <> $ then error

构造 LR(1) 分析表： （思路）

构造一个 DFA（转移图）模拟栈顶，其状态表示分析栈的当前内容。

注意：DFA！
使用该 DFA 构造 LR(1) 分析表

构造 DFA

想法：DFA 中的状态将包含带标记的产生式，指示当前栈顶是什么，以及为了使得某个右端在栈顶、从而可以进行归约操作，还需要把哪些额外的符号压入栈中。

在文法中加入一条新的产生式 $S' \rightarrow S$ ，其中 $S'$ 是新的起始符号。

注意：这样做是为了让当起始符号在栈上时，就表示串被接受。如果起始符号出现在某个右端中，就不是这种情况了。
在产生式的右端放置一个标记 "_" ，以指示分析过程的状态。

$S' \rightarrow \_S$

标记左边右端中的条目是我们已经分析过的条目（它们在栈顶），标记右边的条目是我们尚未看到的条目（仍然需要压入栈中）。

例子： $A \rightarrow a\ {\_}\ Ab$ 表示 "a" 在栈顶，并且需要把 "A" 和 "b" 压入栈中，之后才能把 "aAb" 归约为 "A"。
计算产生式集合 $\mbox{closure}(S' \rightarrow \_S)$。

closure 的定义：
1. 如果 $x$ 是终结符，则 $\mbox{closure}(A \rightarrow v\_xy) = \{A \rightarrow v\_xy\}$
2. 如果 $x$ 是变量，则 $\mbox{closure}(A \rightarrow v\_xy) = \{A \rightarrow v\_xy\} \cup (\mbox{closure}(x \rightarrow \_w)$ 对所有 $w$ （其中 $w$ 是 $x$ 为其左端的产生式的右端））
注意：这是一个递归定义。
$\mbox{closure}(S' \rightarrow \_S)$ 被指定为状态 0，并标记为"未处理的"。
重复直到所有状态都被处理完
- unproc = 任意一个未处理的状态
- 对出现在 $A \rightarrow u\_xv$ 中的每个 $x$ （其中 A 产生式来自状态 "unproc"）
  - 添加一条标记为 "x" 的从状态 "unproc" 到一个新状态的转移，该新状态带有产生式 $A \rightarrow ux\_v$
    
    （注意：如果状态 "unproc" 中有不止一条产生式的标记在 $x$ 之前，那么只创建一个新状态，并把所有这些产生式都放入新状态中，移动标记使它们位于 $x$ 的右边）
  - 新状态的产生式集合为： $\mbox{closure}(A \rightarrow ux\_v)$
    
    （注意：如果上一步放入的不止一条产生式，则对所有这些产生式都应用 closure）。
  - 如果新状态与另一个状态相同（两边有相同的产生式和标记位置），那么把这两个状态合成一个状态。否则，把新状态标记为"未处理的"
识别终结状态。任何状态只要至少有一条产生式的右端以 "_" 结尾，就是终结状态。

在 DFA 中回溯

简略版本：

考虑 $aabbb$

从状态 0 开始。
移进 "a" 并转移到状态 2。
移进 "a" 并转移到状态 2。
移进 "b" 并转移到状态 3。

按 "$S \rightarrow b$" 归约

弹出 "b" 并回溯到状态 2。

移进 "S" 并转移到状态 4。
移进 "b" 并转移到状态 5。

按 "$S \rightarrow aSb$" 归约

弹出 $aSb$ 并回溯到状态 2。

移进 "S" 并转移到状态 4。
移进 "b" 并转移到状态 5。

按 "$S \rightarrow aSb$" 归约

弹出 "aSb" 并回溯到状态 0。

移进 "S" 并转移到状态 1。
接受。 $aabbb$ 属于该语言。

关于回溯的更详细解释

DFA 中的一个状态表示栈的"顶部"当前是什么。如果某个状态表示某个右端在栈顶，那么它就是终结状态。

考虑串 $aabbb$ 。我们沿着 DFA 追踪该串。

从状态 0（起始状态）开始。我们还没有识别出该串的任何部分。

我们识别出该串的第一个 "a"（把 "a" 移进栈中）并进入状态 2。状态 2 表示 "$aa^*$" 在栈顶。在这种情况下，"a" 在栈顶。

我们识别出该串的第二个 "a"（把它移进栈中）并保持在状态 2。此时栈包含 "aa" ，形式为 $aa^*$。

我们识别出第一个 "b" ，把它移进栈中，并进入状态 3。状态 3 表示 $aa^*b$ 或 $b$ 在栈顶。在这种情况下， $aab$ 在栈上（"b" 在顶部）。现在栈顶有一条产生式规则的右端。这就是状态 3 是终结状态的原因。终结状态表明可以进行归约。我们应用归约 $S \rightarrow b$。我们将 "b" 从栈中弹出，并在 DFA 中回溯到状态 2 ，因为栈的当前内容现在是 $aa$ （状态 2 表示这个内容）。我们将 "math:S 压入栈中，并从状态 2 转移到状态 4 ，因为状态 4 表示 $aa^*S$ ，现在栈的内容是 $aaS$。

我们识别出该串的第二个 "b" ，把它移进栈中，并进入状态 5 ，该状态表示当前栈内容的形式为 $aa^*Sb$ ，在这种情况下是 $aaSb$。状态 5 是终结状态，这意味着产生式 "$S \rightarrow aSb$" 的右端在栈顶。我们可以用这条产生式进行归约。我们将从栈中弹出 $aSb$ ，并在 DFA 中从状态 5 回溯到状态 4 再到状态 2 再到状态 2。栈的当前内容现在是 "a" ，由状态 2 表示。我们把 $S$ 压入栈中并进入状态 4。此刻栈的内容是 $aS$。

我们识别出该串的第三个 "b" ，把它移进栈中并进入状态 5。当前栈是 $aSb$。我们进行归约，从栈中弹出 $aSb$ ，并从状态 5 回溯到状态 4 再到状态 2 再到状态 0。栈的当前内容是空的。我们把 $S$ 压入栈中并进入状态 1 ，该状态表示栈的内容是 $S$ ，即我们的目标。该串被接受。

注意，按顺序识别出的产生式为：

\(S \rightarrow b\)
\(S \rightarrow aSb\)
\(S \rightarrow aSb\)
\(S' \rightarrow S\)

按相反顺序，产生式及相应的推导为：

\[\begin{split}\begin{array}{lll} S' \rightarrow S & \ \ \ \ \ \ \ \ \ \ \ \ & S' \Rightarrow S\\ S \rightarrow aSb && \Rightarrow aSb \\ S \rightarrow aSb && \Rightarrow aaSbb \\ S \rightarrow b && \Rightarrow aabbb \\ \end{array}\end{split}\]

从图中构造 LR(1) 分析表：

如果有一条从状态 1 到状态 2 的弧
1. 标记为 $x$ 的弧是终结符或 $
  
  T[state1, x] = state2
2. 标记为 $X$ 的弧是非终结符
  
  T[state1, X] = state2
如果状态 1 是终结状态，且 $X \rightarrow w\_$

对于 $\mbox{FOLLOW}(X)$ 中的所有 $a$ ， T[state1, a] = 按 $X \rightarrow w$ 归约

（或 T[state1, a] = rN，其中 N 是产生式 $X \rightarrow w$ 的编号）
如果状态 1 是终结状态，且 $S' \rightarrow S\_$

T[state1, $] = accept
所有其他表项都是错误

示例：LR(1) 分析表

(0) $S' \rightarrow S$

(1) $S \rightarrow aSb$

(2) $S \rightarrow b$

这是带有每个状态栈内容附加信息的 LR(1) 分析表。

\[\begin{split}\begin{array}{|r|r||c|c|c|c|} \hline \mbox{Stack} & \mbox{State} & \multicolumn{3}{c}{\mbox{Terminals}} & \mbox{Variables} \\ \cline{3-6} \mbox{contents}&\mbox{number}&a & b & \$ & S \\ \hline\hline \mbox{(empty)}&0 & s2 & s3 & & 1 \\ \hline S&1 & & &acc & \\ \hline aa^*&2&s2&s3&&4 \\ \hline aa^*b \mid b&3&&r2&r2& \\ \hline aa^* S&4&&s5&& \\ \hline aa^* Sb&5&&r1&r1& \\ \hline \end{array}\end{split}\]

LR(1) 分析表 T[state,symbol] 中各表项的动作

设 entry = T[state,symbol]。

如果 symbol 是终结符或 $
- 如果 entry 是 "shift $\mbox{state}i$"
  
  把向前看符号和 $\mbox{state}i$ 压入栈中
- 如果 entry 是 "reduce by rule $X \rightarrow w$"
  
  从栈中弹出 $w$ 和 $k$ 个状态（ $k$ 是 $w$ 的大小）。设 $\mbox{state}i$ 是当前栈顶的状态。把 $X$ 压入栈中。把 $\mbox{state}j$ 压入栈中，其中 $\mbox{state}j =$ T[statei, X]。
- 如果 entry 是 "accept"
  
  停机。该串属于该语言。
- 如果 entry 是 "error"
  
  停机。该串不属于该语言。
如果 symbol 是非终结符

我们刚刚把产生式 $X \rightarrow w$ 的右端归约为一个符号。这个表项是一个状态号，把它记为 $\mbox{state}i$。把 T[statei, X] 压入栈中。

为含 $\lambda$ 规则的 CFG 构造分析表

$A \rightarrow \lambda$ 写作 $A \rightarrow \lambda\_$

一条 $\lambda$ 规则会被识别为立即可归约。任何含有 $\lambda$ 规则的状态都是可以应用该 $\lambda$ 规则进行归约的终结状态。

把 $\lambda$ 压入栈中没有意义，所以不会有带 $\lambda$ 的弧。（而且，在我们的 DFA 中允许 $\lambda$ 会把我们的 DFA 变成 NFA！）。对于规则 "$A \rightarrow \lambda$"，我们把它填入表中任何属于 $\mbox{FOLLOW}(A)$ 的向前看符号对应的表项。

注意：关于构造 LR(1) 分析表的另一个示例，请参阅项目 3 讲义。

构造 LR 分析表时的冲突

如果尝试构造 LR(1) 分析表，而表的某个表项中有两个条目，那么这个文法就不是 LR(1) 的。

可能的冲突：

移进/归约冲突（Shift/Reduce Conflict） - 某条产生式规则的右端在栈顶。也可能移进更多的符号，使另一个右端在栈顶。

例子：假设某个文法包含下面这 2 条产生式规则：

$A \rightarrow ab$

$A \rightarrow abcd$

备注

添加规则 $S \rightarrow bAc$ ，则 $c \in \mbox{FOLLOW}(A)$。

那么 DFA 中会有一个状态同时包含

$A \rightarrow ab\_$

$A \rightarrow ab\_\ cd$

第一条规则表示归约（REDUCE）（因此该状态是终结状态）。第二条规则表示移进（SHIFT）。如果你把 c 和 d 移进栈中，那么就可以按第二条规则归约。

那么，是按 "ab" 归约还是移进 "c" 呢？冲突！
归约/归约冲突（Reduce/Reduce Conflict）

存在一个状态包含两条右端完全相同的规则。

例子：假设某个文法包含下面这两条产生式规则：

$A \rightarrow ab$

$B \rightarrow ab$

那么 DFA 中可能有一个状态同时包含

$A \rightarrow ab\_$

$B \rightarrow ab\_$

你知道想替换 ab ，但不知道应用哪条规则。冲突！
移进/移进冲突（Shift/Shift Conflict）

这是不可能发生的，因为该图是 DFA。对于每个符号，要移入的状态是唯一的。

CS4114 形式语言与自动机

Chapter 11 Parsing

3. LR 分析¶

3.1. LR 分析¶

3.1.1. LR(k) 分析器¶

3.1.2. LR 分析过程¶

3.1.3. LR 分析动作¶

3.1.4. LR(1) 分析表¶