大多数编译器具有以下架构：
在本文中，我将逐个要素详细剖析该体系结构。
我们可以说本文是对编译器主题的大量现有资源的补充。 它是一种自治资源，可让您了解编程语言的设计和实现基础。
本文的目标读者是对编译器工作的想法极为有限的人（最大程度是他们参与编译）。 但是，我希望读者能理解数据结构和算法。
本文决不是专门针对具有数百万行代码的现代生产编译器的，不，这是一门简短的课程“傻瓜编译器”，有助于理解编译器是什么。
引言
我目前正在研究受Rust和Go启发的
Krug系统语言。 在本文中，我将以克鲁格为例来说明我的想法。 Krug正在开发中，但已经在
caasper和
krug存储库中的
https://github.com/krug-lang上可用。 与通常的编译器体系结构相比，该语言不是很典型，后者在一定程度上激发了我写一篇文章的知识，但稍后会介绍更多。
我赶紧通知您，我绝对不是编译器专家！ 我没有博士学位，也没有接受任何正式的培训-我在业余时间自己研究了本文中描述的所有内容。 我还必须说，我不是在描述创建编译器的实际的，唯一的真实方法，而是要介绍适用于创建小型“玩具”编译器的基本方法。
前端
让我们回到上面的图：指向前端字段的左侧箭头是众所周知的并且喜欢的语言，例如C。前端看起来像这样：词法分析->解析器。
词法分析
当我开始研究编译器和语言设计时，被告知词法分析与标记化相同。 我们将使用此描述。 分析器以字符串或字符流的形式获取输入数据，并识别其中的模式，并将其切成标记。
对于编译器，它在输入处接收一个编写的程序。 从文件中将其读取为字符串，然后分析器标记其源代码。
enum TokenType { Identifier, Number, }; struct Token { std::string Lexeme; TokenType type; // ... // It's also handy to store things in here // like the position of the token (start to end row:col) };
在以C形语言编写的此片段中，您可以看到包含上述词素的结构以及用于识别此令牌的TokenType。
注意：本文并不是有关使用示例创建语言的说明-但为了更好地理解，我将不时插入代码段。
分析器通常是最简单的编译器组件。 实际上，与其余拼图相比，整个前端非常简单。 尽管这在很大程度上取决于您的工作。
采取以下C代码：
int main() { printf("Hello world!\n"); return 0; }
从文件读取它到一行并执行线性扫描后，您也许可以切片令牌。 我们以一种自然的方式识别标记-看到int是一个“单词”，而return语句中的0是一个“数字”。 词法分析器执行与我们相同的过程-稍后我们将更详细地检查此过程。 例如，分析数字：
0xdeadbeef — HexNumber ( ) 1231234234 — WholeNumber ( ) 3.1412 — FloatingNumber ( ) 55.5555 — FloatingNumber ( ) 0b0001 — BinaryNumber ( )
定义单词可能很困难。 大多数语言将单词定义为字母和数字的序列，标识符通常应以字母或下划线开头。 例如：
123foobar := 3 person-age := 5 fmt.Println(123foobar)
在Go中，此代码将不被认为是正确的，并将被解析为以下标记：
Number(123), Identifier(foobar), Symbol(:=), Number(3) ...
遇到的大多数标识符如下所示：
foo_bar __uint8_t fooBar123
分析人员将不得不解决其他问题，例如空格，多行和单行注释，标识符，数字，数字系统和数字格式（例如1_000_000）和编码（例如，支持UTF8而不是ASCII）。
如果您认为可以使用正则表达式-最好不要这样做。 从零开始编写分析器要容易得多，但是我强烈建议您从我们的国王和上帝罗布·派克那里阅读
这篇文章 。 正则表达式不适用于我们的原因在其他许多文章中都有介绍，因此我将忽略这一点。 此外，编写分析器比早上5:24上传到regex101.com的冗长冗长的表达式折磨自己要有趣得多。 在我的第一种语言中，我使用了
split(str)函数进行标记化-而且我走得很远。
解析中
解析比词法分析要复杂得多。 解析器和解析器生成器很多-游戏在这里以很大的方式开始。
编译器中的解析器通常以令牌形式获取输入并构建特定的树-抽象语法树或解析树。 从本质上讲，它们是相似的，但有一些区别。
这些阶段可以表示为功能：
fn lex(string input) []Token {...} fn parse(tokens []Token) AST {...} let input = "int main() { return 0; }"; let tokens = lex(input); let parse_tree = parse(tokens); // ....
通常，编译器是由许多小的组件构成的，这些组件接受输入，更改输入或将它们转换为不同的输出。 这是功能语言非常适合创建编译器的原因之一。 其他原因是出色的基准测试和相当广泛的标准库。 有趣的事实：
Rust编译器的第一个实现是在Ocaml上。
我建议您将这些组件保持尽可能简单和自治-模块化将大大简化此过程。 我认为，软件开发的许多其他方面也可以这样说。
树木
解析树
这到底是什么？ 也称为解析树，此厚树用于可视化源程序。 它们包含有关输入程序的所有信息（或大部分信息），通常与您的语言语法中描述的信息相同。 每个树节点都将是尾随的或不可尾随的，例如NumberConstant或StringConstant。
抽象语法树
顾名思义，ASD是
抽象语法树。 解析树包含有关您的程序的许多（通常是冗余的）信息，对于ASD，则不是必需的。 ASD不需要有关结构和语法的无用信息，这不会影响程序的语义。
假设您的树具有（（5 + 5）-3）+2这样的表达式。 在解析树中，您将完整地将其与括号，运算符和值5、5、3和2一起存储。但是，您可以简单地与ASD关联-我们只需要知道值，运算符及其顺序即可。
下图显示了表达式a + b / c的树。
ASD可以表示如下：
interface Expression { ... }; struct UnaryExpression { Expression value; char op; }; struct BinaryExpression { Expression lhand, rhand; string op; // string because the op could be more than 1 char. }; interface Node { ... }; // or for something like a variable struct Variable : Node { Token identifier; Expression value; };
该视图非常有限，但是我希望您能看到节点的结构。 要进行解析，可以采用以下过程：
Node parseNode() { Token current = consume(); switch (current.lexeme) { case "var": return parseVariableNode(); // ... } panic("unrecognized input!"); } Node n = parseNode(); if (n != null) { // append to some list of top level nodes? // or append to a block of nodes! }
我希望您能从高级语言构造入手，了解如何逐步进行其余节点的解析。 如何精确实现具有递归下降的解析器，您需要学习一下自己。
文法
从一组令牌中解析ADS可能很困难。 通常，您应该从语言语法入手。 本质上，语法决定语言的结构。 有几种用于定义可以描述（或解析）自身的语言的语言。
用于确定语言的语言的示例是
Backus-Naur （RBNF）的
扩展形式 。 这是
BNF的变体，带有较少的尖括号。 这是来自维基百科文章的RBNF示例：
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; digit = "0" | digit excluding zero ;
定义了生产规则：它们指示哪个终端模板是“非终端”的。 终端是字母的一部分，例如，上例中的if标记或0和1是终端。 非终结符是相反的，它们位于生产规则的左侧，可以将它们视为指向终端和非终结点组的变量或“命名指针”。
许多语言都有包含语法的规范。 例如，对于
Go ，
Rust和
D。递归下降分析仪
递归下降是许多解析方法中最简单的。
递归下降分析器-基于递归过程的下降。 编写解析器要容易得多，因为语法没有
左递归 。 在大多数“玩具”语言中，此技术足以解析。 尽管以前使用YACC，但GCC使用手写的降序解析器。
但是，解析这些语言可能会导致问题。 特别是C，其中
foo * bar
可以解释为
int foo = 3; int bar = 4; foo * bar; // unused expression
或如何
typedef struct { int b; } foo; foo* bar; bar.b = 3;
Clang实现还使用递归下降分析器：
由于这是常规的C ++代码，因此递归下降使初学者更容易理解它。 它支持C / C ++所需的自定义规则和其他奇怪的东西，并帮助您轻松诊断和修复错误。还值得关注其他方法：
解析器生成器
另一个好方法。 当然，也有缺点-但这可以说是程序员在创建软件时所做的任何其他选择。
解析器生成器非常快地工作。 比起编写自己的分析仪并获得质量结果，使用它们要容易得多-尽管它们并不十分用户友好，并且并不总是显示错误消息。 另外，您将必须学习如何使用解析器生成器，并且在升级编译器时，可能必须解散解析器生成器。
解析器生成器的一个示例是
ANTLR ，还有很多其他的。
我认为该工具适合那些不想花时间编写前端的人，并且更愿意编写编译器/解释器的中间和后端并分析任何内容的人。
解析应用
如果您仍然不了解自己。 甚至编译器前端（lex / parse）也可以用来解决其他问题：
- 语法高亮
- 用于渲染引擎的HTML / CSS解析
- 编译器：TypeScript，CoffeeScript
- 连接器
- 正则表达式
- 界面数据分析
- URL解析
- 格式工具，例如gofmt
- SQL解析等等。
中端
语义分析！ 创建编译器时，语言语义分析是最困难的任务之一。
您需要确保所有输入程序都能正常工作。 在我的Krug语言中，还没有包括与语义分析有关的方面，如果没有它，将始终要求程序员编写正确的代码。 实际上，这是不可能的-我们总是编写，编译，有时运行，纠正错误。 这种螺旋是无止境的。
此外，如果不在适当的编译阶段分析语义的正确性，就不可能编译程序。
我曾经遇到一张有关前端，中端和后端百分比的图表。 然后看起来像
F: 20% M: 20%: B: 60%
今天就像
F: 5% M: 60% B: 35%
前端主要与生成器有关，在不具有语法二元性的无上下文语言中，它们可以很快完成-递归下降将在这里提供帮助。
借助LLVM技术，大多数优化工作都可以上载到框架中，从而提供了许多现成的优化方法。
下一步是语义分析，这是编译阶段的重要部分。
例如，在Rust中，借助其内存管理模型，编译器可充当强大的大型计算机，对入门表格执行各种类型的静态分析。 此任务的一部分是将输入数据转换成更方便的形式以进行分析。
因此，语义分析在编译器的体系结构中起着重要的作用，并且为您完成了各种准备工作，例如优化生成的程序集或读取ASD中的输入数据。
语义通道
在语义分析的过程中，大多数编译器对SDA或其他抽象形式的代码表达进行大量的“语义传递”。
本文提供有关.NET C＃编译器进行的大多数传递的详细信息。
我不会考虑每个段落，特别是因为它们会因语言而异，但是下面在Krug中介绍了几个步骤。
顶级广告
编译器将遍历模块中的所有“顶级”公告，并意识到它们的存在。 他不会深入探讨块-他只会声明哪些结构，功能等。 在一个或另一个模块中可用。
名称/符号解析
编译器将遍历函数中所有的代码块，等等。 并解决它们-即找到需要许可的字符。 这是一个常见的过程，正是从这里开始，在编译Go代码时通常
不会出现此类符号XYZ错误。
执行此过程可能非常困难，尤其是在依赖关系图中存在循环依赖关系的情况下。 某些语言不允许使用这些语言，例如，如果您的其中一个软件包形成循环，Go会抛出错误，例如我的Krug语言。 循环依赖性可以被认为是不良体系结构的副作用。
可以通过在依赖关系图中修改DFS来确定循环，也可以使用
Tarjan算法 （由Krug完成）来定义（多个）循环。
类型推断
编译器将遍历所有变量并显示其类型。 Krug中的类型推断非常弱；它仅根据变量的值输出变量。 这绝不是一个奇怪的系统，就像您可以在Haskell这样的功能语言中找到的系统一样。
类型可以使用“统一”过程或“类型统一”来派生。 对于更简单的系统，可以使用非常简单的实现。
类型是在Krug中实现的，如下所示：
interface Type {}; struct IntegerType : Type { int width; bool signed; }; struct FloatingType : Type { int width; }; struct ArrayType : Type { Type base_type; uint64 length; };
您还可以进行简单的类型推断，即在其中将类型分配给表达式节点，例如，
IntegerConstantNode可以是IntegerType（64）类型。 然后，您可能会得到
unify(t1, t2)函数，该函数将选择最宽的类型，该类型可用于推导更复杂的表达式的类型，例如二进制表达式。 因此，需要在左侧将变量分配给右侧的给定类型的值。
我曾经在Go上编写过一个简单的
类型转换 ，它成为Krug的原型实现。
变异通行证
默认情况下，Krug（如Rust）是一种不可变的语言，也就是说，除非另有说明，否则变量将保持不变：
let x = 3; x = 4; // BAD! mut y = 5; y = 6; // OK!
编译器遍历所有块和函数，并检查其“变量正确”，即，我们不更改未遵循的内容，并且传递给某些函数的所有变量在需要时都是恒定的或可变的。
这是借助先前遍历中收集的符号信息来完成的。 基于语义传递结果的符号表包含令牌名称和变量可变性的符号。 它可能包含其他数据，例如，在C ++中，表可以存储有关符号是外部符号还是静态符号的信息。
角色表
字符表或“ stab”是用于查找程序中使用的字符的表。 为每个作用域创建一个表，并且所有表都包含有关特定作用域中存在的字符的信息。
此信息包括符号名称，类型，可变性的符号，外部通信的存在，静态存储器中的位置等属性。
适用范围
这是编程语言中的重要概念。 当然，您的语言并不一定要创建嵌套的作用域，所有内容都可以放在一个通用的命名空间中！
尽管表示范围对于编译器体系结构是一项有趣的任务，但是在大多数类似于C的语言中，范围的行为（或确实）类似于堆栈数据结构。
通常，我们创建和销毁作用域，并且它们通常用于管理名称，也就是说，它们使我们能够隐藏（隐藏）变量：
{ // push scope let x = 3; { // push scope let x = 4; // OK! } // pop scope } // pop scope
可以用不同的方式表示：
struct Scope { Scope* outer; SymbolTable symbols; }
有点小题外话，但我建议阅读有关
意大利面条堆栈的信息 。 这是一种数据结构，用于在相对块的ASD节点中存储可见性区域。
类型系统
下面的许多部分可以分解为单独的文章，但在我看来，这个标题应该得到最大的支持。 如今，有关类型系统以及系统本身的变体的大量信息可用，许多副本都围绕这些信息而破裂。 我不会
深入探讨这个主题，只留下与
Steve Klabnik的
精彩文章的链接 。
类型系统是使用编译器表示形式和对这些表示形式的分析在编译器中提供并在语义上定义的。
拥有
这个概念越来越多地用于编程中。 所有权和移动语义的原理已嵌入
Rust语言中，我希望它们会以其他语言出现。 Rust执行许多不同类型的静态分析，这些分析检查输入是否满足有关内存的一组规则：谁拥有哪个内存，何时销毁内存以及对这些值或内存存在多少引用（或借用）。
Rust的优点在于，所有这些都是在编译期间在编译器内部完成的，因此程序员不必处理垃圾回收或链接计数。 所有这些语义都分配给类型系统，甚至可以在以完整二进制文件的形式呈现程序之前就可以提供所有这些语义。
我不能说这一切是如何进行的，但这都是Mozilla团队和
Cyclone项目参与者进行静态分析和出色研究的结果。
控制流程图
为了表示程序流，我们使用控制流图（CFG），其中包含程序执行可以遵循的所有路径。 在语义分析中使用它来排除代码的空闲部分，即程序执行期间将永远无法实现的块，函数甚至模块。 图形还可以用于识别不能中断的循环。 或搜索无法访问的代码，例如，当您调用“紧急事件”（称为紧急事件）或在循环中返回而循环外的代码不执行时。
数据流分析在编译器的语义阶段起着重要的作用，因此，我建议阅读有关您可以执行的分析类型，其工作方式以及优化工作的信息。
后端
我们的架构方案的最后一部分。我们已经完成了生成可执行二进制文件的大部分工作。 这可以通过多种方式完成，我们将在下面讨论。
- , . , , «».
, . , , . , , , . , .
, . , ++ — Cfront — C.
JavaScript. TypeScript , , , , .
«» , , , , « » . — , , .
LLVM
LLVM: Rust, Swift, C/C++ (clang), D, Haskell.
« », , . , LLVM . , . , , , , 1, 4, 8 16-. , , - .
-
— , — , .
Go — , LLVM ( ). Go , Windows, Linux MacOS. , Krug -.
. , LLVM, , , LLVM , .
, , , LLVM, IR, , , , ( ).
. , , , . IR ( ) «» fprintf .
8cc .
. — Java: ,
JVM , , Kotlin.
, Java . , . , .
, JVM JIT , JIT-, .
, ! , , . - , , .
Godbolt — , , . , , .
, , (strip the debug symbols), , GCC. , - .
. . , . production-.
rwmj , 8 , 80% . 1971-!
, Rust.
IR
(intermediate representation, IR) , . , , .
IR . , , , .
IR, «», IR . , SSA — Static Single Assignment, , .
Go IR SSA. IR LLVM SSA, .
SSA , , (constant propagation), ( ) .
, . , , , , . ( 16 32), , (spill to the stack).
— ( ). , , .
:
- (graph colouring) — (NP- ). , (liveness ranges) .
- — .
. , . , , .
-, , . , .
fn main() int { let x = 0; { let x = 0; { let x = 0; } } return 0; }
, ( - :) ) , . , .
LLDB
DWARF . LLVM , DWARF GNU-. , , , .
(Foreign Function Interface, FFI )
libc , , . , ?
— . , ( .s/.asm)? ? ,
Jai . , .
(CaaS)
API-. , Krug-, . , , .
, , , . , API-.
production- CaaS. Microsofts Roslyn, , . , , , , API-, , , Rust
RLS .
Krug — — Caasper CaaS-.
Caasper (, , ), , krug, . , , (bootstrap) , .
Krug JavaScript, Go*, , , Krug. JavaScript , yarn/npm.
* Go () , JS.Caasper
.
Github Krug, D LLVM. YouTube-
.
Krug ()
.
有用的链接