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

Question

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

标签： compiler-construction

Answer 1

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

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

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

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

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

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

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

长话短说，您可以通过确保您的词法分析器识别两者但选择使用最大可能（接受）输入来区分作为其他标记截断的标记。您可以通过在 DFA 上跟踪该算法并将两个偏移量保持到您正在词法分析的输入中来试验该算法。您可以在此处阅读有关最大咀嚼的更多信息。另一个有用的资源是一篇描述如何使该算法成为线性时间的论文，“线性时间中的“Maximal-Munch”标记化——我在上面描述的算法，连同它的改进，在第 5 页，尽管描述有点不同。