目录
前言
通过开发一门类 Lisp 的编程语言来理解编程语言的设计思想，本实践来自著名的《Build Your Own Lisp》。
- 代码实现：https://github.com/JmilkFan/Lispy
前文列表
《用 C 语言开发一门编程语言 — 交互式解析器l》
《用 C 语言开发一门编程语言 — 语法解析器运行原理》
波兰表达式
波兰表达式（Polish Notation），也称为逆波兰表达式，由波兰数学家扬·卢卡谢维奇提出，是一种用前缀形式表示算术表达式的方法，所以也称为前缀表达式。
所谓前缀表达式，即：操作符位于其操作数之前，而不是在中间或之后。这种表达形式的好处在于可以尽可能的避免使用括号，以及避免处理操作符的优先级。区别于常见的中缀表达式，必须要通过括号来解决操作符优先级的问题。
举例来说，下述两种不同表达式的意义是一致的：
// 中缀表达式，需要处理 * 和 + 的优先级。
2 + 3 * 4
// 前缀表达式，不需要关心操作符的优先级，这是有顺序决定的。
+ 2 * 3 4
- 总是以 Operator（操作符）开头。
- Operator 后面可以是 Number（操作数），也可以是 Expression（表达式）。
- Expression 又可以由 Operator 和 Number 或 Other Expression 组成。
综上采用波兰表达式作为 Lispy 的算术表达式，主要的目的有在于其可以有效简化了语法规则和解析器的实现。然而，波兰表达式的缺点在于阅读不友好，尤其对于复杂的计算式子。但这对于 Lispy 来说不是关键的问题。
波兰表达式的语法规则定义
在实现波兰表达式解析器之前，我们首先需要定义其语法规则。
经过观察，我们可以总结出波兰表达式的以下语法规则：
所以我们对波兰表达式进行了如下解构和描述：
波兰表达式的词法规则定义
有了语法规则的描述之后，我们还需要定义词法规则，即：对针对表达式的输入进行约束，例如：如何表达开始和结束输入、如何规定可选字符和字符范围等。因为一个任意的输入中，很可能包含了一些解析器还没定义清楚的结构。
我们考虑使用正则表达式（Regular Expression）来实现这一目的。
正则表达式适合定义一些小型的语法规则，例如单词或是数字等。正则表达式不支持复杂的规则，但它清晰且精确地界定了输入是否符合规则。在 mpc 中，我们需要将正则表达式包裹在一对 / 中。例如：Number 可以用 /-?[0-9]+/ 来表示。
波兰表达式解析器
根据上面的分析，我们最终基于 MPC 来实现一个波兰表达式的解析器，让我们的 Lispy 编程语言可以理解并处理这一算数运算类型。
语法解析实现
#include <stdio.h>
#include <stdlib.h>
#include "mpc.h"
#ifdef _WIN32
#include <string.h>
static char buffer[2048];
char *readline(char *prompt) {
fputs(prompt, stdout);
fgets(buffer, 2048, stdin);
char *cpy = malloc(strlen(buffer) + 1);
strcpy(cpy, buffer);
cpy[strlen(cpy) - 1] = '\0';
return cpy;
}
void add_history(char *unused) {}
#else
#ifdef __linux__
#include <readline/readline.h>
#include <readline/history.h>
#endif
#ifdef __MACH__
#include <readline/readline.h>
#endif
#endif
int main(int argc, char *argv[]) {
/* 定义波兰表达式所包含的各个组成部分的 Parsers。*/
mpc_parser_t *Number = mpc_new("number"); // 数字解析器
mpc_parser_t *Operator = mpc_new("operator"); // 操作数解析器
mpc_parser_t *Expr = mpc_new("expr"); // 表达式解析器
mpc_parser_t *Lispy = mpc_new("lispy"); // lispy 解析器
/* Define them with the following Language */
mpca_lang(MPCA_LANG_DEFAULT,
" \
number : /-?[0-9]+/ ; \
operator : '+' | '-' | '*' | '/' ; \
expr : <number> | '(' <operator> <expr>+ ')' ; \
lispy : /^/ <operator> <expr>+ /$/ ; \
",
Number, Operator, Expr, Lispy);
puts("Lispy Version 0.1");
puts("Press Ctrl+c to Exit\n");
while(1) {
char *input = NULL;
input = readline("lispy> ");
add_history(input);
/**
* 解析用户的每一条输入。
* 调用了 mpc_parse 函数，并将 Lispy 解析器和用户输入 input 作为参数。
* 它将解析的结果保存到 &r 中，如果解析成功，函数返回值为 1，失败为 0。
*/
mpc_result_t r;
if (mpc_parse("<stdin>", input, Lispy, &r)) {
/**
* 如果解析成功，则生成一个 Output，并保存到 r.output。
* 可以使用 mpc_ast_print 将 Output 打印，使用 mpc_ast_delete 将其删除。
*/
mpc_ast_print(r.output);
mpc_ast_delete(r.output);
} else {
/**
* 如果解析失败，则生成一个 Error，并保存到 r.error。
* 可以使用 mpc_err_print 将 Error 打印，使用 mpc_err_delete 将其删除。
*/
mpc_err_print(r.error);
mpc_err_delete(r.error);
}
free(input);
}
/* Undefine and delete our parsers */
mpc_cleanup(4, Number, Operator, Expr, Lispy);
return 0;
}
- 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
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
编译：
gcc -std=c99 -Wall main.c mpc.c -lreadline -lm -o main
- 1
运行，尝试解析一条波兰表达式 + 5 (* 2 2)。
Lispy Version 0.1
Press Ctrl+c to Exit
lispy> + 5 (* 2 2)
>
regex
operator|char:1:1 '+'
expr|number|regex:1:3 '5'
expr|>
char:1:5 '('
operator|char:1:6 '*'
expr|number|regex:1:8 '2'
expr|number|regex:1:10 '2'
char:1:11 ')'
regex
lispy> hello
<stdin>:1:1: error: expected '+', '-', '*' or '/' at 'h'
lispy> / 1dog
<stdin>:1:4: error: expected one of '0123456789', '-', one or more of one of '0123456789', '(', newline or end of input at 'd'
lispy>
<stdin>:1:1: error: expected '+', '-', '*' or '/' at end of input
lispy> ^C
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
可以看见，上述的正常输出就是一个 AST（Abstract Syntax Tree，抽象语法树），它用来表示用户输入的表达式的结构。其中，操作数（Number）和操作符（Operator）等需要被处理的实际数据都位于叶子节点上。而非叶子节点上则包含了遍历和求值的信息。
运算处理实现
上面我们在通过 MPC 对波兰表达式进行了词法分析、语法分析后，得到了相应的 AST（抽象语法树）。那么，现在我们可以对它进行求值运算了。
但在最终实现之前，我们还需要对 MPC 输出的 AST 结构有一定的了解。
MPC AST 数据结构
MPC AST 的结构体定义如下：
typedef struct mpc_ast_t {
char *tag;
char *contents;
mpc_state_t state;
int children_num;
struct mpc_ast_t **children;
} mpc_ast_t;
- 5
- 6
- 7
- tag（节点标签）：它表示了解析这个节点时所用到的所有规则。例如：
expr|number|regex。tag 字段非常重要，因为它可以让我们知道创建节点时所匹配到的规则。 - contents（节点内容）：包含了节点中具体的操作数和操作符内容，例如：
*、(、5。- 对于表示分支的非叶子节点而言，这个字段是空的。
- 而对于叶子节点，则包含了操作数或操作符的字符串形式。
- state（节点状态）：包含了解析器发现这个节点时所处的状态，例如：行数和列数等信息。
- children_num 和 children：用于帮助遍历 AST 树。前者告诉我们有多少个子节点，后者则是包含了这些节点的数组。其中，children 的数据类型为
mpc_ast_t **二重指针类型，是一个指针数组。
添加下列语句，我们可以打印出 MPC AST 的字段数据：
/* Load AST from output */
mpc_ast_t *a = r.output;
printf("Tag: %s\n", a->tag);
printf("Contents: %s\n", a->contents);
printf("Number of children: %i\n", a->children_num);
/* Get First Child */
mpc_ast_t *c0 = a->children[0];
printf("First Child Tag: %s\n", c0->tag);
printf("First Child Contents: %s\n", c0->contents);
printf("First Child Number of children: %i\n", c0->children_num);
- 5
- 6
- 7
- 8
- 9
- 10
- 11
使用递归来遍历 AST
树的每个子节点都是树，每个子节点的子节点也是树，以此类推。可见，树形结构是递归和重复的。
素以，如果我们想编写函数处理所有可能的情况，就必须要保证函数可以处理任意深度，我们可以使用递归函数的天生优势来轻松地处理这种重复自身的结构。
递归函数就是在执行的过程中调用自身的函数。理论上，递归函数会无穷尽地执行下去。但实际上，递归函数对于不同的输入会产生不同的输出，如果我们每次递归都改变或使用不同的输入，并设置递归终止的条件，我们就可以使用递归实现预期的效果。例如：使用递归来计算树形结构中节点个数。
首先考虑最简单的情况，如果输入的树没有子节点，我们只需简单的返回 1 表示根节点就行了。如果输入的树有一个或多个子节点，这时返回的结果就是根节点再加上所有子节点的值。
使用递归，遍历统计子节点的数量：
int number_of_nodes(mpc_ast_t* t) {
if (t->children_num == 0) { return 1; }
if (t->children_num >= 1) {
int total = 1;
for (int i = 0; i < t->children_num; i++) {
total = total + number_of_nodes(t->children[i]);
}
return total;
}
}
- 5
- 6
- 7
- 8
- 9
- 10
求值运算
lispy> + 5 (* 2 2)
>
regex
operator|char:1:1 '+'
expr|number|regex:1:3 '5'
expr|>
char:1:5 '('
operator|char:1:6 '*'
expr|number|regex:1:8 '2'
expr|number|regex:1:10 '2'
char:1:11 ')'
regex
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
从 AST 我们知道操作数（Number）和操作符（Operator）等需要被处理的有效数据都位于叶子节点上。而非叶子节点上则包含了遍历和求值的信息。所以，在实现代码之前再好好总结一下 AST 输出的特征：
- 有 number 标签的节点一定是一个数字，并且没有子节点。我们可以直接将其转换为一个数字。
- 如果一个节点有 expr 标签，但没有 number 标签，那么第一个子节点永远是
(字符，最后一个子节点是)字符。我们需要看他的第二个子节点是什么操作符，然后我们需要使用这个操作符来对后面的子节点进行求值。
在对语法树进行求值的时候，还需要保存计算的结果。在这里，我们使用 C 语言中 long 类型。另外，为了检测节点的类型，或是为了获得节点中保存的数值，我们会用到节点中的 tag 和 contents 字段。这些字段都是字符串类型的。
我们引入一些辅助性的库函数：
- 使用 strcmp 来检查应该使用什么操作符；
- 使用 strstr 来检测 tag 中是否含有某个字段。
#include <stdio.h>
#include <stdlib.h>
#include "mpc.h"
#ifdef _WIN32
#include <string.h>
static char buffer[2048];
char *readline(char *prompt) {
fputs(prompt, stdout);
fgets(buffer, 2048, stdin);
char *cpy = malloc(strlen(buffer) + 1);
strcpy(cpy, buffer);
cpy[strlen(cpy) - 1] = '\0';
return cpy;
}
void add_history(char *unused) {}
#else
#ifdef __linux__
#include <readline/readline.h>
#include <readline/history.h>
#endif
#ifdef __MACH__
#include <readline/readline.h>
#endif
#endif
/* Use operator string to see which operation to perform */
long eval_op(long x, char *op, long y) {
if (strcmp(op, "+") == 0) { return x + y; }
if (strcmp(op, "-") == 0) { return x - y; }
if (strcmp(op, "*") == 0) { return x * y; }
if (strcmp(op, "/") == 0) { return x / y; }
return 0;
}
long eval(mpc_ast_t *t) {
/* If tagged as number return it directly.
* 有 number 标签的节点一定是一个数字，并且没有子节点
* 直接将其转换为一个数字。
*/
if (strstr(t->tag, "number")) {
return atoi(t->contents);
}
/* The operator is always second child.
* 如果一个节点有 expr 标签，但没有 number 标签，那么它的第二个子节点肯定是操作符。
* 这个操作符后面的子节点肯定是操作数。
*/
char *op = t->children[1]->contents;
long x = eval(t->children[2]);
/* 迭代剩余的子节点，并求值。 */
int i = 3;
while (strstr(t->children[i]->tag, "expr")) {
x = eval_op(x, op, eval(t->children[i]));
i++;
}
return x;
}
int main(int argc, char *argv[]) {
/* Create Some Parsers */
mpc_parser_t *Number = mpc_new("number");
mpc_parser_t *Operator = mpc_new("operator");
mpc_parser_t *Expr = mpc_new("expr");
mpc_parser_t *Lispy = mpc_new("lispy");
/* Define them with the following Language */
mpca_lang(MPCA_LANG_DEFAULT,
" \
number : /-?[0-9]+/ ; \
operator : '+' | '-' | '*' | '/' ; \
expr : <number> | '(' <operator> <expr>+ ')' ; \
lispy : /^/ <operator> <expr>+ /$/ ; \
",
Number, Operator, Expr, Lispy);
puts("Lispy Version 0.1");
puts("Press Ctrl+c to Exit\n");
while(1) {
char *input = NULL;
input = readline("lispy> ");
add_history(input);
/* Attempt to parse the user input */
mpc_result_t r;
if (mpc_parse("<stdin>", input, Lispy, &r)) {
/* On success print and delete the AST */
long result = eval(r.output);
printf("%li\n", result);
mpc_ast_delete(r.output);
} else {
/* Otherwise print and delete the Error */
mpc_err_print(r.error);
mpc_err_delete(r.error);
}
free(input);
}
/* Undefine and delete our parsers */
mpc_cleanup(4, Number, Operator, Expr, Lispy);
return 0;
}
- 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
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
编译：
gcc -std=c99 -Wall main.c mpc.c -lreadline -lm -o main
- 1
运行：
lispy> + 4 5 // 4+5
9
lispy> - 8 3 // 8-3
5
lispy> * 6 2 // 6 * 2
12
lispy> / 10 5 // 10/5
2
lispy> - (* 10 10) (+ 1 1 1) // (10*10) - (1+1+1)
97
- 5
- 6
- 7
- 8
- 9
- 10
