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