关于构建编译器扫描器的问题

Question

我想从头开始构建一个编译器。所以第一步，我想构建一个扫描仪。但我遇到了一个问题，我应该如何对待关系运算符，例如“>=”、“==”、“<=”？我应该简单地将它们视为 "> then =、= then =、< then =" 还是作为一个整体？顺便问一下，“++”和“--”怎么样？感谢帮助！

Answer 1

扫描算法通常被设计为匹配最大可能的令牌。为了做到这一点，他们采用了“最大咀嚼”算法，每当遇到错误时都会回溯，并通过重置状态来继续。

\n

词法分析器最简单的实现策略是构建一个 DFA，对每个标记的正则表达式的并集进行建模。因此，如果您的语言的标记由=或===（但不是==）组成，由空格分隔（我将为此答案明确建模为_），那么您的词法分析器基本上将使用接受的 DFA 的状态=|===|__*（请注意，空白的规则是“至少一个_”，_+）。

\n

\n

正如您所看到的，有一个中间状态（您可以在输入时达到该状态==，但不会接受，因为它不是接受状态）。因此，假设您已经计算出 DFA（实际上，有用于压缩每个输入字符上的范围和其他广义谓词的快捷方式），您可以开始编写状态机。

\n

DFA 可以写成一个循环，对于每个状态（使用switch带有case每个状态的语句），根据源缓冲区中的当前字符检查当前状态。如果转换有效 - 即当前状态和当前输入字符作为 DFA 中的传出箭头存在 - 您将当前状态设置为该状态（并跟踪它是否接受）。

\n

为了使这项工作以最大程度的咀嚼方式进行，您需要在输入缓冲区中维护两个偏移量，previous并且current。最初，这些都是 0。您current在每次转换期间前进并跟踪最后的接受状态。这个想法是，如果在任何时候都不存在这样的转换，您可以回溯/倒回到最后一个有效的接受状态。因此，如果不存在这样的转换，您可以倒回，生成一个令牌，然后更新前一个（以匹配当前、错误、偏移量），并将状态重置为初始状态。

\n

假设我们正在词法分析===____=. 词法分析器将处于初始状态，查看=，然后进入中间（接受）状态。从那里，它将看到下一个=并决定进入下一个（不接受）状态。然后，它会看到最终状态=并进入该链上的最终接受状态。一旦它看到，它将通过注意到和 的===接受状态没有有效的转换来看到新词位的开始。因此它会产生（通过获取 length 的子串，从 开始），重置机器，然后从初始状态开始检查 s 的序列。类似的故事会发生在 yield和上（使用一个特殊的标记，当输入耗尽时，所有词法分析器都倾向于使用该标记）。===_===current-prevprev_____=EOF

\n

我在这里描述的是最大 munch 算法的简单形式。这很简单，因为倒带永远不需要多个输入标记。其中描述了您可能希望进一步回溯的情况，以及由于巧妙构造的回溯场景，朴素算法（执行有限的簿记）可能具有最坏情况的 O(n^2) 时间复杂度。

\n

长话短说，您可以通过确保词法分析器识别其他标记但选择消耗最大可能（接受）输入来区分标记和其他标记的截断。您可以通过在 DFA 上跟踪该算法并在您正在词法分析的输入中维护两个偏移量来试验该算法。您可以在这里阅读有关最大咀嚼的更多信息。另一个有用的资源是一篇论文，描述了如何使该算法成为线性时间，\xe2\x80\x9cMaximal-Munch\xe2\x80\x9d 线性时间标记化- 我上面描述的算法及其改进是第 5 页，尽管描述略有不同。

\n