假设您有一种语言，其中标识符可能以关键字开头。例如，假设"case"是一个关键字，但"caser"是一个有效标识符。还假设词法分析器规则只能处理正则表达式。然后，我似乎不能将关键字规则放在词法分析器中的标识符规则之前，因为这会将"caser"解析为"case"后面跟着"r"。我也不能将关键字词法分析规则放在标识符规则之后，因为标识符规则将匹配关键字，而关键字规则将永远不会触发。
因此，我可以在词法分析器中创建一个keyword_or_identifier规则，并让解析器确定keyword_or_identifier是关键字还是标识符。这是通常的做法吗?
我意识到"使用另一个具有前瞻性的词法分析器"是一个答案(某种程度上)，但我也对如何在传统的基于dfa的词法分析器中实现这一点感兴趣，因为我当前的词法分析器似乎是这样工作的。
大多数词法分析器，从原始的lex开始，按如下方式匹配备选项:
-
使用最长匹配
-
如果有两个或两个以上的备选项为最长匹配，则使用词法分析器定义中的第一个。
允许以下样式:
"case" { return CASE; }
[[:alpha:]][[:alnum:]]* { return ID; }
如果输入模式是caser，那么将使用第二个选择，因为它是最长的匹配。如果输入模式是case r，那么将使用第一个选项，因为它们都匹配case，并且根据上面的规则(2)，第一个获胜。
虽然这看起来有点武断，但它在很大程度上与DFA方法一致。首先，DFA不会在第一次达到接受状态时停止。如果是这样，那么像[[:alpha:]][[:alnum:]]*这样的模式将是无用的，因为它们在第一个字符上进入接受状态(假设它是字母)。相反，基于dfa的词法分析器会继续工作，直到不可能从当前状态转换为止，然后它们会备份到最后一个接受状态。(见下文)。
给定的DFA状态可能因为两个不同的规则而被接受，但这也不是问题;只记录第一个接受规则。
公平地说，这与DFA的数学模型略有不同，DFA对每个状态下的每个符号都有一个转换(尽管其中许多可能是向"接收"状态的转换)，并且根据读取输入的最后一个符号时自动机是否处于接受状态来匹配完整的输入。词法分析器模型略有不同，但也可以很容易地形式化。
理论模型中唯一的难点是"回到最后接受状态"。在实践中，这通常是通过每次达到接受状态时记住状态和输入位置来完成的。这确实意味着可能需要倒带输入流，可能是任意数量的倒带。
大多数语言不需要经常备份，很少有语言需要无限期备份。如果没有备份状态，某些词法分析器生成器可以生成更快的代码。(如果您使用-Cf或-CF, flex将执行此操作。)
导致无限期备份的一个常见情况是未能为字符串字面值提供适当的错误返回:
["][^"n]*["] { return STRING; }
/* ... */
. { return INVALID; }
在这里，如果在同一行上有一个匹配的"，那么第一个模式将匹配以"开头的字符串字面值。(为了简单起见，我省略了转义。)如果字符串字面量没有终止，则最后一个模式将匹配，但输入将需要重新缠绕到"。在大多数情况下，通过忽略不匹配的"来继续词法分析是没有意义的;忽略这条线的其余部分会更有意义。因此，备份不仅效率低下，而且很可能导致虚假错误消息的激增。一个更好的解决方案可能是:
["][^"n]*["] { return STRING; }
["][^"n]* { return INVALID_STRING; }
在这里，第二个选择只有在字符串没有终止的情况下才能成功，因为如果字符串终止，第一个选择将多匹配一个字符。因此，这些选项出现的顺序并不重要，尽管我认识的每个人都会按照我的顺序排列它们。