上一章词法分析的内容里我们介绍了解析数字的方法，当时还提到了对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));
int arg1 = TRY(expr(e));
if (e->token.type != SLM_EXPRESSION_TOKEN_COMMA) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_COMMA);
}
TRY(next(e));
int arg2 = TRY(expr(e));
if (e->token.type != SLM_EXPRESSION_TOKEN_CLOSE) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_CLOSE_PARENTHESIS);
}
TRY(next(e));
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));
int arg1 = TRY(expr(e));
if (e->token.type != SLM_EXPRESSION_TOKEN_COMMA) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_COMMA);
}
TRY(next(e));
int arg2 = TRY(expr(e));
if (e->token.type != SLM_EXPRESSION_TOKEN_CLOSE) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_CLOSE_PARENTHESIS);
}
TRY(next(e));
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));
result = TRY(expr(e));
if (e->token.type != SLM_EXPRESSION_TOKEN_CLOSE) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_CLOSE_PARENTHESIS);
}
TRY(next(e));
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));
int args[ArgMaxCount];
args[0] = TRY(expr(e));
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));
args[j] = TRY(expr(e));
}
if (e->token.type != SLM_EXPRESSION_TOKEN_CLOSE) {
THROW(SLM_EXPRESSION_ERROR_EXPECT_CLOSE_PARENTHESIS);
}
TRY(next(e));
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型词法和函数调用语法
