c语言手搓一个500+行的类c语言解释器(1)- 目标和前言

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程(1)- 目标和前言

项目github地址及源码:
https://github.com/yunwei37/tryC

一个小目标

这一系列教程希望面向初学者,使用c语言手工实现一个简单的解释器来玩,不需要您掌握除了c语言以外的其他前置知识,也不需要您学习过编译原理的相关知识(当然如果能对简单的数据结构有所了解的话会更好,比如树、栈等)。

写一个能执行代码的解释器不仅是一件很有(zhuang)趣(bi)的事情,大概也可以作为刚学习完c语言的一个练手的小项目啦

不同于大部分常见的其他只支持四则运算的所谓”手工解释器“教程,我们希望在代码结构尽量清晰的600行代码中,手工(不借助lex/yacc等工具)完成一个脚本语言“try”,实现以下功能:

  • 选择和循环的流程控制语句
  • 支持的数据类型:双精度浮点数、字符型、字符串、浮点数数组
  • 支持函数和变量的定义、函数的递归调用、嵌套作用域

(如果看不懂下面这段也没关系,可以略过啦)

这个小玩意采用递归下降法进行语法分析,同时不显式构建语法树,不生成中间代码或目标代码,在语法分析的同时进行解释执行;

解释器可运行的代码示例

递归计算文波那契数列 1 - 15,将结果存入数组中,并打印:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Fibonacci sequence
func fun{
if(x <= 2){
return(1);
}
y = 0;
x = x - 1;
y = fun(x);
x = x - 1;
return(y + fun(x));
};

# save the Fibonacci sequence of 1 to 15 in an array
array arr(15);
x = 1;
while( x <= 15 ){
arr[x - 1] = fun(x);
x = x + 1;
}

puts("Fibonacci sequence:");
# print the Fibonacci sequence of 1 to 15
i = 0;
while(i < 15){
print(arr[i]);
i=i+1;
}

(起名困难x)这个小玩意我们就随便叫它tryC吧,当做是一个小的尝试。

本人水平有限,如有疏漏之处,还请多多指教。

部分语言规则:

  • 注释在一行内,以‘#’开头;

  • 语句以‘;’结尾

  • 赋值语句类型:

    1
    2
    3
    x = 123.4;
    x = 'c';
    x = "hello world!";
  • 循环语句:

    1
    2
    3
    while( bool ){
    statements
    }
  • 选择语句:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    if( bool ){
    statements
    }

    if( bool ){
    statements
    }else{
    statements
    }
  • 定义函数:函数参数在定义中不出现,在调用中获取;返回值为double

    1
    2
    3
    4
    5
    func function_name{
    ...
    return(expression);
    }

  • 定义数组:

    1
    2
    array array_name(array_length);        

  • 输入输出:

    1
    2
    3
    puts(string);
    print(num);
    read(num);

写在前面

关于写这玩意的缘由(写的很乱可以不看系列)

之前大一学c语言的时候,老师要求实现一个四则运算的计算器,于是我想…要是能给计算器加上函数和变量的定义就好啦…那大概能算一个简单的解释器?我应该怎样去实现它呢?就去查了不少资料七拼八凑加上自己脑补搓了一个出来…虽然能跑起来但是代码混乱不堪一塌糊涂,不过也挺好玩的。

这里的部分是过了一年之后大二学编译原理的时候,把当时的代码用相对比较规范完善的方式重写了一遍,也因此希望把它整理成一个简单的教程,让c语言的初学者也可以愉快地搓一个解释器玩;或者让学过编译原理的同学,能够把理论和实践联系起来,(不要像我一样被一大堆的理论迷惑住或吓跑),对于如何构造一个解释器有个直观感性的认识,并且发现它并不像想象的那么困难。

需要了解的前置知识

  • c语言的指针、函数指针、结构体等
  • 递归的思想

心理准备

  • 写一个600行的解释器虽然不算什么大工程,但相关的原理还是稍微有些复杂的,可能需要多花一些时间理解程序的运行过程;

  • 代码可能难以调试,尤其在没有生成中间代码的情况下;

参考资料

c语言手搓一个500+行的类c语言解释器(2)- 简介和设计

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程(2)- 简介和设计

项目github地址及源码:
https://github.com/yunwei37/tryC

需要了解的一些基本概念

编译器和解释器的区别不同

通常我们说的 “编译器” 是一种计算机程序,负责把一种编程语言编写的源码转换成另外一种计算机代码,后者往往是以二进制的形式被称为目标代码(object code)。这个转换的过程通常的目的是生成可执行的程序。

而解释器是一种计算机程序,它直接执行由编程语言或脚本语言编写的代码,它并不会把源代码预编译成机器码,而是一行一行地分析源代码并且直接执行,相对编译器而言可能效率较为低下,但实现也相对简单,并且容易在不同的机器上进行移植(比如x86和mips指令集的机器)。

先来看看通常的编译器是如何实现的:

编译器从源码翻译为目标代码大致需要这样几个步骤,每个步骤都依赖于上一个步骤的结果:

  1. 词法分析:

    编译器对源程序进行阅读,并将字符序列,也就是源代码中一个个符号收集到称作记号(token)的单元中;比如:

    1
    num = 123.4;

    这样个赋值语句中,变量num算是一个token,“=”符号算是一个token,“123.4”算是一个token;每个token有自己的类别和属性,比如“123.4”的类别是数字,属性(值)是123.4

  2. 语法分析:

    语法分析指将词法分析得到的标记流(token)进行分析,组成事先定义好的有意义的语句,这与自然语言中句子的语法分析类似。通常可以用抽象语法树表示语法分析的结果,比如赋值语句:

    1
    num = 123.4 * 3;

    可以用这样一个抽象语法树来表示:

    1
    2
    3
    4
    5
    graph TD
    = --> num
    = --> *
    * --> 123.4
    * --> 3
  3. 语义分析:
    程序的语义就是它的“意思”,程序的语义确定程序的运行方式。语义分析阶段通常包括声明和类型检查、计算需要的一些属性值等等。编译器在这个阶段中通常会维护一个叫做“符号表”的东西,保存变量的值、属性和名称。同样以

    1
    num = 123.4 * 3;

    为例,假如我们是第一次在这里遇见“num”,就将num的名称字符串“num” 和当前计算出来的初始值370.2插入符号表中,当下次再遇见num时。我们就知道它是一个数字,已经初始化完毕,并且当前值是370.2;

  4. 目标代码生成:
    在语义分析之后,我们就可以将语法分析和语义分析的结果(通常是抽象语法树)转换成可执行的目标代码。

解释器与编译器仅在代码生成阶段有区别,而在前三个阶段如词法分析、语法分析、语义分析基本是一样的。

当然,已经有许多工具可以帮助我们处理阶段1和2,如 flex 用于词法分析,bison 用于语法分析;但它们的功能都过于强大,屏蔽了许多实现上的细节,对于学习构建编译器帮助不大,所以我们要完全手写这些功能。

(实际上完成一个可以跑起来的解释器并不难,而且还是一件很有成就感的事,不是嘛?)

tryC编译器的设计:

从上面可以看出,我们的tryC解释器需要这三个模块:

  1. 词法分析
  2. 语法分析
  3. 语义分析和解释执行

需要这两个数据结构(用来在阶段之间保存或传递值):

  1. token,用来在词法分析和语法分析之间传递标记;
  2. 符号表,保存语义分析阶段遇见的变量值,使用一个数组存储;

在了解过这些之后,我们先来大概看看代码的基本结构:

(从上往下在代码中依次对应,“…”表示省略的相关代码,在后续文章中会详细讲解)

  • 数据结构的声明部分:token类型、符号表结构:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
...

typedef struct symStruct {
int type;
char name[MAXNAMESIZE];
double value;
..........
} symbol;
symbol symtab[SYMTABSIZE]; // 符号表
int symPointer = 0;

char* src, * old_src; // 当前分析的源代码位置指针

// tokens 的枚举类型
enum {
Num = 128, Char, Str, Array, Func,
........
};

// token 的表示形式
int token; // current token type
union tokenValue {
symbol* ptr;
double val;
} token_val;

  • 词法分析的两个函数:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 获取输入流中的下一个记号:
void next() {
char* last_pos;

while (token = *src) {
++src;
if(token == AAA ){
.....
}else if(token == BBB ){
.....
}
}
}

// 匹配一个记号,并获取下一个token:
void match(int tk) {
if (token == tk) {
next();
}
else { // 遇到了一个错误
exit(-1);
}
}

  • 语法分析和语义分析,以及执行阶段:使用递归下降法实现(后面会再提到什么是递归下降法啦)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 计算表达式的值:
double expression(){}
double factor(){}
double term(){}

// 计算布尔表达式的值:
int boolOR();
int boolAND();
int boolexp();

// 执行一个语句;
double statement();

// 执行一个函数:
double function();

  • main() 函数,代码的入口,并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int main(int argc, char** argv)
{
// 往符号表里面添加关键词
int i, fd;
src = "array func else if return while print puts read";
for (i = Array; i <= Read; ++i) {
next();
symtab[symPointer -1].type = i;
}

src = old_src = (char*)malloc(POOLSIZE); // 分配空间

....

fd = open(*argv, 0); // 打开读取文件

read(fd, src, POOLSIZE - 1);

src[i] = 0;
close(fd);
next();
while (token != 0) { // 一条一条语句执行
statement();
}
return 0;
}

重要概念

  • 编译器/解释器
  • 词法分析
  • 语法分析
  • 语义分析
  • token
  • 符号表

可参照github源码查看(如果觉得写得还行麻烦您帮我点个star哦)
https://github.com/yunwei37/tryC

c语言手搓一个500+行的类c语言解释器(5)- 语法分析2 tryC的语法分析实现

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程(5)- 语法分析2: tryC的语法分析实现

项目github地址及源码:
https://github.com/yunwei37/tryC

tryC的语法分析

完整的tryC文法:

(这里我们用单引号包裹那些在BCNF文法定义中出现但又作为终结符出现的字符)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
exp -> term { addop term }
term -> factor { mulop factor }
factor -> number | ( exp ) | Sym | array_name '[' exp ']' | function // 处理数组单元、函数、变量等
addop -> + | -
mulop -> * | /

boolOR = boolAND { '||' boolAND }
boolAND = boolexp { '||' boolexp }
boolexp -> exp boolop exp | ( boolOR ) | !boolexp
boolop -> > | < | >= | <= | ==

statement -> '{' { statement } '}' | // 语句块
if-stmt -> if ( exp ) statement [ else statement ] | // 选择语句
while-stmt -> while ( exp ) statement | // 循环语句
Sym = exp; | // 赋值语句
print ( exp ); | // 输入输出语句
puts ( Str ); |
read ( Sym ); |
return ( exp ); | // 函数的返回语句
func func_name statement; | // 函数定义
array array_name length; | // 数组定义

statement的代码实现

布尔表达式和算术表达式的代码之前已经讲过了,这里看看statement的实现,以及如何在语法分析的同时解释执行:

这里使用的方法是,对于流程控制语句,在语法分析的时候就进行条件判断,如果if判断失败或者while不进入循环块,就跳过该语句块不进行语法分析、解释执行;

其中RETURNFLAG用来表示在函数中返回,跳过剩余的语句;statement默认返回0,当有return语句在其中出现时才需要使用返回值。

代码块:

在一个statement中通过花括号包含多个语句

1
2
3
4
5
6
7
8
9
10
double statement() {
if (token == '{') {
match('{');
while (token != '}') {
if (RETURNFLAG == statement())
return RETURNFLAG;
}
match('}');
}
....

if语句

由于tryC解释器是边进行语法分析,边解释执行的,因此如果不需要解释执行执行某一个语句块,就调用函数

1
skipStatments()

跳过该语句块,不对其进行语法分析,不解释执行;(在if语句和while语句中使用):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
else if (token == If) {
match(If);
match('(');
int boolresult = boolOR();
match(')');
if (boolresult) {
if (RETURNFLAG == statement())
return RETURNFLAG;
}
else skipStatments();
if (token == Else) {
match('Else');
if (!boolresult) {
if (RETURNFLAG == statement())
return RETURNFLAG;
}
else skipStatments();
}
}
...

其中skipStatments()的实现如下:

1
2
3
4
5
6
7
8
9
10
11
void skipStatments() {
if(token == '{')
token = *src++;
int count = 0;
while (token && !(token == '}' && count == 0)) {
if (token == '}') count++;
if (token == '{') count--;
token = *src++;
}
match('}');
}

while语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
else if (token == While) {
match(While);
char* whileStartPos = src;
char* whileStartOldPos = old_src;
int boolresult;
do {
src = whileStartPos;
old_src = whileStartOldPos;
token = '(';
match('(');
boolresult = boolOR();
match(')');
if (boolresult) {
if (RETURNFLAG == statement())
return RETURNFLAG;
}
else skipStatments();
}while (boolresult);
}
...

赋值语句

赋值语句的左边可以是数组中间的一个单元,也可以是一个变量,右边是字符串或表达式、字符。

(在下一篇文章中还会提及具体变量赋值的实现)

数组需要先定义才能进行赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
...
else if (token == Sym || token == ArraySym) {
symbol* s = token_val.ptr;
int tktype = token;
int index;
match(tktype);
if (tktype == ArraySym) {
match('[');
index = expression();
match(']');
match('=');
if (index >= 0 && index < s->value) {
s->pointer.list[index].value = expression();
}
}
else {
match('=');
if (token == Str) {
s->pointer.funcp = (char*)token_val.ptr;
s->type = Str;
match(Str);
}
else if (token == Char) {
s->value = token_val.val;
s->type = Char;
match(Char);
}
else {
s->value = expression();
s->type = Num;
}
}
match(';');
}
...

定义函数语句

定义函数的时候并不执行函数体,所以同样跳过语句块;

1
2
3
4
5
6
7
8
9
10
11
12
13
...
else if (token == Func) {
match(Func);
symbol* s = token_val.ptr;
s->type = FuncSym;
match(Sym);
s->pointer.funcp = src;
s->value = token;
skipStatments();
match(';');
}
...

定义数组语句

定义数组并分配空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
...
else if (token == Array) {
match(Array);
symbol* s = token_val.ptr;
match(Sym);
match('(');
int length = (int)expression();
match(')');
s->pointer.list = (double*)malloc(sizeof(struct symStruct) * length + 1);
for (int i = 0; i < length; ++i)
s->pointer.list[i].type = Num;
s->value = length;
s->type = ArraySym;
match(';');
}
...

返回语句

返回RETURNFLAG作为标志;

1
2
3
4
5
6
7
8
9
10
11
...
else if (token == Return) {
match(Return);
match('(');
return_val = expression();
match(')');
match(';');
return RETURNFLAG;
}
...

输入输出语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
else if (token == Print || token == Read || token == Puts) {
int func = token;
double temp;
match(func);
match('(');
switch (func) {
case Print:
temp = expression();
printf("%lf\n", temp);
break;
case Puts:
printf("%s\n", (char*)token_val.ptr);
match(Str);
break;
case Read:
scanf("%lf", &token_val.ptr->value);
token_val.ptr->type = Num;
match(Sym);
}
match(')');
match(';');
}
return 0;
}

可对照源码查看(如果觉得写得还行麻烦您帮我点个star哦)
https://github.com/yunwei37/tryC

c语言手搓一个500+行的类c语言解释器(3)- 词法分析

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程(3)- 词法分析

项目github地址及源码:
https://github.com/yunwei37/tryC

这一篇讲讲在tryC中词法分析器是怎样构建的

词法分析器是什么玩意

回想一下上一篇我们说的词法分析阶段,编译器做了这样一件事:

对源程序进行阅读,并将字符序列,也就是源代码中一个个符号收集到称作记号(token)的单元中

帮编译器执行词法分析阶段的模块,就叫词法分析器啦。词法分析器能够对源码字符串做预处理,以减少语法分析器的复杂程度。

词法分析器以源码字符串为输入,输出为标记流(token stream),即一连串的标记,比如对于源代码中间:

1
num = 123.4;

这样一个赋值语句中,变量num算是一个token,“=”符号算是一个token,“123.4”算是一个token;每个token有自己的类别和属性,比如“123.4”的类别是数字,属性(值)是123.4;每个token可以用这一对儿表示:{token, token value},就像“123.4”可以表示为{Num, 123.4}

词法分析器输入上面那句话,就得到这样一个标记流:

1
{Sym, num}, {'=', assign}, {Num, 123.4}

词法分析器的具体实现

由于词法分析器对于各个语言基本都是大同小异,在其他地方也有很多用途,并且手工构造的话实际上是一个很枯燥又容易出错的活计,因此其实已经有了不少现成的实现,比如 lex/flex 。

通常词法分析器的实现会涉及到正则表达式、状态机的一些相关知识,或者通过正则表达式用上面那些工具来生成。但对于我们这样一个简单的解释器来说,手工构造词法分析器,并且完全不涉及到正则表达式的知识,理解起来也并不是很困难啦。

先来看看token是怎样写的

token的数据结构如下:

1
2
3
4
5
6

int token; // current token type
union tokenValue { // token value
symbol* ptr;
double val;
} token_val;
  • 用一个整型变量 token 来表示当前的 token 是什么类型的;
  • 用一个联合体来表示附加的token属性,ptr可以附加指针类型的值,val可以附加数值。

token 的类型采用枚举表示定义:

1
2
3
4
5
6
7
/* tokens and classes (operators last and in precedence order) */
enum {
Num = 128, Char, Str, Array, Func,
Else, If, Return, While, Print, Puts, Read,
Assign, OR, AND, Equal, Sym, FuncSym, ArraySym, Void,
Nequal, LessEqual, GreatEqual, Inc, Dec
};

比如我们会将“==”标记为Equal,将Num标记为Sym等等。从这里也可以看出,一个标记(token)可能包含多个字符;而词法分析器能减小语法分析复杂度的原因,正是因为它相当于通过一定的编码(采用标记来表示一定的字符串)来压缩和规范化了源码。

另外,一些单个字符我们直接作为token返回,比如:

1
'}' '{' '(' ')' ';' '[' ']' .....

词法分析器真正干活的函数们

首先需要说明一下,源码字符串为输入,输出为标记流(token stream),这里的标记流并不是一次性将所有的源代码翻译成长长的一串标记串,而是需要一个标记的时候再转换一个标记,原因如下:

  1. 字符串转换成标记流有时是有状态的,即与代码的上下文是有关系的。
  2. 保存所有的标记流没有意义且浪费空间。

所以通常的实现是提供一个函数,每次调用该函数则返回下一个标记。这里说的函数就是 next() 。

这是next()的基本框架:其中“AAA””BBB”是token类型;

1
2
3
4
5
6
7
8
9
10
void next() {
while (token = *src) {
++src;
if(token == AAA ){
.....
}else if(token == BBB ){
.....
}
}
}

用while循环的原因有以下几个:

  • 处理错误:
    如果碰到了一个我们不认识的字符,可以指出错误发生的位置,然后用while循环跳过当前错误,获取下一个token并继续编译;

  • 跳过空白字符;
    在我们实现的tryC语言中,空格是用来作为分隔用的,并不作为语法的一部分。因此在实现中我们将它作为“不识别”的字符进行跳过。

现在来看看AAA、BBB具体是怎样判断的:

换行符和空白符

1
2
3
4
5
6
7
...
if (token == '\n') {
old_src = src; // 记录当前行,并跳过;
}
else if (token == ' ' || token == '\t') { }
...

注释

1
2
3
4
5
6
7
8
...
else if (token == '#') { // skip comments
while (*src != 0 && *src != '\n') {
src++;
}
}
...

单个字符

1
2
3
4
5
6
7
8
...
else if ( token == '*' || token == '/' || token == ';' || token == ',' ||
token == '(' || token == ')' || token == '{' || token == '}' || token == '[' || token == ']') {
return;
}

...

数字

token 为Num;
token_val.val为值;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
else if (token >= '0' && token <= '9') { // process numbers
token_val.val = (double)token - '0';
while (*src >= '0' && *src <= '9') {
token_val.val = token_val.val * 10.0 + *src++ - '0';
}
if (*src == '.') {
src++;
int countDig = 1;
while (*src >= '0' && *src <= '9') {
token_val.val = token_val.val + ((double)(*src++) - '0')/(10.0 * countDig++);
}
}
token = Num;
return;
}

...

字符串

token 为Str;
token_val.ptr保存字符串指针;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
else if (token == '"' ) { // parse string
last_pos = src;
char tval;
int numCount = 0;
while (*src != 0 && *src != token) {
src++;
numCount++;
}
if (*src) {
*src = 0;
token_val.ptr = malloc(sizeof(char) * numCount + 8);
strcpy(token_val.ptr, last_pos);
*src = token;
src++;
}
token = Str;
return;
}

...

字符

token 为Char;
token_val.val为值;

1
2
3
4
5
6
7
8
9
10
...
else if (token == '\'') { // parse char
token_val.val = *src++;
token = Char;
src++;
return;
}

...

变量:这是最复杂的一部分

对变量的处理需要以下几个步骤:

  1. 获取完整的变量名:
  2. 在符号表中查找变量:
  3. 如果在符号表中找到了变量,根据变量不同的类型,返回不同的token值;
  4. 如果没有找到,在符号表中间插入新的变量

关于符号表具体的内容,会独立出一篇文章来解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
...
else if ((token >= 'a' && token <= 'z') || (token >= 'A' && token <= 'Z') || (token == '_')) {
last_pos = src - 1; // process symbols
char nameBuffer[MAXNAMESIZE];
nameBuffer[0] = token;
while ((*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z') || (*src >= '0' && *src <= '9') || (*src == '_')) {
nameBuffer[src - last_pos] = *src;
src++;
}
nameBuffer[src - last_pos] = 0; // get symbol name
int i;
for (i = symPointer-1; i >= 0; --i) { // search symbol in symbol table
if (strcmp(nameBuffer, symtab[i].name) == 0) { // if find symbol: return the token according to symbol type
if (symtab[i].type == Num || symtab[i].type == Char) {
token_val.ptr = &symtab[i];
token = Sym;
}
else if (symtab[i].type == FuncSym) {
token_val.ptr = &symtab[i];
token = symtab[i].type;
}
else if (symtab[i].type == ArraySym) {
token_val.ptr = &symtab[i];
token = symtab[i].type;
}
else {
if (symtab[i].type == Void) {
token = Sym;
token_val.ptr = &symtab[i];
}
else token = symtab[i].type;
}
return;
}
}
strcpy(symtab[symPointer].name, nameBuffer); // if symbol not found, create a new one
symtab[symPointer].levelNum = currentlevel;
symtab[symPointer].type = Void;
token_val.ptr = &symtab[symPointer];
symPointer++;
token = Sym;
return;
}
...

其他的一些符号,可能需要再多读取一个字符才能确定具体token

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
...
else if (token == '=') { // parse '==' and '='
if (*src == '=') {
src++;
token = Equal;
}
return;
}
else if (token == '+') { // parse '+' and '++'
if (*src == '+') {
src++;
token = Inc;
}
return;
}
else if (token == '-') { // parse '-' and '--'
if (*src == '-') {
src++;
token = Dec;
}
return;
}
else if (token == '!') { // parse '!='
if (*src == '=') {
src++;
token = Nequal;
}
return;
}
else if (token == '<') { // parse '<=', or '<'
if (*src == '=') {
src++;
token = LessEqual;
}
return;
}
else if (token == '>') { // parse '>=', or '>'
if (*src == '=') {
src++;
token = GreatEqual;
}
return;
}
else if (token == '|') { // parse '||'
if (*src == '|') {
src++;
token = OR;
}
return;
}
else if (token == '&') { // parse '&&'
if (*src == '&') {
src++;
token = AND;
}
return;
}

...

错误处理

1
2
3
4
5
6
7
...
else {
printf("unexpected token: %d\n", token);
}

...

match函数:用于匹配当前token并获取下一个token

1
2
3
4
5
6
7
8
9
10
// 匹配一个记号,并获取下一个token:
void match(int tk) {
if (token == tk) {
next();
}
else { // 遇到了一个错误
exit(-1);
}
}

可对照源码查看(如果觉得写得还行麻烦您帮我点个star哦)
https://github.com/yunwei37/tryC

c语言手搓一个500+行的类c语言解释器(6)- 语义分析:符号表和变量、函数

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程(6)- 语义分析:符号表和变量、函数

项目github地址及源码:
https://github.com/yunwei37/tryC

这一部分,我们再回过头来看看变量、函数是怎样存储和处理的、以及符号表是怎样构建的。

符号表

我们先来回顾一下符号表的定义:

符号表是一种用于语言翻译器(例如编译器和解释器)中的数据结构。在符号表中,程序源代码中的每个标识符都和它的声明或使用信息绑定在一起,比如其数据类型、作用域以及内存地址。

简单来说就是,我们在符号表中存储对应的变量的各种信息,在定义的时候对符号表进行插入,以便下次碰见它的时候可以知道这个变量的具体信息。

我们可以在符号表中保存五种变量:Num(数值), Char(字符), Str(字符串), Array(数组), Func(函数)

tryC符号表的完整定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* this structure represent a symbol store in a symbol table */
typedef struct symStruct {
int type; // 符号的类型: Num, Char, Str, Array, Func
char name[MAXNAMESIZE]; // 符号名称
double value; // 如果是数值变量,记录它的值; 如果是数组或者字符串,记录它的长度
union {
char* funcp; // 指向函数定义在源代码中位置的字符指针
struct symStruct* list; // 指向数组列表
} pointer;
int levelNum; // 作用域层
} symbol;
symbol symtab[SYMTABSIZE]; // 用数组定义符号表
int symPointer = 0; // 符号表数组当前使用的最大下标的指针+1(栈顶 + 1)
int currentlevel = 0; // 当前作用域层

作用域

作用域就是程序中定义的变量所存在的区域,超过该区域变量就不能被访问。

(这里就不具体举例介绍了)

作用域可以相互嵌套;当内层作用域和外层作用域存在同名变量时,在内层的程序访问的应当是内层的变量,在外层的程序访问的应当是外层的变量;在函数中的变量,只有在所在函数被调用时才动态地为变量分配存储单元,并在调用结束时回收。

作用域可以是块作用域、函数作用域等,tryC中只实现了函数作用域。

我们可以用currentlevel这个变量记录当前的嵌套深度;

1
int currentlevel = 0; 

对于函数作用域我们可以这样处理:在函数调用时加深作用域层,并把需要传入的参数插入符号表;并在函数退出的时候,删除该作用域层的所有变量,并减少作用域层,对应代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
double function() {
currentlevel++;
return_val = 0;

.....

while (symtab[symPointer - 1].levelNum == currentlevel) {
symPointer--;
}
currentlevel--;
return return_val;
}

由于插入的变量肯定在符号表数组的最上面,因此只要减少符号表数组最大值的指针就可以表示删除啦。

变量

对变量的处理主要分为几个部分:

  • 词法分析阶段,当我们遇见一个标识符名称时,需要返回对应的token;
  • 在表达式中,当遇见一个变量时,我们需要获取它的值;
  • 在定义语句中,对变量进行定义和在符号表中插入相关信息;

词法分析阶段

当我们在词法分析的时候,对变量的处理需要以下几个步骤:

  1. 获取完整的变量名:
  2. 在符号表中查找变量,从上往下查找,这样返回的一定是最近作用域的那个变量:
  3. 如果在符号表中找到了变量,根据变量不同的类型,返回不同的token值;
  4. 如果没有找到,在符号表中间插入新的变量,返回的token值为void;这时应该对应赋值语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
...
else if ((token >= 'a' && token <= 'z') || (token >= 'A' && token <= 'Z') || (token == '_')) {
last_pos = src - 1; // process symbols
char nameBuffer[MAXNAMESIZE];
nameBuffer[0] = token;
while ((*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z') || (*src >= '0' && *src <= '9') || (*src == '_')) {
nameBuffer[src - last_pos] = *src;
src++;
}
nameBuffer[src - last_pos] = 0; // get symbol name
int i;
for (i = symPointer-1; i >= 0; --i) { // search symbol in symbol table
if (strcmp(nameBuffer, symtab[i].name) == 0) { // if find symbol: return the token according to symbol type
if (symtab[i].type == Num || symtab[i].type == Char) {
token_val.ptr = &symtab[i];
token = Sym;
}
else if (symtab[i].type == FuncSym) {
token_val.ptr = &symtab[i];
token = symtab[i].type;
}
else if (symtab[i].type == ArraySym) {
token_val.ptr = &symtab[i];
token = symtab[i].type;
}
else {
if (symtab[i].type == Void) {
token = Sym;
token_val.ptr = &symtab[i];
}
else token = symtab[i].type;
}
return;
}
}
strcpy(symtab[symPointer].name, nameBuffer); // if symbol not found, create a new one
symtab[symPointer].levelNum = currentlevel;
symtab[symPointer].type = Void;
token_val.ptr = &symtab[symPointer];
symPointer++;
token = Sym;
return;
}
...

在表达式中对变量的处理:

在表达式中遇到的标识符可能是三种形式:

  1. 普通变量:Char或Num,token_val传递数值类型;
  2. 函数变量:进行调用函数操作;
  3. 数组变量:获取token_val传递的数组指针,获取下标,进行边界检查,获取元素;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
double factor() {
double temp = 0;
.....
else if (token == Sym) { // 普通变量
temp = token_val.ptr->value;
match(Sym);
}
else if (token == FuncSym) { // 函数变量
return function();
}
else if (token == ArraySym) { // 数组变量
symbol* ptr = token_val.ptr;
match(ArraySym);
match('[');
int index = (int)expression();
if (index >= 0 && index < ptr->value) {
temp = ptr->pointer.list[index].value;
}
match(']');
}
return temp;
}

在变量定义语句中对变量的处理

由于是动态类型语言,我们对变量的定义语句也是变量的赋值语句;根据赋值的类型确定变量的类型。进入赋值语句时,传递过来的token_val包含的是一个指向当前变量结构体的指针,赋值就是对其进行操作:

赋值语句的左边可以是数组中间的一个单元,也可以是一个变量,右边是字符串或表达式、字符。

数组需要先定义才能进行赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
...
else if (token == Sym || token == ArraySym) {
symbol* s = token_val.ptr;
int tktype = token;
int index;
match(tktype);
if (tktype == ArraySym) { // 对数组进行特殊判断:获取要赋值的数组单元;
match('[');
index = expression();
match(']');
match('=');
if (index >= 0 && index < s->value) {
s->pointer.list[index].value = expression();
}
}
else {
match('=');
if (token == Str) { // 根据赋值类型进行不同的操作
s->pointer.funcp = (char*)token_val.ptr;
s->type = Str;
match(Str);
}
else if (token == Char) {
s->value = token_val.val;
s->type = Char;
match(Char);
}
else {
s->value = expression();
s->type = Num;
}
}
match(';');
}
...

函数

tryC的函数实现完整代码:这个函数做了以下几件事:

  1. 对变量的作用域进行控制;
  2. 将函数参数中的变量直接插入作用域;
  3. 保存当前词法分析的源代码位置和token,并跳转到函数定义时的源代码位置和token;
  4. 语法分析和执行定义时的函数体,如果碰到返回语句,就将返回值存入return_val;
  5. 恢复保存的当前源代码位置和token;
  6. 返回值从全局变量return_val中获取;

由于function()函数本身是递归的,且变量作用域等可以得到控制,因此可以实现函数的递归调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
double function() {
currentlevel++;
return_val = 0; // 对变量的作用域进行控制;

symbol* s = token_val.ptr; // 将函数参数中的变量直接插入作用域;
match(FuncSym);
match('(');
while (token != ')') {
symtab[symPointer] = *token_val.ptr;
strcpy(symtab[symPointer].name, token_val.ptr->name);
symtab[symPointer].levelNum = currentlevel;
symPointer++;
match(Sym);
if (token == ',')
match(',');
}
match(')');
char* startPos = src; // 保存当前词法分析的源代码位置和token
char* startOldPos = old_src;
int startToken = token;
old_src = src = s->pointer.funcp; // 跳转到函数定义时的源代码位置和token;
token = (int)s->value;
statement(); // 语法分析和执行定义时的函数体
src = startPos;
old_src = startOldPos;
token = startToken; // 恢复保存的当前源代码位置和token;

while (symtab[symPointer - 1].levelNum == currentlevel) {
symPointer--;
}
currentlevel--;
return return_val;
}

可对照源码查看(如果觉得写得还行麻烦您帮我点个star哦)
https://github.com/yunwei37/tryC

c语言手搓一个500+行的类c语言解释器(4)- 语法分析1:EBNF和递归下降文法

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程(4)- 语法分析1:EBNF和递归下降文法

项目github地址及源码:
https://github.com/yunwei37/tryC

这一章开始进入解释器的核心部分: 语法分析器;

我们来看看两个概念,EBNF和递归下降文法,以及如何用这两个方法来计算tryC中的表达式。

基本概念

就像之前所说的那样,语法分析指将词法分析得到的标记流(token)进行分析,组成事先定义好的有意义的语句。那么如何完成这样一个工作呢?我们可以借助一个叫“BNF”的数学工具。

BNF与上下文无关文法

Backus-Naur符号(就是众所周知的BNF或Backus-Naur Form)是描述语言的形式化的数学方法,由John Backus (也许是Peter Naur)开发,最早用于描述Algol 60编程语言的语法。

BNF类似一种数学游戏:从一个符号开始(叫做起始标志,实例中常用S表示),然后给出替换前面符号的规则。

BNF语法定义的语言是一个字符串集合,可以按照下述规则书写,这些规则叫做书写规范(产生式规则),例如一个四则运算表达式可以表示为:

1
2
exp -> exp op exp | ( exp ) | number
op -> + | - | * | /

其中’|’用于表示可选择的不同项,”->”用于表示推导规则,从产生式左边的符号可以推导出产生式右边的符号;

要解析一个表达式,我们可以完成这样一个替换:对于

1
(3+2)*4

可以替换为

1
2
3
4
exp => exp op exp => exp * number
=> ( exp ) * number
=> ( exp op exp ) * number
=> ( number + number ) * number

其中我们把能够被替换的符号叫做非终结符,不能被替换的叫做终结符。

上下文无关文法就是说,这个文法中所有的产生式左边只有一个非终结符,就像上面写的那个文法一样。通常我们在编译器构建中使用的都是上下文无关文法。

EBNF

EBNF是基本巴科斯范式(BNF)元语法符号表示法的一种扩展,主要对BNF中常见的两种情况,即重复项和可选项添加了相应的语法规则,如用方括号”[ …. ]”
表示可选部分,用花括号”{ … }”表示重复出现的部分,如上面那个文法可以改写为:

1
2
exp -> exp { op exp } | ( exp ) | number
op -> + | - | * | /

又比如对于if语句可以写成:

1
if-stmt -> if ( exp ) statement; [ else statement; ]

递归下降文法

递归下降分析法也很简单,就是用函数的调用来模拟BNF的替换过程,我们只需要为每个非终结符定义一个分解函数,它就能从起始非终结符开始,不断地调用非终结符的分解函数,不断地对非终结符进行分解,直到匹配输入的终结符。

当然,递归下降分析并不是对于所有的文法都能正常使用的,例如经典的左递归问题:比如这样一个文法

1
2
exp -> exp { op exp } | ( exp ) | number
op -> + | - | * | /

对于exp的替换需要调用exp的分解函数,而exp的分解函数一进来就调用它自身(即最左边的符号),就会导致无限递归。这时就需要对文法进行改造。

实际上,EBNF文法就是为了映射递归下降分析法的具体程序实现而设计的,因此我们这里就用EBNF文法来实现递归下降分析。

来看看怎样用递归下降文法计算tryC中的表达式

上面说了一大堆,现在看看实际的计算表达式的实现是怎样的呢

算术表达式

tryC中需要计算四则运算表达式的EBNF文法如下:

1
2
3
4
5
exp -> term { addop term }
term -> factor { mulop factor }
factor -> number | ( exp )
addop -> + | -
mulop -> * | /

这里对文法进行了一定的改造,让它能够正确表达四则运算的优先级,同时避免了左递归的问题,具体可以自己试着验证一下。

tryC中算术表达式具体的代码实现(就是上述文法直接转换过来的啦):

(在下一篇文章中还会提及表达式中对变量的处理过程)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
double term() {
double temp = factor();
while (token == '*' || token == '/') {
if (token == '*') {
match('*');
temp *= factor();
}
else {
match('/');
temp /= factor();
}
}
return temp;
}

double factor() {
double temp = 0;
if (token == '(') {
match('(');
temp = expression();
match(')');
}
else if(token == Num || token == Char){
temp = token_val.val;
match(Num);
}
else if (token == Sym) {
temp = token_val.ptr->value;
match(Sym);
}
else if (token == FuncSym) {
return function();
}
else if (token == ArraySym) {
symbol* ptr = token_val.ptr;
match(ArraySym);
match('[');
int index = (int)expression();
if (index >= 0 && index < ptr->value) {
temp = ptr->pointer.list[index].value;
}
match(']');
}
return temp;
}

double expression() {
double temp = term();
while (token == '+' || token == '-') {
if (token == '+') {
match('+');
temp += term();
}
else {
match('-');
temp -= term();
}
}
return temp;
}

布尔表达式

tryC中同样设计了布尔表达式:

tryC中需要计算四则运算表达式的EBNF文法如下:

1
2
3
4
boolOR = boolAND { '||' boolAND }
boolAND = boolexp { '||' boolexp }
boolexp -> exp boolop exp | ( boolOR ) | !boolexp
boolop -> > | < | >= | <= | ==

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
int boolexp() {
if (token == '(') {
match('(');
int result = boolOR();
match(')');
return result;
}
else if (token == '!') {
match('!');
return boolexp();
}
double temp = expression();
if (token == '>') {
match('>');
return temp > expression();
}
else if (token == '<') {
match('<');
return temp < expression();
}
else if (token == GreatEqual) {
match(GreatEqual);
return temp >= expression();
}
else if (token == LessEqual) {
match(LessEqual);
return temp <= expression();
}
else if (token == Equal) {
match(Equal);
return temp == expression();
}
return 0;
}

int boolAND() {
int val = boolexp();
while (token == AND) {
match(AND);
if (val == 0) return 0; // short cut
val = val & boolexp();
if (val == 0) return 0;
}
return val;
}

int boolOR() {
int val = boolAND();
while (token == OR) {
match(OR);
if (val == 1) return 1; // short cut
val = val | boolAND();
}
return val;
}

一些重要概念

  • 终结符/非终结符
  • BNF/EBNF
  • 上下文无关文法
  • 递归下降法

可对照源码查看(如果觉得写得还行麻烦您帮我点个star哦)
https://github.com/yunwei37/tryC