前言

Go 编译原理系列文章，试图深刻的搞清楚 Go 文本文件（.go）被编译器编译的整个过程，也就是下边这十一个过程

关注公众号：IT 猿圈，后盾回复：Go 编译原理系列 1，可取得 pdf 版

图片起源：《Go 语言底层原理分析》

本系列文章会先从编译原理的角度，分享一下编译一门高级语言通常有哪些阶段，以及各个阶段在做什么；而后切回到 Go 编译器编译 Go 文本文件的过程，看它的编译过程有哪些本人独特的中央；最初，因为笔者对 PHP 语言也比拟相熟，会大抵分享一下 PHP 代码的解析与执行过程，刚好它是一门解释型语言，能够和 Go 这种编译型语言做个比照

长文 warning！！！

综上，这个系列文章会蕴含以下几个主题

1. 编译原理概览
2. 词法剖析 & 语法分析基础知识
3. Go 编译过程 - 词法剖析
4. Go 编译过程 - 语法分析
5. Go 编译过程 - 形象语法树构建
6. Go 编译过程 - 类型查看
7. Go 编译过程 - 变量捕捉
8. Go 编译过程 - 函数内联
9. Go 编译过程 - 逃逸剖析
10. Go 编译过程 - 闭包重写
11. Go 编译过程 - 遍历函数
12. Go 编译过程 -SSA 生成
13. Go 编译过程 - 机器码生成
14. PHP 代码的解释与执行 - 词法 & 语法分析
15. PHP 代码的解释与执行 -opcode
16. PHP 代码的解释与执行 -Zend
17. 编译型语言和解释型语言比照
18. 总结

为防止内容过于干燥，相干中央会尽量画图

传统编译器的编译阶段介绍

咱们晓得一门高级语言编写的代码，能够被咱们本人看懂，然而计算机看不懂。因而，它首先须要被翻译成一种可能被计算机执行的模式。实现这项翻译工作的软件系统，统称为 编译器（compiler）

而编译原理，其实介绍的就是设计和实现编译器的办法。编译器设计的原理和技术，还能够利用于编译器设计之外的很多畛域

最相熟的就比方 PHP 中会用到 模板引擎实现界面设计与代码的拆散，模板引擎对模板进行编译，造成可执行的 PHP 代码。如果你理解编译技术，会更容易把握这些模板引擎，甚至写出更合乎畛域需要的模板引擎

还有像数据库软件、大数据平台，都会用到编译原理中的思维。所以，学习编译原理并不是为了写一个编译器，学习其它计算机根底的货色，也是雷同的情理

语言处理器

这部分次要是分享编译器、解释器是什么？以及将源程序翻译成指标机器的代码，两头还可能波及哪些过程？以及这些过程都干了什么？

编译器

编译器其实就是一个程序，宏观上说，它能够浏览某一种语言（源语言）编写的程序，并把该程序翻译成为一个等价的、用另一种语言（目标语言）编写的程序

留神：如果目标程序是一个可执行的机器语言程序，那么它就能够被用户调用，解决输出并产生输入

解释器

解释器 （interpreter）是另一种常见的语言处理器，它并不通过翻译的形式生成目标程序。从用户的角度看， 解释器间接利用用户提供的输出，执行源程序中指定的操作。在把用户输出映射成输入的过程中，由一个编译器产生的机器语言目标程序，通常比解释器快很多。然而，解释器的错误诊断成果，通常比编译器更好，因为它一一逐句地执行程序

示例

Java 语言处理器联合了编译和解释过程。一个 Java 源程序首先被编译成一个称为字节码（bytecode）的两头示意模式。而后由一个虚拟机对失去的字节码加以解释执行。这样安顿的益处之一是在一台机器上编译失去的字节码能够在另一台机器上解释执行。通过网络就能够实现机器之间的迁徙

为了更快地实现输出到输入的解决，有些被称为 即时 (just in time) 编译器 的 Java 编译器，在运行两头程序处理输出的前一刻，首先把字节码翻译成为机器语言，而后再执行程序

除了编译器之外，创立一个可执行的目标程序，还须要一些其它的程序。比方一个源程序可能被宰割成多个模块，并存放在不同的文件中。把源文件聚合在一起的工作，通常由一个称为 预处理器（preprocessor）的程序实现。预处理器的职责还负责把那些称为宏的缩写模式转换成源语言的语句（C、C++）

而后，将通过预处理的源程序作为输出传递给一个编译器。编译器可能产生一个汇编语言程序作为其输入，因为汇编语言比拟容易输入和调试。而后，这个汇编语言程序由称为 汇编器 （assembler）的程序进行解决，并生成 可重定位的机器代码

汇编器生成的机器代码，在内存中寄存的起始地位不是固定的，代码中的所有地址，都是绝对于这个起始地位的绝对地址。起始地址 + 绝对地址 = 相对地址（对于什么是可重定位的机器代码能够参考这篇文章）

大型程序常常被分成多个局部进行编译，因而，可重定位的机器代码要和其余可重定位的指标文件以及库文件链接到一起，造成真正在机器上运行的代码。一个文件中的代码可能指向另一个文件中的地位，而 链接器 （linker）可能解决内部内存地址的问题（内部内存地址，是指，一个文件中的代码，可能会援用另外一个文件中的数据对象或过程，这些数据对象的地址或过程地址，绝对于以后文件来说，就是内部内存地址）。最初， 加载器（loader）把所有的可执行指标文件放到内存中执行

一个编译器的构造

这部分就是大抵分享编译器的编译过程有哪几步？以及每步在做的事件。这部分可能会偏实践，然而我会尽量的联合示例，不便了解。并且会在一些设计算法或者设计的中央，分享它们在日常工作中的一些场景

编译器构造概览

下边这个示例参考：编译原理（哈工大）

编译器是如何将一个高级的语言程序，翻译成机器语言程序的？能够看一下咱们是如何人工的将英语翻译成汉语的

In the room, he broke a window with a hammer

这句英语就能够了解成是源语言，汉语就是目标语言。咱们翻译的过程，大抵分为两步

通过剖析源语言来取得句子的语义过程，就是 语义剖析。语义剖析通常是从划分句子成分开始，首先是抓住句子的外围谓语动词，因为谓语动词的意思晓得了，句子的一半意思就晓得了。上边这句的谓语动词就是 broke（打），晓得打这个动作，咱们就会想晓得，是谁施行了打这个动作？谁是被打的对象？用什么打的？为什么打？打的后果如何等等

这些都能够通过剖析 broke 的上下文来取得。上边的句子中，broke 采纳的是被动语态，所以它的主语 he，就是动作的实事者，宾语 window 就是动作的受事者。反过来，如果 broke 采纳的是被动语态 be broken，那它的主语 he 就是动作的受事者

with a hammer 是补语，示意动作应用的工具，in a room 是状语，示意动作产生的地点。这样，咱们就能够剖析出 broke 前后的这些名词性成分同谓语动词 broke 之间的语义关系（这其实就是咱们进行语义剖析的过程）。比方下图

图地方的节点，示意句子中形容的打这个动作，四周的四个节点，对应着句子中的实体，别离是：he、window、hammer、room。从两头的结点，到四周的四个节点，别离引出了四条边，边上的信息示意这些实体同外围谓语动词之间的一一对应关系，其中 he 是动作的实施者 agent，window 是动作的受事者 object，hammer 是动作采纳的工具 tool，room 是动作产生的地点 location

针对这个图的意思，用汉语翻译就是：在房间里，他用锤子砸了一扇窗户 。这样就实现了翻译的过程。上边的图，就是一种 两头示意 ， 它独立于具体的语言，也就是说，英语能够用这个图示意，汉语也能够用这个图示意，日语、法语、意大利语都能够。有了这个图，不论目标语言是什么，都能够用这个图来翻译。所以两头示意很重要，它起到桥梁的作用

依据上边的剖析能够晓得，要想进行语义剖析，首先要划分句子成分。咱们晓得，主语和宾语通常是由名词短语形成的，状语和补语通常由介词短语形成的，因而，要想划分句子成分，就须要辨认出句子中的各类短语，这一过程称为 语法分析。要想辨认句子中的各类短语，就须要晓得词性

比如说一个冠词 + 一个名词，能够以形成一个名词短语，一个代词自身，也能够形成一个名词短语。因而，要想辨认句子中的各类短语，要害是要确定句子中各个单词的词性，这一过程就是 词法剖析

综上，咱们就能够晓得，要翻译一个句子，首先须要进行词法剖析，才词法剖析的根底上进行语法分析，而后进行语义剖析，也就是说，具体的翻译步骤就是，首先进行词法剖析，剖析出句子中各个单词的词性

而后进行语法分析

而后是语义剖析，依据句子的构造剖析出各个短语在句子中充当什么成分，从而确定各个名词性成分，和外围谓语动词之间的语义关系

最初失去两头示意模式

编译器的编译过程，也是经验了以上几个阶段

词法剖析、语法分析、语义剖析、两头代码生成，组成 编译器前端 ，它与源语言相干。代码指标代码生成、机器相干代码优化，组成 编译器后端，它与目标语言相干

咱们能够把编译器看做是一个黑盒子，它能够把源程序映射为在语义上等价的目标程序。在这个映射的过程中，分为两个组成部分：编译器前端 和编译器后端

编译器前端

编译器前端把源程序合成成为多个组成因素，并在这些因素之上加上 语法结构 。而后， 应用这个构造来创立该源程序的一个两头示意 。如果编译器前端局部查看出源程序没有依照正确的语法形成，或者语义上不统一，它就必须提供有用的信息，使得用户能够按此进行改过。编译器前端局部还会收集无关源程序的信息，并把信息寄存在一个称为 符号表 (symbol table) 的数据结构中。符号表将和两头示意模式一起传送给编译器后端局部

编译器后端

编译器后端局部依据两头示意和符号表中的信息来结构用户期待的目标程序

<aside>
💡 Tips：有些编译器在前端和后端之间有一个与机器无关的优化步骤。这个优化步骤的目标是在两头示意之上进行转换，以便后端程序可能生成更好的目标程序。优化是可选的

Tips：上边的这些阶段是编译器的逻辑组织形式，在实现的过程中，多个阶段，可能会被组合在一起。比方语义剖析的后果，通常间接示意成中间代码的模式，所以这两个阶段通常是放在一起实现的

</aside>

词法剖析

词法剖析的工作是从左往右逐行扫描源程序的字符，辨认出各个单词，确定单词的类型（词素）。将辨认出的单词转换成对立的机内示意———词法单元 (token) 模式

〈token-name, attribute-value〉 < 种别码，属性值 >

这个词法单元被传送给下一个步骤，语法分析。在这个词法单元中

• token-name：这个就示意辨认出的单词的种别。比方自然语言中，每一个单词都有一个词性。程序设计语言中的单词，基本上有下表中的几种类型

关系运算符（> < = ≠ ≤ ≥）
逻辑运算符（& | ~）| 一词一码
或
一型一码 | 当时可确定 |
| 5 | 界线符 | ; () {} … | 一词一码 | 当时可确定 |

• attribute-value：指向符号表中对于这个词法单元的条目。符号表条目标信息会被语义剖析和代码生成步骤应用

将下边这个语句进行词法剖析之后，失去的后果
for(i:=0;i<10-2.5;i=i-1){println(i)}

1      for      < _For, - >
2      (        < _Lparen, - >
3      i        < _Name, addr >
4      :=       < _Define, - >
5      0        < INT, addr>
6      ;        < _Semi, - >
......

语法分析

语法分析器从词法分析器输入的 token 序列中辨认出各类短语，并结构语法分析树

假如一个源文件中蕴含下边这个赋值语句

position = initial + rate * 60（1.1）

这个赋值语句中的字符能够组合成如下词素（单词类型），并映射成为如下词法单元。这些词法单元将被传递给语法分析阶段

1. position 是一个词素，被映射成词法单元 <id, 1 >，其中 id 是示意 标识符 (identifier) 的形象符号 ，而 1 指向符号表中 position 对应的条目。一个标识符对应的符号表条目寄存该标识符无关的信息，比方它的名字和类型
2. 赋值符号 = 是一个词素，被映射成词法单元〈=〉。因为这个词法单元不须要属性值，所 以咱们省略了第二个重量。也能够应用 assign 这样的形象符号作为词法单元的名字，然而为了 标记上的不便，咱们抉择应用词素自身作为形象符号的名字
3. initial 是一个词素，被映射成词法单元<id, 2 >，其中 2 指向 initial 对应的符号表条目
4. + 是一个词素，被映射成词法单元 <+>
5. rate 是一个词素，被映射成词法单元 <id, 3 >， 其中 3 指向 rate 对应的符号表条目
6. • 是一个词素，被映射成词法单元 <*>
7. 60 是一个词素，被映射成词法单元 <60>

<aside>
💡 Tips：分隔词素的空格会被词法分析器疏忽掉

</aside>

通过词法剖析之后，赋值语句（1.1）被示意成如下的词法单元序列

**<id, 1> <=> <id, 2> <+> <id, 3> <*> <60>**（1.2）

在这个示意中，词法单元名 =、+ 和 别离是示意赋值、加法运算符、乘法运算符的形象符号（比方在 Go 语言中，=、+、的形象符号别离是_Assign、_Operator）

从图中能够看出，一个标识符或者一个常数自身，能够形成一个表达式，一个表达式加上另一个表达式、或乘上另一个表达式，能够形成一个更大的表达式。一个标识符，连贯一个赋值号，再连贯上一个表达式，能够形成一个赋值语句

编译器的后续步骤应用这个语法结构来帮忙剖析源程序，并生成目标程序

（下边这个图，你能够先不看）

变量申明语句的分析树

文法（文法是由一系列的规定形成的）：

<D> →  <T><IDS>;
<T> → int | real | char | bool
<IDS> → id | <IDS>, id

D：是 declaration 的首字母，申明的意思，示意申明语句
T：是 type 的首字母，类型的意思，示意类型
IDS：是 Identifier Sequence 的缩写，示意标识符序列

因而，从上边的第一条规定能够看出，一个申明语句 D，是由一个类型 T 连贯上一个标识符序列和一个分号形成的。这里的 T 能够是 int 或 real 或 char 或 bool，所以上边第二条规定中的竖线，示意的是或。依据第三条规定能够看出，一个标识符 id 自身，能够形成一个标识符序列；一个标识符序列，连贯一个逗号，再连贯一个标识符 id，也能够形成一个标识符序列 IDS

依据这个文法，假如有这么一段代码

int a, b, c;

那依据上边的文法，就能够失去它的分析树

从 a 能够看出，一个标识符自身，能够形成一个标识符序列 IDS，一个 IDS 连贯一个逗号，再连贯一个标识符，能够形成一个更大的 IDS

对于这里边语法分析器如何依据语法规定为输出的源程序结构分析树？这个须要具体的理解编译原理中的文法相干规定，这里不深刻的去钻研，感兴趣的本人看编译原理这本书的第四章。语法解析器在进行语法扫描的时候，用到的是 自顶向下的递归降落算法，实现无回溯的高效语法扫描

<aside>
💡 意外播种：碰巧上周刷 LeetCode 中二叉树的一道题，就遇到了借助编译原理中的文法规定 + 递归降落算法进行解题：297. 二叉树的序列化与反序列化

</aside>

语义剖析

语义分析器

语义分析器 (semantic analyzer) 应用语法树和符号表中的信息来查看源程序是否和语言定义的语义统一。它同时也收集类型信息，并把这些信息寄存在语法树或符号表中，以便在随后的两头代码生成过程中应用

高级语言程序中的语句，大体分为两类：申明语句 和可执行语句。在申明语句中，会申明一些数据对象或过程，并且为它们取名字，也就是标识符

对于申明语句来说，语义剖析的次要工作就是，收集标识符的属性信息。一个标识符的属性有：

• 种属：简略变量、复合变量（数组、map）、函数 ….
• 类型：整形、字符型、布尔型 …
• 存储地位、长度：程序中申明的数据对象和过程，都会为它在内存中调配一块存储空间，因而就会有存储地位和所需的内存空间的大小
• 值
• 作用域
• 参数和返回值信息：这个是针对函数的（参数个数、参数类型、参数传递形式、返回值类型等）

假如有这么一段代码

var x[8] int
var i, j int
......

语义分析阶段，收集的这些标识符的属性信息，都会寄存在一个称为符号表的数据结构中，每一个标识符，都对应符号表中的一条记录

符号表通常带有一个字符串表，用来存放程序中用到的标识符和字符常数，这样就使 Name 分成了两个局部。一部分存标识符在字符串表中的起始地位，第二局部存标识符的长度（比方 SIMPLE 的长度是 6 个字符，标识符 SYMBLE 的长度也是 6 个字符，标识符 TABLE 的长度是 5 个字符）

<aside>
💡 Question：一个有意思的问题，符号表中为什么要设计字符串表这样一种数据结构？而不是将 Name 字符串，间接寄存在 Name 字段中？

</aside>

语义查看

语义剖析的一个重要局部是 语义查看

• 变量或函数未通过申明就应用
• 变量或函数名反复申明
• 运算重量的类型不匹配（比方数组的名字和函数的名字进行相加，当然也可能存在类型转换）
• 操作符与操作数之间的类型不匹配（数组的下标不是整数、函数调用的参数类型或数目不匹配）

程序设计语言可能容许某些类型转换，这被称为 主动类型转换(coercion)。比方，一个二元算术运算符能够利用于一对整数或者一对浮点数。如果这个运算符利用于一个浮点数和一个整数，那么编译器能够把该整数转换成为一个浮点数

在上边的图中，其实就存在主动类型转换，假如 position、initial 和 rate 已被申明为浮点数类型，而词素 60 自身是一个整数。语义分析器的类型检查程序发现运算符 * 被用于一个浮点数 rate 和一个整数 60。在这种状况下，这个整数能够被转换成为一个浮点数

两头代码生成

在把一个源程序翻译成指标代码的过程中，一个编译器可能结构出一个或多个两头示意。这些两头示意能够有多种形式。语法树 是一种两头示意模式，它们通常在语法分析和语义剖析中应用。还有一种就是 三地址代码

在源程序的语法分析和语义剖析实现之后，很多编译器生成一个明确的低级的或类机器语言的两头示意。咱们能够把这个示意看作是某个形象机器的程序。该两头示意应该具备两个重要的性质：它应该易于生成，且可能被轻松地翻译为指标机器上的语言

三地址代码

这种两头示意 由一组相似于汇编语言的指令组成，每个指令具备三个运算重量（最多三个）。每个运算重量都像一个寄存器。上图中的中间代码生成器的输入是如下的三地址代码序列

position = initial + rate * 60

t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3（1.3）

1. 每个三地址赋值指令的右部最多只有一 个运算符。因而这些指令确定了运算实现的程序。在源程序（1.1）中，乘法应该在加法之前实现
2. 编译器应该生成一个长期名字以寄存一个三地址指令计算失去的值
3. 有些三地址指令的运算重量少于三个(比方下面的序列（1.3）中的第一个和最初一个指令)

罕用的三地址指令（红色为指令操作符）

x = *y
*x = y | |

其实是 能够用源程序中的名字（也就是标识符）来作为三地址指令中的地址，因为每个标识符的地址都寄存在符号表中，所以通过名字就能够找到它们的地址。常量和编译器生成的长期变量也能够作为三地址指令的地址

三地址指令的示意

• 四元式
• 三元式
• 间接三元式

这里次要分享四元式，它长这样(op, y, z, x)，第一个重量，对应三地址指令中的操作符，后边三个重量代表三地址指令中的三个操作数

三地址指令的四元式示意

其实三地址指令的四元式示意模式，和前边的自然语言的两头示意模式有相似之处。比如说给定一个动作 打，那它就波及到施事者、受事者、工具、地点。在三地址指令中，操作符就相当于句子的外围谓语动词，操作数就相当于各个语义角色，只不过这里的操作数最多有三个

会发现除了赋值指令之外，每一个指令都只有一个操作符，也就是说只能实现一个动作。因而，一个三地址指令序列，惟一确定了运算的实现程序

两头代码生成示例

while a < b do
    if c < 5 do
        while x > y do
            z = x + 1;
    else x = y;

上边代码生成的分析树如下：

上边的分析树被翻译成中间代码就是这样

指令编号：指令   

100: (j<, a, b, 102)  // 条件跳转指令，j 是 jump 的缩写。意思就是，如果 a < b 就跳转到 102 号指令。否则就往下执行 101 号指令    
101: (j, -, -, 112)   // 无条件跳转指令，也就是跳转到 112 号指令（就跳出了整个 while 循环语句）102: (j<, c, 5, 104)  // 条件跳转指令，如果 c <5，跳转到 104 号指令，否则往下执行 103 号指令
103: (j, -, -, 110)   // 无条件跳转指令，也就是跳转到 110 号指令
104: (j>, x, y, 106)  // 条件跳转指令，如果 x >y，跳转到 106 号指令，否则往下执行 105 号指令
105: (j, -, -, 100)   // 无条件跳转指令，也就是跳转到 100 号指令
106: (+, x, 1, t1)    // 将 x 的值，加上 1，而后赋给 t1。而后往下执行 107 号指令
107: (=, t1, -, z)    // 将 t1 的值，赋给 z
108: (j, -, -, 104)   // 无条件跳转指令，也就是跳转到 104 号指令
109: (j, -, -, 100)   // 无条件跳转指令，也就是跳转到 100 号指令
110: (=, y, -, x)     // 赋值指令，将 y 的值，赋给 x。执行完之后，往下执行 111 号指令
111: (j, -, -, 100)   // 执行 110 号指令
112: 

对于编译器是如何依据分析树生成中间代码的，这个波及比拟多 文法 和上下文无关文法 等形象的概念以及规定表达式。我这里次要的目标是分享每个过程在做什么样的事件，没有深入研究实现。感兴趣的能够本人看一下《编译原理》的第六章

代码优化

机器无关的代码优化步骤，目标是改良中间代码，以便生成更好的指标代码。“更好”通常意味着更快，然而也可能会有其余指标，如更短的或能耗更低的指标代码。比方，一个简略间接的算法会生成中间代码（1.3）。它为由语义分析器失去的树形两头示意中的每个运算符都应用一个指令

应用一个简略的两头代码生成算法，而后再进行代码优化步骤是生成优质指标代码的一个正当办法。优化器能够得出结论：把 60 从整数转换为浮点数的运算能够在编译时刻一劳永逸地实现。因而，用浮点数 60.0 来代替整数 60 就能够打消相应的 inttofloat 运算。而且，t3 仅被应用一次，用来把它的值传递给 id1。因而，优化器能够把序列（1.3）转换为更短的指令序列

t1 = id3 * 60.0
id1 = id2 + t1（1.4）

不同的编译器所做的代码优化工作量相差很大。那些优化工作做得最多的编译器，即所谓的“优化编译器”，会在优化阶段花相当多的工夫。有些简略的优化办法能够极大地提高目标程序的运行效率而不会过多升高编译的速度

代码生成

代码生成器以源程序的两头示意模式作为输出，并把它映射到目标语言 。如果目标语言是机器代码，那么就 必须为程序应用的每个变量抉择寄存器或内存地位 。而后，两头指令被翻译成为可能实现雷同工作的机器指令序列。 代码生成的一个至关重要的方面是正当调配寄存器以寄存变量的值

比方（1.4）中的中间代码，能够被翻译成下边的机器代码（R1、R2 是寄存器）

LDF      R2,   id3
MULF     R2,   R2,  #60.0
LDF      R1,   id2
ADDF     R1,   R1,  R2
STF      id1,  R1（1.5）

每个指令的第一个运算重量指定了一个指标地址 。各个指令中的 F 通知咱们它解决的是浮点数。代码（1.5）把地址 id3 中的内容加载到寄存器 R2 中，而后将其与浮点常数 60.0 相乘。井号“#”示意 60.0 应该作为一个 立刻数 解决。第三个指令把 id2 挪动到寄存器 R1 中，第四个指令把后面计算失去并存放在 R2 中的值加到 R1 上。最初，在寄存器 R1 中的值被寄存到 id1 的地址中去

上面对代码生成的探讨疏忽了对源程序中的标识符进行存储调配的重要问题。实际上，运行时刻的存储组织办法依赖于被编译的语言。编译器在两头代码生成或代码生成阶段做出无关存储调配的决定

符号表治理

编译器的重要性能之一是记录源程序中应用的变量的名字，并收集和每个名字的各种属性无关的信息。这些属性能够提供一个名字的存储调配、它的类型、作用域（即在程序的哪些地方能够应用这个名字的值）等信息。对于函数名字，这些信息还包含：它的参数数量和类型、每个参数的传递办法（比方传值或传援用）以及返回类型

符号表数据结构为每个变量名字创立了一个记录条目。记录的字段就是名字的各个属性。这个数据结构应该容许编译器迅速查找到每个名字的记录，并向记录中疾速寄存和获取记录中的数据（疾速的获取和插入，你会想到哪种数据结构？）

符号表 (symbol table) 是一种供编译器用于保留无关源程序结构的各种信息的数据结构。这些信息在编译器前端阶段被逐渐收集并放入符号表，它们在编译器后端阶段用于生成指标代码。符号表的每个条目中蕴含与一个标识符相干的信息，比方它的字符串(或者词素)、它的类型、它的存储地位和其余相干信息。符号表通常须要反对同一标识符在一个程序中的多重申明

一个申明的作用域是指该申明起作用的那一部分程序。它将为每个作用域建设一个独自的符号表来实现作用域。每个带有申明的程序块（比方 C 里边的程序块，要么是一个函数，要么是函数中由大括号分隔的一部分）都会有本人的符号表，这个块中的每个申明都在此符号表中有一个对应的条目。这种办法对其余可能设立作用域的程序设计语言结构同样无效。例如，每个类也能够领有本人的符号表，它的每个域和办法都 在此表中有一个对应的条目

<aside>
💡 Tips：符号表条目是在分析阶段，由词法分析器、语法分析器和语义分析器创立并应用的

</aside>

词法剖析详解

词法分析器的作用

词法分析器的次要工作是读入源程序的输出字符、将它们组成 词素 ，生成并输入一个词法 单元序列 ，每个 词法单元 对应于一个词素。这个词法单元序列被输入到语法分析器进行语法分析。词法分析器通常还要和符号表进行交互。当词法分析器发现了一个标识符的词素时，它要将这个词素增加到符号表中。在某些状况下，词法分析器会从符号表中读取无关标识符品种的信息，以确定向语法分析器传送哪个词法单元

能够通过下边这个图理解词法分析器和语法分析器的交互过程。通常，交互是由语法分析器调用词法分析器来实现的。图中的命令 getNextToken 所批示的调用，使得词法分析器从它的输出中一直读取字符，直到它辨认出下 一个词素为止。词法分析器依据这个词素生成下一个词法单元并返回给语法分析器

词法分析器在编译器中负责读取源程序，它还会实现一些辨认词素之外的其它工作

• 过滤掉源程序中的正文和空白等
• 将编译器生成的谬误音讯与源程序的地位分割起来。例如词法分析器能够负责记录遇到换行符的个数，以便给每个出错音讯赋予一个行号
• 如果源程序应用了一个宏预处理器，则宏的扩大也能够由词法分析器实现

词法剖析和语法分析

把编译过程的剖析局部划分为词法剖析和语法分析阶段有如下几个起因

• 最重要的思考是简化编译器的设计。将词法剖析和语法分析拆散通常使咱们至多能够简化其中的一项工作。例如，如果一个语法分析器必须把空白符和正文当作语法单元进行解决，那 么它就会比那些假如空白和正文曾经被词法分析器过滤掉的处理器简单得多。如果咱们正在设计一个新的语言，将词法和语法离开思考有助于咱们失去一个更加清晰的语言设计方案（就很像网络分层）
• 进步编译器的效率。把词法分析器独立进去使咱们可能应用专用于词法剖析工作、不进行语法 剖析的技术。此外，咱们能够应用专门的用于读取输出字符的缓冲技术来显著进步编译器的速度（也是网络分层的起因之一）
• 加强编译器的可移植性。输出设施相干的特殊性能够被限度在词法分析器中

词法单元、模式、词素

• 词法单元由一个词法单元名和一个可选的属性值组成。词法单元名是一个示意某种词法单位的形象符号（在 2.2.1 的词法剖析局部有阐明，比方 Go 语言中，赋值符号 = 的形象符号是_Assign），比方一个特定的关键字，或者代表一个标识符的输出字符序列。词法单元名字是由语法分析器解决的输出符号。通常应用词法单元的名字来援用一个词法单元
• 模式形容了一个词法单元的词素可能具备的模式。当词法单元是一个关键字时，它的模式就是组成这个关键字的字符序列。对于标识符和其余词法单元，模式是一个更加简单构造，它能够和很多符号串匹配（其实我感觉就能够了解成正则表达式的模式串，依据模式匹配不同类型的词素，比方匹配变量名这类词素、匹配表达式符号这类词素，他们的模式是不一样的）
• 词素是源程序中的一个字符序列，它和某个词法单元的模式匹配，并被词法分析器辨认为该词法单元的一个实例（这个很好了解，就是看源程序中的每个词素能和那个模式匹配，如果和某个词法单元的模式匹配，就辨认为该词法单元的一个实例）

示例

下图中给出了一些常见的词法单元、非正式形容的词法单元的模式，并给出了一些示例词素。用下边这个示例来阐明上边几个概念是如何利用的。假如有这么一个 C 语句

printf("Total = %d\n", score);

图片起源：《编译原理》

printf 和 score 都是和词法单元 id 的模式匹配的词素，而 ”Total = %d\n” 则是一个和 literal 匹配的词素

在很多程序设计语言中，上面的类别笼罩了大部分的词法单元：

1. 每个关键字有一个词法单元。一个关键字的模式就是该关键字自身
2. 示意运算符的词法单元。它能够示意单个运算符，也能够像上图中的 canparison 那样，示意一类运算符
3. 一个示意所有标识符的词法单元
4. 一个或多个示意常量的词法单元，比方数字和字面值字符串
5. 每一个标点符号有一个词法单元，比方左右括号、逗号和分号

词法单元的属性

如果有多个词素能够和一个模式匹配，那么词法分析器必须向编译器的后续阶段提供无关被匹配词素的附加信息。例如，0 和 1 都能和词法单元 number 的模式匹配，然而对于代码生成器而言，至关重要的是晓得在源程序中找到了哪个词素。因而，在很多状况下，词法分析器不仅仅向语法分析器返回一个词法单元名字，还会返回一个形容该词法单元的词素的属性值。词法单元的名字将影响语法分析过程中的决定，而这个属性则会影响语法分析之后对这个词法单元的翻译

假如一个词法单元至少有一个相干的属性值，当然这个属性值可能是一个组合了多种信息的结构化数据。最重要的例子是词法单元 id，咱们通常会将很多信息和它关联。一般来说，和一个标识符无关的信息——例如它的词素、类型、它第一次呈现的地位（在收回一个无关该标识符的谬误音讯时须要应用这个信息）都保留在符号表中。因而，一个标识符的属性值是一个指向符号表中该标识符对应条目标指针

词法谬误

如果没有其余组件的帮忙，词法分析器很难发现源代码中的谬误。比方，当词法分析器在解决下边这个 C 程序片断时，就会有问题

fi（a == f(x)）

第一次遇到 fi 时，它无奈指出 fi 到底是关键字 if 的误写还是一个未声明的函数标识符。因为 fi 是标识符 id 的一个非法词素，因而词法分析器必须向语法分析器返回这个 id 词法单元，而让编译器的另一个阶段（在这个例子里是语法分析器）去解决这个因为字母颠倒而引起的谬误

然而，假如呈现所有词法单元的模式都无奈和残余输出的某个前缀相匹配的状况，此时词法分析器就不能持续解决输出。当呈现这种状况时，最简略的谬误复原策略是“恐慌模式”复原。从残余的输出中一直删除字符，直到词法分析器可能在残余输出的结尾发现一个正确的词法单元为止。这个复原技术可能会给语法分析器带来凌乱

可能采取的其余谬误复原动作包含：

1. 从残余的输出中删除一个字符
2. 向残余的输出中插入一个脱漏的字符
3. 用一个字符来替换另一个字符
4. 替换两个相邻的字符

这些变换能够在试图修复谬误输出时进行。最简略的策略是看一下是否能够通过一次变换将残余输出的某个前缀变成一个非法的词素。这种策略还是有情理的，因为在实践中，大多数词法谬误只波及一个字符。另外一种更加通用的改过策略是计算出起码须要多少次变换才可能把 一个源程序转换成为一个只蕴含非法词素的程序。然而在实践中发现这种办法的代价太高，不值得应用

参考资料

• 《Go 语言底层原理分析》- 第一章
• 《编译原理》
• 编译原理之美 – 极客工夫
• Go 语言设计与实现 – 编译原理
• 编译原理（哈工大）