likes
comments
collection
share

编译原理两三事

作者站长头像
站长
· 阅读数 5

前言

编译原理是一套复杂庞大的偏底层的知识体系。目的是将高级程序设计语言转换成计算机硬件能识别的机器语言，以便计算机进行处理。本文将给大家提炼介绍整体的流程，以及具体深挖部分细节流程。主要会围绕以下几个方面进行介绍：

  • 代码到底是什么
  • 什么是编译
  • 计算机如何将代码转换成可以运行的目标程序(重点介绍)
  • 计算机怎么理解机器语言并落实在硬件上执行
  • JS代码的编译解析执行过程

代码到底是什么

如果你是内行。代码就是你现在想的那个东西（程序、与计算机交流的语言、指令、blablabla……）。一个懂得都懂，只可意会，不可言传的东西。

如果你是专家。代码是一个文本文件，包含了CPU指令和预置数据。

如果你是大师。代码就是两杯水，一杯是空的，一杯是满的。道德经里说上善若水，水善利万物而不争……

什么是编译

编译原理两三事

机器语言，晦涩难记。所以有了汇编语言。

汇编语言，依赖目标机器，需要熟悉相关机器特性。所以有了高级语言。

高级语言方便记忆，方便开发，甚至可跨平台，但计算机无法理解。

编译就是将高级语言(源语言)翻译成汇编语言或机器语言(目标语言)的过程。

计算机如何将代码转换成可以运行的目标代码

一般计算机会先将源代码转换成一种中间表达形式，然后由这个中间表达形式再翻译成目标代码。先解释下不同情况下我理解的目标代码

  • 如果源代码在操作系统上运行：目标代码就是“汇编代码”。再通过汇编的过程形成可执行的机器码文件，然后通过加载器加载到操作系统执行。

    为什么编译器不直接产生机器语言而是产生汇编语言？

    因为汇编语言比较容易输出和调试，方便优化，汇编语言到机器语言由硬件实现即可,这样分层处理可以有效降低编译器编写复杂性，提高效率。

  • 如果源代码在虚拟机(解释器)上运行：目标代码就是“解释器可以理解的中间形式的代码”，比如字节码(中间代码)、AST语法树。

由源语言到目标语言的转换流程如下：（下文将逐一解释）

编译原理两三事

词法分析

词法分析的目的是将源程序代码分成一堆编译器可以理解的单词。实际上分析过程就是从左到右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。然后转换成词法单元(token)的形式。此外，这个阶段还会完成两件事：

  • 过滤掉源程序中的注释和空白
  • 将编译器生成的错误信息与源程序位置关联起来

token：<词法单元名，属性值>：

单词类型示例词法单元名
关键字if、else、while一词一名
标识符变量名、数组名……多词一名
常量整型、布尔型……一型一名
运算符+、&&、>……一词一名
界限符; {} ()……一词一名

举个🌰

1. while(value!=100){num++;} 

    // 经过词法分析后得到的token序列：

    <while,->
    <(,->
    <id,指向value的符号表项的指针>
    <!=,->
    <id,指向100的符号表项的指针>
    <),->
    <{,->
    <id,指向num的符号表项的指针>
    <++,->
    <;,->
    <},->
    
 2. a = b + c * 60;
 
    // 经过词法分析后得到的token序列： 
    
    <id,a> <=> <id,b> <+> <id,c> <*> <id,60> <;>

语法分析

如果把词法分析看作为字母组合成单词的过程，那么语法分析就是一个把单词组合成句子的过程。语法分析器从词法单元中识别出各类短语，如“程序”，“语句”，“表达式”等等。并构造语法分析树AST。

举个🌰

我们来分析一个赋值语句的语法树。依然是上面的a = b + c * 60;

编译原理两三事

我们可以看到通过词法分析，可以得到a,b,c三个标识符，还有一个常数60.

结合下图看，一个标识符或一个常数可以构成一个表达式1和表达式2。一个表达式1通过运算符可以和另一个表达式2构成一个更大的表达式3（或者是一个表达式3通过运算符可以和另一个表达式4构成一个更大的表达式5）最终一个标识符a和一个表达式5通过一个赋值符号连接，再加一个分号。这样就构成了一个赋值语句。

编译原理两三事

我们在语法分析中使用一种很具有表达力的工具,用来描述语言的语法规则 —— 上下文本无关语法 G （ context-free grammar, CFG） ：

一个 4 元组： (T, N, P, S) ， 其中 T 为终结符集合， N 为非终结符集合， P 为产生式集合， S 为起始符号。

一个句子如果能从语法 G 的 S 推导得到， 可以直接称此句子由语法 G 推导得到， 也可称此句子符合这个语法， 或者说此句子属于 G 语言。 G语言（ G language） 就是语法 G 推导出来的所有句子的集合， 有时也用 G 代表这个集合

语义分析

语法分析环节，我们初步构建了抽象语法分析树。语义分析阶段就会根据上下文分析，丰富优化这个语法分析树。我们知道高级语言中的语句一般分为两类，声明语句和可执行语句。在声明语句中，会声明一些变量、函数等。并且会给他们一个变量名、函数名等。我们把这类名称叫做标识符。语义分析的任务就是收集标识符的属性信息和语义检查。

收集标识符的属性信息包括以下内容：

  • 种类/种属 分析当前标识符是属于简单变量、复合变量（数组、对象）、还是函数等
  • 数据类型 分析标识符变量或函数对应的数据类型，属于常量、数字、布尔值等
  • 存储位置/长度 根据标识符的各类型所占用的内存长度，分配存储位置
  • 值
  • 作用域
  • 参数和返回信息 参数个数、参数类型、返回值类型等

每一个收集的标识符属性内容会被收录在符号表里。

编译原理两三事

语义分析的另一个工作，语义检查实际上就是要让计算机理解我们的真实意图，把一些模棱两可的地方消除掉。比如：

  • 变量或函数未经声明就使用
  • 变量或函数名重复声明
  • 运算分量类型不匹配，比如说把一个数组和一个函数相加
  • 操作符与操作数之间的类型不匹配
    • 数组下标不是整数
    • 对非数组变量使用数组访问操作符
    • 对非函数名使用函数调用操作符
    • 函数调用的参数类型或数目不匹配
    • 函数返回类型有误

最终，语义分析获得的一些信息（引用消解信息、类型信息等）以及上下文分析结果，会附加到 AST 上，AST 加上这些语义规则，就能完整地反映源代码的含义。

中间代码生成

为什么需要中间代码？编译器不能直接使用语义分析的结果去解释执行或者生成目标代码吗？

  • 对于不同架构的CPU，还需要生成不同的汇编代码，如果对每一种汇编代码做优化就很繁琐了。因此我们需要增加一个环节：生成中间代码IR，统一优化后中间代码，再去将中间代码生成目标代码。并且从软降工程上考虑，这样更容易实现，容易维护。

中间代码生成属于编译器前端结构的最后一部分，传入一棵语法树，从根结点，根据该节点的词法属性，分析词法结点之间的逻辑，翻译成合适的中间表示。中间代码有两个用途：

  • 解释执行 像前面提到的在虚拟机上运行的代码，实际上到这一步就完成了编译。可以根据中间代码直接执行
  • 代码优化 并不是所有的优化都要在汇编的时候才能完成，所以针对中间代码也会做一部分的代码优化工作

代码优化器

代码优化可以分为机器无关代码优化和机器相关代码优化。代码优化实际上是为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些，或者二者兼顾。代码优化按照优化的代码块尺度分为：

  • 局部优化 只有一个控制流入口、一个控制流出口的基本程序块上进行的优化；
  • 循环优化 对循环中的代码进行的优化；
  • 全局优化 在整个程序范围内进行的优化。

常见的代码优化技术有：删除多余运算、合并已知量和复写传播，删除无用赋值等。

目标代码生成器

目标代码生成，就是生成虚拟机执行的字节码，或是操作系统执行的汇编代码。代码生成的过程，其实很简单，就是将中间代码逐个翻译成想要的汇编的代码。

目标代码生成阶段的任务就有：

  • 选择合适指令，生成性能最高的代码。
  • 优化寄存器的分配，让频繁访问的变量，比如循环语句中的变量放到寄存器中，寄存器比内存快。
  • 在不改变运行结果下，对指令做重排序优化，从而充分运用CPU内部的多个功能部件的并行能力。

计算机怎么理解机器语言并落实在硬件上执行

通过上述内容实际上已经完成了编译的过程，我们会得到一个汇编语言。汇编语言到机器语言实际上是一个很简单的“查字典”的过程，这部分工作操作系统会自己完成。计算机说到底就是一个电器，他是怎么理解执行这些0101的序列号的呢。实际上计算机执行指令的过程分为四步：

  • 取指 控制器将指令的地址送往存储器，存储器根据指令地址读出指令的内容再送回控制器
  • 译码 控制器分析指令的操作性质，并向有关部件发出指令所需的控制信号
  • 执行 控制器从通用寄存器或存储器中取出操作数，然后命令运算器对操作数进行运算
  • 回写 将运算结果写入通用寄存器或存储器

编译原理两三事

这里列举了一个简单的图示。其实我简单理解这里主要是两大重点存储和运算。这里会涉及到相关专业的知识，比如模电和数电。我们都知道01实际上在计算机就代表电平。我简单理解模电在其中的作用就是去控制这些电平信号，还有过滤一些干扰信号。而数电就和运算的关系比较大。会通过一些电器元件的特殊功能，比如单向二极管。就可以模拟一些逻辑运算。实际上这个图示例子有一个比较完整的解读说明。大家感兴趣可以看看这个文章： 计算机执行指令的过程

JS代码的编译解析执行过程

了解了整个编译原理的过程，我们来分析一下js的编译解析过程。js作为一个高级语言，在被执行前，也需要被某种程序翻译成机器语言让cpu识别并执行。而这种程序大家把它叫做js引擎。js有很多引擎，其中最著名的就是v8引擎。虽然引擎品类众多，但是这些引擎的执行流程基本是都是以下四个步骤：

  • Parser：解析器，此处进行此法和语法分析，将JavaScript源码转换为AST抽象语法树并且生成执行期上下文；
  • Ignition：解释器，解释器会根据 AST 生成字节码，并解释执行字节码（字节码最终也会转为机器码执行），同时收集优化编译所需的信息;
  • TurboFan：编译器，负责将字节码“翻译”为不同系统识别的机器码。

解释器和编译器

解释器比较容易让用户实现自己跨平台的代码，同一套代码可以几乎在所有的操作系统上执行，而无需根据操作系统做修改；但是解释器不会一次把整个程序转译出来，每次运行程序时都要先转成另一种语言再作运行，而且是逐行转译执行，因此解释器的程序整体运行速度缓慢。编译器一次性将所有源代码编译为一个可执行程序，一次编译可重复执行。

所以为了沿用解释器优点的同时避免解释器的低效性，即遇到相同代码时还会重新翻译一遍，浏览器开始混合加入编译器，产生了即时编译器（JIT）。浏览器会标记反复运行的代码，即HotSpot热点代码。JIT即把解释器解释代码过程中的热点代码编译成可立即执行的机器码，再次命中热点代码时不再重新解释，能够提高性能。

  • Garbage Collector：垃圾回收模块，负责将程序不再需要的内存空间回收；

接下来我们将通过v8引擎进行举例。简单说明下v8引擎是如何运行js的。

早期的v8引擎实际上会直接把AST翻译生成机器代码。也就是说没有解释器，却有两个编译器，它的编译流程是这样的

编译原理两三事

首先源码通过解析器会生成一个AST，AST经过基准编译器直接生成一个基准的未被优化的机器代码，而不进行任何的中间转换。这样做的好处是当你第一次执行js的时候就是执行了高效的机器代码。因为没有中间代码的产生所以就不需要解释器。当代码运行一段时间后，v8引擎中的分析器线程收集了足够的数据来帮助另一个编译器来做代码优化，这个编译器叫做优化编译器。需要优化的源码重新解析生成AST，然后优化编译器根据AST生成优化后的机器代码。来提升整体的运行效率。但这样设计的缺点是：

  • 机器码会占用大量的内存
  • 缺少中间层机器码，无法实现一些优化策略
  • 无法很好的支持和优化JS的新语特性，无法拥抱未来

所以v8引擎在17年的时候做了一次大的架构调整，很大程度的去解决和改善了这个问题。改善后的架构加入了解释器，流程如下：

编译原理两三事

解析生成AST的过程还是一样的，但在随后引入了解释器，根据AST会生成字节码。同时AST也会被清除掉，释放内存空间。生成的字节码直接被解释器执行，同时会被作为基准执行模型。字节码相对机器码可以节省50%-75%的内存。在代码运行的过程中，解释器收集了很多代码优化的信息，这些信息被发送给编译器，编译器会根据这些优化信息和字节码生成优化过的机器代码。这里简单说几个v8引擎的优化策略：

  • 声明未调用，不会被解析生成AST
  • 函数只被调用一次，bytcode直接被解释执行，不会进入到编译优化阶段
  • 函数被调用多次，Igniton会收集函数类型信息，可能会被标记为热点函数，可能被编译成优化后的机器代码

优化后的v8引擎架构实际上在运行阶段处于一种字节码和机器码共存的状态。优化后的显著好处体现在：

  • 由于一开始不需要直接编译成机器码，生成了中间层的字节码，从而节约了时间
  • 优化编译阶段，不需要从源码重新解析,直接通过字节码进行优化，也可以deoptimization回退操作

QA虚拟机最终是如何执行机器码的