37

每次我编写一个简单的词法分析器和解析器时，我都会偶然发现同一个问题：词法分析器和解析器应该如何通信？我看到四种不同的方法：

  1. 词法分析器急切地将整个输入字符串转换为标记向量。完成此操作后，将向量馈送到解析器，解析器将其转换为树。这是迄今为止实现的最简单的解决方案，但由于所有令牌都存储在内存中，因此浪费了大量空间。

  2. 每次词法分析器找到一个标记时，它都会调用解析器上的一个函数，传递当前标记。以我的经验，这只有在解析器可以自然地实现为像 LALR 解析器这样的状态机时才有效。相比之下，我认为它根本不适用于递归下降解析器。

  3. 每次解析器需要一个令牌时，它都会向词法分析器询问下一个令牌。由于yield关键字，这在 C# 中很容易实现，但在没有它的 C++ 中很难实现。

  4. 词法分析器和解析器通过异步队列进行通信。这在“生产者/消费者”的标题下是众所周知的，它应该大大简化了词法分析器和解析器之间的通信。它是否也优于其他多核解决方案？还是词法太琐碎？

我的分析合理吗？还有其他我没有想到的方法吗？实际编译器中使用什么？如果像 Eric Lippert 这样的编译器作者能够对这个问题有所了解，那将是非常酷的。

4

5 回答 5

12

虽然我不会将以上大部分内容归类为不正确的，但我确实相信有几项具有误导性。

  1. 在运行解析器之前对整个输入进行词法分析与其他选项相比具有许多优势。实现方式各不相同，但一般来说，此操作所需的内存不是问题，尤其是当您考虑您希望用于报告编译错误的信息类型时。

    • 好处
      • 错误报告期间可能会提供更多信息。
      • 以允许在解析之前进行词法分析的方式编写的语言更容易指定和编写编译器。
    • 缺点
      • 某些语言需要上下文相关的词法分析器，而这些词法分析器在解析阶段之前根本无法运行。

    语言实现说明：这是我的首选策略，因为它会生成可分离的代码，并且最适合翻译为实现该语言的 IDE。

    解析器实现说明：我用 ANTLR v3 试验了这种策略的内存开销。C 目标每个令牌使用超过 130 个字节，Java 目标每个令牌使用大约 44 个字节。使用修改后的 C# 目标，我展示了可以完全表示每个标记仅 8 个字节的标记化输入，这使得该策略即使对于非常大的源文件也很实用。

    语言设计说明：我鼓励人们设计一种新语言，以允许这种解析策略的方式这样做，无论他们最终是否选择它作为他们的参考编译器。

  2. 看来你已经描述了我通常看到的“拉”解析器的“推”版本，就像你在＃3中一样。我的工作重点一直是 LL 解析，所以这对我来说并不是一个真正的选择。如果这对#3 有好处，我会感到惊讶，但不能排除它们。

  3. 其中最具误导性的部分是关于 C++ 的陈述。在 C++ 中正确使用迭代器使其非常适合这种类型的行为。

  4. 队列似乎是对#3 的重演，中间有一个中间人。虽然抽象独立操作在模块化软件开发等领域具有许多优势，但用于可分发产品的词法分析器/解析器对对性能非常敏感，并且这种类型的抽象消除了对数据结构和内存布局进行某些类型优化的能力. 我会鼓励在此使用选项#3。

    作为多核解析的附加说明：单个编译单元编译的初始词法分析器/解析器阶段通常不能并行化，它们也不需要考虑在不同编译单元上简单地运行并行编译任务是多么容易（例如，对每个源文件进行一个词法分析器/解析器操作，跨源文件并行化，但对任何给定文件仅使用单个线程）。

关于其他选项：对于旨在广泛使用（商业或其他）的编译器，通常实现者选择在目标语言的约束下提供最佳性能的解析策略和实现。使用简单的 LR 解析策略可以非常快速地解析某些语言（例如 Go），而使用“更强大”的解析策略（阅读：不必要的功能）只会减慢速度。其他语言（例如 C++）极具挑战性或无法使用典型算法进行解析，因此采用了速度较慢但功能更强大/更灵活的解析器。

于 2012-07-09T15:31:46.543 回答
5

我认为这里没有黄金法则。要求可能因情况而异。因此，合理的解决方案也可能不同。让我根据我自己的经验评论您的选择。

  1. “令牌向量”。此解决方案可能会占用大量内存。想象一下编译带有很多头文件的源文件。存储令牌本身是不够的。错误消息应包含带有文件名和行号的上下文。词法分析器可能会依赖于解析器。合理的例子：“>>” - 这是一个移位运算符还是关闭 2 层模板实例？我会否决这个选项。

  2. (2,3)。“一个部分调用另一个部分”。我的印象是，更复杂的系统应该调用不太复杂的系统。我认为词法分析器更简单。这意味着解析器应该调用词法分析器。我不明白为什么 C# 比 C++ 更好。我将 C/C++ 词法分析器实现为从基于语法的解析器调用的子例程（实际上这是一个复杂的类）。在这个实现中没有问题。

  3. “沟通过程”。在我看来，这有点矫枉过正。这种方法没有错，但也许最好保持简单？多核方面。编译单个文件是比较少见的情况。我建议使用自己的文件加载每个核心。

我看不到将词法分析器和解析器组合在一起的其他合理选择。

我写这些笔记是为了考虑编译软件项目的源代码。解析一个简短的查询请求是完全不同的事情，原因可能会有很大的不同。我的回答是基于我自己的经验。其他人可能对此有不同的看法。

于 2012-07-09T16:04:14.143 回答
3

lexer-parser 关系比coroutines的最一般情况更简单，因为通常通信是单向的；解析器不需要将信息发送回词法分析器。这就是急切生成方法有效的原因（虽然它确实意味着您可以更早地丢弃输入，但会受到一些惩罚）。

正如您所观察到的，如果词法分析器或解析器中的任何一个可以以可重新调用的样式编写，那么另一个可以被视为一个简单的子例程。这总是可以实现为源代码转换，将局部变量转换为对象槽。

尽管 C++ 没有对协程的语言支持，但可以利用库支持，尤其是fiber。Unixsetcontext系列是一种选择；另一种是使用多线程，但使用同步队列（本质上是单线程，但在两个控制线程之间切换）。

于 2012-07-09T15:13:59.717 回答
2

还要考虑 #1 是否使用不需要它的 lex 令牌，例如，如果有错误，此外，您可能会在内存或 I/O 带宽上运行不足。我相信最好的解决方案是由 Bison 等工具生成的解析器使用的解决方案，解析器调用词法分析器来获取下一个标记。最小化空间需求和内存带宽需求。

#4只是不值得。词法分析和解析本质上是同步的——只是没有足够的处理来证明通信成本是合理的。此外，通常您会同时解析/解析多个文件——这已经可以一次最大化您的所有内核。

于 2012-07-09T15:26:57.057 回答
1

我在我正在进行的玩具构建系统项目中处理它的方式是拥有一个“文件阅读器”类，带有一个函数bool next_token(std::string&,const std::set<char>&). 此类包含一行输入（用于带有行号的错误报告）。该函数接受一个std::string将标记放入的引用，以及std::set<char>包含“标记结束”字符的 a。我的输入类既是解析器又是词法分析器，但如果你需要更多花哨的东西，你可以很容易地把它分开。所以解析函数只是调用next_token并且可以做他们的事情，包括非常详细的错误输出。

如果您需要保留逐字输入，则需要存储在 avector<string>或其他内容中读取的每一行，但不要单独存储每个标记和/或双 y。

我正在谈论的代码位于此处：

https://github.com/rubenvb/Ambrosia/blob/master/libAmbrosia/Source/nectar_loader.cpp

（搜索::next_token和extract_nectar功能是一切开始的地方）

于 2012-07-09T15:12:31.763 回答