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

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.+\<++++

我已经创建了一个类，它的唯一目的是将上面的字符串分解为小部分(我称它们为文本，不知道它是否是正确的术语)，它们可以与regex匹配，也可以用DFA验证。

出现了问题，例如++可以是加法运算符，也可以是即将出现的整数文字的一部分，甚至是增量运算符的一部分。下一段对我老师的要求作了解释。

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

我尝试使用复杂的嵌套(对我来说)嵌套的结构来编写所有可能的代码，并取得了部分成功。你能建议我一个简单而优雅的解决方案吗？我还考虑过将这个问题构造成一个状态机，但我不太确定，因为我以前从未实现过一个状态机，除了一个DFA，它可以为模式匹配区分是或否。

正如你所看到的，这是一个家庭作业问题，但我要求的不是仅仅的代码。

Answer 1

常用的词法分析方法是使用“最大咀嚼”算法:通过重复使用最长的前缀(可以是单个令牌)将输入流划分为令牌。有关一个算法，请参见这个答案。

偶尔有必要对此规则进行异常(例如，在c++中，<::通常被编成<、::)，但总的来说，极大的munch规则易于实现，更重要的是易于阅读。