编译器也是个程序,可以阅读某一种语言(源语言)编写的程序,并把该程序翻译为一个等价的,用另一种语言(目标语言)编写的程序。
即,输入源程序,输出目标程序的程序,能够把源程序映射为语义等价的目标程序:
编译器
源程序 -------> 目标程序
源程序一般是可读性较好的字符串,目标程序则有多种形式:
.class
文件其实就是翻译,比如从字符串编译到机器码,就是把人能理解的代码语言翻译成机器能“理解”(识别执行)的机器语言,然后用户借助目标程序就可以与机器交互了:
目标程序
用户输入 ---------> 输出
P.S.与编译器很像的是解释器,区别在于没有生成目标程序的环节:
解释器
源程序 & 用户输入 -------> 输出
运行时解释执行,所以解释型语言的运行效率一般要低于编译型语言
分为两部分:
典型编译器的处理步骤如下:
(输入)字符流
|
|- 词法分析器(lexer)
| (生成)符号流
| (生成)符号表
|- 语法分析
| (生成)语法树
|- 语义分析
| (生成)语法树
|- 中间代码生成器
| (生成)中间表示形式
|- 机器无关代码优化器
| (生成)中间表示形式
|- 代码生成器
| (生成)目标机器语言
|- 机器相关代码优化器
v
(输出)目标机器语言
其中,主要步骤是词法分析,语法分析,语义分析,以及代码生成,而中间代码生成和两步优化是可选的
编译工作的第一步,目标是把字符流转换成词法单元(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.关键字也像标识符一样存放在符号表里,查表时通过返回码来区分
语法分析阶段,取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
:一般表达式,能被上面任何一个运算符分开所以,控制优先级的思路是,每个优先级都有一个专用的非终结符,表示能被该优先级的或更高优先级的运算符分开的表达式
在这个阶段会做一些静态检查,看输入的语法结构是否满足语法要求:
例如:
=
(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
分为两类:
前者发生在中间代码生成环节之后,而后者发生在目标程序生成之后,是出厂前的最后一道工序
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个必要环节。实际实现中,这些环节并不一定都有清晰的边界,而是尽量一趟完成多道工序,以提高性能