如何在Lex中处理关键字？

Question

假设您有一种语言，允许像这样生成代码：optional optional = 42。其中第一个“optional”是关键字，第二个“optional”是标识符。

一方面，我想要一个类似optional { return OPTIONAL; }的Lex规则，稍后可以在YACC中使用，例如：

optional : OPTIONAL identifier '=' expression ;

如果我将identifier定义为，比如说：

identifier : OPTIONAL | FIXED32 | FIXED64 | ... /* couple dozens of keywords */ 
    | IDENTIFIER ;

感觉很糟糕……另外，我需要两种标识符，一种是当关键字作为标识符时使用，另一种是不允许使用关键字作为标识符时使用……

有没有惯用的解决方法？

- wvxvw

Answer 1

这是一个关键词未保留的情况。一些编程语言允许这样做：PL/I、FORTRAN。这不是词法分析器的问题，因为词法分析器应该始终知道哪些标识符是关键字。这是一个解析器的问题。通常会在语言规范中造成太多的歧义，进而导致解析变得非常困难。文法如下所示： identifier: keyword | IDENTIFIER; keyword: OPTIONAL | FIXED32 | FIXED64 | ...; 如果你的文法没有冲突，那么就没事了。如果有冲突，那么你需要使用更强大的解析器生成器，例如LR(k)或GLR。

- user1524750

Answer 2

除了您已经找到的解决方案之外，没有成语化的方法来解决这个问题。半保留关键字绝对不是lex/yacc语法预期使用情况之一。柠檬解析器生成器有一个备用声明，专为这种情况设计，但据我所知，这个有用的功能从未被添加到bison中。您可以使用GLR语法来避免需要弄清所有不同的identifier子集。但当然会有性能惩罚。

- rici

---

先生，我有一个问题。在词法分析（自定义，没有正则表达式引擎）的情况下，如何对类似“RETURNA”的标识符进行词法分析？如果我运行词法分析器，它将检测到“RETURN”作为关键字，并将末尾的“A”作为标识符。它将该单词拆分为关键字和标识符，但是我确定它是一个标识符。顺序是...->关键字->标识符->.. - user15307601

@DickWilliams：那么你需要修复词法分析器（lexer）。 （或使用词法分析器生成器，这对您和可执行文件都更有效率。）如果您想手动构建高效的词法分析器，请构建一个trie（这实际上是生成器为您执行的操作，可以节省您确保覆盖所有情况的麻烦）。 如果您不想这样做，那么每个关键字模式都需要检查第一个不匹配的字符是否是有效的标识符字符（字母，数字，“_”，以及其他允许的字符）。 - rici

谢谢您！我正在构建自己的词法分析器，因为我想学习它的工作原理。当然，使用现有的工具也很好！ - user15307601

@DickWilliams：通过构建自己的词法分析器，你不会学习到词法分析器的工作原理，因为手动构建表驱动状态机——编写词法分析器最有效的方法——太难且容易出错。在我看来，你更好地学习如何使用词法分析器。我通常使用的类比是：你会通过坚持使用泰勒展开式编写自己的sin和cos函数来学习三角学吗？这可能是一个有趣的数学练习，但它不会帮助你编写更好的图形。 - rici

编写非臃肿软件的关键是打造一个良好的API，舍弃不再需要（或从未必要）的功能。编写良好的接口可能是最困难的设计任务之一；它需要在满足用例（而不仅仅是你自己的用例）和避免过度工程之间取得微妙的平衡。首先，总是尝试使用各种不同用例的不同API。此外，不要立即拒绝现有的API；尝试找出动机以及它们是否有效。实现是最后要做的事情，而不是第一件事情。 - rici

Answer 3

您已经发现了在lex / yacc中处理这个问题的最常见方法，虽然不太美观，但也不算太糟糕。通常情况下，您会调用匹配标识符或（一组）关键字的规则，并且您可能有多个这样的规则 - 因为不同的上下文可能具有不同的关键字集合，可以接受作为名称。

另一种方法是，如果您有仅在易于识别的位置（例如在行首）被识别为关键字的关键字，则可以使用lex起始状态，以便仅在该上下文中返回关键字标记。在任何其他上下文中，关键字将被返回为标识符标记。您甚至可以使用yacc操作来设置词法分析器状态以处理相对复杂的上下文，但是您需要注意解析器执行的可能的一个令牌词法分析器前瞻（规则可能直到读取动作后的令牌之后才运行）。

- Chris Dodd

---

先生，我有一个问题。在词法分析（不使用正则表达式引擎的情况下）中，如何处理像 returna 这样的标识符？如果我运行词法分析器，它会将“return”检测为关键字，并将末尾的“a”检测为标识符。它会将该单词拆分为关键字和标识符，但我确信它是一个标识符。顺序是 ... -> 关键字 -> 标识符 -> ... - user15307601

@DickWilliams：lex总是匹配与模式相匹配的最长词元--只有当两个模式匹配相同长度时，顺序才有意义。因此，如果您有一个匹配return的模式和一个（稍后）匹配returna的模式，则会匹配更长的模式。 - Chris Dodd