前言

通过开发一门类 Lisp 的编程语言来理解编程语言的设计思想，本实践来自著名的《Build Your Own Lisp》。

代码实现：https://github.com/JmilkFan/Lispy

前文列表

《用 C 语言开发一门编程语言 — 交互式解析器l》
《用 C 语言开发一门编程语言 — 语法解析器运行原理》
《用 C 语言开发一门编程语言 — 波兰表达式解析器》

数值存储器

在实现了波兰表达式解析器之后，我们开发了一个最简单的 “读取-求值-输出-循环" 流程。在接下来我们继续实现其他更复杂的表达式解析器之前，还需要先实现一个数值存储器，称为 Lispy Values，作为 Lisp REPL 的核心存储器，用于存储 AST（抽象语法树）的数值，以及用于存储更多的状态数值。

我们首先从操作数和错误信息这 2 种 Value Types 入手。就目前实现的波兰表达式解析器而言，基于 MPC 已经可以很好的支持语法分析层面的错误检测了，但语义层面的错误检测还是空缺，例如：对于表达式求值过程中产生的错误，这部分需要我们实现相应的逻辑。

实现效果：

lispy> / 10 0
Error: Division By Zero!

lispy>
<stdin>:1:1: error: expected '+', '-', '*' or '/' at end of input

lispy> / 10 2
5

存储器结构定义

定义一个 lval（Lispy Value）结构体，作为数值存储器，有 num（操作数）和 err（错误检测）这 2 种 Value Types。其中：

/* Declare New lval Struct */
typedef struct {
  int  type;
  long num;
  int  err;
} lval;
1
2
3
4
5
6

lval.type 成员声明为 int 类型。同时，定义一个 Value Type Enumeration，用作类型越苏，也提高了代码的可读性。
- 如果 type 为 0，表示该 lval 是一个 num 类型。
- 如果 type 为 1，表示该 lval 是一个 err 类型。

/* Create Enumeration of Possible lval Types */
enum {
	LVAL_NUM,  // 默认整型数值为 0
	LVAL_ERR   // 默认整型数值为 0 + 1
};
1
2
3
4
5

lval.err 成员也声明为 int 类型，结合 Error Enumeration，以表示不同的错误原因。

/* Create Enumeration of Possible Error Types */
enum {
	LERR_DIV_ZERO,  // 除数为零
	LERR_BAD_OP,	// 操作符未知
	LERR_BAD_NUM	// 操作数过大
};
1
2
3
4
5
6

存储器构造函数

为 num 和 err 这 2 种 Value Types 分别定义一个构造函数，用于完成数值存储器的初始化：

/* Create a new number type lval
 * 因为使用无名创建方式定义的 lval 结构体是自定义数据类型，
 * 所以我们可以使用 lval 来声明函数返回值类型。
 */
lval lval_num(long x) {
  lval v;
  v.type = LVAL_NUM;
  v.num = x;
  return v;
}

/* Create a new error type lval */
lval lval_err(int x) {
  lval v;
  v.type = LVAL_ERR;
  v.err = x;
  return v;
}

/* Print an "lval" */
void lval_print(lval v) {
  switch (v.type) {
    /* In the case the type is a number print it */
    /* Then 'break' out of the switch. */
    case LVAL_NUM:
      printf("%li", v.num);
      break;

    /* In the case the type is an error */
    case LVAL_ERR:
      /* Check what type of error it is and print it */
      if (v.err == LERR_DIV_ZERO) {
        printf("Error: Division By Zero!");
      }
      if (v.err == LERR_BAD_OP)   {
        printf("Error: Invalid Operator!");
      }
      if (v.err == LERR_BAD_NUM)  {
        printf("Error: Invalid Number!");
      }
      break;
  }
}

/* Print an "lval" followed by a newline */
void lval_println(lval v) {
	lval_print(v);
	putchar('\n');
}
910
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

语义错误检测实现

最后，我们使用 num lval 来存储表达式操作数，使用 err lval 来存储错误检测结果。此外，还要在 “输入“ 逻辑中实现输入校验检测功能，在 “求值“ 逻辑中实现基本的数字运算错误检测功能。

#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

/* Create Enumeration of Possible lval Types */
enum {
    LVAL_NUM,
    LVAL_ERR
};

/* Create Enumeration of Possible Error Types */
enum {
    LERR_DIV_ZERO,
    LERR_BAD_OP,
    LERR_BAD_NUM
};

/* Declare New lval Struct
 * 使用 lval 枚举类型来替换掉之前使用的 long 类型。
 * 单存的 long 类型没办法携带成功或失败、若失败，是什么失败等信息。
 * 所以我们定义 lval 枚举类型来作为 “算子” 及 “结果”。
 */
typedef struct {
    int type;
    long num;
    int err;
} lval;

/* Create a new number type lval */
lval lval_num(long x) {
    lval v;
    v.type = LVAL_NUM;
    v.num = x;
    return v;
}

/* Create a new error type lval */
lval lval_err(long x) {
    lval v;
    v.type = LVAL_ERR;
    v.err = x;
    return v;
}

/* Print an "lval"
 * 通过对 lval 枚举类型变量的解析来完成对计算结果的解析。
 */
void lval_print(lval v) {
    switch (v.type) {
        /* In the case the type is a number print it */
        case LVAL_NUM:
            printf("%li", v.num);
            break;

        /* In the case the type is an error */
        case LVAL_ERR:
            /* Check what type of error it is and print it */
            if (v.err == LERR_DIV_ZERO) {
                printf("Error: Division By Zero!");
            }
            else if (v.err == LERR_BAD_OP) {
                printf("Error: Invalid Operator!");
            }
            else if (v.err == LERR_BAD_NUM) {
                printf("Error: Invalid Number!");
            }
            break;
    }
}

/* Print an "lval" followed by a newline */
void lval_println(lval v) {
    lval_print(v);
    putchar('\n');
}

/* Use operator string to see which operation to perform */
lval eval_op(lval x, char *op, lval y) {

    /* If either value is an error return it
     * 如果 “算子” 的类型是错误，则直接返回。
     */
    if (x.type == LVAL_ERR) { return x; }
    if (y.type == LVAL_ERR) { return y; }

    /* Otherwise do maths on the number values
     * 如果 “算子” 是 Number，则取出操作数进行运算。
     */
    if (strcmp(op, "+") == 0) { return lval_num(x.num + y.num); }
    if (strcmp(op, "-") == 0) { return lval_num(x.num + y.num); }
    if (strcmp(op, "*") == 0) { return lval_num(x.num + y.num); }
    if (strcmp(op, "/") == 0) {
        /* If second operand is zero return error */
        if (y.type == LVAL_NUM) {
            return y.num == 0
                ? lval_err(LERR_DIV_ZERO)
                : lval_num(x.num / y.num);
        }
    }
    return lval_err(LERR_BAD_OP);
}

lval eval(mpc_ast_t *t) {

    /* If tagged as number return it directly. */
    if (strstr(t->tag, "number")) {
        /* Check if there is some error in conversion */
        errno = 0;

        /* 使用 strtol 函数进行字符串到数字的转换，
         * 这样就可以通过检测 errno 变量确定是否转换成功，
         * 对数据类型转换的准确性进行了加强。
         */
        long x = strtol(t->contents, NULL, 10);
        return errno != ERANGE
            ? lval_num(x)
            : lval_err(LERR_BAD_NUM);
    }

    /* The operator is always second child. */
    char *op = t->children[1]->contents;

    /* We store the third child in `x` */
    lval x = eval(t->children[2]);

    /* Iterate the remaining children and combining. */
    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 */
            lval result = eval(r.output);
            lval_println(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;
}
910
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216