对或错：上下文无关语法识别的任何单词也可以通过最右推导识别吗？
True or false: any word recognized by a context-free grammar can also be recognized via rightmost derivation?
假设我有一个上下文无关文法
S -> ...
...
其中“S”是起始符号。让“w”成为语法识别的词。是不是w只用最右推也能识别？
我认为这里的混淆围绕着语法“识别句子”意味着什么的问题。
事实上，context-free 文法是 生成 句子而不是识别句子的操作的表示。也就是说，语法中的每条规则都定义了一个推导步骤，可以通过将 left-hand-side 的任何一个实例替换为 right-hand-side 来应用于句子形式。如果我们从文法的开始符号开始形成这个操作的闭包，那么我们就有了句子形式的集合；语法的语言是这个集合与语法的终端字母表的 Kleene 闭包的交集。
(“句子形式”是指文法符号字母表的 Kleene 闭包中的元素，而“句子”仅限于终端字母表的 Kleene 闭包中的元素。这种区别来自 Knuth，我相信，但现在我仍然专注于诺姆·乔姆斯基 (Noam Chomsky) 的开创性论文 论文法的某些形式属性，写于 1959 年。)
碰巧，我们可以递归地枚举语言（作为一个集合）。所以我们可以通过开始枚举并等待句子出现来“识别”一个句子。这将适用于任何生成文法，而不仅仅是 context-free 文法，而且适用于乔姆斯基的无限制（类型 0）文法，它存在我们永远不知道何时放弃等待的问题。 （也就是说，它遇到了与一般图灵机相同的停机问题。）但使用受限语法，我们可以生成一个枚举，其中较短的句子先于较长的句子生成，因此我们绝对可以在枚举完所有句子后停止查找目标句子的长度。 （这在实践中仍然不是很令人满意，但在理论上已经很棒了。它是 Chomsky 论文中的定理 3。）这就是递归集合和递归可枚举集合之间的根本区别。
在实践中，我们想创建一个基于语法的解析自动机，更重要的是我们希望自动机保证在 well-defined 时间和 space 限制内工作。对于 Type 2 和 Type 3 语法，这绝对是可能的（对于 Type 3，线性时间和常数 space；对于 Type 2 语法，多项式时间和指数 < 3 的 space，以及线性时间space 在类型 2 语法的受限子集的情况下，称为确定性语法。）
但是让我们回到语法识别（或生成）句子意味着什么的问题。由于语言是 derivation-step 运算符的闭包，因此语言中的每个句子都是有限序列的推导步骤的结果，从开始符号开始。一系列推导步骤称为推导，如果使用语法推导了一个句子，则称该语法推导了该句子。这与我们将要得出的语法识别句子的概念一样接近。
理想情况下，我们希望减少由句子的多种可能派生产生的噪音。除了线性文法，总会有很多可能的推导，因为每当句子形式中有两个或更多 non-terminals 时，就有两个或更多可能的推导步骤可以应用，并且在 context-free (Type 2) 语法可以以任何顺序应用“工作”的语法。这是思考“context-free”在这种情况下的含义的一种简单方法。 （我鼓励任何读者尝试使前面的陈述更准确。我只是想在这里提供一些直觉，而不是数学证明。）
在乔姆斯基的论文中，他展示了如何将推导视为树的遍历，其中树实际上表达了派生句子的句法结构。因为我们实际上对树感兴趣而不是推导序列，所以我们想将遍历同一棵树的所有推导序列混为一谈。如果任何给定的句子只有一棵这样的树，那么我们可以说语法是无歧义的。
不幸的是，正如 Chomsky 也指出的那样，Type 1 文法仍然太强大而无法完成这项工作，而 Type 2 文法还不足以代表 Chomsky 感兴趣的语言（即人类语言）。但是，尽管他对未能定义适用于人类语言的有用语法类别感到沮丧，但他的工作在现代形式语言理论的发展中具有极其重要的意义。
现在，让我们将自己限制在类型 2 语法上，其中推导步骤的应用顺序无关紧要。在那种情况下，我们可以使用一种非常简单的算法将给定的解析树与恰好一个推导序列相关联：我们只允许对应于 depth-first 前序 right-to-left 遍历的推导序列。 （也就是说，我们访问 te children right-to-left.) 这对应的规则是在一个推导序列中，每个推导步骤都适用于句子形式中最右边的non-terminal。 （执行 left-to-right 遍历似乎更自然，这对应于始终扩展最左边的 non-terminal。从从解析树生成唯一推导的角度来看，这也行得通。但它变成了不太方便。）
这些见解来自另一篇开创性论文，Donald Knuth 的 论从左到右的语言翻译 (1965)。
所以我们现在应该对陈述感到满意：
- 句子 BT 使用语法 G 的语言
- G 导出 BT。
- G 仅使用最右边的推导步骤推导 BT。
所有人都说同样的话。但一路走来，我们也为几十年的解析研究奠定了基础。
很容易找到我在这里引用的两篇论文，这样做是值得的，因为它们都非常容易阅读，并且包含许多真正理解 LR 解析所必需的见解。
假设我有一个上下文无关文法
S -> ...
...
其中“S”是起始符号。让“w”成为语法识别的词。是不是w只用最右推也能识别？
我认为这里的混淆围绕着语法“识别句子”意味着什么的问题。
事实上，context-free 文法是 生成 句子而不是识别句子的操作的表示。也就是说，语法中的每条规则都定义了一个推导步骤，可以通过将 left-hand-side 的任何一个实例替换为 right-hand-side 来应用于句子形式。如果我们从文法的开始符号开始形成这个操作的闭包，那么我们就有了句子形式的集合；语法的语言是这个集合与语法的终端字母表的 Kleene 闭包的交集。
(“句子形式”是指文法符号字母表的 Kleene 闭包中的元素，而“句子”仅限于终端字母表的 Kleene 闭包中的元素。这种区别来自 Knuth，我相信，但现在我仍然专注于诺姆·乔姆斯基 (Noam Chomsky) 的开创性论文 论文法的某些形式属性，写于 1959 年。)
碰巧，我们可以递归地枚举语言（作为一个集合）。所以我们可以通过开始枚举并等待句子出现来“识别”一个句子。这将适用于任何生成文法，而不仅仅是 context-free 文法，而且适用于乔姆斯基的无限制（类型 0）文法，它存在我们永远不知道何时放弃等待的问题。 （也就是说，它遇到了与一般图灵机相同的停机问题。）但使用受限语法，我们可以生成一个枚举，其中较短的句子先于较长的句子生成，因此我们绝对可以在枚举完所有句子后停止查找目标句子的长度。 （这在实践中仍然不是很令人满意，但在理论上已经很棒了。它是 Chomsky 论文中的定理 3。）这就是递归集合和递归可枚举集合之间的根本区别。
在实践中，我们想创建一个基于语法的解析自动机，更重要的是我们希望自动机保证在 well-defined 时间和 space 限制内工作。对于 Type 2 和 Type 3 语法，这绝对是可能的（对于 Type 3，线性时间和常数 space；对于 Type 2 语法，多项式时间和指数 < 3 的 space，以及线性时间space 在类型 2 语法的受限子集的情况下，称为确定性语法。）
但是让我们回到语法识别（或生成）句子意味着什么的问题。由于语言是 derivation-step 运算符的闭包，因此语言中的每个句子都是有限序列的推导步骤的结果，从开始符号开始。一系列推导步骤称为推导，如果使用语法推导了一个句子，则称该语法推导了该句子。这与我们将要得出的语法识别句子的概念一样接近。
理想情况下，我们希望减少由句子的多种可能派生产生的噪音。除了线性文法，总会有很多可能的推导，因为每当句子形式中有两个或更多 non-terminals 时，就有两个或更多可能的推导步骤可以应用，并且在 context-free (Type 2) 语法可以以任何顺序应用“工作”的语法。这是思考“context-free”在这种情况下的含义的一种简单方法。 （我鼓励任何读者尝试使前面的陈述更准确。我只是想在这里提供一些直觉，而不是数学证明。）
在乔姆斯基的论文中，他展示了如何将推导视为树的遍历，其中树实际上表达了派生句子的句法结构。因为我们实际上对树感兴趣而不是推导序列，所以我们想将遍历同一棵树的所有推导序列混为一谈。如果任何给定的句子只有一棵这样的树，那么我们可以说语法是无歧义的。
不幸的是，正如 Chomsky 也指出的那样，Type 1 文法仍然太强大而无法完成这项工作，而 Type 2 文法还不足以代表 Chomsky 感兴趣的语言（即人类语言）。但是，尽管他对未能定义适用于人类语言的有用语法类别感到沮丧，但他的工作在现代形式语言理论的发展中具有极其重要的意义。
现在，让我们将自己限制在类型 2 语法上，其中推导步骤的应用顺序无关紧要。在那种情况下，我们可以使用一种非常简单的算法将给定的解析树与恰好一个推导序列相关联：我们只允许对应于 depth-first 前序 right-to-left 遍历的推导序列。 （也就是说，我们访问 te children right-to-left.) 这对应的规则是在一个推导序列中，每个推导步骤都适用于句子形式中最右边的non-terminal。 （执行 left-to-right 遍历似乎更自然，这对应于始终扩展最左边的 non-terminal。从从解析树生成唯一推导的角度来看，这也行得通。但它变成了不太方便。）
这些见解来自另一篇开创性论文，Donald Knuth 的 论从左到右的语言翻译 (1965)。
所以我们现在应该对陈述感到满意：
- 句子 BT 使用语法 G 的语言
- G 导出 BT。
- G 仅使用最右边的推导步骤推导 BT。
所有人都说同样的话。但一路走来，我们也为几十年的解析研究奠定了基础。
很容易找到我在这里引用的两篇论文，这样做是值得的，因为它们都非常容易阅读，并且包含许多真正理解 LR 解析所必需的见解。