“Compiler”的版本间差异

来自osdev
跳到导航 跳到搜索
 
(未显示同一用户的1个中间版本)
第1行: 第1行:
编译器是将来源编程语言中的代码翻译成目标编程语言的程序。 通常,目标编程语言的级别低于来源编程语言 - 编译器的目标语言有C、字节码、汇编或原始机器代码。
{{Template:In_Progress}}


出现语言以另一种高级语言(如C)为目标的一个原因是,编译器可以完全专注于翻译语言,而同时获得所有世界级C编译器高产品质量的优化。 对于动态语言来说,优化过程要困难得多。
所以你想从头开始制作自己的 [[compiler|编译器]]?


大多数编译器输出某种形式的程序集(assembly-汇编),并将其传递给汇编程序。 更罕见的是,一些编译器可能直接生成字节码或机器码,而无需第三方汇编程序。 (JIT-Just In Time即时编译器是一类特殊的嵌入式编译器,可直接生成机器代码。)
这并不容易。 有些编译器的复杂度与整个简单操作系统相当。


== 其它工具 ==
尽管如此,它还是一个有趣且/或有教育意义的项目。 以下是开始之前你应该知道的一些事情:
下面是一些其它常用工具
=== 汇编程序 ===
编译器从最终将要执行的底层机器指令中提取高级代码。


汇编程序获取汇编代码并输出机器代码。 汇编代码是机器指令的一对一表示。 通常,汇编器所做的唯一转换是填写标签(或保留“修复”位置的列表,当多个目标链接在一起时,这些位置会被填写)。更高级的汇编程序可能有宏或某种预处理器,但这些宏通常生成机器指令,因此没有像高级语言那样从底层指令中抽象出来。
== 利弊 ==
为什么要编写编译器而不是使用现有的编译器?


汇编程序可以生成可执行的二进制文件(非常适合运行)或目标文件。 目标文件不同于可执行二进制文件,因为它通常包括导出符号和(或)修复地址的列表。 目标文件可以是指可以在运行时动态加载的文件(动态库),也可以是要与其它目标文件合并以共享其标签并生成最终二进制文件的文件。
优点:
* 你想要的语言和目标的编译器可能根本不存在。
* 教育目的,你可以更好地了解 [[How kernel, compiler, and C library work together|内核、编译器和运行时库如何一起工作]],以及实现一种语言需要什么。
* 说到这里,你可以立即实现自己的新编程语言!有多酷啊?
* 你可以对正在编译的程序执行几乎任何操作:
** 以你喜欢的格式添加调试数据
** 添加分析辅助工具
** 重新编写和重新排列程序的各个部分
** 针对特定事物进行优化
** 将其扔掉并替换为其他程序
* 编译的程序将针对你的机器或你正在开发的操作系统定制。


=== 连接程序(Linkers) ===
缺点:
链接器获取多个目标文件,并将它们组合成单个目标文件或最终的二进制文件。
* 需要完全理解所需的语言。要始终制定充分的官方语言规范。
* 还需要了解特定于目标的汇编过程。
* 关于 [[Getting Started|起步指南]]这篇文章的大多数注解也适用于编译器。
* 完全实现一套语言规范将很棘手。
* 如果你想在编译代码的大小/速度优化方面与GCC竞争,则必须非常非常擅长做编译器。


当你希望将代码与库链接时,或者当你的程序有多个源文件,每个源文件都单独编译,并且你希望生成一个二进制文件时,通常使用链接器。
== 术语 ==
好吧,如果你还打算要做,现在让我们看看编译器是如何工作的:


每个目标文件都包含一个导出符号及其所在位置的列表,以及一个“修复”位置列表及其要查找的符号。然后,链接器尝试用其它文件中的符号填充修复位置。
[[Image:compilers1.png]]


== 阶段 ==
术语:
编译器有多个阶段。 每个阶段采用前一阶段创建的数据结构,并转换为新的数据结构。 支持多种输入语言或多种输出语言的高级编译器通常分为前端、中间端和后端,中间端和后端可以互换。 只支持一种输入语言和一种目标语言的更简单的编译器通常不需要将这些端点分开。
* “Host主机” 是编译器本身运行的环境。
* “Target目标” 是要运行编译后得到程序的地方。
* “run-time运行时” 是目标上存在的资源 (库,进程等)集合。 两台具有相同硬件的机器在运行时资源的可用性方面不同,有时则被认为是不同的目标,因此一个程序可能在一个计算机上运行,但不能在另一个计算机上运行。
* “[[Executable Formats|可执行文件-executable]]” 是一种文件,其中包含目标启动程序所需的信息。 它通常是直接的二进制文件,但通常结构更精细,例如包含链接和重新定位信息。
* “link链接” 表示程序知道如何与运行时对接,并依赖运行时的某些功能。 它是由 [[Linkers|链接器]] 创建的,并且在自主(free-standing)程序 (即OS内核) 中不存在。


=== 前端 ===
如果主机和目标是相同的,则产品是 “原生可执行文件(native executable)”。 99%的情况下,你遇到的就是这种。
编译器的前端是指编译器中读取输入语言的部分。 在像[[GCC]]和[[LLVM]]这样支持多种语言的大型编译器中,前端和后端可以混合和匹配以支持不同的语言,同时共享同一个中间端。
如果编译器能够为与主机不同的目标生成可执行文件,则它就属于 “交叉编译器(cross-compiler)”。
如果编译器能够编译出自己,那就是 “自我托管(self-hosting)”的。


==== 词汇分析(Lexical Analysis) ====
== 内部 ==
[[Lexical Analyzer|词法分析(Lexical analysis)]]读取源文件并将其拆分为令牌。 标记通常有一个类型,可以是诸如FOR、INT、VOID等符号。 标记也可以是附加了额外数据(例如文本的值或标识符的名称)的文本,例如字符串、标识符、浮点值。 lexer通常处理跳过注释。
[[Image:compilers2.png|right]]
编译器也有奇特的内部结构。 你不必完全能复述这里描述的那些定义,但目前这是一个很好的路线图。 通常,编译程序的任务分为几个单独的任务:


lexer可以手工编写,也可以使用“lexer生成器”生成,这是一种接受词法语法并生成lexer代码的工具。
* ''' Front End 前端 ''' 采用某些特定语言的源代码,并输出通用的 “中间表示” (IR)。
* '''Middle End 中端 ''' (可选) 采用中间表示形式,以某种方式对其进行更改,然后将其输出回去。
* '''Back End 后端''' 获取IR并输出特定目标的可执行文件。


==== 解析(Parsing) ====
这种划分的想法是,通过具有不同前端和不同后端的集合,你可以将任何语言的程序编译到任何目标,因为IR对于所有目标都是相同的。
解析阶段从lexer读取标记,并在内存中构建某种形式的代码表示。 表示通常是一个抽象语法树。


解析器可以手工编写(请研究 [http://en.wikipedia.org/wiki/Recursive_descent_parser 递归下降语法分析器-Recursive descent parser])或使用“语法分析器生成器”(parser generator)生成,这是一种接受语言语法并生成语法分析器代码的工具。 正是在这一阶段,局部变量和对象名在遇到时被注册。
=== 前端 ===
 
一些解析器生成器一次性生成解析器和词法分析器,称为“编译编译器(compiler compilers)”。
 
====抽象语法树(Abstract syntax tree)====
抽象语法树(AST-abstract syntax tree)是以树格式表示的程序,通常是以树格式表示的源代码。 抽象语法树通常与输入语言紧密相连,因此是前端的一部分,但有时它可能是中间端的一部分。 然后将抽象语法树转换为独立于语言的中间表示。
 
====语义图(Semantical graph)====
编程语言使用标识符引用在其它地方声明的实体。 在执行进一步的分析之前,应该解析标识符-连接到它们所表示的声明。 这将AST转换为图形。 图形是使用称为符号表或上下文的辅助数据结构构建的。
 
在某些编译器中,AST和语义图使用相同的数据结构。 在这种情况下,解析器可以将声明指针设置为NULL,或者标识符解析可以集成到解析过程中。
 
====语义分析(Semantical analysis)====
此阶段计算表达式和声明的属性,并执行各种有效性检查:确定表达式类型、解析函数重载、检查重写函数的协方差、检查常量变量是否未发生变化、检查所有枚举元素是否在switch语句中处理等。
 
===中间端===
中间端充当前端和后端之间的粘合剂。 这是一个很好的例子[http://en.wikipedia.org/wiki/Intermediate_representation#Intermediate_representation中间表示]这与语言无关,大多数优化都在这里完成。 并非所有编译器都有中间端,有时抽象语法树直接生成机器代码并跳过这些步骤。
 
====字节码(Bytecode)====
有些编译器有一种内部字节码语言(可能不同于字节码目标),用于前端和后端之间的通信。 这些字节码可以是基于寄存器的,也可以是基于堆栈的(基于堆栈的字节码是[http://en.wikipedia.org/wiki/Stack_machine#Simple_compilers 非常容易从抽象语法树生成])。
 
====单一静态赋值(Single static assignment)====
抽象语法树或字节码可以翻译成[http://en.wikipedia.org/wiki/Static_single_assignment_form单一静态赋值],或SSA,形式。 SSA表单是代码的中间表示形式,其中所有变量只分配给一次。 SSA形式非常适合优化,例如常数折叠(constant folding)和死代码消除。 它也是一种简单的形式,可以很好地映射到后端的寄存器。


===后端===
* 首先,前端通常包括某种用户接口,以便可以接受文件和编译选项。 然后,有几个阶段的处理。
编译器的后端将代码输出到目标语言中。后端通常执行特定于目标的优化。
* 对于类似C的语言,会有一个 ''' pre-processor 预处理器 ''' 从头文件中复制并粘贴代码,删除注释执行宏扩展并执行其他相对简单的任务。
* 然后,一个 '''scanner 扫描器''' (或 '''tokenizer 分词器''') 将源文件分解为一系列分词(Token),代表一种语言的基本单词 (即标识符,数字和字符串常量,诸如 “if” 和 “when” 的关键字,标点符号和分号)
* 然后,'''parser解析器''' 读取令牌流并构造 '''parse tree解析树''',这是一种树状结构,表示源代码的结构。 就语言制作而言,每个源代码文件都是该语言的 “sentence 句子”,并且每个句子 (如果有效) 都遵循特定的语法。
* 接下来,'''semantic analyzer 语义分析器''' 遍历解析树,并确定该 “句子” 每个部分的特定含义。 例如,如果是声明语句,则它将条目添加到符号表中,并且如果它是涉及变量的表达式,则它将符号表中已知变量的地址替换为表达式中的变量。
* 最后,前端生成一个 '''Intermediate Representation 中间层表达''',它捕获程序源代码特定的所有信息。 一个好的IR可以说明源代码所表达的所有内容甚至更多,还可以捕获该语言对程序的其他要求。 它可以是 '''parse tree 解析树 ''' 、 '''abstract syntax tree 抽象语法树 ''' 、 '''three address code 三地址代码 ''' 或更奇特的东西。


====解释器====
值得注意的是,这种划分纯粹是为了方便编译器开发人员。 大多数类型的 '''parsers 解析器''' 可以轻松读取字符流,而不是分词令牌流,因此不需要单独的扫描器。 一些非常强大的解析器类甚至可以 “在阅读完成之前” 确定语句的语义含义,因此不需要语义分析器。 不过,它们可能会更难理解和使用。
解释器不输出代码,所以从技术上讲,它们不是编译器,但它们的前端和中间端的实现方式与编译器类似。 它们可以执行即时表示、抽象语法树,或者在语言解析时执行—完全绕过中间端。 JIT(just-in-time 即时)编译器在内存中生成机器代码并立即执行。


====字节码====
=== 中端 ===
编译器可能以字节码为目标,如[[WebAssembly]]。 字节码被设计为在虚拟机内部执行,并且通常比汇编更容易定位(因为不必分配有限数量的寄存器,而且它的级别更高)。
这里会使用一大堆旨在尝试使程序更高效的算法。 我对这部分不是很熟悉,所以我就不详细介绍了。 因为它所做的只是优化,所以为了简单起见,你可以省略它。


====汇编====
=== 后端 ===
编译器可能以汇编语言为目标。 这类似于定位字节码,只是编译器必须分配寄存器,并且经常处理寄存器和堆栈分配,以及[http://en.wikipedia.org/wiki/Calling_convention呼叫约定]
* 首先,'''code generator 代码生成器'''(译者注:这里Code指可执行代码) 读取中间表示,并生成出类似汇编的代码,唯一的区别是,为简单起见,它假定目标是一台具有无限数量的寄存器 (或其他资源) 的机器。
* 其次,'''register allocator寄存器分配器''' 通过决定何时将变量存储在寄存器或内存中来处理CPU上的可用寄存器。 这部分对性能会有 ''主要'' 影响。 一旦完成,类似汇编的代码就会变成真实 '''汇编'''。
* 然后,'''assembler 汇编器''' 读取汇编并输出 '''machine code 机器码'''通常,代码仍然有一些未解决的引用问题(译者注:指对外部库的依赖引用),因此将机器代码放入 '''object file 目标文件 ''' 中。
* 接下来,'''链接器(linker)''' 通过将目标文件与库链接并替换指向库内正在引用的资源的指针来满足目标文件中每个未解析的引用。 链接器还提供必要的信息,以便在动态链接时定位相关库,或者在静态链接时,特定库的一些或全部可能嵌入到目标文件中。 链接器有时被认为是与后端甚至编译器分开的,但事实是,特定链接器的操作特定于它链接的目标 (或目标族),所以我将其包括在编译器后端类别中。


通过输出汇编语言,编译器让汇编器实现目标和可执行格式,计算代码位置、标签,并用机器代码对指令进行编码。
* 最后,后端将解析所有引用,通过添加目标程序加载机制所必需的元数据,将目标文件转换为可执行文件,以达到能识别程序,加载它,在必要时动态链接它并运行它。


====机器码====
编译器可以生成机器代码(如JIT编译器)。当编译器拥有所需的所有输入代码并且不需要将输出文件与其它输出文件合并时,通常会执行此操作。 输出机器代码的过程与输出汇编代码非常相似,但编译器现在必须解析标签位置,编码机器指令,并以[[Executable Formats|可执行格式]]处理输出。


[[Category:Compilers]]
后面很快,我将讨论如何实际编写这些内容。(译者注:然而并没有:-p)

2022年3月19日 (六) 03:37的最新版本

这个页面正在建设中! 此页面或部分内容仍在改进中,因此可能还不完整。 其内容可能会在不久的将来更改。

所以你想从头开始制作自己的 编译器

这并不容易。 有些编译器的复杂度与整个简单操作系统相当。

尽管如此,它还是一个有趣且/或有教育意义的项目。 以下是开始之前你应该知道的一些事情:

利弊

为什么要编写编译器而不是使用现有的编译器?

优点:

  • 你想要的语言和目标的编译器可能根本不存在。
  • 教育目的,你可以更好地了解 内核、编译器和运行时库如何一起工作,以及实现一种语言需要什么。
  • 说到这里,你可以立即实现自己的新编程语言!有多酷啊?
  • 你可以对正在编译的程序执行几乎任何操作:
    • 以你喜欢的格式添加调试数据
    • 添加分析辅助工具
    • 重新编写和重新排列程序的各个部分
    • 针对特定事物进行优化
    • 将其扔掉并替换为其他程序
  • 编译的程序将针对你的机器或你正在开发的操作系统定制。

缺点:

  • 需要完全理解所需的语言。要始终制定充分的官方语言规范。
  • 还需要了解特定于目标的汇编过程。
  • 关于 起步指南这篇文章的大多数注解也适用于编译器。
  • 完全实现一套语言规范将很棘手。
  • 如果你想在编译代码的大小/速度优化方面与GCC竞争,则必须非常非常擅长做编译器。

术语

好吧,如果你还打算要做,现在让我们看看编译器是如何工作的:

Compilers1.png

术语:

  • “Host主机” 是编译器本身运行的环境。
  • “Target目标” 是要运行编译后得到程序的地方。
  • “run-time运行时” 是目标上存在的资源 (库,进程等)集合。 两台具有相同硬件的机器在运行时资源的可用性方面不同,有时则被认为是不同的目标,因此一个程序可能在一个计算机上运行,但不能在另一个计算机上运行。
  • 可执行文件-executable” 是一种文件,其中包含目标启动程序所需的信息。 它通常是直接的二进制文件,但通常结构更精细,例如包含链接和重新定位信息。
  • “link链接” 表示程序知道如何与运行时对接,并依赖运行时的某些功能。 它是由 链接器 创建的,并且在自主(free-standing)程序 (即OS内核) 中不存在。

如果主机和目标是相同的,则产品是 “原生可执行文件(native executable)”。 99%的情况下,你遇到的就是这种。 如果编译器能够为与主机不同的目标生成可执行文件,则它就属于 “交叉编译器(cross-compiler)”。 如果编译器能够编译出自己,那就是 “自我托管(self-hosting)”的。

内部

Compilers2.png

编译器也有奇特的内部结构。 你不必完全能复述这里描述的那些定义,但目前这是一个很好的路线图。 通常,编译程序的任务分为几个单独的任务:

  • Front End 前端 采用某些特定语言的源代码,并输出通用的 “中间表示” (IR)。
  • Middle End 中端 (可选) 采用中间表示形式,以某种方式对其进行更改,然后将其输出回去。
  • Back End 后端 获取IR并输出特定目标的可执行文件。

这种划分的想法是,通过具有不同前端和不同后端的集合,你可以将任何语言的程序编译到任何目标,因为IR对于所有目标都是相同的。

前端

  • 首先,前端通常包括某种用户接口,以便可以接受文件和编译选项。 然后,有几个阶段的处理。
  • 对于类似C的语言,会有一个 pre-processor 预处理器 从头文件中复制并粘贴代码,删除注释执行宏扩展并执行其他相对简单的任务。
  • 然后,一个 scanner 扫描器 (或 tokenizer 分词器) 将源文件分解为一系列分词(Token),代表一种语言的基本单词 (即标识符,数字和字符串常量,诸如 “if” 和 “when” 的关键字,标点符号和分号)
  • 然后,parser解析器 读取令牌流并构造 parse tree解析树,这是一种树状结构,表示源代码的结构。 就语言制作而言,每个源代码文件都是该语言的 “sentence 句子”,并且每个句子 (如果有效) 都遵循特定的语法。
  • 接下来,semantic analyzer 语义分析器 遍历解析树,并确定该 “句子” 每个部分的特定含义。 例如,如果是声明语句,则它将条目添加到符号表中,并且如果它是涉及变量的表达式,则它将符号表中已知变量的地址替换为表达式中的变量。
  • 最后,前端生成一个 Intermediate Representation 中间层表达,它捕获程序源代码特定的所有信息。 一个好的IR可以说明源代码所表达的所有内容甚至更多,还可以捕获该语言对程序的其他要求。 它可以是 parse tree 解析树 abstract syntax tree 抽象语法树 three address code 三地址代码 或更奇特的东西。

值得注意的是,这种划分纯粹是为了方便编译器开发人员。 大多数类型的 parsers 解析器 可以轻松读取字符流,而不是分词令牌流,因此不需要单独的扫描器。 一些非常强大的解析器类甚至可以 “在阅读完成之前” 确定语句的语义含义,因此不需要语义分析器。 不过,它们可能会更难理解和使用。

中端

这里会使用一大堆旨在尝试使程序更高效的算法。 我对这部分不是很熟悉,所以我就不详细介绍了。 因为它所做的只是优化,所以为了简单起见,你可以省略它。

后端

  • 首先,code generator 代码生成器(译者注:这里Code指可执行代码) 读取中间表示,并生成出类似汇编的代码,唯一的区别是,为简单起见,它假定目标是一台具有无限数量的寄存器 (或其他资源) 的机器。
  • 其次,register allocator寄存器分配器 通过决定何时将变量存储在寄存器或内存中来处理CPU上的可用寄存器。 这部分对性能会有 主要 影响。 一旦完成,类似汇编的代码就会变成真实 汇编
  • 然后,assembler 汇编器 读取汇编并输出 machine code 机器码。 通常,代码仍然有一些未解决的引用问题(译者注:指对外部库的依赖引用),因此将机器代码放入 object file 目标文件 中。
  • 接下来,链接器(linker) 通过将目标文件与库链接并替换指向库内正在引用的资源的指针来满足目标文件中每个未解析的引用。 链接器还提供必要的信息,以便在动态链接时定位相关库,或者在静态链接时,特定库的一些或全部可能嵌入到目标文件中。 链接器有时被认为是与后端甚至编译器分开的,但事实是,特定链接器的操作特定于它链接的目标 (或目标族),所以我将其包括在编译器后端类别中。
  • 最后,后端将解析所有引用,通过添加目标程序加载机制所必需的元数据,将目标文件转换为可执行文件,以达到能识别程序,加载它,在必要时动态链接它并运行它。


后面很快,我将讨论如何实际编写这些内容。(译者注:然而并没有:-p)