首页 文章

词法分析器与解析器之间的通信

提问于
浏览 次
35

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

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

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

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

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

我的分析听起来不错？还有其他我没有想过的方法吗？什么在现实世界的编译器中使用？如果像Eric Lippert这样的编译器作者可以对这个问题有所了解，那真的很酷 .

c# c++ parsing compiler-construction lexer

5 回答

  • 11

    虽然我不会将上述大部分内容归类为错误，但我确实认为有些项目具有误导性 .

    • 在运行解析器之前记录整个输入与其他选项相比具有许多优点 . 实现方式各不相同，但一般而言，此操作所需的内存不是问题，尤其是在考虑您希望报告编译错误的信息类型时 .

    • 好处

    • 错误报告期间可用的信息可能更多 .

    • 以一种允许在解析之前发生lexing的方式编写的语言更容易指定和编写编译器 .

    • 缺点

    • 某些语言需要在解析阶段之前无法操作的上下文敏感词法分析器 .

    Language implementation note: 这是我的首选策略，因为它会产生可分离的代码，最适合转换为实现该语言的IDE .

    Parser implementation note: 我用ANTLR v3试验了这种策略的内存开销 . C目标每个令牌使用超过130个字节，Java目标每个令牌使用大约44个字节 . 通过修改的C＃目标，我展示了可以完全表示标记化输入，每个标记只有8个字节，这使得该策略对于非常大的源文件也很实用 .

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

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

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

    • 队列看起来像是中间人＃3的重演 . 虽然抽象独立操作在模块化软件开发等领域具有许多优势，但可分发产品的词法分析器/解析器对具有高度性能敏感性，而这种类型的抽象消除了对数据结构和内存布局进行某些类型优化的能力 . . 我鼓励使用选项＃3 .

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

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

    回复于
  • 4

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

    • “令牌矢量” . 此解决方案可能占用大量内存 . 想象一下，使用大量头文件编译源文件 . 存储令牌本身是不够的 . 错误消息应包含文件名和行号的上下文 . lexer可能会依赖于解析器 . 合理的例子：“>>” - 这是一个移位运算符还是关闭了2层模板实例？我会投票给这个选项 .

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

    • “沟通过程” . 这对我来说似乎有点矫枉过正 . 这种方法没有错，但也许保持简单更好？多核方面 . 编译单个文件是一种相对罕见的情况 . 我建议用自己的文件加载每个核心 .

    我没有看到将词法分析器和解析器组合在一起的其他合理选项 .

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

    回复于
  • 1

    词法分析器关系比coroutines的最常见情况简单，因为通常通信是单向的;解析器不需要将信息发送回词法分析器 . 这就是为什么渴望生成的方法有效（虽然它确实意味着您可以提前丢弃输入） .

    正如您所观察到的，如果词法分析器或解析器可以以可重新调整的样式编写，则另一个可以被视为一个简单的子例程 . 这可以始终实现为源代码转换，将局部变量转换为对象槽 .

    虽然C没有协同程序的语言支持，但可以使用库支持，特别是fibers . Unix setcontext 系列是一个选项;另一种方法是使用多线程但使用同步队列（基本上是单线程但在两个控制线程之间切换） .

    回复于
  • 2

    还要考虑＃1您不需要它的lex标记，例如，如果有错误，此外，您可能会在内存或I / O带宽上运行不足 . 我相信最好的解决方案是由Bison等工具生成的解析器，解析器调用lexer获取下一个令牌 . 最大限度地减少空间要求和内存带宽要求 .

    #4 是不值得的 . 词汇和解析本质上是同步的 - 只是没有足够的处理来证明通信成本的合理性 . 此外，通常您可以同时解析/ lex多个文件 - 这可以同时最大化所有核心 .

    回复于
  • 2

    我在我的玩具构建系统项目中处理它的方式是使用"file reader"类，函数为 bool next_token(std::string&,const std::set<char>&) . 此类包含一行输入（用于带行号的错误报告） . 该函数接受 std::string 引用以放入令牌，并接受包含"token-ending"字符的 std::set<char> . 我的输入类是解析器和词法分析器，但是如果你需要更多的功能，你可以轻松地将它拆分 . 所以解析函数只需调用 next_token 就可以完成它们的工作，包括非常详细的错误输出 .

    如果您需要保留逐字输入，则'll need to store each line that'读入 vector<string> 或其他内容，但不能单独存储每个令牌和/或双y .

    我正在谈论的代码位于：

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

    （搜索 ::next_token 和 extract_nectar 函数是从哪里开始）

    回复于

相关问题