0

我有这个语法

E -> E + i
E -> i

增强语法

E' -> E
E -> E + i
E -> i

现在我尝试扩展项目集 0

I0)
 E' -> .E
+E  -> .E + i
+E  -> .i

然后，既然我有.E，I0我会扩展它，但我会得到另一个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 的转换，但是我不知道这与点有关。

4

1 回答 1

2

您所说的项目集的“扩展”实际上是一个闭包；这就是我见过的所有算法描述中的描述方式（至少在教科书中）。像任何闭包操作一样，您只需继续进行转换，直到达到一个固定点；一旦您包含 的作品E，它们就会被包含在内。

但关键是您不是在构建 DFA。您正在构建一个下推自动机，而 DFA 只是其中的一部分。DFA 用于移位操作；当您移动一个新终端时（因为当前的解析堆栈不是句柄），您根据 DFA 进行状态转换。但是您也将当前状态推送到 PDA 的堆栈中。

有趣的部分是当自动机决定执行归约时会发生什么，即用其左侧的非终结符替换产生式的右侧。（堆栈顶部的右侧称为“句柄”。）要进行归约，您展开堆栈，弹出每个右侧符号（和相应的 DFA 状态），直到到达生产。这样做是将 DFA 倒回到它从右侧移动第一个符号之前的状态。（请注意，只有此时您才能确定使用了哪个产生式。）如此重置 DFA，您现在可以移动遇到的非终端，执行相应的 DFA 转换，并继续解析。

这个过程的基础是解析器堆栈始终是一个“可行的前缀”。也就是说，一系列符号，它们是可以从起始符号派生的某些正确句子形式的前缀。上下文无关语法的可行前缀集的有趣之处在于它是一种常规语言，因此可以被 DFA 识别。当句柄被“修剪”（使用 Knuth 的原始词汇）时，上面给出的缩减过程精确地表示了这个识别过程。

从这个意义上说，使用什么过程来确定要修剪哪个句柄并不重要，只要它提供了一个有效的答案。例如，您可以在每次在堆栈顶部发现潜在句柄时分叉解析，并与两个分叉并行继续。通过巧妙的堆栈管理，对于任何上下文无关文法，这种并行搜索可以在最坏情况 O(n 3 ) 时间内完成（如果文法没有歧义，这可以减少）。这是对 Earley 解析器的非常粗略的描述。

k但是对于 LR(k) 解析器，我们要求语法是明确的，并且我们还要求我们可以通过从输入流中查看不超过多个符号来识别归约，这是一个 O(1)操作因为k是固定的。如果在解析中的每个点我们都知道是否要减少，如果是，那么选择哪个减少，那么可以按照我上面概述的那样实现减少。对于固定文法，每次归约可以在 O(1) 时间内执行（因为特定文法中右侧的最大大小是固定的），并且由于解析中归约的次数与文法的大小成线性关系输入，整个解析可以在线性时间内完成。

这有点非正式，但我希望它可以作为一个直观的解释。如果您对形式证明感兴趣，Donald Knuth 1965 年的原始论文（On the Translation of Languages from Left to Right）很容易找到并且具有很高的可读性。

于 2020-08-24T00:14:13.813 回答