`
java-mans
  • 浏览: 11343328 次
文章分类
社区版块
存档分类
最新评论

随想录(编译器是怎么工作的)

 
阅读更多

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】


编译器一直是我比较喜欢的话题。编译器是个比较神奇的工具,它可以把原来毫无意义的字符数据转变成一行一行可以执行的代码。作为每一个科班出身的同学来说,编译原理都是专业学习中必须经历的一个部分。只是在后来的工作中,真正从事编译器开发的同学少之又少,但是如果你懂得了编译原理的相关机理,会给你的工作带来很大的帮助。关于编译原理的书很多,网上可以搜一下有阿霍版本的《编译原理》,有陈火旺院士的《编译原理》,张素琴版本的《编译原理》,三本书我都觉得不错。另外,现在关于编译原理也有很多的开发工具,比如说lex&yacc,只要你会编写基本的语法范式,设计自己的编译器也不是什么难事。


其实,现在的编译器早已经突破了原来的概念。比如说,编译器最终的代码不一定在实际机器上运行,可能是虚拟机;编译器编译语言时不一定需要生成可执行文件,能解释就行;编译器最好并行编译;编译器不一定很大,可能十几个文件就可以,比如说lua等等。不过,我们今天说的编译器还是比较传统的c编译器,有兴趣的同学可以看看编译器是怎么帮助我们生成可执行文件的。我们按照词法、语法、语义、优化的顺序逐一展开。现在假设有这样一段代码,

#include <stdio.h>

#define MAX_VALUE 7
int test(int value)
{
	return MAX_VALUE + 1 + value * 4;
}

int main(int argc, char* argv)
{
	int p;
	p = test(3);
	printf("p = %d", p);
	return 1;
}

(1)词法分析


词法分析是整个文件编译最基本的环节。上面的文件中就存在很多的字符,那我们就需要分别对它们进行处理。比如说,通常的分类很可能是这样的,

a)字符是否是数字,例如7,1,4

b)字符是否是string类型,例如“p = %d”

c)字符是否是关键字,例如define

d)字符是否是变量,例如value,argc, argv, p

e)字符是否是运算符, 例如 +

f)字符是否是圆括号、方括号、花括号等等



(2)语法分析


语法分析的目的就是构建一个语法树,分析当前的文件是否符合编程语言的文法结构,比如说,

a)整个字符串是否符合表达式要求

b)字符串是否符合判断语句要求

c)字符串是否符合循环语句要求

d)字符串是否符合函数要求

e)字符串是否符合include语法要求

f) 有没有没有未声明就是用的变量等等;



(3)语义分析


语义分析有的时候和语法分析是联系在一起的。但是,这里我们把它拆开来单独成了一部分。所谓的语义分析,其实就是把前面生成的语法树拆解下来,生成原子语句操作的过程。比如说,上面的文件很可能是这样的形式,

SET value
mov temp1[inner], 7
add temp1[inner], 1
mul temp2,value[param], 4
add temp1, temp2
mov result, temp1
pop


SET argc[param]
SET argv[param]
SET 3
call test
pop 
get result
mov p[inner], result
SET p
SET string "p = %d"
pop
pop
mov result, 1
pop
pop
这里需要解释一下,语义转换的结构和形式其实是各个编译器自己定义的,未必有通用的结构。这里的语句只是我自己想出来的,可能和实际的形式有很大的出入,但是基本方法应该是一样的。主要解释如下,

a)SET值为函数参数

b)call为函数调用

c)pop为堆栈平衡使用

d)数据[inner],表示当前变量是函数中的临时变量

e)数据[param],表示当前变量是入参参数

f)temp表示编译器为了自身计算方便,临时添加的局部变量

g)result表示返回值


(4)代码优化


代码优化是编译器处理的一个重要环节,代码优化的目的主要是减少不必要的计算和处理,比如

a)计算没有使用价值的临时变量

b)除去没有判断价值的if语句

c)对于某些const变量,编译器提前计算,这里就可以对temp1提前计算

d)其他优化措施等等



(5)生成汇编代码


在(3)中生成的代码只是中间代码,并不是完全意义上的汇编语言。所以,编译器还需要把它翻译成对应的二进制代码,比如说arm语言、x86语言或者是powerpc语言等等。当然这中间还是存在一些技巧的,比如

a)对于多参数的函数,某些cpu可以用寄存器代替,有些cpu用堆栈表示

b)某些cpu需要对字节对齐,某些cpu则不需要

c)某些cpu有字节序的要求,某些cpu则无所谓,而有的cpu则可选

d)对于临时变量,有的cpu可以寄存器表示,而有的cpu只能自己生成一个temp变量等等,

说到这里,我们也可以自己小试一下身手,看看代码怎么生成,熟悉x86代码的同学也可以自己试试,

push ebp
mov ebp, esp
push ebx
push ecx
mov ebx, 8
mov ecx, ebp[8]
mul ecx, 4
add ebx, ecx
mov eax, ebx
pop ecx
pop ebx
mov esp, ebp
pop ebp


push ebp
mov ebp, esp
sub esp, 0x4
push 3
call test
add esp 4
mov ebp[-4], eax
push ebp[-4]
push string "p = %d"
call printf
add esp, 8
mov eax, 1
sub esp, 0x4
mov esp, ebp
pop ebp

(6)汇编级代码优化


这里的优化其实还挺多的,但是功能基本有限,无外乎就是,

a)乘法转变成移位

b)除法转变成移位

c)寄存器优化使用

d)删除寄存器的重复操作过程

e)部分函数参数用寄存器代替等等



(7)链接和生成可执行文件


在编译过程中,我们常常看到有些代码编译通过了,但是链接失败了。这是很正常的事情,因为在最后生成的文件当中,每一个变量和函数都应该有出处,否则就会链接失败。不管是什么系统平台,链接都是个大学问。这个时候,做的事情其实还是比较多的,比如

a)生成执行文件,确定是否带调试信息

b)链接所有的变量和代码

c)生成map文件

d)确定函数和变量的出处,一旦查找失败,结束

e)调整变量和函数代码的位置,填写文件结构,生成最终可执行文件




分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics