2_上下文无关语言2.4.2.ZH解释

本段是引言，为后续的理论证明设定了舞台和范围。它核心要传达的思想是：确定性下推自动机 (DPDA) 和 确定性上下文无关文法 (DCFG) 这两种描述语言的工具，在某个特定条件下是等价的，这个条件就是语言必须是“带结束标记的”。

1. 核心论点: 本节的目标是证明 DPDA 和 DCFG 在描述“带结束标记的语言”这个范畴内，能力是完全相同的。也就是说，如果一个带结束标记的语言可以用 DPDA 识别，那么它一定能用 DCFG 生成，反之亦然。
2. 证明的两个方向: 为了证明两者等价，需要进行双向证明：
   • 方向一 (DCFG → DPDA): 证明任何一个 DCFG，我们都能构造出一个与之等价的 DPDA。这个方向的转换是普适的，即对任何 DCFG 都成立。
   • 方向二 (DPDA → DCFG): 证明任何一个识别“带结束标记语言”的 DPDA，我们都能构造出一个与之等价的 DCFG。这个方向的转换是有条件的。
3. 关键限制条件：带结束标记的语言 (End-marked Language): 这是理解本节内容最重要的前提。
   • 什么是结束标记？ 它是一个特殊的、不会出现在原始语言字符串中的符号（比如 $ 或者 \dashv）。这个标记被明确地附加在每个合法字符串的末尾。例如，如果原始语言是 {a, aa, aaa}，那么带结束标记的语言就是 {a\dashv, aa\dashv, aaa\dashv}。
   • 为什么需要这个限制？ 文中解释说，如果没有这个结束标记，DPDA 和 DCFG 就不是等价的。
   • 对于 DPDA 来说，加不加结束标记，其识别语言的能力范围（即 确定性上下文无关语言 DCFL）没有变化。DPDA 只要在读完输入后进入接受状态即可，它自身有机制判断输入是否结束。
   • 但对于 DCFG 来说，结束标记至关重要。没有结束标记的 DCFG 只能生成一类特殊的 DCFL，这类语言被称为“无前缀的”。
4. 无前缀性质 (Prefix-free):
   • 定义: 一个语言是无前缀的，意味着该语言中没有任何一个字符串是另一个字符串的前缀。例如，集合 {a, ab, b} 就不是无前缀的，因为 'a' 是 'ab' 的前缀。而集合 {a, ba, bb} 就是无前缀的。
   • 结束标记与无前缀的关系: 任何一个带结束标记的语言天然就是无前缀的。因为结束标记 \dashv 不会出现在任何字符串的中间，所以形如 w\dashv 的字符串不可能是另一个字符串 w'\dashv 的前缀（除非 w=w'）。例如，'a\dashv' 不可能是 'ab\dashv' 的前缀，因为前者的结尾是 \dashv，而不是 b。
   • DCFG 的限制: 如果一个 DCFG 不使用结束标记，它在生成字符串时，很难“知道”一个字符串是否已经“完整”了。这导致它只能生成那些一旦生成完毕就不会成为其他更长字符串开头的语言，即无前缀语言。

这是一个核心定理，它用最简洁的数学语言，正式陈述了上一段引言中描述的核心思想。

1. 定理陈述分析: "一个带结束标记的语言可由确定性上下文无关文法 (DCFG) 生成当且仅当它是确定性上下文无关 (DCFL) 的。"
   • "一个带结束标记的语言": 这是我们讨论的对象，强调了结束标记 \dashv 的存在。
   • "可由确定性上下文无关文法 (DCFG) 生成": 这是一种描述语言的方式。如果一个语言能被一个 DCFG 的所有产生式推导出来，我们就说它可由该 DCFG 生成。这描述的是语言的 生成 模型。
   • "当且仅当": 这是一个逻辑等价关系，意味着左右两边的论述是完全等价的。它要求我们证明两个方向：
   • 正向 (⇒): 如果一个带结束标记的语言可以由 DCFG 生成，那么它是一个 DCFL。
   • 反向 (⇐): 如果一个语言是带结束标记的 DCFL，那么它一定可以由一个 DCFG 生成。
   • "它是确定性上下文无关的 (DCFL)": 这是另一种描述语言的方式，指的是语言的 识别 模型。一个语言是 DCFL，意味着存在一个确定性下推自动机 (DPDA) 能够识别它。
2. 定理的本质: 这个定理是在说，对于加了结束标记的语言来说，“能被 DCFG 生成” 和 “能被 DPDA 识别” 这两件事是完全等价的。它正式地在生成模型 (DCFG) 和 识别模型 (DPDA) 之间划上了等号，但前提是语言必须带结束标记。
3. 证明策略: 作者明确指出了证明这个“当且仅当”定理的标准方法——分别证明两个方向。
   • 方向一 (正向证明): 证明 "每个 DCFG 都有一个等价的 DPDA"。这对应了定理中的 "如果...那么..." 部分。这个证明将在引理 2.58 中给出。
   • 方向二 (反向证明): 证明 "每个识别带结束标记语言的 DPDA 都有一个等价的 DCFG"。这对应了定理中的 "仅当..." 部分。这个证明将在引理 2.59 中给出。

这个引理陈述了定理 2.57 的第一个证明方向：从 DCFG 到 DPDA 的转换是总是可能的。

1. 引理的核心: 任何一个确定性上下文无关文法 (DCFG)，无论它是否生成带结束标记的语言，我们总能找到一个确定性下推自动机 (DPDA)，这个 DPDA 识别的语言与该 DCFG 生成的语言完全相同。
2. “等价”的含义: 这里的“等价”指的是它们描述的语言是同一个集合。即 $L(G) = L(P)$，其中 $G$ 是 DCFG，$P$ 是等价的 DPDA。
3. 普适性: 注意，这个引理没有“带结束标记”的前提。这意味着从 DCFG 到 DPDA 的转换是普遍成立的。这与反向转换（DPDA → DCFG）形成对比，后者需要结束标记。

这部分是构造性证明的核心思想，它描述了一个算法，用于将 DCFG $G$ 转化为 DPDA $P$。这个算法非常巧妙，是 LR 解析的理论雏形。

1. 核心工具：DFA $DK$
   • 这个证明依赖于一个预先存在的工具，一个特殊的 DFA，名为 $DK$。这个 $DK$ 是从 DCFG $G$ 构造出来的，它的作用是识别 $G$ 的所有有效字符串 (viable prefixes) 的句柄 (handles)。
   • 有效字符串：指的是一个最右推导过程中出现的中间字符串的前缀。
   • 句柄：是最左边的、可以被规约的子串。规约就是将一个产生式的右侧替换回左侧的变量，是推导的逆过程。
   • 因为 $G$ 是 DCFG (也叫 LR(0) 文法)，它的句柄是强制性的，意味着一旦在输入中看到一个句柄，就必须立即进行规约，没有其他选择。$DK$ 正是用来识别这种“必须规约”的信号的。
   • 当 $DK$ 读入一串符号并进入一个接受状态时，就意味着它刚刚读完了一个句柄。$DK$ 的接受状态会告诉我们应该用哪个产生式（例如 $T \rightarrow u$）来规约。
2. DPDA $P$ 的工作方式：模拟自底向上的解析
   • 这个 DPDA $P$ 本质上是一个移入-规约 (shift-reduce) 解析器。
   • 移入 (Shift): $P$ 从左到右读取输入字符串。每读一个符号，它就模拟 $DK$ 的行为。这个动作称为“移入”。
   • 规约 (Reduce): 当模拟的 $DK$ 到达一个接受状态时，$P$ 就知道它找到了一个句柄，需要进行规约。例如，如果 $DK$ 指示使用规则 $T \rightarrow u$ 进行规约，那么意味着输入流中最近看到的子串 u 应该被替换为变量 T。
3. 遇到的问题与解决方案
   • 问题: DPDA 的输入带是只读的，不能修改，也不能回头重读。我们怎么在输入带上实现“将 u 替换为 T”这个规约操作呢？
   • 错误想法1: 直接修改输入带。行不通，DPDA 模型不允许。
   • 错误想法2: 把输入复制到栈里，在栈里修改。行不通，因为修改后，你需要从头开始用 $DK$ 重新分析，这就需要把栈清空再读出来，但栈里的内容是后续步骤需要的，不能随便清空。
   • 巧妙的解决方案: 不要在栈里存输入符号，而是在栈里存 $DK$ 的状态！
4. 最终的算法 (核心技巧)
   • 初始化: $P$ 的栈初始时只有一个元素，即 $DK$ 的开始状态 $q_{start}$。
   • 移入 (Shift): $P$ 读取一个输入符号 a。它查看栈顶的 $DK$ 状态 $s_{top}$，然后计算 $DK$ 在状态 $s_{top}$ 读入 a 后会转移到哪个新状态 $s_{new}$。然后，$P$ 将 $s_{new}$ 压入栈。这个过程不断重复。
   • 规约 (Reduce): 假设在某一步之后，栈顶的状态是 $s_{accept}$，这是一个 $DK$ 的接受状态。这个状态告诉 $P$ 需要用规则 $T \rightarrow u$ 进行规约，其中 $u$ 的长度是 $|u|$。
   • $P$ 从自己的栈中弹出 $|u|$ 个状态。
   • 弹出后，栈顶现在是 $s_{before}$，这个状态就是 $DK$ 在开始读取 u 之前所处的状态。
   • 现在， $P$ 假装已经看到了变量 T。它查询 $DK$ 在状态 $s_{before}$ “读取” T 后会去哪个状态，我们称之为 $s_{after_T}$。
   • $P$ 将 $s_{after_T}$ 压入栈。
   • 这样就完成了一次规约，栈的内容反映了规约后的状态，而输入指针没有回退。
   • 接受: 当 $P$ 成功地将整个输入规约为文法的开始变量 (例如，通过规则 $S' \rightarrow S$ 进行规约) 时，它就进入接受状态，成功识别了输入字符串。

这个引理是定理 2.57 的第二个、也是更复杂的一个证明方向。它要说明如何从一个识别带结束标记语言的 DPDA 出发，反向构造出一个等价的 DCFG。

1. 引理的核心: 对于任何一个确定性下推自动机 (DPDA)，只要它识别的语言是带结束标记的（即所有合法字符串都以特殊符号 \dashv 结尾），那么我们一定能构造出一个确定性上下文无关文法 (DCFG)，这个 DCFG 生成的语言与该 DPDA 识别的语言完全相同。
2. 关键前提: “带结束标记语言”。这个前提在这里至关重要，证明过程会严重依赖这个特性。没有这个前提，引理不成立。一个 DPDA 可以识别有前缀的语言，但一个 DCFG 无法生成它们，所以必须通过结束标记来消除前缀，使得两者能力对齐。
3. 等价性: 同样，$L(P) = L(G)$，其中 $P$ 是给定的 DPDA，$G$ 是我们构造出的 DCFG。

这部分概述了将 DPDA 转换为 DCFG 的证明策略。它不是一个全新的发明，而是对一个已知的通用构造（从任意 PDA 到 CFG）的精巧改造，使其适应确定性的约束。

1. 基础：PDA 到 CFG 的通用构造 (引理 2.27)
   • 证明的基础是一个已知的定理：任何一个（不一定是确定性的）PDA 都能被转换成一个等价的 CFG。
   • 这个通用构造的核心思想是创建形如 $A_{pq}$ 的文法变量，其中 $A_{pq}$ 的目标是生成所有能让 PDA 从状态 $p$ 开始，到状态 $q$ 结束，并且最终栈状态与初始栈状态相同的字符串。 essentially "net stack change is zero".
   • 例如，如果 PDA 从状态 $p$ 读入字符 a 并将 X 压栈，然后转移到状态 $p_1$，之后从 $p_1$ 开始经过一系列计算消耗了字符串 w 后，最终回到状态 $p_2$ 并恰好将 X 弹出，那么文法中就会有一条规则，将这个过程编码，例如 $A_{pp_2} \rightarrow a A_{p_1 p_2} \dots$。
2. 为确定性进行改造 (第一步): 处理接受状态
   • 在通用的 PDA->CFG 构造中，为了简化，通常会修改 PDA，使其满足“接受前清空栈”的特性。
   • 对于一个非确定性 PDA，它可以通过“猜测”自己已经读到输入末尾，然后用一系列 ε 转移来清空栈，最后进入唯一的接受状态 $q_{\text{accept}}$。
   • 但我们的 DPDA 不能“猜测”，它的每一步都是确定的。这里，结束标记 \dashv 派上了用场。
   • 改造方法: 我们修改给定的 DPDA $P$。新的 $P'$ 的行为和 $P$ 完全一样，直到它读到结束标记 \dashv。当 $P'$ 读到 \dashv 并且进入了 $P$ 的一个原始接受状态时，它就知道输入真的结束了。此时，$P'$ 才开始清空它的栈，并最终转移到一个全新的、唯一的接受状态 $q_{\text{accept}}$。因为 \dashv 只在末尾出现一次，这个过程仍然是确定性的。
3. 应用构造并修复歧义 (第二步): 构造文法并消除不确定性
   • 现在我们对改造后的 DPDA $P'$ 使用标准的 PDA->CFG 构造算法，得到一个文法 $G$。
   • 由于 $P'$ 是确定性的，它生成的文法 $G$ “几乎”是确定性的 (DCFG)。但有一个小问题会导致歧义。
   • 歧义的来源: 来源于形如 $A_{pq} \rightarrow A_{pr} A_{rq}$ 的规则。这种规则的含义是：要从状态 $p$ 到状态 $q$ 且净栈变化为零，可以先从 $p$ 到 $r$（净栈变化为零），再从 $r$ 到 $q$（净栈变化为零）。如果从 $p$ 到 $q$ 的过程中，栈多次变为空（回到了起始高度），那么就可以在任何一个栈变为空的中间点 $r$ 进行切分，导致一个字符串有多种推导方式（即多种分析树），这就是歧义。
   • 消除歧义的方法: 修改文法构造规则，强制只在最后一次栈变为空的地方进行切分。这样，对于任何一个计算过程，切分点都是唯一的，从而消除了这类歧义。
   • 文中的例子:
   • 有歧义文法: $T \rightarrow T T | (T) | \varepsilon$。字符串 ()() 可以有两种推导：$(T \rightarrow TT) \rightarrow (T \rightarrow (T))T \rightarrow ()T \rightarrow ()(T) \rightarrow ()()$ 或者 $(T \rightarrow TT) \rightarrow T(T \rightarrow (T)) \rightarrow T() \rightarrow (T)T() \rightarrow ()()$。这两种推导对应不同的分析树。
   • 无歧义文法: $T \rightarrow T(T) \mid \varepsilon$。这个文法强制要求 () 成对出现，并且是右递归的，避免了上述的歧义。这只是一个类比，说明通过修改规则可以消除歧义。实际的修改是在 $A_{pq} \rightarrow \dots$ 规则上。
4. 最终验证 (第三步): 使用 DK 检验
   • 在获得了修正后的文法 $G$ 之后，我们需要严格地证明它确实是一个 DCFG。
   • 我们使用 DK 检验（在前面证明引理 2.58 时提到过的工具）来证明 $G$ 的确定性。
   • 为了进行检验，我们需要分析 DPDA $P$ 在遇到文法 $G$ 的变量（如 $A_{pq}$）时会如何表现。
   • 技巧: 假想地扩展 DPDA $P$ 的能力，让它不仅能读输入符号（如 a, b），也能直接“读取”我们构造出的文法变量 $A_{pq}$。我们定义，当 $P$ 在状态 $p$ 时，如果它“读取”了 $A_{pq}$，它就不消耗任何实际输入，也不动栈，直接跳转到状态 $q$。即 $\delta(p, A_{pq}, \varepsilon) = (q, \varepsilon)$。
   • 有了这个扩展的 $P$，我们就可以分析 $G$ 的推导过程，并最终证明 $G$ 满足 DK 检验的所有条件，从而证明 $G$ 是一个 DCFG。

这个断言是在证明“我们构造出的文法 $G$ 是 DCFG”这个大目标过程中的一个关键辅助结论。它试图在文法 G 的推导过程和DPDA P 的计算过程之间建立一个精确的对应关系。

1. 断言的对象:
   • $L(G)$: 我们从 DPDA $P$ 构造出来的文法 $G$ 所生成的语言。
   • $w$: $L(G)$ 中的任意一个字符串。
   • $A_{q_{0}, q_{\text {accept}}}=v_{0} \Rightarrow v_{1} \Rightarrow \cdots \Rightarrow v_{k}=w$: 这是 $w$ 在文法 $G$ 中的一个最右推导序列。
   • $A_{q_{0}, q_{\text {accept}}}$: 这是文法 $G$ 的开始变量，它的设计目标就是生成所有能让 DPDA $P$ 从开始状态 $q_0$ 走到最终接受状态 $q_{\text{accept}}$ 的字符串。
   • $v_i$: 推导过程中的第 $i$ 个中间字符串，它可能包含终结符（如 a, b）和变量（如 $A_{rs}$）。
   • $\Rightarrow$: 表示一步推导。
2. 断言的核心内容:
   • "如果 $P$ 读取包含变量 $A_{pq}$ 的 $v_i$" : 这里的“读取”是一个思想实验。我们假想 DPDA $P$ 不仅能读 a, b 等普通符号，也能“读取”像 $A_{pq}$ 这样的文法变量。正如之前定义的，当 $P$ 在状态 $p$ “读取” $A_{pq}$ 时，它会直接跳转到状态 $q$。
   • "...它会在读取 $A_{pq}$ 之前进入状态 $p$。" : 这是断言的关键。它声称，在 DPDA $P$ 模拟运行到中间推导形式 $v_i$ 的 $A_{pq}$ 这个位置时， $P$ 的内部状态正好是 $p$。
3. 断言的意义: 这个断言将文法变量的下标 ($p$) 与 DPDA 的运行时状态精确地联系了起来。变量 $A_{pq}$ 被设计出来的初衷就是为了表示“从状态 $p$ 到状态 $q$ 的一段计算”，这个断言证明了在任何推导步骤中，这个设计意图都得到了忠实的保持。这就像是在说，我们给变量起的名字 ($A_{pq}$) 不是随便起的，它在每时每刻都准确地反映了 DPDA 的行为。

这部分是断言 2.60 的形式化证明，使用了标准的数学归纳法。

1. 证明方法：数学归纳法
   • 我们要证明的命题 P(i) 是：“对于推导步骤数 $i$，在句型 $v_i$ 中出现的任何变量 $A_{pq}$，当 DPDA $P$ 的计算到达它时，P 的状态为 $p$。”
   • 归纳法需要两步：
   • 基础情况 (Base Case): 证明 P(0) 成立。
   • 归纳步骤 (Inductive Step): 假设 P(i) 成立（这被称为归纳假设），然后利用这个假设来证明 P(i+1) 也成立。
2. 基础情况 (i=0)
   • 当 $i=0$ 时，推导还没开始，句型是 $v_0 = A_{q_0, q_{\text{accept}}}$。
   • DPDA $P$ 的计算也还没开始，它处于初始状态 $q_0$。
   • $P$ 即将“读取”的变量是 $A_{q_0, q_{\text{accept}}}$，这个变量的第一个下标是 $q_0$。
   • $P$ 的当前状态 ($q_0$) 与变量的第一个下标 ($q_0$) 完全匹配。
   • 因此，断言在 $i=0$ 时成立。
3. 归纳步骤 (假设 P(i) 成立，证明 P(i+1) 成立)
   • 归纳假设: 我们假设在第 $i$ 步的句型 $v_i$ 中，断言是成立的。
   • 考虑从 $v_i$ 到 $v_{i+1}$ 的一步推导。这意味着 $v_i$ 中的某个变量被它的产生式右侧替换了。
   • 设 $v_i = x A_{pq} y$，其中 $A_{pq}$ 是被替换的那个变量。$x$ 和 $y$是 $A_{pq}$ 前后的字符串片段。
   • 根据归纳假设，当 DPDA $P$ 读完 $x$ 后、准备读 $A_{pq}$ 前，它的状态是 $p$。
4. 分情况讨论替换规则
   • 从 DPDA 构造 CFG 的算法会产生两种主要类型的规则（这里为了简化，只列出了其中一种复杂形式和一种简单形式的代表）：
   • 类型1 (复杂情况): $A_{pq} \rightarrow A_{pr} a A_{st} b$。这条规则对应 DPDA 的一系列动作：从 $p$ 读 $A_{pr}$ 到 $r$，再读 $a$ 到 $s$，再读 $A_{st}$ 到 $t$，再读 $b$ 到 $q$。
   • 类型2 (简单情况): $A_{pp} \rightarrow \varepsilon$。这条规则对应 DPDA 在状态 $p$ 不动，栈也不变的情况。
   • 情况A: 应用类型1规则
   • $v_{i+1}$ 变成 $x (A_{pr} a A_{st} b) y$。
   • 我们来分析 DPDA $P$ “读取” $v_{i+1}$ 的过程：
   • 对于 x 部分: $P$ 读取 $x$ 的行为和它读取 $v_i$ 的 $x$ 部分时完全一样。因此，对于 $x$ 中可能存在的任何变量，断言仍然成立。
   • 对于 $A_{pr}$: 读完 $x$ 后，$P$ 的状态是 $p$ (根据归纳假设)。现在它要读 $A_{pr}$。$A_{pr}$ 的第一个下标是 $p$。$P$ 的当前状态与变量下标匹配。断言对 $A_{pr}$ 成立。
   • 对于 $A_{st}$: 根据规则的构造，$P$ 从 $p$ “读”完 $A_{pr}$ 会到 $r$，再读 a 会到 $s$。所以，在准备读 $A_{st}$ 之前，$P$ 的状态恰好是 $s$。$A_{st}$ 的第一个下标是 $s$。$P$ 的当前状态与变量下标匹配。断言对 $A_{st}$ 成立。
   • 对于 y 部分: $P$ 在读完 $A_{pr} a A_{st} b$ 这一整块后，状态会从 $p$ 变为 $q$。之后它开始读取 $y$。这和在 $v_i$ 中，$P$ 读完 $A_{pq}$ 后状态变为 $q$ 再读取 $y$ 的情况完全一致。因此，对于 $y$ 中可能存在的任何变量，断言也成立。
   • 结论：在情况A中，断言对 $v_{i+1}$ 成立。
   • 情况B: 应用类型2规则
   • $v_{i+1}$ 变成 $xy$。
   • 变量 $A_{pp}$ 被 ε 替换，消失了，没有引入新的变量。
   • $P$ 读取 $v_{i+1}$ 的行为，就是在读完 $x$ 之后直接读取 $y$。
   • 在 $v_i$ 中，P 读完 $x$ 到达状态 $p$，然后“读取”$A_{pp}$，状态不变还是 $p$，然后再读取 $y$。
   • 在 $v_{i+1}$ 中，P 读完 $x$ 到达状态 $p$，然后直接读取 $y$。
   • 两种情况下，读取 $x$ 和 $y$ 的上下文（起始状态）完全一致。既然断言在 $v_i$ 的 $x$ 和 $y$ 中成立，那么在 $v_{i+1}$ 中也必然成立。
   • 结论：在情况B中，断言对 $v_{i+1}$ 成立。
5. 归纳法结论
   • 我们已经证明了基础情况成立，并且如果断言对第 $i$ 步成立，那么它对第 $i+1$ 步也成立。
   • 根据数学归纳法原理，该断言对所有 $i \ge 0$ 都成立。证明完毕。

这是证明 DPDA P 等价于 DCFG G 的核心步骤的最终宣言。它宣称，我们通过一系列精巧构造和修正得到的文法 $G$，最终是可以通过确定性的“年审”——DK 检验的。

1. 什么是 DK 检验?
   • DK 检验是一种用于判断一个 CFG 是否为 DCFG (即 LR(0) 文法) 的算法。
   • 它首先从文法 $G$ 构造一个 NFA (我们称之为 $K$)，这个 NFA 的状态是“带点规则 (dotted rules)”，例如 $A \rightarrow u \cdot v$。
   • 然后，通过子集构造法将这个 NFA $K$ 转换为一个 DFA，我们称之为 $DK$。$DK$ 的每个状态都是一个带点规则的集合。
   • 检验的核心内容: 检查 $DK$ 的所有状态。如果没有任何一个状态同时包含以下两种冲突情况，那么文法就通过 DK 检验：
   • 规约/规约冲突 (reduce/reduce conflict): 状态中包含两个或更多已完成的规则（点在最末尾），例如 $\{ A \rightarrow u \cdot, B \rightarrow v \cdot \}$。这会导致解析器不知道是该按 $A \rightarrow u$ 规约，还是按 $B \rightarrow v$ 规约。
   • 移入/规约冲突 (shift/reduce conflict): 状态中既包含一个已完成的规则 ($A \rightarrow u \cdot$)，又包含一个点后面跟着终结符的未完成规则 ($B \rightarrow v \cdot a w$)。这会导致解析器困惑：是应该立即按 $A \rightarrow u$ 进行规约，还是应该移入下一个输入符号 a？
   • DCFG 的定义: 一个文法是 DCFG，当且仅当它通过 DK 检验。
2. 断言的意义
   • 断言 2.61 直接声称我们构造的文法 $G$ 满足上述检验条件，即在它的 $DK$ 自动机的任何状态里，都不会出现规约/规约冲突或移入/规约冲突。
   • 一旦这个断言被证明，根据 DCFG 的定义，我们就证明了 $G$ 是一个 DCFG。
   • 这就完成了引理 2.59 的证明，从而完成了定理 2.57 的半壁江山。

这部分是断言 2.61 的核心证明，采用的是反证法和分类讨论。其目标是证明在 $DK$ 自动机的任何一个状态里，都不会出现冲突。证明的焦点集中在接受状态，因为根据 DK 检验的定义，冲突只可能发生在包含已完成规则（即准备规约）的状态中。

证明策略：

1. 任选一个 $DK$ 的状态，假设它包含一个已完成规则 $R$。
2. 我们将证明这个状态里不可能有任何其他规则与之形成冲突。
3. 冲突有两种：规约/规约冲突（另一个已完成规则）和移入/规约冲突（一个点后是终结符的未完成规则）。
4. 同时，已完成规则 $R$ 本身也分为两种类型，一种是复杂的（来自 DPDA 的一系列动作），一种是简单的（来自 ε 规则）。
5. 这就构成了 2 x 2 = 4 种需要排除的情况。

这一部分将理论从纯粹的 DCFG 拓展到了一个在实践中更有用、更强大的概念——LR(k) 文法。

1. 动机：DCFG 的局限性
   • DCFL 非常重要，因为它们可以用高效的 DPDA 解析，而大多数编程语言的语法都属于 DCFL。
   • 我们刚刚证明了 DCFG 在有结束标记时可以描述所有 DCFL。但理论上可以，不代表实践中好用。
   • DCFG (也就是 LR(0) 文法) 的一个核心要求是“句柄是强制的”。这意味着解析器在决定是否规约时，完全不能看它还没读到的任何输入符号。它仅仅根据已经读过的内容，就必须做出唯一的决定。
   • 这个要求太严格了，导致用 DCFG 来写一些直观的语法变得非常困难和反直觉。
2. 解决方案：引入前瞻 (Lookahead)
   • LR(k) 文法 放松了这个严格的限制。它允许解析器在做决定前，偷偷地“向前看 k 个”还未处理的输入符号。
   • 这个小小的“偷看”能力，极大地增强了文法的表达能力和自然性。
   • LR(k) 的含义拆解:
   • L (Left to right): 输入是从左到右处理的。
   • R (Rightmost derivation): 文法对应的是一个最右推导的逆过程（即最左规约），这正是我们之前讨论的移入-规约解析的特点。
   • k (k symbols of lookahead): 决定是否规约以及如何规约时，最多可以参考句柄之后（即输入流中尚未读取的）$k$ 个终结符。
3. DCFG 与 LR(0) 的关系
   • DCFG 就是 LR(0) 文法。$k=0$ 意味着完全没有前瞻能力。解析器做决定时是个“睁眼瞎”，只看自己已经处理过的东西。
4. 前瞻强制句柄的精确定义
   • 假设我们有一个可能的句柄 $h$，它出现在字符串 $xhy$ 中。
   • 我们说这个句柄 $h$ 是“由前瞻 k 强制的”，意思是：
   • 不仅要考虑当前的字符串 $y$ (句柄后面的部分)，还要考虑所有可能的、以与 $y$ 前 $k$ 个符号相同的方式开头的其他字符串 $\hat{y}$。
   • 在所有这些可能的未来（$xh\hat{y}$）中，$h$ 都必须是唯一的、正确的句柄。
   • 换句话说，只要句柄后面 $k$ 个符号不变，我们的规约决策就不会改变。

这部分给出了 LR(k) 文法的正式定义，并立即阐明了它在计算能力谱系中的位置。

1. 正式定义:
   • LR(k) 文法首先是一个上下文无关文法。
   • 它的核心特性是：对于任何一个合法的中间推导形式（有效字符串），其句柄（下一个要被规约的部分）都是由“前瞻 k 强制”的。
   • “前瞻 k 强制”的含义是，只要句柄后面跟着的 $k$ 个输入符号是确定的，那么关于这个句柄的解析决策（是规约？按哪个规则规约？）就是唯一的。
2. 重要推论:
   • DCFG = LR(0): DCFG 的定义是句柄必须是“强制”的，不依赖任何前瞻。这正好是 $k=0$ 的情况。所以，DCFG 和 LR(0) 文法是同一个概念的两种不同叫法。
   • LR(k) 文法描述的能力范围:
   • LR(k) → DPDA: 我们可以证明（后面会展示思路），任何一个 LR(k) 文法都能被转换成一个等价的 DPDA。这意味着 LR(k) 生成的语言最多就是 DCFL。
   • DPDA → LR(0): 我们已经证明（引理 2.59），任何一个识别带结束标记 DCFL 的 DPDA 都能被转换成一个等价的 DCFG，也就是 LR(0) 文法。
   • 结论: 结合这两点，形成了一个闭环：DPDA 描述的能力范围是 DCFL。LR(k) 能被 DPDA 识别，而 DPDA 能被 LR(0) 生成。这意味着，对于 $k=0, 1, 2, \dots$，所有 LR(k) 文法生成的语言集合都是完全相同的，这个集合不多不少，正好就是确定性上下文无关语言 (DCFL) 的集合。
3. 能力 vs. 便利性:
   • 能力上等价: 在“能生成哪些语言”这个问题上，LR(0), LR(1), LR(2), ... 都没区别，它们的能力上限都是 DCFL。
   • 便利性上不同: 但在“写出一个文法来描述某个特定 DCFL 有多方便”这个问题上，它们差别巨大。LR(1) 比 LR(0) (DCFG) 要方便得多、自然得多。后面的例子将会证明这一点。

本段是一个过渡说明，旨在简化后续的讨论。

1. 聚焦于 k=1: 作者决定，为了教学清晰，避免陷入复杂的通用符号表示，接下来的讨论将只关注 LR(1) 文法。
2. LR(1) 的代表性: 这种情况（$k=1$）是最重要、最普遍、最具代表性的。
   • 理论上: 掌握了从 LR(1) 到 DPDA 的转换，就等于掌握了其核心思想。推广到任意 $k$ 只是符号上的复杂化，而非概念上的飞跃。
   • 实践上: 几乎所有的现代编程语言都可以用 LR(1) 文法来描述。现实世界中几乎用不到 $k>1$ 的情况。因此，深入理解 LR(1) 具有最高的实用价值。
3. 转换的存在性: 本段重申了之前的一个结论：LR(k) 文法可以被转换为 DPDA。现在，作者准备展示这个转换的具体构造思路，但仅限于 $k=1$ 的情况。

这部分描述了如何将用于 LR(0) 的 DK 检验升级为用于 LR(1) 的 $DK_1$ 检验。核心思想是在自动机的每个状态中，不仅记录句柄的解析进度，还附带记录了句柄后面应该跟什么符号。

1. 核心变化：引入前瞻符号
   • 在原始的 DK 检验中，自动机的状态是带点规则，如 $A \rightarrow u \cdot v$。
   • 在 $DK_1$ 检验中，自动机的状态升级为“LR(1) 项”，形式为 $[T \rightarrow u \cdot v, a]$。
   • $T \rightarrow u \cdot v$: 这部分和以前一样，表示我们期望识别一个 $T$，目前已经看到了 $u$，希望能看到 $v$。
   • $a$: 这是新增的前瞻符号 (lookahead symbol)。它是一个终结符，代表我们期望在整个规则 $T \rightarrow uv$ 被成功规约后，输入流中紧接着出现的符号是 $a$。
2. 构造 $DK_1$ 自动机
   • 与构造 $DK$ 类似，我们先构造一个 NFA $K_1$，然后通过子集构造得到 DFA $DK_1$。
   • $K_1$ 的状态: 就是上面定义的 LR(1) 项。
   • $K_1$ 的转移:
   • 移进 (Shift): 如果当前项是 $[T \rightarrow u \cdot x v, a]$，当“读取”符号 $x$ 时，会转移到新项 $[T \rightarrow ux \cdot v, a]$。注意，前瞻符号 $a$ 在移进过程中保持不变。
   • ε-转移 (Closure): 这是最关键的变化。如果当前有一个项 $[T \rightarrow u \cdot C v, a]$，其中点后面是一个变量 $C$。我们需要找到所有 $C$ 的产生式，比如 $C \rightarrow r$。对于每个这样的产生式，我们都要添加一个新的起始项 $[C \rightarrow \cdot r, b]$。这里的前瞻符号 $b$ 是如何确定的呢？
   • $b$ 是紧跟在 $C$ 后面的字符串 $v$ 所能推导出的所有可能开头的终结符（FIRST集）。
   • 特殊情况: 如果 $v$ 可以推导出空串 ε，那么 $C$ 规约完后，紧接着的符号就是原始项的前瞻符号 $a$。因此，这种情况下 $b$ 也可以是 $a$。
   • 这个过程直观地体现了前瞻的传递。
3. $DK_1$ 检验的冲突定义
   • $DK_1$ 的状态是 LR(1) 项的集合。
   • 检验的核心: 检查 $DK_1$ 的任何一个状态（即任何一个 LR(1) 项的集合），是否存在冲突。
   • 冲突的精确定义:
   • 移入/规约冲突: 状态中同时包含：
4. 一个已完成的项（准备规约）: $[A \rightarrow u \cdot, a]$
5. 一个未完成的项（准备移入）: $[B \rightarrow v \cdot b w, c]$，其中 $b$ 是一个终结符。

如果 $a = b$，就发生了冲突。因为当下一个输入符号是 $a$ 时，解析器不知道是应该根据第一条规则用前瞻 $a$ 来规约，还是根据第二条规则移入符号 $a$。

• 规约/规约冲突: 状态中同时包含：

1. 一个已完成的项: $[A \rightarrow u \cdot, a]$
2. 另一个已完成的项: $[B \rightarrow v \cdot, b]$

如果 $a = b$，就发生了冲突。因为当下一个输入符号是 $a$ 时，解析器不知道是应该按 $A \rightarrow u$ 规约，还是按 $B \rightarrow v$ 规约。

• 原文的“一致”定义: 原文用一个更紧凑的方式描述了冲突。一个状态里不能有两个“一致”的规则。
• R1: [A -> u., a1] 和 R2: [B -> v., a2] 是一致的，如果 a1=a2。 (规约/规约)
• R1: [A -> u., a1] 和 R2: [B -> v.aw, c] 是一致的，如果 a1=a。(移入/规约)
• 如果一个状态中没有“一致”的带点规则，文法就通过 $DK_1$ 检验。

这是一个定义性的定理，它将一个抽象的数学定义（LR(1) 文法）与一个具体的、可执行的算法（$DK_1$ 检验）等同起来。

1. 定理内容: "一个文法 $G$ 是 LR(1) 文法" 这个陈述，与 "文法 $G$ 通过 $DK_1$ 检验" 这个陈述，是完全等价的。
   • LR(1) 文法 (定义): 在任何有效字符串中，句柄都是由前瞻 1 强制的。这是一个比较抽象的、关于整个语言和所有推导的性质的描述。
   • $DK_1$ 检验 (算法): 一个构造性的、机械的检查过程，通过构建 $DK_1$ 自动机并检查其状态中是否存在特定类型的冲突。
2. 定理的意义: 这个定理为我们提供了一个“抓手”。我们不再需要去遍历一个文法生成的所有无限多个有效字符串来检查“句柄是否强制”，只需要运行一次 $DK_1$ 检验算法即可。如果算法报告没有冲突，我们就能百分之百确定这个文法是 LR(1) 的。
3. 证明思路部分:
   • 原文中 "推论 2.51 仍然适用于 $DK_1$，因为我们可以忽略前瞻符号" 这句话给出了证明的一个提示。
   • 推论 2.51 (在本书前面部分) 大概是说 $DK$ 自动机能够正确地识别文法的所有有效前缀。
   • 这句话的意思是，$DK_1$ 自动机本质上就是 $DK$ 自动机加上了前瞻信息。如果我们把所有的前瞻符号都擦掉，剩下的结构就和 $DK$ 完全一样，所以它同样能识别有效前缀。
   • 完整的证明会展示，$DK_1$ 状态中的冲突，精确地对应于文法中存在某个句柄在某个前瞻符号下不是“强制”的情况。反之亦然。

本段通过一个具体的例子，生动地展示了 LR(1) 相对于 LR(0) (DCFG) 的优势。

1. 例子的目的: 找出一个文法，它不是 DCFG (即通不过 DK 检验)，但却是 LR(1) 文法 (即能通过 $DK_1$ 检验)。这个例子是证明 LR(1) 比 DCFG 更“宽容”、更具表达力的直接证据。
2. 文法分析:
   • 这是一个典型的算术表达式文法，但做了一些简化。
   • S -> E-1: 整个表达式必须以 -1 结尾。
   • E -> E+T | T: 表达式 E 是由 T 通过 + 连接而成。
   • T -> Ta | a: 项 T 是由 a 通过 连接而成。
   • 这个文法定义了 + 比 * 优先级低，并且两者都是左结合的。
3. 为什么它通不过 DK 检验 (不是 LR(0))?
   • 让我们模拟一下 DK 自动机的构造。
   • 考虑解析器已经读入了一个 a。这个 a 可以被规约为 T (根据 $T \rightarrow a$)。
   • 此时，一个 DK 状态中会包含类似 { T -> a. } 这样的完成项。
   • 但是，这个 T 接下来可以被 * 跟随（根据 $T \rightarrow T \cdot * a$），也可以被 + 跟随（因为 T 可以被规约为 E，然后根据 $E \rightarrow E \cdot + T$）。
   • 问题出在规约 T 为 E。当 T 被看作 E 时 (通过规则 $E \rightarrow T$)，解析器会面临一个冲突。
   • 假设解析器看到了一个 T。它需要决定：
   • 规约?: 将 T 规约为 E (根据 $E \rightarrow T$)。
   • 移入?: 如果下一个符号是 ，则应该移入 ，以匹配规则 $T \rightarrow T * a$。
   • 在一个 LR(0) 解析器中，当它看到 T 时，它的状态中既有完成项 E -> T.，又有未完成项 T -> T . * a。这是一个移入/规约冲突。解析器不知道该怎么做。因此，这个文法不是 LR(0) (DCFG)。
4. 为什么它能通过 $DK_1$ 检验 (是 LR(1))?
   • 现在我们用 LR(1) 的视角来看。当解析器看到了 T，面临同样的决策时，它会向前看一个符号。
   • 情况A: 如果下一个符号是 *。
   • E \rightarrow T 这个规约动作，其合法的前瞻符是什么？E 后面可以跟 + 或者 -1。所以 * 不在 E 的前瞻集里。
   • 因此，当下一个符号是 时，唯一的合法动作就是移入 。
   • 情况B: 如果下一个符号是 +。
   • + 是 E 的合法前瞻符。
   • T 后面可以跟 *，但不能跟 +。
   • 所以当下一个符号是 + 时，唯一的合法动作就是规约 T 为 E。
   • 情况C: 如果下一个符号是 - (来自 -1)。
   • - 也是 E 的合法前瞻符。
   • 唯一的合法动作也是规约 T 为 E。
   • 结论: 通过检查下一个符号，解析器总能做出唯一的决定。
   • 看到 * -> 移入
   • 看到 + 或 - -> 规约
   • 由于不存在任何一个前瞻符号同时允许移入和规约，所以没有冲突。文法通过 $DK_1$ 检验，是 LR(1) 的。
5. 关于图 2.65:
   • 图中展示了为该文法构造出的 $DK_1$ 自动机的一部分。
   • 每个方框是一个 $DK_1$ 的状态，里面是 LR(1) 项的集合。
   • 例如，在状态 I2 中，有项 [T -> a., +] 和 [T -> a., ]。这表示在读了 a 之后，如果下一个符号是 + 或 ，都应该将 a 规约为 T。
   • 在状态 I4 (E+T) 中，有 [E -> E+T., +] 和 [T -> T., *]。
   • 这是一个潜在的冲突点。我们有一个完成的 E -> E+T. 和一个完成的 T -> T.（通过 $E->T$ 来的）。
   • 但 E -> E+T. 的前瞻是 + (和 -)。
   • T -> T.a 的移入是 。
   • 因为 {+, -} 和 {*} 不相交，所以没有冲突。
   • 图示的目的就是直观地展示在任何一个状态里，对于任何一个前瞻符号，动作都是唯一的。

这个定理是 定理 2.57 的一个平行版本，只是把 DCFG 替换成了更强大的 LR(1) 文法。

1. 定理陈述: "一个带结束标记的语言可由 LR(1) 文法生成" 和 "它是一个 DCFL" 这两件事是等价的。
   • 这再次在生成模型（这次是 LR(1) 文法）和识别模型（DPDA，其语言即 DCFL）之间划上了等号。
   • 前提条件依然是 "带结束标记的语言"。
2. 证明策略: 这是一个“当且仅当”的定理，需要双向证明。
   • 反向证明 (⇐): 如果一个语言是带结束标记的 DCFL，那么它可以由 LR(1) 文法生成。
   • 作者指出，这一方向的证明已经间接完成了。
   • 逻辑链是：我们之前在 引理 2.59 中证明了，任何一个带结束标记的 DCFL 都有一个等价的 DCFG。
   • 而 DCFG 就是 LR(0) 文法。
   • 任何一个 LR(0) 文法自然也是一个 LR(1) 文法（因为 LR(1) 的要求比 LR(0) 更宽松）。
   • 所以，任何一个带结束标记的 DCFL 都有一个等价的 LR(1) 文法。反向得证。
   • 正向证明 (⇒): 如果一个语言可由 LR(1) 文法生成，那么它是一个 DCFL。
   • 要证明这一点，我们需要展示如何将任何一个 LR(1) 文法转换为一个等价的 DPDA (因为 DPDA 识别的正是 DCFL)。
   • 作者明确指出，这个任务将由接下来的引理 2.67 来完成。

这个引理是 定理 2.66 的最后一块拼图，也是 LR(1) 理论能够实际应用的关键。

1. 引理的核心: 任何一个 LR(1) 文法，我们总能构造出一个等价的确定性下推自动机 (DPDA)。
2. 等价性: $L(G) = L(P)$，其中 $G$ 是给定的 LR(1) 文法，$P$ 是构造出的 DPDA。
3. 意义:
   • 它完成了 定理 2.66 的正向证明。
   • 它表明，LR(1) 文法生成的所有语言都在 DPDA 的识别能力范围之内，即它们都是 DCFL。
   • 最重要的是，这个证明是构造性的，它提供了一个从 LR(1) 文法到 DPDA 的算法。这个算法正是 LR(1) 解析器的工作原理。

这部分描述了如何构造一个能识别 LR(1) 文法的 DPDA，即 LR(1) 解析算法的原理。

1. 基础：引理 2.58 的 DPDA P
   • 证明的起点是我们在将 DCFG (LR(0)) 转换为 DPDA 时所用的那个 DPDA $P$。
   • 那个 DPDA $P$ 的核心思想是：在栈里存储 DK 自动机的状态，来模拟一个移入-规约过程。
2. 为 LR(1) 进行升级：构造 DPDA $P_1$
   • 新的 DPDA $P_1$ 同样在栈里存储状态，但它模拟的是 $DK_1$ 自动机，而不是 $DK$。
   • 核心增强: $P_1$ 被赋予了前瞻 (lookahead) 的能力。
   • $P_1$ 的“有限状态存储器” (即它的状态集合) 被设计得更复杂，用来额外存储一个终结符。
   • 在任何时候，$P_1$ 不仅知道自己当前的状态，还知道输入流中的下一个符号是什么。它总是“超前读取 1 个符号”。
3. $P_1$ 的工作流程 (LR(1) 解析算法)
   • 移入 (Shift): 和以前一样，$P_1$ 读取输入，模拟 $DK_1$ 的状态转移，并将新状态压栈。同时，它更新自己存储的“下一个输入符号”。
   • 决策点 (规约或移入?): 当 $P_1$ 模拟的 $DK_1$ 到达一个包含完成项的状态时，它就面临一个决策。
   • 这个 $DK_1$ 状态可能包含一个或多个完成项（如 [A -> u., a]），也可能包含未完成项（如 [B -> v.bw, c]）。
   • 此时，$P_1$ 拿出它预先存储的前瞻符号（即当前输入流中真正的下一个符号）。
   • 它用这个前瞻符号去匹配当前 $DK_1$ 状态里的所有可能性：
   • 如果前瞻符号匹配了某个完成项 [A -> u., a] 的前瞻 a，那么规约就是一个合法的选项。
   • 如果前瞻符号匹配了某个未完成项 [B -> v.bw, c] 的移入符号 b，那么移入就是一个合法的选项。
   • 利用 LR(1) 性质:
   • 因为我们假设文法是 LR(1) 的，所以它通过了 $DK_1$ 检验。
   • 这意味着，对于任何一个前瞻符号，在任何一个 $DK_1$ 状态中，合法的选项永远只有一个。
   • 不可能会出现“既可以规约又可以移入”或“可以按两种不同方式规约”的情况。
   • 执行: $P_1$ 根据这个唯一的合法选项，执行相应的规约或移入操作。
   • 整个过程因此是确定性的。

这一部分是教材第二章的课后练习题，旨在巩固本章学习的核心概念，包括上下文无关文法 (CFG)、下推自动机 (PDA)、乔姆斯基范式 (CNF)、确定性与非确定性、歧义性以及闭包性质等。

• 练习 2.1: 核心考察对推导 (derivation) 和分析树 (parse tree) 的理解。这是一个基础练习，要求学生能够手动模拟文法的生成过程，并将其可视化。
• 练习 2.2: 考察 CFL 的闭包性质。这是一个经典的证明题，利用反例来证明 CFL 在交集和补集运算下是不封闭的。这揭示了 CFL 相对于正则语言的一个重要弱点。
• 练习 2.3: 考察对文法基本定义和推导关系 ⇒ (一步推导) vs *⇒ (零步或多步推导) 的掌握。要求学生能识别文法的组成部分，并判断各种推导关系是否成立，最终理解文法所描述的语言。
• 练习 2.4: 考察设计 CFG 的能力。要求学生为一系列具有特定模式的语言构造生成文法。这是从“分析文法”到“创造文法”的进阶。
• 练习 2.5: 考察设计 PDA 的能力，与 2.4 配对。要求为相同的语言设计识别它们的下推自动机，从而在 CFG 和 PDA 之间建立直观的联系。
• 练习 2.6 & 2.7: 难度更高的 CFG 和 PDA 设计题，涉及更复杂的语言结构，如数量比较、子字符串关系和回文等。
• 练习 2.8: 考察歧义性 (ambiguity)。要求学生找到一个句子的两种不同推导，并解释这两种推导在自然语言理解中对应的不同含义，从而揭示语法歧义的实际影响。
• 练习 2.9 & 2.10: 再次结合 CFG 和 PDA，处理一个由“或”连接的复合语言，并探讨其歧义性。
• 练习 2.11 & 2.12: 考察对 CFG → PDA 构造算法（定理 2.20）的掌握。要求学生机械地、按步骤地执行算法，将给定的文法转化为等价的 PDA。
• 练习 2.13: 综合性题目，要求理解一个较复杂的文法生成的语言，并证明该语言不是正则的（通常使用泵引理）。
• 练习 2.14: 考察对 CFG → CNF 转换算法的掌握。乔姆斯基范式是一种重要的文法范式，在某些算法（如 CYK 解析算法）中是必需的。
• 练习 2.15: 考察批判性思维，要求学生为一种错误的“证明”构造一个反例。这训练学生不仅仅是接受定理，还要能识别证明中的漏洞。
• 练习 2.16 & 2.17: 考察 CFL 的闭包性质（在并集、连接、星号下是封闭的），并利用这些性质来提供一个从正则表达式到 CFG 的直接构造，从而再次证明正则语言是 CFL 的子集。