词法分析器和分析器之间的通信
每次我写一个简单的词法分析器和解析器时，我都会遇到同样的问题：词法分析器和解析器应该如何通信？ 我看到四种不同的方法：
词法分析器急切地将整个输入字符串转换为一个标记向量。 一旦完成，矢量将被馈送到解析器，该解析器将其转换为树。 这是迄今为止最简单的解决方案，但由于所有令牌都存储在内存中，因此浪费了大量空间。
每当词法分析器找到一个标记时，它就会在解析器上调用一个函数，传递当前的标记。 根据我的经验，这仅适用于解析器自然可以像LALR解析器那样的状态机实现的情况。 相比之下，我认为它不会用于递归下降解析器。
每次解析器需要一个标记时，它都会要求词法分析器处理下一个标记。 由于yield关键字，这在C＃中很容易实现，但在C ++中很难实现。
词法分析器和解析器通过异步队列进行通信。 这在“生产者/消费者”标题下通常是众所周知的，它应该简化词法分析器和解析器之间的通信。 它是否也超越了其他多核解决方案？ 或者是太轻松了？
我的分析结果是什么？ 我还没有想过其他方法吗？ 实际编译器中使用什么？ 如果像Eric Lippert这样的编译器作者能够解释这个问题，那将非常酷。
虽然我不会将上述许多内容归类为不正确的内容，但我确实认为有几项内容具有误导性。
在运行解析器之前浏览整个输入与其他选项相比具有许多优点。 实现方式各不相同，但总的来说，此操作所需的内存不成问题，特别是当您考虑希望可用于报告编译错误的信息类型时。
语言实现注意事项：这是我的首选策略，因为它会产生可分离的代码，并且最适合翻译为实现该语言的IDE。
解析器实现注意事项：我使用ANTLR v3关于此策略的内存开销进行了试验。 C目标每个令牌使用超过130个字节，而Java目标使用每个令牌约44个字节。 使用修改后的C＃目标，我发现可以完全表示每个标记只有8个字节的标记化输入，这使得该策略对于甚至非常大的源文件都很实用。
语言设计说明：我鼓励设计一种新语言的人以允许此解析策略的方式这样做，无论他们是否最终选择参考编译器。
看起来你已经描述了一个“推”版本，我通常将其描述为一个“拉”解析器，就像你在＃3中描述的那样。 我的工作重点始终在LL解析上，所以对我来说这不是一个真正的选择。 如果在＃3中有利于这一点，我会感到惊讶，但不能排除它们。
这个最令人误解的部分是关于C ++的陈述。 在C ++中正确使用迭代器使其非常适合这种类型的行为。
一个队列看起来像是一个中间人＃3的重复。 虽然抽象独立操作在模块化软件开发等领域具有很多优势，但用于可分发产品的词法分析器/解析器对对性能高度敏感，并且这种抽象类型无法对数据结构和内存布局进行某些类型的优化。 我会鼓励使用选项＃3。
作为关于多核解析的补充说明：单个编译单元编译的初始词法分析器/解析器阶段通常不能并行化，也不需要考虑简单地在不同的编译单元上运行并行编译任务是多么容易（例如在每个源文件上执行一个词法分析器/解析器操作，跨源文件进行并行处理，但只对任何给定文件使用单个线程）。
关于其他选择：对于一个旨在广泛使用（商业或其他）的编译器，通常实现者选择一个解析策略和实现，在目标语言的约束下提供最佳性能。 一些语言（例如Go）可以使用简单的LR解析策略异常快速地解析，而使用“更强大”的解析策略（阅读：不必要的功能）只会减慢速度。 其他语言（如C ++）对于典型算法的解析极具挑战性或不可能，因此采用速度较慢但功能更强大/灵活的解析器。
我认为这里没有黄金法则。 要求可能因案例而异。 所以，合理的解决方案也会有所不同。 让我从我自己的经验中评论你的选择。
“令牌的矢量”。 此解决方案可能会占用大量内存。 想象一下，用很多标题编译源文件。 只存储令牌本身是不够的。 错误消息应该包含文件名和行号的上下文。 可能发生的一个情况是，词法分析器依赖于解析器。 合理的例子：“>>” - 这是一个移位运算符，或者这是关闭2层模板实例吗？ 我会投下这个选项。
（2,3）。 “一部分叫另一部分”。 我的印象是更复杂的系统应该称之为不太复杂的系统。 我认为词法更简单。 这意味着解析器应该调用词法分析器。 我不明白为什么C＃比C ++更好。 我将C / C ++词法分析器实现为一个子例程（实际上这是一个复杂的类），它是从基于语法的解析器中调用的。 这个实现没有问题。
“沟通过程”。 这似乎是一个矫枉过正的问题。 这种方法没有错，但也许最好让事情简单些？ 多核方面。 编译单个文件是一个比较罕见的情况。 我会建议使用自己的文件加载每个核心。
我没有看到将词法分析器和解析器组合在一起的其他合理选项。
我写这些笔记考虑编译软件项目的来源。 解析一个简短的查询请求是完全不同的事情，原因可能会有很大的不同。 我的回答是基于我自己的经验。 其他人可能会看到这一点。
词法分析器关系比最常见的协程简单，因为一般来说，通信是单向的; 解析器不需要将信息发送回词法分析器。 这就是为什么渴望生成的方法有效（有一些惩罚，尽管它意味着你可以更早地放弃输入）。
正如你所观察到的，如果词法分析器或解析器都可以用可重新编译的风格编写，那么另一个可以被视为一个简单的子程序。 这可以始终作为源代码转换实现，并将局部变量转换为对象插槽。
尽管C ++没有对协程的语言支持，但可以使用库支持，特别是光纤。 Unix setcontext系列是一种选择; 另一种方法是使用多线程，但使用同步队列（实质上是单线程，但在两个控制线程之间切换）。