编译原理（龙书）阅读笔记1：绪论上

引

前段时间买了三本书，本篇的主角编译原理也就是龙书、信息论基础和编码这三本。正好最近毕设做的差不多了，论文定稿也完成了，接下来准备慢慢读一读这三本书。不过有一说一，这种东西的难度对我来说还是略微高了一点，所以准备开一个系列来简单记录一下我的读书笔记，这个系列更新会非常非常缓慢。

今天简单看了一下龙书的第一章引论的前几节，因此本篇笔记主要记录引论中的内容。在开始之间，这里援引书中原话，“研究编译器的编写将涉及程序设计语言、计算机结构体系、形式语言理论、算法和软件工程”。所以希望我已经做好了心理准备。

语言与语言处理器

继电器与数字电路

我们都知道，香农发表的有史以来最为重要的硕士论文《继电器与开关电路的符号分析》中，为我们阐释了如何通过布尔代数描绘开关继电器状态，论证了数字计算机及数字线路逻辑设计的可能性，为后世利用电位状态设计的二进制计算机打下了基础。

学过数字逻辑电路设计的我们都知道，无论是用于计算的以加法器为核心的ALU单元，还是以触发器为核心设计的寄存器，他们都是由最基本的逻辑门构成，而逻辑门正是开关继电器的组和。因此，我们的数据无论是保存还是计算均是由电位状态所表示，而为了人类进行理解，则赋予其1与0的表征。

指令与语言

因此，我们必须要理解，程序设计中我们所写的代码计算机并没有办法直接进行运行，需要通过编译器来将我们的代码编译成为计算机可以理解的语言计算机才能正确地执行，这里计算机能够理解的语言并不是我们前文提到的0与1，而是指令。CPU指令分为两种，一是机器指令，二是汇编指令。

机器指令是CPU能够直接识别的唯一的“语言”，它是在CPU设计中就规定好的一套指令方案。而将大量的指令总结起来，所形成的就是我们所谓的指令集，我们常说的包括x86在内的CISC复杂指令集与包括ARM在内的RISC精简指令集都属于这一范畴。

然而，由于机器指令是由二进制编码的形式构成，并不利于人类理解与开发，因此诞生了汇编指令。汇编指令以指令助记符的形式使用，例如ADD加法指令。汇编指令与机器指令一一对应，是一般开发者所能接触并使用的最底层的语言。

然而，哪怕是汇编语言，学习成本与使用难度依旧十分巨大，在这样的因素影响下，更高级的语言应运而生，如C语言，Java语言甚至更高级的Python语言等。这些高级语言计算机并不能直接理解，因此需要一些手段辅助我们将这些语言转换为计算机可以理解的语言，这就是语言处理器的作用。

语言处理器

常见的语言处理器分为两种，一种是编译器，另一种是解释器。

编译器的本质是一个程序，他的作用就是将一种语言所编写的代码翻译成另一种语言，比如汇编，代码届的DeepL了属于是。当然，它也具有在翻译过程中找到源代码错误的功能。

而另一种语言处理器则是解释器，像我们常用的Python就是典型的解释型语言，它不需要预先将源代码进行编译形成汇编，他的编译是实时的，将源代码放入解释器，解释器逐行对源码进行翻译并运行。

一般来说，编译器编译出的程序运行速度更快，因为编译后的程序一般是CPU可以直接理解的，而解释器运行的时候需要先翻译，在运行，因此就会略慢。不过，解释器执行的过程中更直观，对开发者更为友好，就需要我们做出相应的取舍了。

除此之外，我们也会将两者结合起来，比如Java语言。我们首先使用javac编译器将Java源代码翻译成相对容易理解的字节码语言，在运行的时候通过JVM虚拟机这一解释器对字节码进行翻译运行，这样效率会比单独的解释器更高，同时也相对容易理解。

编译器结构

我们理解的编译器究竟是什么，现在，我们要对一个编译器进行拆解，了解一下编译器在运行的过程中到底进行了什么样的工作。

其实，整个翻译的流程分为两个大步，分别是分析和综合。分析就是将源程序分解成各个小的组成元素，并在元素之间构建语法结构，同时要按照一定规则对语法结构进行检查，是否是符合语言规定，如果不符，则要抛出相关错误供开发者对源程序进行修改。此外，分析还要将源程序信息存储在符号表中。综合则是利用分析构成的中间结构与符号表构造源代码对应的翻译后的程序。

一般，在编译器设计中，分析流程被称为编译器的前端，而综合被称为后端。

而对其进行展开，整个编译流程则包含词法分析，语法分析，语义分析，中间代码生成，和最终代码生成这几大阶段。

词法分析

词法分析是编译器执行的第一步，又被称作扫描，它将源代码作为字符流读入，形成词素序列，并将词素通过词法分析器产生语法单元，其结构为<token,value>。其中，token是后续语法分析中所使用的抽象符号（可以理解为一个由词法分析器生成的ID），value为词法单元条目数，可以理解为符号表中的映射关系。我在以前讲C语言的时候就提到过，无论是符号，变量名，保留字，其在编译是都叫做词素。

比如以下C代码，

a=10+b;

利用词法单元进行表示就是<id,1><=><10><+><id,2>，同时，在符号表中，第一行内保存a，第二行内保存b，其用于保存对词素与语法单元的映射。

同时，由于等号不需要属性值，因此不需要将该词素保存到符号表中，而10则涉及到了数字词法单元的表示，此部分在第二三章中，因此这里不展开。

语法分析

我们通过词法分析将代码转换为了词法单元与符号表，接下来我们需要对其进行解析，一般最常见的，解析过程将第一步的词法单元转换为一颗语法树，树的每一个节点表示一种运算，子节点则为运算的分量。

因此，上面的赋值语句可以转换为以下树：

语义分析

在构建好语法树后，利用语义分析器对其与符号表中的信息检查经过解析后的语义是否与源代码一致。同时，还会对变量常量等类型进行收集，并将其存放到树或符号表中。

其中，类型检查是语法分析中一个重要的步骤，编译器会对每个运算符的分量进行检查，检查其运算分量是否合法、符合运算类型，如果不符合类型要求，比如在C语言中使用非整型变（常）量作为数组角标，如a['a']，语义分析器则会抛出相关错误。

同时，根据语言的不同，语言可能支持自动类型转换，语义分析器也负责将类型进行转换。比如浮点数与整数之间进行的运算，则会将双方转换为浮点数。

中间代码生成

中间表示是一个源代码被翻译为另一个源代码的过程中，采用的一种中间状态代码形式。上面提到的语法树就是一种中间表示形式。

除了语法树外，很多编译器会生成一个明确的低级或类机器语言的中间表示，它不是我们最终要生成的代码翻译，但是可以理解为一个抽象的机器语言。

它应该具有易于生成，容易翻译成目标语言的特性。

代码优化生成

中间代码中可能拥有一些与机器指令无关的修饰代码，为了最终生成的目标语言代码能达到最快最优，代码优化器会首先对中间代码进行优化，删掉无实际含义的代码，转义一些可以在编译流程中简化的步骤，比如上面的将整型10转换的inttofloat，可以在这一步直接替换为10.0。

在完成优化后，将最简中间代码作为源程序，一一映射入目标语言，形成翻译后的代码。如果目标语言是机器码，在代码生成的时候还必须为每个变量指定寄存器或内存位置，因此，一个好的编译器应该合理地对内存进行分配。

符号表管理与步骤组合

除了以上过程之外，编译器还应记录源程序使用的变量名，并收集其相关的各种属性，包括类型，作用域，存储分配等，此外，还应包括参数类型、数量，传值与返回值等信息。这些信息都应存储在符号表中。

而对于编译流程，以上流程是一个完整编译器的逻辑组织方式，但是，特定情况下可以将多个步骤整合起来，形成为趟，这样，我们就可以针对特定情境编写编译器，并针对该组合进行特定优化。

总结

绪论部分主要讲述了一个编译器的整体工作流程，还未涉及到具体的工作原理，因此难度并不大。但是需要理解编译器的功能，以及其整体工作流程，我们才能更深刻地理解其不同部分采用的算法的意义。因此本篇特此将绪论部分较为重要的内容进行记录并以我自己的语言表述出来。

绪论后面还有一部分内容，太晚了，所以在此先分段，剩余的部分之后再进行补充。

本篇内容为原创内容，采用CC BY-NC-SA 4.0协议许可
2022-05-20 00:35
UtopiaXC
于大连