再看编译原理

编译器

编译器也是个程序，可以阅读某一种语言（源语言）编写的程序，并把该程序翻译为一个等价的，用另一种语言（目标语言）编写的程序。

即，输入源程序，输出目标程序的程序，能够把源程序映射为语义等价的目标程序：

       编译器
源程序 -------> 目标程序

源程序一般是可读性较好的字符串，目标程序则有多种形式：

• 机器码，例如C语言编译得到可执行的二进制程序
• 中间字节码，例如Java编译得到面向JVM的.class文件
• 字符串，例如经Babel转过的JavaScript代码

其实就是翻译，比如从字符串编译到机器码，就是把人能理解的代码语言翻译成机器能“理解”（识别执行）的机器语言，然后用户借助目标程序就可以与机器交互了：

         目标程序
用户输入 ---------> 输出

P.S.与编译器很像的是解释器，区别在于没有生成目标程序的环节：

                 解释器
源程序 & 用户输入 -------> 输出

运行时解释执行，所以解释型语言的运行效率一般要低于编译型语言

编译过程

分为两部分：

• 分析：把源程序拆分成多个部分，再加上语法结构，生成中间表示形式与符号表（symbol table）
• 合成：根据中间表示形式及符号表来构造目标程序

典型编译器的处理步骤如下：

（输入）字符流
|
|- 词法分析器（lexer）
|  （生成）符号流
|  （生成）符号表
|- 语法分析
|  （生成）语法树
|- 语义分析
|  （生成）语法树
|- 中间代码生成器
|  （生成）中间表示形式
|- 机器无关代码优化器
|  （生成）中间表示形式
|- 代码生成器
|  （生成）目标机器语言
|- 机器相关代码优化器
v
（输出）目标机器语言

其中，主要步骤是词法分析，语法分析，语义分析，以及代码生成，而中间代码生成和两步优化是可选的

词法分析（lexical analysis）

编译工作的第一步，目标是把字符流转换成词法单元（token）序列

Takes raw input, which is a stream of characters, and converts it into a stream of tokens, which are logical units, each representing one or more characters that “belong together.”

例如：

// 输入
position = initial + rate * 60// 输出
[
 (id, 1),
 (=),
 (id, 2),
 (+),
 (id, 3),
 (*),
 (number, 4)
]

具体过程是逐字符扫描，去掉注释和空白字符，把字符流拆分成词素（lexeme）：

position,=,initial,+,rate,*,60

再把词素转换成token形式：

(token-name, attribute-value)

token是建立在字符之上的第一层抽象，之所以是这种键值对儿的形式，是因为之后的多数环节都只需要关注类型（token-name），最后生成代码时才需要详细的值信息（attribute-value）。其中token-name是语法分析步骤需要的抽象符号（比如id表示标识符），attribute-value是符号表中该词素的索引：

[
 (1, position),
 (2, initial),
 (3, rate),
 (4, 60)
]

符号表

符号表是一种供编译器用于保存有关源程序构造的各种信息的数据结构。

在分析阶段生成，在合成阶段使用：

从效果看，符号表的作用是把信息从声明的地方传递到实际使用的地方。

由于词法分析器拥有的信息有限（词素字面量），生成的符号表只含有基本信息（词素字面量与标识符的映射关系），之后语法分析器会根据语义信息来决定是采用现有符号表条目还是创建新条目

另外，符号表并不是全局只有一张，而是每个作用域都有一张独立的符号表，目的是支持同一标识符在程序的不同声明块中可以重复出现，即让不同作用域下变量名不冲突。同时，为了支持语句块的最近嵌套（most-closely）规则，需要把这些符号表按嵌套层级链接起来形成树结构，以支持继承、闭包等语法特性

P.S.关键字也像标识符一样存放在符号表里，查表时通过返回码来区分

语法分析（syntax analysis）

语法分析阶段，取token-name创建树形的中间表示，用来描述语法结构，同时校验语法错误

Check input is well-formed and build a parse tree or similar representation of input.

比如抽象语法树（abstract syntax tree）就是一种常见的中间表示形式，能够描述源程序的层次化语法结构，树中每个节点表示一个运算，子节点表示该运算的运算分量：

=
 (id, 1)
 +
   (id, 2)
   *
     (id, 3)
     (number, 4)

语法树是字符之上的第二层抽象，到这里就有优先级与结合性的概念了，运算需要按照这些规则匹配其运算分量，从而生成唯一的树结构（要求语法没有二义性）。这个阶段能够确认输入的源程序形式是否正确，比如括号是否匹配之类的

上下文无关文法

语言的语法结构通常用上下文无关文法（context-free grammar）来定义，例如：

if (expression) statement else statement

对应的产生式（production）为：

stmt -> if (expr) stmt else stmt

其中expr，stmt这样的变量是非终结符（nonterminal），表示终结符（terminal，如if，()这样的词法元素）序列

上下文无关文法由4个要素组成：

• 终结符集合：语言的基本符号集合
• 非终结符集合：也称为语法变量，能够替换为终结符序列
• 产生式集合：用来表示某个构造的某种书写形式
• 开始符号：指定一个非终结符作为开始符号

从开始符号出发，不断将非终结符替换为右侧的产生式体的过程叫做推导。可以从开始符号推导得到的所有终结符序列的集合就是该文法所定义的语言，反过来看，语言就是符合产生式规则的一系列终结符串

例如，CSS中属性声明对应的文法：

// 终结符
ident   [-]?{nmstart}{nmchar}*
// 非终结符
IDENT   {ident}
// 产生式
property    : IDENT;

P.S.开始符号是stylesheet，对应的产生式为stylesheet : [ CDO | CDC | S | statement ]*;，具体见CSS核心语法

优先级与结合性

运算的优先级与结合性也由产生式规则来定义，例如：

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | (expr)

含义如下：

• factor：不能被任何运算符分开的表达式，是运算分量的最小单元，要么是数值，要么是由括号保护起来的表达式
• term：能被高优先级的运算符（*和/）分开，但不能被低优先级运算符（+和-）分开的表达式
• expr：一般表达式，能被上面任何一个运算符分开

所以，控制优先级的思路是，每个优先级都有一个专用的非终结符，表示能被该优先级的或更高优先级的运算符分开的表达式

语义分析

在这个阶段会做一些静态检查，看输入的语法结构是否满足语法要求：

• 类型检查（type checking）：比如看每个运算符是否具有匹配的运算分量，数组下标数据类型是否正确
• 类型转换（coercion）：比如对操作数进行隐式类型转换

例如：

=
 (id, 1)
 +
   (id, 2)
   *
     (id, 3)
     inttofloat
       (number, 4)

P.S.其中inttofloat表示整型转浮点型的一元运算，是类型转换中插入的操作

中间代码生成

语法分析和语义分析完成之后，接下来可能要生成一种类机器语言的中间表示，这种表示形式有两个特点：

• 易于生成（只是中间表示，生成成本不能太高）
• 容易翻译到机器语言（一步步向目标语言逼近）

比如三地址码（three-address code）是一种常见的中间表示形式，类似于汇编指令：

t1 = inttofloat(number4)
t2 = id3 * t1
t2 = id2 + t2
id1 = t3

代码优化

分为两类：

• 机器无关优化：针对中间表示的优化，以生成更好的目标程序，比如Closure Compiler对JS代码做的一些优化，比如优化循环、不可达代码消除、冗余代码简化等等
• 机器相关优化：针对目标程序的优化，涉及CPU寄存器、内存引用等，目标是最大限度的利用并行性、内存层次结构等计算机体系结构特性

前者发生在中间代码生成环节之后，而后者发生在目标程序生成之后，是出厂前的最后一道工序

P.S.比如上一步中的inttofloat类型转换可以在编译时完成（把60转成60.0），算是机器无关优化

代码生成

输入中间表示形式，输出目标语言。比如要生成机器语言的话，需要给每个变量指定寄存器或内存位置，再把中间表示翻译成等价的机器指令序列

优化过的三地址码对应的机器语言（不知道什么语言，看着像汇编）是：

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

用了2个寄存器R1和R2，读入id3放到R2里，再与60.0相乘，把乘积放到R2里……最后把R1的值被放到id1对应的内存地址，完成赋值

不考虑机器相关优化的话，编译过程到这里就结束了。逻辑上要经历词法分析，语法分析，语义分析，代码生成这4个必要环节。实际实现中，这些环节并不一定都有清晰的边界，而是尽量一趟完成多道工序，以提高性能

参考资料

• 《编译原理》（龙书 第二版）
• http://infolab.stanford.edu/~ullman/dragon/slides1.pdf
• Compiler Design – Code Optimization
• Compiled language