maximal-munch是如何实现的？

Question

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

但是,我的问题是,如何实施最大 - 蒙克规则？在内部,词法分析者如何"继续"找到最长的lexeme？

谢谢!

Answer 1

maximal munch 算法是通过向 DFA 执行器添加少量可变状态，并添加 DFA 执行器“倒回”输入的能力来实现的：实际上，为它提供了 和 等tell()函数seek()。

\n\n

还值得注意的是，DFA 并不完整，即转换函数不完整。有些{state, input}配对没有明确的结果。[笔记2]

\n\n

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

\n\n

Set Accepted NFA State to \xe2\x8a\xa5\nSet Accepted Position to Tell(Input Stream)\nSet State to Starting State\nRepeat:\n  If State \xe2\x88\x88 Accepting:\n    Set Accepted NFA State to Accepting NFA State for State  [Note 1]\n    Set Accepted Position to Tell(Input Stream)\n  Read one symbol from Input Stream into Next Symbol\n  If there is a transition from {State, Next Symbol} to New State:\n    Set State to New State\n    Continue the loop\n  Otherwise:\n    Rewind Input Stream to Accepted Position\n    Return Accepted NFA State\n

\n\n

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

\n\n\n\n

笔记：

\n\n

\n

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

\n

2. sink通过添加一个附加的（且唯一的）状态（不接受并且仅具有向其自身的转换），可以轻松地使 DFA 完成。然后我们可以将sink状态添加为任何其他未指定转换的转换。如果我们将sink状态称为⊥，那么如何修改所提供的算法就很清楚了；实际上，这根本没有必要，因为实际上我们并不关心 DFA 是否不完整。不过，它确实对状态最小化算法有一些影响。

\n

\n