词法分析器和分析器之间的通信

每次我写一个简单的词法分析器，我都会碰到同样的问题：词法分析器和parsing器应该如何交stream？ 我看到了四种不同的方法：

1. 词法分析器急切地将整个inputstring转换为一个标记向量。 一旦完成，vector被送到parsing器，parsing器将其转换成树。 这是迄今为止最简单的解决scheme，但是由于所有的令牌都存储在内存中，所以浪费了大量的空间。

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

3. 每一次parsing器都需要一个标记，它会要求词法分析器进行下一个标记。 由于yield关键字，这在C＃中很容易实现，但在C ++中很难实现。

4. 词法分析器和parsing器通过asynchronous队列进行通信。 这在“生产者/消费者”的标题下是众所周知的，它应该简化词法分析器和parsing器之间的通信。 它是否也超越了其他多核解决scheme？ 还是太轻松了？

我的分析是否正确？ 有没有其他的方法我没有想到？ 在实际编译器中使用什么？ 如果像Eric Lippert这样的编译器作者能够解释这个问题，这将是非常酷的。

Answer 1

虽然我不会把上面的很多内容归类为不正确的 ，但我相信有几个项目是误导性的。

1. 在运行parsing器之前查阅整个input与其他选项相比具有许多优点。 实现方式各不相同，但通常情况下，此操作所需的内存不成问题，特别是在考虑您希望用于报告编译错误的信息types时。

   • 优点
     • 错误报告期间可能提供更多信息。
     • 以一种允许在parsing之前进行的方式编写的语言更易于指定和编写编译器。
   • 缺点
     • 某些语言需要在分析阶段之前无法运行的上下文相关的词法分析器。

   语言实现注释：这是我的首选策略，因为它导致可分离的代码，并且最适合于翻译为实现该语言的IDE。

   parsing器实现注意事项：我对此策略进行了ANTLR v3关于内存开销的实验。 C目标每个令牌使用超过130个字节，而Java目标使用每个令牌约44个字节。 使用修改后的C＃目标，我发现可以完全表示每个标记只有8个字节的标记化input，使得这个策略对于甚至相当大的源文件来说都是实用的。

   语言devise说明：我鼓励人们devise一种新的语言来实现这种parsing策略，无论他们是否select参考编译器。

2. 看起来你已经描述了一个“推”的版本，我通常把它看作是一个“拉”parsing器，就像你在＃3中所描述的那样。 我的工作重点一直在LLparsing，所以这不是我的select。 如果这对3号球队有好处，我会感到惊讶，但不能排除这一点。

3. 这个最令人误解的部分是关于C ++的陈述。 正确使用C ++中的迭代器使得它非常适合这种types的行为。

4. 一个队列似乎像一个中间人＃3的重燃。 虽然抽象独立操作在模块化软件开发等领域具有诸多优势，但用于可分发产品的词法分析器/分析器对性能高度敏感，并且此类抽象化无法对数据结构和内存布局进行某些types的优化。 我会鼓励使用选项＃3。

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

关于其他select：对于一个旨在广泛使用（商业或其他）的编译器，通常实现者select一个parsing策略和实现，在目标语言的约束下提供最佳性能。 一些语言（例如Go）可以用一个简单的LRparsing策略exception快速地parsing，而使用“更强大”的parsing策略（阅读：不必要的特性）只会减慢速度。 其他语言（例如C ++）对于典型的algorithm来说是非常具有挑战性或不可能的，所以采用速度较慢但function更强大/灵活的parsing器。

Answer 2

我认为这里没有黄金法则。 要求可能会因个案而异。 所以，合理的解决scheme也可以不同。 让我从我自己的经验评论你的select。

1. “令牌的向量”。 这个解决scheme可能有很大的内存占用。 想象一下，用很多头文件编译源文件。 存储令牌本身是不够的。 错误消息应该包含文件名和行号的上下文。 词法分析器可能会发生这种情况。 合理的例子：“>>” – 这是一个移位运算符，或者这是2层模板实例的closures？ 我会投下这个选项。

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

3. “沟通过程”。 这似乎是一个矫枉过正的问题。 这种方法没有错，但也许最好保持简单？ 多核方面。 编译单个文件是比较less见的情况。 我会build议加载每个核心与自己的文件。

我没有看到合并词法分析器和parsing器的其他合理select。

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

Answer 3

词法分析器关系比最简单的协程简单 ，因为一般来说，通信是单向的; parsing器不需要将信息发送回词法分析器。 这就是为什么渴望生成的方法是有效的（虽然这确实意味着你可以更早地放弃input）。

正如你所观察到的，如果词法分析器或parsing器都可以用可重新编译的风格编写，那么另一个可以被看作一个简单的子程序。 这可以始终作为源代码转换来实现，将局部variables转换为对象插槽。

虽然C ++没有对协程的语言支持，但可以使用库支持，特别是光纤 。 Unix的setcontext族是一个选项; 另一种方法是使用multithreading，但使用同步队列（实质上是单线程，但在两个控制线程之间切换）。

Answer 4

还要考虑＃1你不需要它的标记，例如，如果有错误，另外，你可能在内存或I / O带宽上运行不足。 我相信最好的解决scheme就是由像Bison这样的工具生成的parsing器所使用的parsing器，在这里parsing器调用词法分析器来获取下一个标记。 最大限度地减less空间要求和内存带宽要求。

#4是不值得的。 Lexing和parsing本质上是同步的 – 没有足够的处理来certificate通信的成本。 另外，通常可以同时parsing/parsing多个文件 – 这可能已经最大化您的所有核心一次。

Answer 5

我在我的玩具构build系统项目中处理它的方式是通过一个“文件阅读器”类，使用函数bool next_token(std::string&,const std::set<char>&) 。 这个类包含一行input（用于错误报告的行号）。 该函数接受std::string引用来放置该标记，而std::set<char>则包含“标记结尾”字符。 我的input类是parsing器和词法分析器，但是如果你需要更多的幻想，你可以很容易地分割它。 所以parsing函数只是调用next_token ，可以做他们的事情，包括非常详细的错误输出。

如果你需要保留逐字input，你需要将每一行读入一个vector<string>或其他东西，而不是单独存储每个token和/或double-y。

我在说的代码位于这里：

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

（search::next_token和extract_nectar函数是在哪里开始）