假设我有一个上下文无关的语法
S -> ...
...
其中"；S〃；是一个起始符号。设"；w"；是语法能识别的单词。w也只能用最右边的导数来识别，这是真的吗？
我认为这里的困惑围绕着语法"；识别一个句子"；。
事实上，上下文无关语法是生成句子而不是识别它们的操作的表示。也就是说，语法中的每个规则都定义了一个派生步骤，可以通过用右手边替换左手边的任何一个实例来应用于句子形式。如果我们从语法的起始符号开始形成这个运算的闭包，那么我们就有了一组句子形式；语法的语言是这个集合与语法的终端字母表的Kleene闭包的交集。
(我们所说的"句子形式"指的是语法符号字母表的Kleene闭包中的一个元素，而"句子"仅限于词尾字母表Kleene闭包的元素。我相信，这种区别源于Knuth，但目前我仍专注于诺姆·乔姆斯基1959年发表的开创性论文《语法的某些形式性质》。)
碰巧的是，我们可以递归地枚举语言(作为一个集合)。所以我们可以"；识别"；开始列举并等待句子出现的句子。这将适用于任何生成语法，不仅是上下文无关语法，而且适用于乔姆斯基的无限制(0型)语法，它的问题是我们永远不知道何时放弃等待。(也就是说，它和一般的图灵机一样存在Halting问题。)但使用受限语法，我们可以生成一个枚举，其中在较长的句子之前生成较短的句子，所以我们肯定可以在枚举完目标句子长度的所有句子后停止查看。(这在实践中仍然不太令人满意，但在理论上很好。这是乔姆斯基论文中的定理3。)这从根本上就是递归集和递归可枚举集之间的区别。
在实践中，我们希望基于语法创建一个解析自动机，更重要的是，我们希望自动机能够保证在定义明确的时间和空间限制内工作。对于类型2和类型3语法，这是肯定可能的(类型3的线性时间和常数空间；在类型2语法的情况下指数<3的多项式时间和空间，以及在类型2文法的受限子集(称为确定性语法)的情况下的线性时间和空间。)
但让我们回到语法识别(或生成)一个句子意味着什么的问题上来。由于该语言是推导步骤运算符的闭包，因此该语言中的每个句子都是从起始符号开始的有限推导步骤序列的结果。一系列推导步骤被称为推导，如果使用语法推导出一个句子，那么该语法就被称为派生出该句子。这就像我们将要了解的语法识别句子的概念一样。
理想情况下，我们希望减少一个句子的大量可能派生所产生的噪音。除了线性语法之外，总是会有很多可能的派生，因为每当句子形式中有两个或更多个非词尾时，就有两个以上可能的派生步骤可以应用，而在上下文无关(类型2)语法中；工作；可以按任何顺序应用。这是一种简单的思考方式；上下文无关"；在本文中的意思。(我鼓励任何读者尝试使前面的陈述更加准确。我只是想在这里提供一些直觉，而不是数学证明。)
在乔姆斯基的论文中，他展示了派生如何被视为树的遍历，其中树实际上表达了派生句子的句法结构。由于我们实际上对树而不是派生序列感兴趣，我们希望将同一棵树的所有派生序列合并。如果任何给定的句子只有一个这样的树，那么我们可以说语法是明确的。
不幸的是，正如乔姆斯基所指出的，类型1语法仍然太强大，无法实现这一点，而类型2语法的强大程度不足以代表乔姆斯基感兴趣的语言(即人类语言)。尽管他对未能定义一类适用于人类语言的有用语法感到沮丧，但他的工作在现代形式语言理论的发展中具有极其重要的意义。
现在，让我们将自己限制在类型2语法中，其中派生步骤的应用顺序是无关的。在这种情况下，我们可以使用一个非常简单的算法将给定的解析树与恰好一个派生序列相关联：我们只允许与深度优先预序从右到左遍历相对应的派生序列。(也就是说，我们从右到左访问孩子。)这对应于在推导序列中，每个派生步骤都适用于句子形式中最右边的非终端。(从左到右遍历似乎更自然，这将对应于始终扩展最左边的非终端的遍历。从从解析树生成唯一派生的角度来看，这也很有效。但事实证明，这不太方便。)
这些见解来自另一篇开创性的论文，唐纳德·克努思的《从左到右的语言翻译》(1965)。
因此，我们现在应该对以下声明感到满意：
- 句子β是语法G的语言
- G推导出¦Β
- G只使用最右边的推导步骤来推导β
都说同样的话。但在这一过程中，我们也为几十年的解析研究奠定了基础。
我在这里引用的这两篇论文都很容易找到，这是值得的，因为它们都很容易阅读，并且包含了真正理解LR解析所需的许多见解。