词法分析器的文字提取策略

Question

我已经为类似 C 的语言构建了一个词法分析器，例如给定此输入会产生以下结果。

输入

int i = 0 ; int j = i + 3;

输出

int    KEYWORD
i      IDENTIFIER
=      OPERATOR
;      PUNCTUATION
int    KEYWORD
j      IDENTIFIER
=      OPERATOR
i      IDENTIFIER
+      OPERATOR
3      INTEGER_CONSTANT
;      PUNCTUATION

在上面的例子中你可能已经注意到给定的输入在语法上是正确的，但是当我给它类似下面的内容时它失败了。

输入

int i = "1.2.2222.+\<++++

我做了一个class，其唯一目的是将上面的字符串分成小部分（我称它们为文字，不知道它是否正确）可以与正则表达式或匹配通过 DFA 验证。

问题出现在模棱两可的情况下，例如 +，其中 + 可以是加法运算符，也可以是即将到来的整数文字的一部分，甚至可以是增量运算符的一部分。我的老师要求在下一段解释。

如果+前面有+，则应作为递增运算符处理。简而言之，程序必须尝试寻找每一种可能性并选择最好的。这意味着如果程序有一些有效输入然后一些无效输入再次一些有效输入它不应该停止在那个无效输入而不是继续寻找正确的文字。对我来说，虽然我反对它。我的论点是，如果一个程序字符串在某个索引处变得无效，它应该停止处理，因为毕竟我们不是在编写错误检查系统。

我尝试使用复杂的（对我来说）嵌套 if else 结构来编写所有可能性，并取得了部分成功。你们能不能建议我一个更简单和优雅的解决方案。我也考虑过将这个问题构建到状态机中，但我不太确定，因为我之前从未实现过状态机，除了 DFA 可以告诉模式匹配是或否。

如您所见，这是一道作业题，但我不只是要求代码。

Answer 1

通常的词法分析方法是对一种算法使用"maximal munch" algorithm: the input stream is divided into tokens by repeatedly taking the longest prefix which could be a single token. See this answer。

偶尔需要对这条规则进行例外处理（在c++中，例如，<::通常被词法化为<、::），但总的来说，最大munch 规则易于实施，更重要的是，易于阅读。