文档章节

深入理解编译器

krircc
 krircc
发布于 11/17 16:19
字数 3434
阅读 9
收藏 0

深入理解编译器

原文出处

欢迎向Rust中文社区投稿,投稿地址,好文将在以下地方直接展示

编程语言是如何工作的

从内部理解编译器会使你更有效的使用它。在这个时间顺序的摘要中,概括了编程语言和编译器是如何工作的。我们排版了大量的链接,示例代码,和图表来帮助你理解。

作者注

理解编译器—— 是我的在Medium上第二篇文章的后续,超过了21000的阅读量。我很高兴我能在人们的教育产生积极的影响,我很兴奋能够根据我从原始文章收到的反馈进行完全的重写

Understanding Compilers — For Humans

我选择Rust作为这部作品的主要语言。它是冗长,高效,现代的,并且在设计上似乎对编写器非常简单。我喜欢使用它。https://www.rust-lang.org/

本文的目的是为了保持读者的注意力而非20页的麻木阅读。本文有许多链接会导航您到引起您兴趣的主题以进行更深入的探索。大多数链接会带领你到Wikipedia。

什么是编译器

总的来说,你所谓的编程语言其实就是软件,叫做编译器,它读取文本文件,做了许多处理,并生成二进制文件。 由于计算机只能读1或0,人们写Rust更高质量,而不是写二进制文件,编译器被用来将人类可读的文本转换为计算机可读的机器码。

编译器可以是任何一个能将一个文本翻译为另一个文本的程序。例如,这是一个用Rust写的编译器,它将所有的0转为1,1转为0 。

// An example compiler that turns 0s into 1s, and 1s into 0s.
 
fn main() {
    let input = "1 0 1 A 1 0 1 3";
 
    // iterate over every character `c` in input
    let output: String = input.chars().map(|c|
        if c == '1' { '0' }
        else if c == '0' { '1' }
        else { c } // if not 0 or 1, leave it alone
    ).collect();
 
    println!("{}", output); // 0 1 0 A 0 1 0 3
}

尽管这个编译器不读取文件,不生成AST,不产生二进制文件,但是它仍然被认为是一个编译器,因为它翻译了输入。

编译器做了什么

简单来说,编译器读取源代码生成二进制文件。由于直接将复杂的、人类可读的代码转为一和零是非常复杂的,编译器在程序可运行前有几个步骤要做:

  • 1 读取你给它的源代码中的独立字符。
  • 2 将字符分类为字,数字,符号和操作符。
  • 3 获取已排序完的字符,并通过将它们与模式匹配相匹配和生成操作树来确定它们尝试进行的操作。
  • 4 迭代上一步中生成操作树中的每一个操作,并生成等效的二进制文件。

当我说编译器立刻从一个操作树转化到二进制文件时,它实际生成了汇编代码,汇编代码随后被汇编/编译成二进制文件。汇编像是更高级的,人类可读的二进制文件。在这里阅读关于汇编更多的东西。

解释器(Interpreter)是什么

解释器非常像编译器,它们读取一门语言并处理它。但是,解释器跳过代码生成并且会即时执行AST。解释器的最大的优点是它在调试期间运行你的程序时所用的时间。一个编译器在程序执行前可能会花费一秒到几分钟时间编译程序,然而解释器立刻执行,不需要编译。解释器最大的缺点是它要求在程序可被执行前,用户的电脑上必须安装解释器。

本文主要谈论编译器,但是你应该清楚他们之间的不同以及和编译器之间的关系。

1. 词法分析

第一步是按字符分割输入字符。这步叫做词法分析,或者符号化。词法分析主要的思想是 将字符组合在一起形成单词,标识符,符号等等。词法分析大多不处理任何类似2+2的逻辑——它只会说有三个符号:一个数字:2,一个加号,以及另一个数字:2。

假设你正在分析如12+3这样的字符串:它会读取字符1,2,+,和3。我们有了独立的字符,但我们必须将他们组合在一起,这是符号化的主要任务之一。例如,我们得到了1和2作为独立的字母,但是我们需要将他们放在一起,并解析他们作为一个单独的整型数字。+同样需要被认为是一个加号,而不是它的文字字符值——字符码43.

如果你可以看到代码,并以这种方式赋予更多的意义,随后,按照Rust符号化可以组合数字位32-bit整型,加号作为Token值Plus。

Rust Playground

你可以在Rust 操作界面点击左上角的“运行”按钮来在浏览器中编译和执行代码。

在编程语言的编译器中,词法分析器可能需要几种不同类型的符号。例如:符号(symbols),数字,标识符,字符串,操作符等。它完全依赖于语言自身,才能知道您需要从源代码中提取哪种类型的符号。

int main() {
    int a;
    int b;
    a = b = 4;
    return a - b;
}
 
Scanner production:
[Keyword(Int), Id("main"), Symbol(LParen), Symbol(RParen), Symbol(LBrace), Keyword(Int), Id("a"), Symbol(Semicolon), Keyword(Int), Id("b"), Symbol(Semicolon), Id("a"), Operator(Assignment), Id("b"),
Operator(Assignment), Integer(4), Symbol(Semicolon), Keyword(Return), Id("a"), Operator(Minus), Id("b"), Symbol(Semicolon), Symbol(RBrace)]

这是一段经过词法分析的C语言源码,且它的符号都被打印了出来。

2. 解析

解析器是语法(分析)的核心。解析器使用词法分析器生成的符号,尝试判断它们是否处于某种排列样式,随后,将那些排列形式与表达式联系,如调用函数,召回变量或者数学操作。 解析器是按照字面定义语言的语法。

int a = 3 和 a: int = 3的不同在解析器中。解析器决定了语法的外观。它确定了括号和花括号平衡,每条语句以分号结束,每个函数有一个名字。解析器知道当符号不能匹配到预设的样式时,有些东西的顺序出现了问题。

你可以编写几种不同类型的解析器。其中最常见的是自上而下,递归下降解析器。递归下降解析是最容易使用和理解的。我编写的许多解析器示例都是基于递归解析的。

可以使用语法来概括语法解析器解析。如EBNF这样的语法可以描述解析器的简单数学操作,如12+3:

expr = additive_expr ;
additive_expr = term, ('+' | '-'), term ;
term = number ;

简单加减表达式的EBNF语法

记住,语法文件不是解析器,但是它的确概括了解析器所做的。你按照这样的语法构造一个类似的解析器。它被人类使用,相对于直接查看解析器的代码更容易阅读和理解。

该语法的解析器是expr解析器,因为它是顶级项目,基本所有都与它有关。唯一有效的输入必须是任何数字,接加号或减号,接任何数字。expr期望一个additive_expr,这是加法和减法主要出现的地方。additive_expr首先期望一项(term)(一个数字),随后是加号或减号,另一项。

解析12+3生成的AST示例

当解析器解析时生成的树称为抽象语法树(abstract syntax tree),或AST。 AST包含了所有的操作。解析器不需要计算(所解析的)操作,只需以正确的顺序收集它们即可。

我之前添加了我们的词法分析器代码,以便与我们的语法匹配,并生成如图中的ASTs。我用// BEGIN PARSER //// END PARSER //标记了新解析器代码的开始和结束。

Rust Playground

我们实际上可以更深入。假设我们想支持只有数字没有操作的输入,或者添加乘法或除法,甚至添加优先级。这可以快速更改语法文件,并在我们解析器代码中做调整来反映出来。

expr = additive_expr ;
additive_expr = multiplicative_expr, { ('+' | '-'), multiplicative_expr } ;
multiplicative_expr = term, { ("*" | "/"), term } ;
term = number ;

新语法

Rust Playground

C语言的扫描器(又称词法分析器)和解析器的案例。从字符序列“if(net>0.0)total+=net*(1.0+tax/100.0);”开始,扫描器组建了符号序列,并分类,例如作为标识符,保留字,数字字符,或操作符。后面的序列由解析器转换成语法树,然后由生于的编译器阶段处理。扫描器和解析器处理C语言语法常规的和正确的无上下文的部分。

3. 生成代码

代码生成器使用AST和代码的等价物或者汇编代码。代码生成器必须以递归下降顺序遍历AST中的每一项——很像解析器所做的——随后发出等效的代码

Compiler Explorer - Rust (rustc 1.29.0)

如果你打开了上面的链接,你可以看到左侧示例代码产生的汇编代码。汇编代码的3-4行展示了编译器在遇到常量时如何生成常量的代码。

Godbolt Compiler Explorer是非常好的工具,允许你用高级语言写代码并看到它生成的汇编代码。你可以对用它做一些有趣的尝试,看看生成哪一类的代码,但是,不要忘记对你的编译器添加优化标志来显示它的智能之处。(Rust语言使用-o)

如果你对ASM中编译器是如何保存局部变量到内存感兴趣,这篇文章(代码生成节)详细解释了栈。大多时候,当变量不是局部的,高级编译器会在堆上为变量分配内存,并在那里存储,而不是在栈上。你可以阅读更多有关存储变量的内容在StackOverflow答案

由于汇编是完全不同的,复杂的主题,我不会特别谈论它太多。我只想强调代码生成器的工作和重要性。并且,代码生成器可以生成的不仅仅是汇编。Haxe有可以生成超过六种不同编程语言的后端;包括C++,Java和Python。

后端指的是编译器的代码生成器或评估器;因此,前端是词法分析器和解析器。也有中端,大多数是做本节之后的优化和IRs解释。后端大多与前端无关,只需考虑接受到的AST。这意味着可以为几个不同的前端或语言重用相同的后端。众人皆知的GNU Compiler Collection就是一个。

我的C编译器后端是最好的代码生成器示例;你可以在这里找到它。

汇编产生后,它会被写入新的汇编文件(.s或.asm)。这个文件会被汇编器传递,汇编器是汇编的编译器,会生成二进制的等价物。二进制代码随后会被写入称作对象文件的新文件(.o)。

对象文件是机器码,但不可执行。要让它们变得可执行,对象文件需要一起被链接。链接器使用这个通用机器码,并使它变得可执行,共享库或静态库。更多关于连接器点击这里

链接器是基于操作系统的可变有效程序。一个单独的,第三方的链接器应该能够编译你的后端生成的对象代码。当制作编译器时,不需要创建你自己的链接器。

编译器可能有中间表示(intermediate representation,IR)。IR是用于无损地表示原始指令以进行优化或翻译成另一种语言。 IR不是原始源代码;IR是为了在代码中找到潜在优化的无损简化。循环展开矢量化是使用IR完成的。更多有关IR的优化示例可以在这个PDF中找到。

总结

当你理解了编译器,你可以更高效的使用你的编程语言。可能有一天你会想制作你自己的编程语言?我希望本文可以帮助到你。

参考&拓展阅读

本文转载自:https://bbs.pediy.com/thread-247810.htm

共有 人打赏支持
krircc
粉丝 26
博文 54
码字总数 99883
作品 2
深圳
程序员
私信 提问
读《深入理解Java虚拟机》- 笔记08

《深入理解Java虚拟机:JVM高级特性与最佳实践》第2版 第10章 早期(编译期)优化 59. 语法糖 在计算机语言中添加某种语法,对语言的功能没有影响,但是方便开发人员使用。 泛型是一种语法糖...

阿历Ali
08/18
0
0
C语言编译全过程剖析

一、 摘要 C语言编译的整个过程是非常复杂的,里面涉及到的编译器知识、硬件知识、工具链知识都是非常多的,深入了解整个编译过程对工程师理解应用程序的编写是有很大帮助的,希望大家可以多...

长平狐
2013/01/06
34
0
构造函数的理解和应用场景

最近对C++的构造函数做了一个小小的总结,说是C++,其实java等面向对象高级语言对构造函数处理的本质都是一样的,只不过是有些许语法的区别罢了。 1、 为什么需要构造函数? 当我们在创建一个...

沙米笔记
2016/03/30
598
1
深入理解C语言

--作者:陈皓   --地址:http://coolshell.cn/articles/5761.html Dennis Ritchie 过世了,他发明了C语言,一个影响深远并彻底改变世界的计算机语言。一门经历40多年的到今天还长盛不衰...

江海一客
2016/10/31
13
0
c#基础系列3---深入理解ref 和out

“大菜”:源于自己刚踏入猿途混沌时起,自我感觉不是一般的菜,因而得名“大菜”,于自身共勉。 扩展阅读 c#基础系列1---深入理解 值类型和引用类型 c#基础系列2---深入理解 String 在上篇文...

大菜
09/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

大数据学习有哪几个步骤

目前大数据行业异常火爆,不少人都对大数据充满了兴趣,其中有大部分人都从没接触过大数据,对于应该如何学习大数据一头雾水。大数据学习并不是高深莫测的,虽然它并没有多简单,但是通过努力...

董黎明
22分钟前
4
0
shell习题_3

1:监控httpd的进程;每隔10s检测一次服务器的httpd的进程数,如果大于500则自动重启httpd服务;并检测是否启动成功; 如果没有正常启动还需要再启动一次,最大不成功数超过五次立即发邮件给管理...

芬野de博客
22分钟前
3
0
Android 9.0 优势探讨

我们来谈论一下 Android。尽管 Android 只是一款内核经过修改的 Linux,但经过多年的发展,Android 开发者们(或许包括正在阅读这篇文章的你)已经为这个平台的演变做出了很多值得称道的贡献...

问题终结者
39分钟前
4
0
vue 组件使用中的一些细节点

细节一 基础例子 运行结果: 以上大家都懂,这边就不多说,回到代码里,有时候我们需要 tbody 里面每一行是一个子组件,那我们代码可以怎么写呢?我们可以这样写,定义一个全局组件,如下: ...

peakedness丶
46分钟前
2
0
vue 之 css module的使用方法

动手之前先配置项目,网上很多文章说需要下载css-loader插件,Vue中的vue-loader已经集成了 CSS Modules,因此删掉也能正常运行 在vue.config.js中添加如下配置 `css: {``loaderOptions: ...

前端小攻略
50分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部