我有这个语法
E -> E + i
E -> i
增广语法
E' -> E
E -> E + i
E -> i
现在我尝试扩展项目集0
I0)
E' -> .E
+E -> .E + i
+E -> .i
然后，由于我在I0中有.E，我会扩展它，但随后我会得到另一个E规则，依此类推，这是我的第一个疑问。
假设这是可以的，下一个项目集是
I0)
E' -> .E
+E -> .E + i
+E -> .i
I1) (I moved the dot from I0, no variables at rhs of dot)
E' -> E.
E -> E. + i
E -> i.
I2) (I moved the dot from I1, no vars at rhs of dot)
E -> E +. i
I3) (I moved the dot from I2, also no vars)
E -> E + i.
然后我会有这个DFA
I0 -(E, i)-> I1 -(+)-> I2 -(i)-> I3
| |
+-(∅)-> acpt <-(∅)--+
我错过了一些东西，因为E -> E + i必须接受i + i + ..，但DFA不会返回到I0，所以我觉得这是错误的。我的猜测是它应该有I0到I0的转换，但我不知道这与点有关。
您称之为"；扩展"；项集合的实际上是一个闭包；这就是我所见过的所有算法描述中对它的描述(至少在教科书中是这样(。像任何闭合操作一样，您只需继续进行转换，直到达到定点；一旦包含了E的制作，它们就包含在内了。
但最重要的一点是，您并不是在构建DFA。你正在构建一个下推自动机，DFA只是其中的一部分。DFA用于移位操作；当您移动一个新终端时(因为当前解析堆栈不是句柄(，您将根据DFA进行状态转换。但是您也可以将当前状态推送到PDA的堆栈中。
有趣的部分是，当自动机决定执行约简时会发生什么，该约简将生产的右侧替换为其左侧非终端。(叠层顶部的右手边被称为"手柄"。(要进行还原，请展开叠层，弹出每个右手边符号(以及相应的DFA状态(，直到开始生产。这样做的目的是将DFA倒带到它从右侧移动第一个符号之前的状态。(请注意，只有在这一点上，您才能确定使用了哪种产品。(随着DFA的重置，您现在可以移动遇到的非终端，进行相应的DFA转换，并继续解析。
这个过程的基础是解析器堆栈在任何时候都是一个"；可行前缀"；；也就是说，一系列符号是某个右句子形式的前缀，它可以从起始符号派生出来。上下文无关语法的一组可行前缀的有趣之处在于，它是一种正则语言，因此可以被DFA识别。上面给出的还原过程精确地表示了当手柄为"0"时的这种识别过程；修剪的"；(使用Knuth的原始词汇(。
从这个意义上说，使用什么过程来确定要修剪哪个句柄并不重要，只要它提供了有效的答案。例如，每当在堆栈顶部发现潜在句柄时，您可以派生解析，并使用两个派生并行地继续。通过巧妙的堆栈管理，对于任何上下文无关语法，这种并行搜索都可以在最坏的O(n3(时间内完成(如果语法不模糊，则可以减少(。这是对Earley解析器的一个非常粗略的描述。
但在LR(k(解析器的情况下，我们要求语法是明确的，并且我们还要求我们可以通过从输入流中查看不超过k的符号来识别缩减，这是一个O(1(运算，因为k是固定的。如果在解析的每一点上，我们都知道是否要减少，如果是的话，选择哪种减少，那么减少就可以按照我上面概述的那样实现。对于固定语法，每个缩减可以在O(1(时间内执行(因为特定语法中右手边的最大大小是固定的(，并且由于解析中的缩减次数在输入大小上是线性的，所以整个解析可以在线性时间内完成。
这一切都有点不正式，但我希望这能成为一个直观的解释。如果你对形式证明感兴趣，唐纳德·克努思1965年的原始论文(关于语言从左到右的翻译(很容易找到，而且可读性很高。