如何编写一个非常基本的编译器

#1 楼

简介
典型的编译器执行以下步骤：

解析：将源文本转换为抽象语法树（AST）。
对其他模块的引用的解析（C推迟）此步骤直到链接为止。）
语义验证：清除语法上无意义的正确语句，例如无法访问的代码或重复的声明。
等效转换和高级优化：AST被转换为表示具有相同语义的更有效的计算。这包括早期计算公共子表达式和常量表达式，消除了过多的局部分配（另请参见SSA）等。代码生成：AST被转换为具有跳转，寄存器分配等功能的线性低级代码。在此阶段可以内联一些函数调用，展开某些循环，等等。
窥孔优化：扫描低级代码以查找简单的本地效率低下的现象。

大多数现代编译器（例如gcc和clang）再次重复最后两个步骤。他们使用中间的低级但与平台无关的语言来生成初始代码。然后，将该语言转换为平台特定的代码（x86，ARM等），并以平台优化的方式做大致相同的事情。这包括在可能的情况下使用矢量指令，对指令重新排序以提高分支预测效率，等等。
之后，目标代码就可以链接了。大多数本机代码编译器都知道如何调用链接器以生成可执行文件，但这本身不是编译步骤。在Java和C＃之类的语言中，链接可能是完全动态的，由VM在加载时完成。
请记住基础知识

使它起作用
使它美观
使高效

此经典序列适用于所有软件开发，但具有重复性。
专注于序列的第一步。创建可能可行的最简单的方法。
阅读书籍！
阅读Aho和Ullman撰写的Dragon Book。这是经典之作，并且在今天仍然很适用。
现代编译器设计也受到称赞。
如果现在对您来说这东西太难了，请先阅读一些解析的介绍。通常，解析库包括简介和示例。
请确保您习惯使用图，尤其是树。这些东西是程序在逻辑级别上构成的。
定义好您的语言
使用所需的任何符号，但要确保对语言有完整且一致的描述。这包括语法和语义。
现在是时候用新语言编写代码片段作为将来的编译器的测试用例了。
使用您喜欢的语言
编写编译器完全可以用Python或Ruby或任何您喜欢的语言。使用简单的算法，您会很好理解。第一个版本不必快速，高效或功能完善。它只需要足够正确并且易于修改。
如果需要，可以用不同的语言编写编译器的不同阶段。
准备编写很多测试
测试用例应涵盖语言；有效地，它将由他们来定义。熟悉您首选的测试框架。从第一天开始编写测试。专注于接受正确代码的“积极”测试，而不是检测错误代码。
定期运行所有测试。在继续之前，请修复损坏的测试。最终以不正确的语言接受不可接受的有效代码而感到遗憾。
创建一个好的解析器
解析器生成器很多。选择任何你想要的。您也可以从头开始编写自己的解析器，但是仅当您的语言语法简直简单时才值得。
解析器应检测并报告语法错误。编写很多测试用例，包括正面和负面的；重用您在定义语言时编写的代码。
解析器的输出是一个抽象的语法树。
如果您的语言具有模块，则解析器的输出可能是“目标代码”的最简单表示。生成。有很多简单的方法可以将树转储到文件中并快速将其重新加载。
创建语义验证器
您的语言很可能允许语法正确的构造，在某些情况下可能没有意义。一个示例是相同变量的重复声明或传递错误类型的参数。验证器将在树上检测到此类错误。
验证器还将解析对使用您的语言编写的其他模块的引用，加载这些其他模块并在验证过程中使用。例如，此步骤将确保从另一个模块传递给函数的参数数量正确。
再次编写，运行许多测试用例。在故障诊断中，平凡的案例是必不可少的，既聪明又复杂。
生成代码
使用您已知的最简单的技术。通常，直接将语言结构（如if语句）转换为参数化的代码模板（与HTML模板不同）是可以的。
再次，忽略效率并专注于正确性。
以平台为目标-独立的低级虚拟机
我想除非您对特定于硬件的细节非常感兴趣，否则您将忽略低级内容。这些细节是复杂的。
您的选择：

LLVM：允许高效的机器代码生成，通常用于x86和ARM。
CLR：目标.NET，多平台；具有良好的JIT。
JVM：面向Java世界，相当多平台，具有良好的JIT。

忽略优化
优化很难。优化几乎总是过早的。
生成效率低下但正确的代码。在尝试优化结果代码之前，请先实现整个语言。
当然，可以引入琐碎的优化。但是，在编译器稳定之前，请避免使用任何狡猾多毛的东西。
那又如何？
如果所有这些东西对您来说都不是太吓人，请继续！对于简单的语言，每个步骤可能比您想象的要简单。
从编译器创建的程序中看到“ Hello world”可能是值得的。

#2 楼

Jack Crenshaw的“让我们构建一个编译器”虽然未完成，但它是引人注目的可读性介绍和教程。

Nicklaus Wirth的“ Compiler Construction”是一本很好的关于简单编译器构建基础的教科书。他专注于自上而下的递归下降，让我们面对现实，这比lex / yacc或flex / bison更容易。他的小组编写的原始PASCAL编译器是通过这种方式完成的。

其他人提到了各种Dragon书籍。

#3 楼

如果您真的只想写机器可读的代码，而不是针对虚拟机，那么您将必须阅读Intel手册并了解


a。链接和加载可执行代码
b。 COFF和PE格式（适用于Windows），或者了解ELF
格式（适用于Linux）
c。了解.COM文件格式（比PE更容易）
d。了解汇编器
e。了解编译器和编译器中的代码生成引擎。

比说的难得多。我建议您阅读C ++的编译器和解释器作为起点（作者Ronald Mak）。另外，也可以使用Crenshaw的“让我们构建编译器”。

如果您不想这样做，您也可以编写自己的VM并编写针对该VM的代码生成器。


另一个起点：
http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/

肯尼思·劳登的好书：
http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724


提示：学习Flex和Bison首先。然后继续构建自己的编译器/ VM。

祝你好运！

#4 楼

我实际上是从为Brainfuck编写编译器开始的。这是一种相当晦涩难懂的语言，但是只有8条指令可以实现。它尽可能地简单，并且如果发现语法不正确，则其中包含等效的C指令，其中涉及的命令。

#5 楼

简单编译器的DIY方法可能如下所示（至少这就是我的uni项目的外观）：


定义语言的语法。上下文无关。
如果您的语法还不是LL（1），请立即执行。请注意，在普通CF语法中看起来不错的一些规则可能看起来很丑。也许您的语言太复杂了。
编写Lexer，它将文本流切成标记（单词，数字，文字）。
为您的语法编写自上而下的递归下降解析器，该解析器接受或拒绝输入。
将语法树生成添加到解析器中。
从语法树中编写机器代码生成器。
Profit＆Beer，或者您可以开始思考如何做更聪明的解析器或生成更好的代码。

应该有大量的文献详细描述每个步骤。