regex - 最大咀嚼是如何实现的？

Question

我正在研究编译器并且正在学习词法分析。我了解将每个词位指定为正则表达式，并使用 flex ，可以自动生成词法分析器。我正在进一步了解如何将正则表达式转换为 NFA，然后再将其转换为 DFA，以便对其进行快速评估。

但是，我的问题是， 怎么样？最大咀嚼规则 实现的？在内部，词法分析器如何知道“继续”以找到可能最长的词素？

谢谢!

Answer 1

最大蒙克算法是通过向 DFA 执行器添加少量可变状态，并添加 DFA 执行器“回退”输入的能力来实现的:实际上，为它提供了类似 tell() 的功能。和 seek() .

还值得注意的是，DFA 是不完整的，从某种意义上说，转换功能是不完整的。一些 {state, input}对没有定义的结果。 [笔记2]

考虑到这一点，算法如下:

Set Accepted NFA State to ⊥
Set Accepted Position to Tell(Input Stream)
Set State to Starting State
Repeat:
  If State ∈ Accepting:
    Set Accepted NFA State to Accepting NFA State for State  [Note 1]
    Set Accepted Position to Tell(Input Stream)
  Read one symbol from Input Stream into Next Symbol
  If there is a transition from {State, Next Symbol} to New State:
    Set State to New State
    Continue the loop
  Otherwise:
    Rewind Input Stream to Accepted Position
    Return Accepted NFA State

如果算法返回 ⊥，则没有识别到​​任何标记，输入流将被倒回到初始位置。

笔记:

NFA 通常在状态和接受 Action 之间具有明确的同态性，但是 DFA 构造算法可以将两个接受 NFA 状态与不同的 Action 结合起来。在这种情况下，flex算法是优先考虑输入文件中的第一个 Action 。在上述算法中，我们通过将每个接受 DFA 状态映射到具有优先级的接受 NFA 状态的组件来表示这一点。

通过添加额外的(且唯一的)sink 可以轻松完成 DFA状态是不接受的并且只有转换到自身。然后我们可以添加 sink state 作为任何其他未指定转换的转换。如果我们调用 sink state ⊥ 那么如何修改提供的算法就很清楚了；实际上，这根本没有必要，因为实际上我们并不关心 DFA 是否不完整。不过，它确实对状态最小化算法有一些影响。