7

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

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

我意识到“使用具有前瞻功能的不同词法分析器”是一个答案（有点），但我也对如何在传统的基于 DFA 的词法分析器中完成这一点感兴趣，因为我当前的词法分析器似乎是这样工作的。

4

1 回答 1

8

大多数词法分析器，从原来的 开始lex，匹配备选方案如下：

  1. 使用最长的匹配。

  2. 如果有两个或多个备选方案并列最长匹配，请使用词法分析器定义中的第一个。

这允许以下样式：

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

如果输入模式是caser，则将使用第二种选择，因为它是最长的匹配。如果输入模式是case r，则将使用第一个替代方案，因为它们都匹配case，并且根据上面的规则（2），第一个替代方案获胜。

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

由于两个不同的规则，给定的 DFA 状态可能正在接受，但这也不是问题；只记录第一个接受规则。

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

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

大多数语言不需要经常备份，很少需要无限期备份。如果没有备份状态，一些词法分析器生成器可以生成更快的代码。（flex如果您使用-Cfor将执行此操作-CF。）

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

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

在这里，第一个模式将匹配以 if 开头的字符串文字，如果在同一行上"有匹配项。"（为简单起见，我省略\了 -escapes。）如果字符串文字未终止，则最后一个模式将匹配，但输入将需要倒回到". "在大多数情况下，通过忽略不匹配的;来继续进行词法分析是没有意义的。忽略该行的整个其余部分会更有意义。因此，不仅备份效率低下，而且还可能导致错误错误消息的爆炸式增长。更好的解决方案可能是：

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

在这里，第二个替代方案只有在字符串未终止的情况下才能成功，因为如果字符串终止，第一个替代方案将再匹配一个字符。因此，即使我认识的每个人都会按照我所做的相同顺序排列它们，这些替代方案的出现顺序甚至都无关紧要。

于 2013-05-05T23:04:54.570 回答