如何编写标识符可能以关键字开头的lexer解析器？

Question

假设您有一种语言，其中标识符可能以关键字开头。例如，假设“case”是一个关键字，但“caser”是一个有效的标识符。还假设lexer规则只能处理正则表达式。那么我似乎不能将关键字规则放在lexer中标识符规则的前面，因为这会将“caser”解析为“case”后跟“r”。我也不能在标识符规则之后放置关键字列表规则，因为标识符规则将匹配关键字，并且关键字规则永远不会触发。

因此，我可以在lexer中创建一个keyword_or_identifier规则，并让解析器确定keyword_or_identifier是关键字还是标识符。这是正常的做法吗？

我意识到“使用一个具有前瞻性的不同的lexer”是一个答案（某种程度上），但我也对如何在传统的基于DFA的lexer中做到这一点感兴趣，因为我当前的lexer似乎就是这样工作的。

Answer 1

大多数lexer从原始的lex开始，匹配备选项如下：

>

使用最长的匹配。

如果有两个或更多的备选项是最长的匹配项，则使用lexer定义中的第一个。

"case"                  { return CASE; }
[[:alpha:]][[:alnum:]]* { return ID; }

虽然这看起来有点武断，但它基本上与DFA方法是一致的。首先，DFA不会在第一次到达接受状态时停止。如果是这样，那么[[:alpha:]][[:alnum:]]*这样的模式就没有用了，因为它们会在第一个字符（假设是字母）上进入接受状态。取而代之的是，基于DFA的lexer会继续，直到当前状态没有可能的转换，然后它们会备份，直到最后一个接受状态。（见下文）

一个给定的DFA状态可能会因为两个不同的规则而接受，但这也不是问题；只记录第一个接受规则。

公平地说，这与DFA的数学模型略有不同，DFA的数学模型在每个状态下对每个符号都有一个转换（尽管其中许多转换可能是到“接收器”状态），并且根据自动机在读取输入的最后一个符号时是否处于接受状态，它匹配完整的输入。lexer模型略有不同，但也很容易被形式化。

理论模型中唯一的难点是“回到最后接受状态”。在实践中，这通常是通过每次达到接受状态时记住状态和输入位置来完成的。这确实意味着可能需要倒回输入流，可能倒回的量是任意的。

大多数语言并不经常需要备份，极少数语言需要无限期备份。如果没有备份状态，一些lexer生成器可以生成更快的代码。(flex将在使用-cf或-cf时执行此操作。）

导致不确定备份的一种常见情况是未能为字符串文本提供适当的错误返回：

["][^"\n]*["]    { return STRING; }
 /* ... */
.                { return INVALID; }

在这里，如果同一行上有匹配的“”，则第一个html" target="_blank">模式将匹配以“开头的字符串文字。（为了简单起见，我省略了\-转义。）如果字符串文字未终止，则最后一个模式将匹配，但需要将输入重绕到“。在大多数情况下，试图通过忽略不匹配的”来继续词法分析是没有意义的；忽略该行的全部剩余部分会更有意义。因此，备份不仅效率低下，而且很可能导致错误消息的爆炸。更好的解决办法可能是：

["][^"\n]*["]    { return STRING; } 
["][^"\n]*       { return INVALID_STRING; }

在这里，第二个备选方案只有在字符串未终止的情况下才能成功，因为如果字符串终止，第一个备选方案将多匹配一个字符。因此，即使我认识的每个人都会把它们按我所做的相同顺序排列，但它们的出现顺序并不重要。