上一章词法分析的内容里我们介绍了解析数字的方法,当时还提到了对ID的解析,但是因为当时还用不到ID类型,所以就没有做对应的解析,这一章我们将会讲解下ID类型的解析方法。

ID类型通常用在变量名和函数名上,变量要应用的话至少还得实现赋值表达式,所以我们先用ID类型来尝试实现函数调用功能。注意是调用我们在计算器里内置的函数,暂时还没有办法动态定义新的函数。

ID类型的词法分析

有了上一章的基础,ID类型的解析应该对大家是易如反掌了,简单到我都懒得画状态机图了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct {
int type;
int value;
char* name;
} slm_token;

void next(slm_expr *e) {
...
if (isalpha(*e->expStr)) {
e->token.type = SLM_EXPRESSION_TOKEN_ID;
const char *start = e->expStr;
do {
(e->expStr)++;
} while (isalpha(*e->expStr) || isdigit(*e->expStr));
size_t length = e->expStr - start;
char *name = calloc(length + 1, sizeof(char));
strncpy(name, start, length);
name[length] = '\0';
e->token.name = name;
}
...
}

我们在slm_token结构体里新增了一个name字段用来存储解析出的ID,这里的ID型token以字母开头,后面可以跟着多位字母或数字。C语言里的内存管理是要重点注意的,一定要在适当的时机释放掉自己申请的内存,我一开始也漏了一处😂。

函数调用的语法分析

哈哈,又回到语法分析步骤了。回到语法分析,首先要写的就是文法,这次只列出来要修改的文法:

1
2
3
4
factor -> number | func | '(' expr ')'
func -> func1 | func2
func1 -> id '(' expr ')'
func2 -> id '(' expr ',' expr ')'

我们只打算支持三个函数:max(x, y)min(x, y)abs(x)。因为这里只有单参数和双参数两种情况,所以文法就直接生硬的把所有情况列出来了。有了给定的文法,想必写逻辑也不是难事。因为懒得去弄一个新的变量暂存函数名字串,所以我直接把三个函数展开成三个if段来写:

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
62
63
64
65
66
67
68
69
70
71
72
73
int func(slm_expr *e)
{
if (e->token.type != SLM_EXPRESSION_TOKEN_ID || !e->token.name) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_ID);
}
int result;
if (strcmp(e->token.name, "max") == 0) {
TRY(next(e));
// '('
if (e->token.type != SLM_EXPRESSION_TOKEN_OPEN) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_OPEN_PARENTHESIS);
}
TRY(next(e));
// arg1
int arg1 = TRY(expr(e));
// ','
if (e->token.type != SLM_EXPRESSION_TOKEN_COMMA) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_COMMA);
}
TRY(next(e));
// arg2
int arg2 = TRY(expr(e));
// ')'
if (e->token.type != SLM_EXPRESSION_TOKEN_CLOSE) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_CLOSE_PARENTHESIS);
}
TRY(next(e));
// result
result = arg1 >= arg2 ? arg1 : arg2;
} else if (strcmp(e->token.name, "min") == 0) {
TRY(next(e));
// '('
if (e->token.type != SLM_EXPRESSION_TOKEN_OPEN) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_OPEN_PARENTHESIS);
}
TRY(next(e));
// arg1
int arg1 = TRY(expr(e));
// ','
if (e->token.type != SLM_EXPRESSION_TOKEN_COMMA) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_COMMA);
}
TRY(next(e));
// arg2
int arg2 = TRY(expr(e));
// ')'
if (e->token.type != SLM_EXPRESSION_TOKEN_CLOSE) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_CLOSE_PARENTHESIS);
}
TRY(next(e));
// result
result = arg1 <= arg2 ? arg1 : arg2;
} else if (strcmp(e->token.name, "abs") == 0) {
TRY(next(e));
// '('
if (e->token.type != SLM_EXPRESSION_TOKEN_OPEN) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_OPEN_PARENTHESIS);
}
TRY(next(e));
// arg1
result = TRY(expr(e));
// ')'
if (e->token.type != SLM_EXPRESSION_TOKEN_CLOSE) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_CLOSE_PARENTHESIS);
}
TRY(next(e));
// result
result = abs(result);
} else {
THROW(SLM_EXPRESSION_ERROR_UNKNOW_FUNCTION);
}
return result;
}

做一些测试验证下逻辑是否正常,函数调用功能就算完成啦。到这一步的完整代码可以在SlimeExpressionC-chapter5.1获得。

用函数表优化函数解析

不用我说,大家应该也觉得上一节的函数解析逻辑写得太丑了,这种代码不应该存在于我们的库里!

首先我们肯定不能给每一个函数写一个if段,那么我们肯定需要一个表来存储我们支持的所有函数,这样就可以在表里查询我们支持的函数该怎么处理了。然后就是要考虑函数怎么存在内存里呢?答案当然是用函数指针呀。我们先做的粗糙一点,把参数数量不同的函数定义成不同的结构体成员:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct {
const char *name;
int argCount;
int (*func1)(int);
int (*func2)(int, int);
} slm_func;

const int FuncCount = 3;
const int ArgMaxCount = 2;
const slm_func FuncList[FuncCount] = {
{.name = "max", .argCount = 2, .func2 = &slm_max},
{.name = "min", .argCount = 2, .func2 = &slm_min},
{.name = "abs", .argCount = 1, .func1 = &slm_abs},
};

这样,我们的函数表就先搞定了。把函数指针对应的函数给实现一下:

1
2
3
4
5
6
7
8
9
10
11
int slm_abs(int x) {
return x < 0 ? -x : x;
}

int slm_max(int x, int y) {
return x >= y ? x : y;
}

int slm_min(int x, int y) {
return x <= y ? x : y;
}

接下来的重头戏就是对func函数的改造啦,有了思路大家应该也大概能知道实现是什么样的了:

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
int func(slm_expr *e)
{
if (e->token.type != SLM_EXPRESSION_TOKEN_ID || !e->token.name) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_ID);
}
for (int i = 0; i < FuncCount; i++) {
slm_func funcItem = FuncList[i];
if (strcmp(e->token.name, funcItem.name) == 0) {
TRY(next(e));
// '('
if (e->token.type != SLM_EXPRESSION_TOKEN_OPEN) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_OPEN_PARENTHESIS);
}
TRY(next(e));
// arg1
int args[ArgMaxCount];
args[0] = TRY(expr(e));
// arg2 ~ argN
for (int j = 1; j < funcItem.argCount; j++) {
// ','
if (e->token.type != SLM_EXPRESSION_TOKEN_COMMA) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_COMMA);
}
TRY(next(e));
// arg2 ~ argN
args[j] = TRY(expr(e));
}
// ')'
if (e->token.type != SLM_EXPRESSION_TOKEN_CLOSE) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_CLOSE_PARENTHESIS);
}
TRY(next(e));
// result
switch (funcItem.argCount) {
case 1:
return (*funcItem.func1)(args[0]);
break;
case 2:
return (*funcItem.func2)(args[0], args[1]);
break;
}
break;
}
}
THROW(SLM_EXPRESSION_ERROR_UNKNOW_FUNCTION);
}

当然这代码还是有优化空间的,比如我们可以用hash表来存储函数表,加快检索的效率;比如我们可以用链表或者数组之类的手段传递参数,这样就可以动态的支持无限多的参数。不过这些就不深入在这里展开啦,目前完成的完整的代码放在SlimeExpressionC-chapter5.2

借助函数表也是以后我们实现动态定义新函数的关键点,到时候大家把FuncList定义成可变的就好,具体深入的做法这里我也不展开了,因为那个已经超出入门课的范畴啦!

入门课总结

到这里我们的编译原理入门课就告一段落了。通过实现一些简单的表达式解析计算功能,我们把编译器前端的语法分析和词法分析工作原理讲了个大概。过程中也介绍了一些设计编译器的方法,大家掌握了之后应该也可以在其基础上,做出一些自己想要的功能,例如实现变量和赋值表达式等。我也只能做到领大家入个门,更深入的知识就需要大家自己再去找资料深入学习啦(前言里我也列了一些资料)。

那么希望我的入门课对你有所帮助。如果以后我的懒癌痊愈了,兴许会再写个编译原理中级课吧~再见~😁

其它章节

(前言)实现一个表达式解析计算器

(一)用最简单的语法分析器解析加减法

(二)递归解析中怎么处理运算符优先级

(三)简单错误处理逻辑以及负数的解析

(四)用词法解析处理多位数字和空白符

(五)解析ID型词法和函数调用语法

001