本文将以极粗的粒度概述编译原理相关常识及其流程

约好:

  1. 若未专门指定, “代码” 均指由现代高档言语书写的代码
  2. 若未专门拟定, “编译” 均指会直接发生最终方针代码的翻译方法, 即 “Compiler”

编译概述

言语分类

以下分类按笼统程度进行

  • 高档言语: 大部分程序员每天触摸的言语, 笼统程度最高, 大部分现代言语都简直彻底屏蔽了底层细节, 大部分高档言语都有相对高的可读性和可移植性, 如 Js,Java,C++,Rust 等
  • 汇编言语: 大部分程序员听说过但简直没见过的言语, 笼统程度居中, 简直能够直接触摸到硬件底层, 如直接操作寄存器、PC 等, 大部分汇编言语都有很强的渠道相关性, 移植性很差, 一般是针对不同的 CPU 设置不同的指令集, 如 ARM, Intel
  • 机器言语: 大部分现代程序员一辈子都不会看到的言语, 能被计算机直接识别并履行, 简直没有可读性和可移植性, 也简直没有笼统可言, 每一条机器指令都是对具体硬件的极为具体的操作

代码怎样运作起来的

代码是任务履行流程的高档笼统, 程序员通过书写代码, 来指示计算机履行自己希望履行的任务, 举个现实生活中的比方就相似我们是主人, 而计算机是家丁, 主人需求通过言语来指挥家丁履行自己的指令

而这个过程中一个很为难的点在于, 这个家丁往往只能听懂机器言语, 而现代主人一般都是说高档言语, 这就意味着言语不通

解决方案便是引进编译器作为翻译官, 编译器会将程序员书写的高档言语翻译为计算机能够直接履行的机器言语

关于以上这句话进行注解

编译器其实一般不会直接编译到机器言语, 而是发生对应渠道的汇编, 再凭借操作系统自带的汇编器进行履行 汇编器本质上也便是编译器, 能够将汇编言语编译到机器言语 此外也有其他方案, 比方编译到 C, 再凭借简直大部分系统都自带的 C 编译环境去直接编译 可是究其底子, 也仍是需求编译到机器言语计算机才能够直接履行

编译器分类

以下分类粗略的依照是否直接发生编译产品为规范分类为编译器和解说器, 不考虑其他分类方法

编译器(Compiler)

此处的编译器是真编译器, 会将输入的源代码编译后发生能够直接履行的方针代码文件, 如 gcc

解说器(Interpret)

此处的解说器一般对应脚本言语, 谨慎的说解说器应该是一边解说一边运转, 逐行分块的将源代码翻译并履行, 换言之解说器是走一步算一步, 翻译一句履行一句, 不会发生额外产品

可是个人认为若是依照这个界说的话, 只有 shell 这样的纯纯脚本言语才算得上是真正的解说履行, 由于程序员们常用的脚本言语比方 python Js 等, 都会在履行之前预先扫描一遍全体文件, 并发生一个渠道无关的中间代码方式, 这个中间代码方式无法被计算机直接履行, 需求在运转时凭借虚拟机来进行解说

Compiler & Interpret

此处举个比方来描绘两者的差异, 假定场景为某个只会英语的人想读一篇彻底由中文撰写的文章

  • Compiler: 文书翻译, 翻译人员拿到中文文章, 一次性将一切内容翻译完, 发生翻译过后的产品, 即一篇由英文编写的文章
  • Interpret: 实时翻译, 翻译人员先大致看一眼中文文章内容, 大致熟悉文章, 接着看一行翻译一行, 实时进行翻译作业, 不会发生英文译本

从上面比方也能够看出两者的特点, 一般情况下, 相对的:

  • Compiler: 履行高效, 渠道相关性强, 可移植性弱(运转时虚拟机开支小, 直接发生的机器码渠道相关性太强, 不便于移植)
  • Interpret: 履行低效, 渠道相关性弱, 可移植性强(运转时虚拟机开支大, 能够由虚拟机来兼容不同 CPU 架构, 便于移植 )

编译流程

以下将编译流程简略截至生成方针代码为止, 省略后续链接等步骤

Rust 实现一个表达式 Parser(1) 前置干货

预处理

  • 输入: 字符流(源文件)
  • 输出: 字符流

预处理进行的只是简略的文本替换作业, 会进行一些简略作业, 比方宏展开, 注释删除等等

词法剖析

  • 输入: 字符流
  • 输出: Token 流

词法剖析阶段需求从源文件字符流中识别出一个一个的 Token 并组成 Token 流供下一阶段使用, Token 指的是在语法中不行进一步切割的语法单元, 具体说明便是若是再切割就会损失语义

如 Hello World 切割为 H,e,l,l,o,(空格) 等字符, 每个单元都损失了语义, 无法理解是什么意思, 因此应该将每个单词作为一个 Token, 切割为 Hello,(空格),World 三个 Token, 这样就能够得知语义是 你好 国际

语法剖析

  • 输入: Token 流
  • 输出: IR

语法剖析阶段会测验将 Token 流处理为能够表明语义的某种中间成果, 作为后续处理的根底, 在这个过程中会进行语法查看, 若是不符合语法要求的不合法输入, 则会直接报错

这儿的 IR 是”中间表明” Intermediate Representation 的缩写, 不过语法剖析的输出一般都是 AST(Abstract Syntax Tree) 笼统语法树

例如, 表达式 1 + 2 + 3, 其 AST 如下

Rust 实现一个表达式 Parser(1) 前置干货

值得一提的是, 形似许多言语的一些有意思的 feature 都是在这一步完成后进行的

比方 Rust 的生命周期查看和一切权查看, 还有大部分言语的静态类型查看

由于这一步一般解析出 AST, 会保存最多的语义信息, 到后边进行优化时, 若转化成某些特别的 IR 可能会形成语义的损失

代码优化

  • 输入: IR
  • 输出: IR

这一阶段会进行很多很多的代码优化作业, 也是现在学术界首要研讨方向之一, 毕竟这是个无底洞, 简直能够无止尽的优化下去, 这一部分可能会发生很多不同种类的 IR, 可能会针对某种特定的优化手法发生 IR

举例如

  • 常量折叠
  • 循环优化
  • 尾递归优化

这儿是天坑, 现在本人了解较少, 且项目不包含这一步骤, 因此就简略略过

方针代码生成

  • 输入: IR
  • 输出: 字符流(编译最终产品)

这一阶段的方针便是发生方针代码, 根据不同的需求, 这儿发生的所谓”方针代码”存在很大差异

比方这个专栏要完成的 tiny-expr-parser 最终方针代码是格式化过后的表达式字符串, 而像 gcc 在编译阶段发生汇编代码, 在汇编阶段发生二进制机器代码

在这个阶段一般会进行一些渠道相关性很强的优化作业, 比方寄存器分配优化, 流水线操控等等, 这儿也是现在的首要研讨方向之一, 水很深

这儿常见的 IR 有经典的三地址编码TAC(Three Address Code) 和 LLVM IR

编译使用

编译作为高笼统->低笼统的垂直电梯, 配合各种强壮的 IDE , 作业过程一般是无感的, 用计算机领域的词汇来形容的话便是”对程序员通明”, 但实际上编译原理的使用不只在于”完成一个编译器”, 在日常出产的各种地方都能够发现他的使用

  • 代码剖析工具
    • 对代码进行静态查看, 能够在正式运转之前提早知晓部分问题, 比方编码格式上的问题或部分 bug
    • 如 Js 的 ESlint, Java 的 FindBugs 等
  • 格式化工具
    • 对代码进行格式化
    • 如 Prettier
  • DSL(Domain Specific Language)
    • 为某些领域专门完成的言语
    • 如 SQL, Regex, JSX 等