编译过程

作者: LiHui 分类: Compiler 发布时间: 2014-12-28 16:35

平时用的GCC实际上是一些后台程序的包装,假如手动编译一个新版本的gcc以及它的所有依赖模块,单核估计会耗费你几十分钟的时间,安装过程中可以看到as,ld之类的可执行程序安装到系统目录下,实际上gcc就是这些程序的包装,它根据不同的参数去调用相应的程序,比如预处理编译程序cc1,汇编器as,链接器ld

编译过程是将高级语言翻译成机器语言,应该算是程序完成过程最关键的地方,结合《程序员的自我修养》,学习了一番,总结一下

编译过程是将预处理完的文件进行一系列词法分析,语法分析,语义分析以及优化后生成响应的汇编代码,大体分为6步:

(1)词法分析

(2)语法分析

(3)语义分析

(4)源代码优化

(5)代码生成和目标代码优化

例如下面一句C代码:

a [ i ] = (i + 1) * (2 + 3)

1:词法分析

首先源代码程序呗输入到扫描器(Scanner),扫描器的任务是简单地进行词法分析,运用一种类似有限状态机(Finite State Machine)的算法可以很轻松地将源代码的字符序列分割成一系列的几号(Token);上面C程序一共16个非空字符,经过扫描器扫描之后,会产生16个记号

但是有一点很重要的:数组a[i]分割为4个记号,假如数组名array[index],这时候尽管非空字符远不止4个,但是依旧分割成4个记号,也就是数组名array和下标index都相当于是标识符类型,它们都应该划分为一个记号,所以上面语句的记号有:

a,[,i,],=,(,i,+,1,),*,(,2,+,3,)这16个

词法分析产生的记号可以分类为:关键字,标识符,字面量(包含数字,字符串等)和特殊符号(加减号等);在识别记号的同时,扫描器也完成了其它工作,比如将标识符存放到符号表,将数字,字符串常量存放到文字表等以便后面步骤使用

有个lex程序可以实现词法草庙,按用户之前描述好的词法规则将输入的字符串分割成一个一个记号,根据这个程序就无需为每个编译器开发一个独立的词法扫描器,而是根据需要改变的词法规则就可以了

2:语法分析

语法分析器(Grammar Parser)将对扫描器产生的记号进行语法分析,从而产生语法树(Synatx Tree),这个过程采用上下文无关语法(Context-free Grammar)的分析手段,也就是由语法分析器生成的语法树就是以表达式(Expression)为结点的树,例如C里一个语句是一个表达式,而复杂的语句是很多表达式的组合,上面一句C是由赋值表达式,加法表达式,乘法表达式,数组表达式,括号表达式组成的复杂语句,经过了语法分析器a[i] = (i + 1) * (2 + 3)会形成语法树,这16个记号按二叉树层序遍历依次为:=,[],*,a,i,+,+,i,1,2,3

可以自己画一画,左子树是一个数组表达式,右子树是一个乘法表达式;数组表达式由两个符号表达式组成;符号和数字是最小的表达式,不由其他的表达式组成,所以通常作为整个语法树的叶子结点

在语法分析的同时,很多运算符号的优先级和含义也被确定下来了,比如乘法表达式优先级比加法表达式高,而括号表达式优先级比乘法表达式高等;还有一些符号有多重含义,比如*既可以表示为乘法表达式,也可以表示获取指针的内容的表达式,所以语法分析阶段必须对这些内容进行区分,假如出现了表达式不合法,比如括号不匹配,表达式中缺少操作符等,编译器就会报语法分析阶段的错误

语法分析也有一个工具yacc(Yet Another Compiler Compiler);它和lex一样,可以根据用户给定的语法规则对输入的记号序列进行解析,从而构建出一棵语法树;对于不同的编程语言,编译器开发者值需要改变语法规则,不必要每个编译器都编写一个语法分析器,所以也被称为“编译器编译器”(Compiler Compiler)

3:语义分析

语义分析由语义分析器(Semantic Analyzer)来完成;上面语法分析仅仅是完成了对表达式的语法层面的分析,但是它并不了解这个语句真正的意义,只需要语法上合法

编译器所能分析的语义是静态语义(Static Semantic),也就是在编译期可以确定的语义,与之对应的是动态语义(Dynamic Semantic)只有在运行期才能确定的语义

静态语义通常包含声明和类型的匹配,类型的转换,比如赋值语句两边类型不匹配,语义分析程序就会发现不匹配,从而编译器就会报错;动态语义一般是指在运行期间出现的语义相关的问题,比如除数为0就是一个动态语义错误

经过了语义分析阶段之后,整个语法树的表达式就呗标识了类型,假如有些类型需要做隐式转换,语义分析程序就会在语法树中插入响应的转换结点,语法树按照二叉树层序遍历就会变成:integer,= integer,… integer,3 integer;其中每个表达式(包括符号和数字)都呗标识了类型,这条C语句里所有表达式都整形,所以无需做转换

4:源代码优化

编译器往往在源代码级别都会有一个优化过程,源码级优化器(Source Code Optimizer)在不同编译器中可能会有不同的定义或者有一些其它的差异,但源码级优化器会在源代码级别进行优化,其实上面a [ i ] = (i + 1) * (2 + 3)语句中(2 + 3)这个表达式可以呗优化掉,因为它的值在编译期间就可以确定,类似还有一些其它优化过程;经过优化了之后,语法树的叶子结点2和3就会消失,而他们的双亲结点也会由+变成了8,可以自己画出二叉树

其实直接在语法树上进行优化比较困难,所以源码级优化器往往将整个语法树转换成了中间代码(Intermediate Code),它是语法树的顺序表示,其实它十分接近目标代码了,但是它跟目标机器和运行环境是无关的,比如它不包含数据的尺寸,变量地址和寄存器名字等;中间代码有很多种类型,在不同的编译器中也有不同的形式,比较常见的有:三地址码(Three-address Code)和P-代码(P-Code)

最基本三地址码表示形式:

a = b op c

它表示将变量b和c进行op操作之后,赋值给a,这里的op操作可以是算数运算,也可以是其他应用到b和c的操作,所以这个语句里有两个变量地址,因而得到三地址码这个名字

a [ i ] = (i + 1) * (2 + 3)语法树被翻译成三地址码之后:

x1 = 2 +3

x2 = i + 1

x3 = x2 * x1

a [ i ] = x3

所以为了满足三地址码的形式,利用几个临时变量x1,x2,x3实现

在三地址码的基础上进行优化时,优化程序会将2 +3的结果计算出来,得到x1 = 5;然后将后面代码中的x1替换成数字5,还可以省去一个临时变量x3,因为x2可以重复利用,所以经过优化之后的三地址码为:

x2 = i + 1

x2 = x2 * 5

a [ i ] = x2

中间代码使得编译器被分为前端和后端;前端负责产生机器无关的中间代码,后端将中间代码转换成目标机器代码,这样对于一些可以跨平台的编译器而言,可以针对不同的平台使用同一个前端和针对不同机器平台的数个后端

5:目标代码生成和优化

源码级优化器产生中间代码标志着后面的过程都是编译器后端;后端主要包括代码生成器(Code Generator)和目标代码优化器(Target Code Optimizer)

代码生成器将中间代码转换成目标机器代码,这个过程十分依赖于目标机器,因为不同的机器有着不同的字长,寄存器,整数数据类型和浮点数据类型等,一般生成的代码序列也就是汇编来表示,有兴趣的可以自行学习

目标代码优化器对上面的目标代码进行优化,比如选择合适的寻址方式,使用位移来代替乘法运算,删除多余的指令等等

 

这样经过了语法分析,语法分析,语义分析,源代码优化,目标代码生成和优化,编译器才将源代码编译成目标代码,通常也就是汇编代码

纯属恶搞

浙ICP备16024533号

浙公网安备 33010802007459号