c# - 词法分析器和解析器之间的通信

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

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

   语言设计说明:我鼓励人们在设计新语言时以允许这种解析策略的方式来这样做，无论他们最终是否为自己的需要选择它引用编译器。

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

3. 这其中最容易引起误解的部分是关于 C++ 的陈述。在 C++ 中正确使用迭代器使其异常非常适合这种类型的行为。

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

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

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