词法分析c语言,简单的C语言解释运行器实现（一）——词法分析

引入

编译器的构造想必度过编译原理的同学已经了解了。大概分为

预处理器 -> 编译器 -> 汇编器 -> 链接器&＃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;方便我们进行语法分析。