[PHP知识库]Go编译原理系列1（编译原理概览）

前言

获取pdf版，请评论区留言

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

图片来源：《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)的数据结构中。符号表将和中间表示形式一起传送给编译器后端部分

编译器后端

编译器后端部分根据中间表示和符号表中的信息来构造用户期待的目标程序

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

词法分析

词法分析的任务是从左往右逐行扫描源程序的字符，识别出各个单词，确定单词的类型（词素）。将识别出的单词转换成统一的机内表示———词法单元(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>

经过词法分析之后，赋值语句（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

关于这里边语法分析器如何根据语法规则为输入的源程序构造分析树？这个需要详细的了解编译原理中的文法相关规则，这里不深入的去研究，感兴趣的自己看编译原理这本书的第四章。语法解析器在进行语法扫描的时候，用到的是自顶向下的递归下降算法，实现无回溯的高效语法扫描

💡 意外收获：碰巧上周刷LeetCode中二叉树的一道题，就遇到了借助编译原理中的文法规则+递归下降算法进行解题：高频算法面试题（四十六）- 二叉树的序列化与反序列化

语义分析

语义分析器

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

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

对于声明语句来说，语义分析的主要任务就是，收集标识符的属性信息。一个标识符的属性有：

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

假设有这么一段代码

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

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

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

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

语义检查

语义分析的一个重要部分是语义检查

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

程序设计语言可能允许某些类型转换，这被称为自动类型转换(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里边的程序块，要么是一个函数，要么是函数中由大括号分隔的一部分）都会有自己的符号表，这个块中的每个声明都在此符号表中有一个对应的条目。这种方法对其他能够设立作用域的程序设计语言构造同样有效。例如，每个类也可以拥有自己的符号表，它的每个域和方法都 在此表中有一个对应的条目

词法分析详解

词法分析器的作用

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

可以通过下边这个图了解词法分析器和语法分析器的交互过程。通常，交互是由语法分析器调用词法分析器来实现的。图中的命令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语言设计与实现 - 编译原理
• 编译原理（哈工大）