22

使用 lex/yacc 编写 C++ 编译器需要多少时间？

我可以从哪里开始？

4

13 回答 13

23

有许多解析规则无法被 bison/yacc 解析器解析（例如，在某些情况下区分声明和函数调用）。此外，有时对标记的解释需要来自解析器的输入，尤其是在 C++0x 中。例如，字符序列的处理>>关键取决于解析上下文。

这两个工具对于解析 C++ 来说是非常糟糕的选择，为了正确解析 C++，您必须放入许多超出这些工具所依赖的基本框架的特殊情况。这将花费您很长时间，即使那样您的解析器也可能会出现奇怪的错误。

yacc 和 bison 是LALR(1)解析器生成器，它们不够复杂，无法有效处理 C++。正如其他人所指出的那样，大多数 C++ 编译器现在都使用递归下降解析器，并且其他几个答案指出了编写自己的解决方案的好方法。

C++ 模板不适合处理字符串，甚至是常量字符串（尽管这可能在 C++0x 中已修复，我没有仔细研究过），但如果是这样，您可以很容易地在 C++ 模板中编写递归下降解析器语。我觉得这很有趣。

于 2009-12-25T18:18:58.217 回答
10

这可能会花费您数年时间，并且您可能会在此过程中切换到其他一些解析器生成器。

解析 C++ 是出了名的容易出错。该语法不是完全可 LR 解析的，因为许多部分是上下文相关的。你将无法让它在 flex/yacc 中正常工作，或者至少实现起来会很尴尬。据我所知，只有两个前端可以做到这一点。您最好的选择是使用其中之一并专注于编写后端。无论如何，这就是有趣的地方:-)。

现有的 C++ 前端：

  1. 大多数商业供应商（英特尔、波特兰集团等）在其编译器中使用EDG 前端。花钱，但是很彻底。人们为此付出了高昂的代价，因为他们不想承受编写自己的 C++ 解析器的痛苦。

  2. GCC 的 C++ 前端对于生产代码来说已经足够完善了，但是你必须弄清楚如何将它集成到你的项目中。我相信将它与 GCC 分开是相当复杂的。这也是 GPL，但我不确定这对你来说是否有问题。您可以通过gcc_xml在项目中使用 GCC 前端，但这只会为您提供类、函数、命名空间和 typedef 的 XML。它不会为您提供代码的语法树。

  3. 另一种可能性是使用clang，但他们的 C++ 支持目前参差不齐。很高兴看到他们解决了所有的错误，但是如果您查看他们的C++ 状态页面，您会发现仍有不少测试用例无法解决。注意——clang 是一个大项目。如果这些人要花几年时间来实现一个 C++ 前端，那你会花更长的时间。

  4. 其他人提到了ANTLR，并且有可用的 C++ 语法，但我持怀疑态度。我还没有听说过任何主要编译器中使用了 ANTLR 前端，但我相信它已在 NetBeans IDE 中使用。它可能适用于 IDE，但我怀疑您能否在生产代码中使用它。

于 2009-12-25T19:08:44.133 回答
10

听起来您对解析/编译器创建很陌生。如果是这种情况，我强烈建议不要从 C++ 开始。这是一种语言的怪物。

要么发明一种你自己的简单的玩具语言，要么做一些以更小更简单的东西为模型的东西。我看到一个 lua 解析器，其中语法定义大约有一页长。作为起点，这会更合理。

于 2009-12-25T19:20:21.870 回答
6

很长一段时间，lex 和 yacc 无济于事

如果您有能力为如此庞大的语言编写编译器，您将不需要 lex 和 yacc 为您提供的少量帮助。事实上，虽然 lex 没问题，但使用 yacc 可能需要更长的时间，因为它对于 C 或 C++ 来说还不够强大，而且你最终可能会花费更多的时间让它正常工作，而不是仅仅编写一个递归下降解析器。

我相信 lex 和 yacc 最适合用于简单的语法，或者当值得付出额外努力来拥有一个可读性好的语法文件时，可能是因为语法是实验性的并且可能会发生变化。

就此而言，整个解析器可能不是您工作的主要部分，具体取决于您对代码生成器的目标。

于 2009-12-25T18:24:09.987 回答
4

正如其他人已经说过的，yacc 是实现 C++解析器的糟糕选择。一个人可以做到；在 GCC 团队对维护和扩展的难度感到反感之前，原始的 GCC 就这样做了。（Flex 作为词法分析器可能没问题）。

有人说递归下降解析器是最好的，因为 Bjarne Stroustrop 是这么说的。我们的经验是 GLR 解析是解决这个问题的正确答案，我们基于 GLR 的 C++ 前端就是一个很好的证明，Elsa 前端也是如此。我们的前端已经在数百万行 C++（包括微软和 GCC 方言）上进行了程序分析和海量源代码转换。

但没有得到足够强调的是，解析只是构建编译器所需的一小部分，尤其是对于 C++。您还需要构建符号表（“此标识符在此上下文中的含义是什么？”），为此您需要对数百页 C++ 标准的大部分内容进行编码。我们相信，我们构建类似编译器的工具DMS的基础非常适合执行此操作，并且我们花了一个人年的时间才将这部分做好。

但是你需要考虑编译器的其余部分：

  • 预处理器
  • AST 建设
  • 语义分析和类型检查
  • 控制、数据流和指针分析
  • 基本代码生成
  • 优化
  • 寄存器分配
  • 最终代码生成
  • 调试支持

我一直在说：为一种语言构建解析器（BNF 部分）就像攀登喜马拉雅山的山脚。构建一个完整的编译器就像攀登珠穆朗玛峰。几乎任何 clod 都可以做到前者（尽管 C++ 就在边缘）。只有真正认真的人才会做后者，而且只有在准备充分的情况下。

预计构建 C++ 编译器会花费您数年时间。

（SD C++ 前端处理主要 C++ 方言的词法分析、解析、AST 生成、符号表、一些类型检查和从 AST 重新生成可编译源文本，包括原始注释。它已经开发了一段时间大约 6 年）。

编辑：2015 年 5 月。原始答案写于 2010 年；我们现在已经投入了 11 年，从 C++14 开始。关键是要构建其中的一个是无止境的、巨大的努力。

于 2010-01-24T11:13:03.527 回答
3

首先，SO 上的“flex”标签是关于 Adob​​e 的产品，而不是词法分析器生成器。其次，Bjarne Stroustrup 公开表示他希望他使用递归下降而不是表驱动工具来实现 Cfront（第一个 C++ 编译器）。第三，直接回答你的问题——很多。如果你觉得你需要写一个，看看ANTLR——不是我最喜欢的工具，但已经有 C++ 解析器了。

于 2009-12-25T18:05:13.393 回答
3

这是一个不平凡的问题，并且需要相当多的时间才能正确完成。一方面，C++ 的语法不能被LALR 解析器（如 yacc）完全解析。你可以做语言的子集，但是让整个语言规范正确是很棘手的。

你不是第一个认为这很有趣的人。这是一篇关于该主题的不错的博客风格文章： Parsing C++

这是这篇文章的重要引述：

“经过大量调查，我认为为 C++ 编写解析器/分析工具非常困难，超出了我的爱好。”

那篇文章的问题是它有点旧，而且有几个链接坏了。以下是一些关于编写 C++ 解析器主题的其他资源的链接：

于 2009-12-25T18:24:42.940 回答
2

Lex,yacc 是不够的。你需要一个链接器，也需要一个汇编器......，c预处理器。这取决于你怎么做。您打算使用多少预制组件？您需要从某个地方获取语法及其标记的描述。

例如，如果您使用 LLVM，则可以更快地进行。它已经提供了很多工具，汇编器、链接器、优化器……你可以从 boost 项目中获得 ac 预处理器。你需要创建一个测试套件来自动测试你的编译器。

如果你每天都在努力，可能需要一年的时间，或者更少你有更多的天赋和动力。

于 2009-12-25T18:05:56.887 回答
2

几年——如果你能获得研究资助来重写新的 lex/yacc :-)

人们一直在追逐他们的尾巴——从 Stroustrup 开始，他总是幻想成为语言“设计师”而不是真正的编译器编写者（请记住，他的 C++ 多年来只是一个代码生成器，如果不是 gcc，它仍然会存在和其他人）。

核心问题是，自从 CPU-s 变得足够快以处理函数式语言和暴力递归下降以来，对解析器生成器的真正研究几乎不复存在。当您不知道该做什么时，递归下降是最后的手段——它会进行详尽的搜索，直到找到一个触发的“规则”。一旦你对此感到满意，你就会对研究如何有效地做到这一点失去兴趣。

你本质上需要的是一个合理的中间立场——比如 LALR(2) 具有固定的、有限的回溯（加上静态检查器，如果“设计者”挥霍到一个不确定的树中）以及有限和分区的符号表反馈（现代解析器需要对并发友好）。

听起来像是一项研究资助计划，不是吗:-) 现在，如果我们能找到真正资助它的人，那将是 :-))

于 2010-08-07T21:18:00.680 回答
2

除非您已经编写了其他几个编译器；C++ 不是你甚至想从头开始编写编译器的语言，该语言有很多地方的含义需要很多上下文才能消除歧义。

即使你有很多编写编译器的经验，你也会为一个开发团队寻找几年的时间。这只是为了将代码正确解析为中间格式。编写后端以生成代码是另一项专门的任务（尽管您可以窃取 gcc 后端）。

如果你在谷歌上搜索“C++ 语法”，有几个可以帮助你入门。

C++ LEX  Tokens:   http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxLexer.l
C++ YACC Grammer:  http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxGrammar.y
                   http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxTester.y
于 2009-12-25T21:06:06.080 回答
1

C++ 编译器非常复杂。要实现足够多的 C++ 以与大多数 C++ 代码兼容，需要几个开发人员的全部时间。clang是一个由 Apple 资助的编译器项目，旨在为 C、C++ 和 Objective-C 开发新的编译器，有几个全职开发人员，经过几年的开发，对C++ 的支持还远未完成。

于 2009-12-25T18:21:20.770 回答
0

那么，编写编译器是什么意思？

我怀疑是否有人制作了一个真正的 C++ 编译器，将其一直分解为汇编代码，但我使用 lex 和 yacc 制作了一个 C 编译器，但我没有这样做。

使用这两种方法，您可以在几天内创建一个忽略语义的编译器，但弄清楚如何使用它们可能需要数周或数月的时间。无论如何，弄清楚如何制作一个编译器都需要几周或几个月的时间，但我记得的数字是，一旦你知道它是如何工作的，使用 lex 和 yacc 需要几天，而没有使用则需要几周，但第二个效果更好并且错误更少，因此真的值得怀疑它们是否值得使用。

“语义”是实际的代码生产。这可以是非常简单的代码，足以工作并且可能根本不需要很长时间，或者你可以花费你的一生来优化它。

对于 C++，最大的问题是模板，但是有很多小问题和规则，我无法想象有人想要这样做。即使你完成了，问题是你不一定具有二进制兼容性，即能够被链接器或操作系统识别为可运行的程序，因为它不仅仅是 C++，而且很难确定标准，但有还有更多标准需要担心，这些标准更不普及。

于 2009-12-27T10:27:53.993 回答
0

递归体面是解析 C++ 的不错选择。GCC 和 clang 使用它。

Elsa 解析器（和我的 ellcc 编译器）使用 Elkhound GLR 编译器生成器。

无论哪种情况，编写 C++ 编译器都是一项艰巨的工作。

于 2009-12-25T18:07:54.277 回答