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

Question

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

c#c++parsingcompiler-constructionlexer

38

每次我写一个简单的词法分析器和语法分析器时，都会遇到同样的问题：词法分析器和语法分析器应该如何通信？我看到了四种不同的方法：

词法分析器急切地将整个输入字符串转换为令牌向量。一旦完成，向量被提供给解析器，解析器将其转换为树形结构。这是实现最简单的解决方案，但由于所有令牌都存储在内存中，它浪费了大量空间。
每当词法分析器找到一个令牌时，它会调用解析器上的函数，传递当前令牌。根据我的经验，只有像LALR解析器这样自然可以作为状态机实现的解析器才能使用此方法。相比之下，我认为对于递归下降解析器根本行不通。
每当解析器需要一个令牌时，它会请求词法分析器提供下一个令牌。由于C#具有“yield”关键字，因此这非常容易实现，但在没有此功能的C++中实现起来相当困难。
词法分析器和解析器通过异步队列进行通信。这通常称为“生产者/消费者”，它应该大大简化词法分析器和解析器之间的通信。它是否在多核方面优于其他解决方案？或者词法分析过于琐碎了吗？

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

- fredoverflow

我一定是漏了什么，为什么有一个“GetNextToken（）”同步函数会有问题？ - Blindy

编写无需词法分析器的解析器（例如基于 PEGs），从而不必再担心这个问题。 - SK-logic

关于问题 #2，任何解析器都可以被实现为状态机（毕竟你的处理器就是一个状态机）。 - Ben Voigt

@DeadMG，我还是不明白，我实现了一个完整编译器的解析器，没有使用yield return语句，只有一个返回下一个标记的函数。它在解析器类的字段中保存当前语句的位置（技术上它保存当前和前一个标记，并返回前一个标记，所以我有向前看的能力，但这是细节）。 - Blindy

@Blindy：误解在问题方面。你的方法和标记为#3的方法是一样的，正如你所提到的，根本不需要一个yield return语句。还有其他等效的选择，比如词法分析器生成一个iterator<token>，在operator++中获取下一个标记...但这又是相同的方法：解析器以某种方式请求下一个标记。 - David Rodríguez - dribeas

@Blindy 在C#中，将字符串转换为标记向量的函数和获取下一个标记的函数之间的区别很小，这要归功于yield关键字。您可以假装一直拥有控制流，并使用for循环迭代字符串并yield return标记。在C++中，实现这两个不同的函数需要不同的“心态”。如果您认为在C++中实现迭代器很容易，那么您可能已经多次完成了此操作，并且可能从未在其他语言中使用过yield，以了解实际上实现迭代器有多容易。 - fredoverflow

5个回答

5

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

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

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

3. “通信进程”。这对我来说似乎有点过度。这种方法没有什么问题，但也许保持简单更好？多核方面。编译单个文件是相对较少的情况。我建议为每个核心加载自己的文件。

我不认为还有其他合理的将词法分析器和解析器结合在一起的选项。

我写下这些笔记是考虑到编译软件项目的源代码。解析短查询请求完全是另一回事，原因可能大相径庭。我的答案基于我的经验。其他人可能会有不同的看法。

- Kirill Kobelev

3

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

正如您所观察到的，如果词法分析器或解析器中的任何一个都可以以可重新调用的方式编写，则另一个可以被视为简单的子例程。这总是可以作为源代码转换来实现，其中本地变量被翻译成对象插槽。

尽管C++没有对协程的语言支持，但可以利用库支持，特别是fibers。Unix的setcontext族是一种选择；另一种选择是使用多线程，但使用同步队列（基本上是单线程，但在两个控制线程之间切换）。

- ecatmur

2

此处需要翻译的内容为：

另外，对于 #1，你需要考虑不需要进行词法分析的标记，例如如果出现错误，此外，你可能会在内存或 I/O 带宽方面遇到问题。我认为最好的解决方案是使用类似 Bison 工具生成的解析器所采用的方法，其中解析器调用词法分析器以获取下一个标记。这样可以最小化空间需求和内存带宽需求。

#4 不值得花费精力。词法分析和语法分析本质上是同步的-处理的数据量不足以证明通信的成本。此外，通常你会同时解析/词法分析多个文件- 这已经可以一次性占用所有核心。

- Puppy

1

在我的玩具构建系统项目中，我处理它的方式是使用一个“文件读取器”类，其中包含一个函数bool next_token(std::string&,const std::set<char>&)。该类包含一行输入（用于错误报告目的，带有行号）。该函数接受一个std::string引用以放置令牌，并且一个std::set<char>，其中包含“令牌结束”字符。我的输入类既是解析器又是词法分析器，但如果需要更多花哨的功能，您可以轻松地将其拆分。因此，解析函数只需调用next_token并执行其操作，包括非常详细的错误输出。

如果您需要保留逐字输入，则需要将每个读取的行存储在vector<string>或其他类似容器中，但不要单独存储每个令牌和/或重复存储。

我所说的代码位于此处：

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

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

- rubenvb

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sam Harwell · Accepted Answer

虽然我不会将上述内容归类为错误，但我认为其中几项存在误导。

在运行解析器之前对整个输入进行词法分析具有许多优点。实现各不相同，但通常来说，这种操作所需的内存并不是一个问题，特别是考虑到编译错误报告需要的信息类型。
- 优势
  - 在错误报告期间可以提供更多信息。
  - 以使词法分析在解析之前发生的方式编写的语言更容易指定和编写编译器。
- 缺点
  - 某些语言需要上下文敏感型的词法分析器，它们无法在解析阶段之前运行。
语言实现说明: 这是我的首选策略，因为它导致的代码可以分离，并且最适合将其翻译成语言的 IDE 实现。

解析器实现说明: 我尝试使用 ANTLR v3 来测试这种策略的内存开销。 C 目标使用超过每个记号 130 字节，而 Java 目标使用约 44 字节每个记号。使用修改后的 C# 目标，我表明可以完全用每个标记仅 8 字节来表示标记化的输入，使得即使针对相当大的源文件，这种策略也是实用的。

语言设计说明: 我鼓励设计新语言的人以一种允许这种解析策略的方式进行设计，无论他们最终是否选择将其用于参考编译器。
看起来您描述了一个“推”版本，类似于您在第三点中看到的“拉”解析器。我的工作重点始终是 LL 解析，所以这对我来说并不是一个真正的选择。我会惊讶地发现这方面比第 3 点还有好处，但不能排除这些好处。
这其中最具有误导性的部分是有关 C++ 的陈述。在 C++ 中正确使用迭代器使其非常适合这种类型的行为。

队列看起来像是#3的重新设计，介于两者之间。虽然在像模块化软件开发这样的领域中抽象独立操作具有许多优点，但对于一个可分发的产品提供的词法/解析器对而言，其性能敏感度非常高，这种抽象移除了关于数据结构和内存布局某些类型优化的能力。我鼓励使用选项#3。

关于多核解析的其他说明：对于单个编译单元的初始词法/解析器阶段，一般无法并行化，也不需要考虑如何简单地在不同的编译单元上运行并行编译任务（例如，在每个源文件上进行一个词法/解析器操作，并在源文件之间进行并行化，但每个给定文件只使用单个线程）。

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