引入

编译器的构造想必度过编译原理的同学已经了解了。大概分为
预处理器 -> 编译器 -> 汇编器 -> 链接器,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就不能被切成int这种。因此对于下列程序:

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种单词:

  1. 关键字/保留字:如ifforwhile
  2. 标识符:字母开头的字母数字下划线串
  3. 常量:小数(1.2)、科学计数法(1.2e+97.7e-56.666e2)整数(19)、八进制数(012)、十六进制数(0x7FFFFFFF)、字符常量('a')、字符串常量("String"
  4. 符号:+、-、*、/、%、&、|、^、&&、||、!、~、>>、<<、(、)、<<、>>、+=、-=、*=、/=、&=、|=、^=、%=、,、;、>、<、>=、<=、!=、==、::
    我们可以在输出单词流的时候标注是哪种标记,方便我们进行语法分析。

具体代码请参考
https://github.com/huanghongxun/Compiler/blob/master/compiler/lexical_analyzer.cpp

分类: 编译器

发表评论

电子邮件地址不会被公开。 必填项已用*标注