好的，在我寻找编写编译器所需的东西的过程中，我遇到了一些障碍。似乎我发现的每一种技术或工具在某个地方都有一些反对意见。
我现在使用 Bison 和 Flex，但我感觉这种方法已经过时了。这是真的？这是继续编写完整的编程语言的一种良好的前向兼容方式吗？
在大量不同的概念和工具（ANTLR、LL(k)、GLR、LALR、LLVM、Flex、Bison）中，编写编译器的当前趋势和最佳实践是什么？龙书过时了吗？
user204416
问问题
2296 次
8 回答
30
除非您想编写一个真正简单的编译器，否则您的重点是错误的。
编写编译器只是编写解析器的一小部分。当问题是攀登珠穆朗玛峰时，拥有解析器就像攀登喜马拉雅山麓。你到达山脚的顶部并向上看……只有 20,000 英尺的距离，而你只完成了真正简单的部分。而且你会注意到到达山脚所需的技术比你需要的技术要容易得多。
（仅供参考：目前最好的解析技术是GLR，它很容易接受不明确的语法而不破坏语法。GLR 甚至可以轻松解析 C++，这违反了 C++ 难以解析的民间定理。民间定理来自尝试使用 YACC 和ANTLR 来解析它）。
要构建一个编译器，你需要很多机器：
- AST大楼
- 符号表构建
- 控制流分析
- 数据流分析
- 将程序代码表示为数据流计算（SSA 或三元组）
- 目标机器的模型
- 一种将程序代码映射到机器指令的方法
- 寄存器分配
- 优化：不断传播，循环展开，...
我们甚至还没有对涉及 SIMD 指令或缓存优化的现代指令集进行全局流分析、全局优化或特殊处理。......名单还在继续。Dragon 书很好地介绍了基本主题，但没有涉及任何高级主题。您会希望 Cooper 的“Engineering a Compiler”和 Muchnick 的“Advanced Compiler Design”作为参考，如果您在开始之前已经浏览过它们会很好。
构建现代编译器是一项工程壮举。
于 2009-11-06T03:48:26.203 回答
11
解析虽然被大量研究，但它是编译中最不重要的部分。（例外：您正在设计自己的具体语法，并且不断改进和更改语言。）
Yacc、Bison 和朋友是为具有 64K 内存的机器时代而设计的。它们非常适合在内存有限的机器上快速运行。但是今天将语法强制转换为 LALR(1) 形式所需的人工工程量是荒谬的。Ira Baxter 说得对，GLR 可能是最好、最灵活的解析技术，但 PEG（Parsing Expression Grammars）也不错。在这两种情况下，人体工程学都比旧工具早了几光年。
放弃解析后，我现在将开始另一场技术食品大战:-) 编译主要包括将程序从一种形式一遍又一遍地重写为另一种形式，直到最终达到汇编代码或机器代码。对于这类问题，您真的不想使用 C 或 C++：
问：（当 Dave Hanson 与 Chris Fraser 一起出版了关于lcc的惊人著作时被问到）“你和 Chris 花了十年时间来构建可能是有史以来最精心设计的编译器之一。你从这次经历中学到了什么？”
A：“嗯，C 是一种用于编写编译器的糟糕语言。”
我强烈建议您尝试一种流行的函数式语言，例如 Haskell 或 Standard ML。在这个领域工作的人普遍认为编译器是函数式语言的“杀手级应用”。代数数据类型和模式匹配是为将抽象语法写入中间代码和机器代码而量身定制的。了解这些技术的强大功能的一个好地方是 Andrew Appel 的书Compiling With Continuations。（Appel 的编译器教科书也很好读，设计也很优雅，但他并不总是解释为什么设计是这样的。）
于 2009-11-07T03:15:52.177 回答
7
要构建编译器，我强烈建议站在巨人的肩膀上。有很多好东西可以放在一起制作编译器。我一直在为 C/C++ 兼职编译器。它使用 GLR 进行解析，构建 AST，使用 SSA 作为其中间形式，进行过程间优化，并为 X86、ARM、MIPS、PowerPC、Sparc 等生成代码。
秘诀？我从几个来源借用了代码。
- 来自 clang 的预处理器和错误报告
- Elkhound 和 Elsa 编译器生成器和 C/C++ 编译器
- 用于优化和代码生成的 LLVM 系统
兼职工作我已经能够组装出一个非常有用的工具系统。如果我试图从头开始，我现在几乎没有完成解析器。;-)
于 2009-11-06T12:44:40.080 回答
4
我假设你和我的处境相同：你想写一个编译器是为了好玩，并且至少要了解它的每个阶段。所以你不想仅仅为现有的编译器编写一个插件。并且您希望避免使用太多现有的编译器模块，除非您可以准确了解它们在做什么。就我而言，我正在使用bison，这是一个轻微的例外，因为它至少做了一些我认为理所当然的事情（我确实在大学学习过语法等，但那是很久以前的事了）。另一方面，解析器生成器很常见，以至于它是一个值得关注的编译器阶段：bison可能会阻止我编写很多解析代码，但它让我改变了编写解析器动作代码。
与一些建议相反，我想说您可以在不了解输入和目标语言的所有信息的情况下开始。除了一些例外，以后添加语言特性并不是不可行的。我发现的一个例外是控制流：如果您编写大部分后续操作来处理树形形式，则可能难以满足诸如break、continue和之类的语句goto（甚至是结构化形式）。所以我建议在做太多之前从树转换为 CFG。
- 为输入的一些相当稳定的子集编写一个解析器。
- 添加构建有用的内存表示（通常是树）的操作，并让它打印出来。
- 让它以看起来有点像目标语言的形式打印出来。就我而言，我打印“x = y + z;”的树节点 节点为“添加 x，y，z”；"if (c) { ... }" 变成 "bz c label1"，然后翻译 "..." 然后是 "label1:"。
- 在中间添加可选阶段。这些可以是优化和/或检查阶段。您可能需要一个准备表示以方便代码生成的方法：我有一个阶段可以通过添加临时变量来减少过于复杂的表达式。（这实际上是输出所必需的，因为“ADD”指令只能用于简单的输入。）
- 回去改进它的任何部分。例如，在解析器操作中进行一些检查，以便可以在该阶段检测到错误（例如，使用未声明的变量）。
如果您采用迭代方法，完成大部分工作非常容易。
于 2009-11-07T02:49:07.780 回答
2
我无法对各种方法进行比较，但 ANTLR 小组涵盖了广泛的丰富目标语言：
其中包括大多数当前常见的。ANTLR 还支持多种输出语言。我们计划处理类似 CSS 的语言
于 2009-11-06T03:12:57.223 回答
1
有没有人认真的问过龙书会不会过时？这是开创性的工作人。我无法告诉你我从前两章中学到了多少（因为我已经忘记了……ba-dum-bum）。
每种技术（可能除了 goto 语句）都有批评者和支持者。不要沉迷于“做出正确的工具选择”，而是全力以赴地学习概念并以有意义的方式实施它们。我的意思是，即使你选择了世界上最完美的工具，你认为你会像现在的 FORTRAN 一样构建出像 FORTRAN 一样被爱、被崇拜和被尊重的东西……我的意思是我们喜欢它……对吗？
当然不是人......这么多的学习来自犯错误。那是你学得最多的地方。
你能行的！
于 2009-11-06T03:21:41.200 回答
1
Flex 和 Bison 并没有什么问题，但是如果您正在寻找更新的（和面向对象的）东西，您可以考虑使用boost 的 Spirit 库。
于 2009-11-06T03:07:25.720 回答
1
这是因为 1) 一个极端的大型现有语言，如 Java 或 C++，还是 2) 一种没有花哨数据类型的小语言？
如果是 1，您最好了解 Ira 提到的所有技术。
如果是 2，如果您只编写一个递归下降解析器，并且 a) 在解析时将其翻译成您最喜欢的语言 (YFL)，或者 b) 构建符号表和解析树，您就可以立即完成，然后步行生成 YFL。如果您不想生成 YFL，只需编写一个遍历解析树的解释器即可。
如果你的目标是学习所有棘手的技术，那就去做吧。如果不是，那么快速而肮脏是要走的路。如果是后者，不要担心优化！
顺便说一句，如果您想快速入门，并且您拥有 C 或 C++，并且您对编写宏不太自豪，那么创建一种语言的简单方法就是编写一组宏。这样您就可以创建自己的语句，同时利用底层语言的数据类型、表达式语法、效率和运行时库。
于 2009-11-25T04:54:23.530 回答