引入
编译器的构造想必度过编译原理的同学已经了解了。大概分为
预处理器 -> 编译器 -> 汇编器 -> 链接器
,4个阶段。
编译器又可以分为词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成 -> 代码优化 ->生成目标代码
等阶段。
阶段 | 功能 |
---|---|
预处理器 | 处理宏定义,如#include表示引入其他源文件的代码,#define表示定义宏,对代码片进行一个替换,#if系列命令可以控制预处理器的功能做到面向不同环境的代码等等。 |
编译器 | 生成中间代码,生成中间代码的意义是方便该阶段以后的所有阶段共用一个后端,比如LLVM,这样不同的语言能共享同一套优化系统 |
词法分析 | 将高级语言代码文本切割成词汇,输出单词流,删除注释、空格、空行等 |
语法分析 | 根据单词流生成语法树 |
语义分析 | 构建带类型和符号表的语法树、检查类型是否匹配、检查等号左侧是否为左值等 |
中间代码生成 | 生成中间代码 |
代码优化 | 优化中间代码 |
汇编器 | 根据中间代码生成汇编命令 |
链接器 | 将多个目标代码库链接成可执行文件 |
目前本系列文章,我们只做词法分析到中间代码生成4个阶段,以及解释执行中间代码的一个解释器。
##一个小例子
比如我们有一个语句:x = a + b * c;
。
经过词法分析后得到x|=|a|+|2|*|c|;
,其中用|
表示分隔符。更加抽象地:id|=|id|+|constant|*|id|;
,其中id
表示标识符。
我们定义文法:
S ::= ID = E
E ::= T | E + T
T ::= F | T * F
F ::= ID | CONSTANT
经过语法分析后,我们可以得到一棵语法树:
S
/|\
F = E
| /|\
i F + T
| /|\
i F * F
| |
2 i
其中字母表示文法的名字,i表示id。
然后我们根据语法树生成字节码:
iconst 2
iload c
imul
iload a
iadd
istore x
然后解释器解释执行就可以得到答案了。
我将在接下来的博文中解释执行过程。
词汇分析
由于经过我们精简的C语言语法并不复杂,因此词汇分析并没有采用自动机匹配切割文本。如果对自动机更感兴趣的同学可以参考 http://www.cnblogs.com/Ninputer/archive/2011/06/07/2074632.html
首先切割文本,显然比需要有意义地切割才行,也就是连续的有意义的一个单词不能被切开,比如int
就不能被切成i
和nt
这种。因此对于下列程序:
int max(int a, int b) {
// find the maximum of a and b.
return a > b ? a : b;
}
printf("%d %d %c %d", &a, &b, 'c', 1 << 2);
我们可以这么切割:
int|max|(|int|a|,|int|b|)|{
|return|a|>|b|?|a|:|b|;|
}
printf|(|"%d %d %c %d"|,|&|a|,|&|b|,|'c'|,|1|<<|2|)|;
词汇分析阶段我们需要将注释全部清除。同时要注意字符和字符串都是完整的单词不能被切开,这将方便语法分析阶段进行处理。而且两个字符的符号如<<
,++
这类也不能被切开。
那么编写这样简化的词法分析就相当简单了,我们只需要遇到引号就按字符串处理,注意转义;遇到数字就按数字处理,注意科学计数法和16进制数以及类型标识(1LL
, 1L
, 1.0F
等);遇到//
和/*
就按注释处理即可。
最后我们应该得到这样4种单词:
- 关键字/保留字:如
if
、for
、while
等 - 标识符:字母开头的字母数字下划线串
- 常量:小数(
1.2
)、科学计数法(1.2e+9
、7.7e-5
、6.666e2
)整数(19
)、八进制数(012
)、十六进制数(0x7FFFFFFF
)、字符常量('a'
)、字符串常量("String"
) - 符号:
+、-、*、/、%、&、|、^、&&、||、!、~、>>、<<、(、)、<<、>>、+=、-=、*=、/=、&=、|=、^=、%=、,、;、>、<、>=、<=、!=、==、::
我们可以在输出单词流的时候标注是哪种标记,方便我们进行语法分析。
具体代码请参考
https://github.com/huanghongxun/Compiler/blob/master/compiler/lexical_analyzer.cpp