用 C 语言开发一门编程语言 — S-表达式

Green

前文列表《用 C 语言开发一门编程语言 — 交互式解析器l》
《用 C 语言开发一门编程语言 — 跨平台的可移植性》
《用 C 语言开发一门编程语言 — 语法解析器》
《用 C 语言开发一门编程语言 — 抽象语法树》
《用 C 语言开发一门编程语言 — 异常处理》
使用 S-表达式进行重构所谓 S-表达式（Symbolic Expression，S-Expression，符号表达式）是指一种以人类可读的文本形式表达半结构化数据的数学标记语言。S-Expression 在 Lisp 家族的编程语言中被应用而为人所知。S-Expression 在 Lisp 中既用作代码，也用作数据，这使得它非常强大，能完成许多其他语言不能完成的事情。
为了拥有这个强大的特性，Lisp 将运算求值过程分为两个过程：

• 先存储：读取并存储输入。
• 再求值：对输入进行求值。
  

而不再是简单的 “输入 -> 运算 -> 输出”。
读取并存储输入
实现 S-Expression 语法解析器
首先实现 S-Expression 的读取，我们将原有的波兰表达式解析器改造为 S-Expression 解析器。
S-Expression 的语法规则非常简单：

• 小括号之间包含一组表达式
• 表达式可以是数字、操作符或是其他的 S-Expression
  

根据以往实现波兰表达式解析器的经验，我们再实现了 S-Expression 解析器。另外，为了方便后续的演进，我们还把 Operator（操作符）规则重定义为了 Symbol（符号）规定，使其可以表示更多的含义，例如：操作符、变量、函数等。

mpc_parser_t* Number = mpc_new("number");
mpc_parser_t* Symbol = mpc_new("symbol");
mpc_parser_t* Sexpr  = mpc_new("sexpr");
mpc_parser_t* Expr   = mpc_new("expr");
mpc_parser_t* Lispy  = mpc_new("lispy");

mpca_lang(MPCA_LANG_DEFAULT,
  "                      \
  number : /-?[0-9]+/ ;          \
  symbol : '+' | '-' | '*' | '/' ;     \
  sexpr  : '(' <expr>* ')' ;         \
  expr   : <number> | <symbol> | <sexpr> ; \
  lispy  : /^/ <expr>* /$/ ;         \
  ",
  Number, Symbol, Sexpr, Expr, Lispy);

mpc_cleanup(5, Number, Symbol, Sexpr, Expr, Lispy);

实现 S-Expression 存储器
为了存储输入的 S-Expression，我们需要在 Lisp 内部构建一个 **列表（数组）**结构，使其能够递归地表示数字、操作符号以及其他的列表。这一点，我们通过改造 lval 结构体来实现，并围绕器实现一系列的构造函数以及析构函数来完成。
首先，我们在表示 lval 类型的枚举变量中添加两个新的类型，分别表示 Symbols 和 S-Expression：

• LVAL_SYM：表示输入的符号，包括操作符，例如 + 等。
• LVAL_SEXPR：表示 S-Expression。
  

enum { LVAL_ERR, LVAL_NUM, LVAL_SYM, LVAL_SEXPR };

我们知道 S-Expression 肯定是一个可变长度的列表，而且结构体数据类型本身确实不可变长的，所以我们采用 结构体指针成员 的方式来突破这一局限。为 lval 结构体创建一个 cell 成员，cell 成员为一个二重指针类型，即：cell 本身是指针，指向数组结构的首元素，而这个数组又是一个指针数组 * lval[]，指针数据存放着若干个（可变长）指向 lval 结构体变量的指针。这样就可以构成一个可变长的、具有父子节点结构的树状数据结构。
另外，我们还需要知道 cell 数组中所包含的元素个数，所以创建了 count 字段。

typedef struct lval {
  int type;
  long num;
  /* Error and Symbol types have some string data */
  char* err;
  char* sym;
  /* Count and Pointer to a list of "lval*" */
  int count;
  struct lval** cell;
} lval;

为了让 lval 结构体可以直接存储具体的错误信息，而不只是一个错误代码，所以还增加了 char *err 字符串用来存储错误信息，这样我们就可以把之前编写的错误类型枚举变量删除掉了。另外，我们还需要使用一个 char *sym 字符串来表示 Symbols。
实现 lval 变量的构造函数
我们知道 C 函数实参的传入采用的是值传递，即传入一个数据的时候回发生 拷贝 动作，这一特性使得向 C 函数传入大型数据结构时性能低下，解决这一问题的好方法无疑是采用 指针形参 了。所以，我们重写以往的 lval 结构体类型变量的构造函数，让其返回 lval 结构体类型指针，而不再是整个变量。
这个问题在 Python 这类 引用语义 编程语言中不会存在，因为 Python 中的变量本质就是一个指针，指向实际的数据值，所以看似像函数传入了变量，实际只是传入了地址。在 C 语言这类 值语义 编程语言中，就需要显示的实现 指针类型形参 了，本质是一样的。
为此，我们使用 malloc 库函数以及 sizeof 运算符为 lval 结构体在堆上申请足够大的内存区域，然后使用 -> 操作符填充结构体中的相关字段。

/* Construct a pointer to a new Number lval */ 
lval* lval_num(long x) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_NUM;
  v->num = x;
  return v;
}

/* Construct a pointer to a new Error lval */ 
lval* lval_err(char* m) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_ERR;
  v->err = malloc(strlen(m) + 1);
  strcpy(v->err, m);
  return v;
}

/* Construct a pointer to a new Symbol lval */ 
lval* lval_sym(char* s) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_SYM;
  v->sym = malloc(strlen(s) + 1);
  strcpy(v->sym, s);
  return v;
}

/* A pointer to a new empty Sexpr lval */
lval* lval_sexpr(void) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_SEXPR;
  v->count = 0;
  v->cell = NULL;
  return v;
}

注：

• NULL 是什么？NULL 是一个指向内存地址 0 的特殊常量。按照惯例，它通常被用来表示空值或无数据。
• 什么要使用 strlen(s) + 1？在 C 语言中，字符串的本质是一个以空字符做为终止标记的字符数组，所以，C 语言字符串的最后一个字符一定是 \0。请确保所有的字符串都是按照这个约定来存储的，不然程序就会因为莫名其妙的错误退出。而 strlen 函数返回的是字符串的实际长度，不包含终止符，所以为了保证有足够的空间存储所有字符，我们需要在额外 +1。
  

实现 lval 变量的析构函数
既然我们在 lval 结构体类型变量的构造函数中采用了内存分配并返回指针引用的实现，那么在析构函数中自然就是完成内存空间的回收了。当某个 lval 变量完成使命之后，我们不仅需要删除它本身所指向的堆内存，还要轮询着依次删除它的指针成员所指向的堆内存。这样就不会导致内存的泄露了。
调用 free 函数来释放由 malloc 函数所申请的内存。

void lval_del(lval* v) {

  switch (v->type) {
  /* Do nothing special for number type */
  case LVAL_NUM: break;

  /* For Err or Sym free the string data */
  case LVAL_ERR: free(v->err); break;
  case LVAL_SYM: free(v->sym); break;

  /* If Sexpr then delete all elements inside */
  case LVAL_SEXPR:
    for (int i = 0; i < v->count; i++) {
    lval_del(v->cell[i]);
    }
    /* Also free the memory allocated to contain the pointers */
    free(v->cell);
  break;
  }

  /* Free the memory allocated for the "lval" struct itself */
  free(v);
}

值得注意的是，释放内存的时候也要讲究顺序，先释放干净结构体变量指针成员指向的堆内存，最后再释放结构体变量自身指向的堆内存，否则同样会出现诸如 double free or corruption (fasttop) 此类的内存崩溃。

读取 S-Expression
还需要明确的是，用户输入的只是单存的字符串，即便这些字符串看似符合语法解析器约束的语法规则，但就单存的输入内容而言还只是字符串。所以，我们还需要完成的工作就是将这些字符串转化为 Lisp 编程语言内部所能够理解的 S-Expression，即：将字符串按照一定的规则存储到 lval 结构体组成的数据结构中。
当读取到了用户的输入后，S-Expression 语法解析器首先会将输入的字符串解析为 S-Expression 抽象语法树，例如：(* 2 (+ 3 4)) 的 AST。

我们需要递归的查看 AST 中的每个节点，并根据节点的 tag 和 contents 成员信息构造出不同类型的 lval 结构体变量，再以指针的形式返回。最后才可能通过对 lval 结构体变量进行遍历求值而来得到最终的运行结果。
结合以往解析波兰表达式抽象语法树的经验，我们对 S-Expression AST 进行描述：

• 如果给定节点的被标记为 number 或 symbol，则我们可以调用对应的构造函数直接返回一个 lval *。
• 如果给定的节点被标记为 root 或 sexpr，则我们应该构造一个空的 S-Expression 类型的 lval *，并逐一将它的子节点加入。
  

lval* lval_read_num(mpc_ast_t* t) {
  errno = 0;
  long x = strtol(t->contents, NULL, 10);
  return errno != ERANGE ?
  lval_num(x) : lval_err("invalid number");
}

lval* lval_read(mpc_ast_t* t) {

  /* If Symbol or Number return conversion to that type */
  if (strstr(t->tag, "number")) { return lval_read_num(t); }
  if (strstr(t->tag, "symbol")) { return lval_sym(t->contents); }

  /* If root (>) or sexpr then create empty list */
  lval* x = NULL;
  if (strcmp(t->tag, ">") == 0) { x = lval_sexpr(); } 
  if (strstr(t->tag, "sexpr"))  { x = lval_sexpr(); }

  /* Fill this list with any valid expression contained within */
  for (int i = 0; i < t->children_num; i++) {
  if (strcmp(t->children[i]->contents, "(") == 0) { continue; }
  if (strcmp(t->children[i]->contents, ")") == 0) { continue; }
  if (strcmp(t->children[i]->tag,  "regex") == 0) { continue; }
  x = lval_add(x, lval_read(t->children[i]));
  }

  return x;
}

为了更加方便的向一个 S-Expression 中添加元素，我们实现一个 lval_add 函数，这个函数做了两件事情：

• 将 S-Expression 子表达式的数量加 1。
• 使用 realloc 函数为 cell 成员的长度重新扩大申请内存
  

lval* lval_add(lval* v, lval* x) {
  v->count++;
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  v->cell[v->count-1] = x;
  return v;
}

运算求值通过以上的过程，我们就完成了接受输入并存储的步骤，接下来就是进行运算求值。
S-Expression 的运算和波兰表达式的运算并无本质区别，都是对 AST 的遍历。但代码实现上肯定存在着差别：

• 首先取列表第一个元素为操作符
• 然后遍历所有剩下的元素，将它们作为操作数
  

可以把求值函数想象成某种转换器－－它读取 lval* 作为输入，通过某种方式将其转化为新的 lval* 并输出。

• 有些时候，求值函数不对输入做任何修改，原封不动的将其返回。例如：没有子节点，处理空表达式 {} 的情况；又例如：只有一个子节点的表达式，例如 {5}，这种情况我们应该将其包含的表达式直接返回。
• 有些时候，它会对输入的做一些改动；例如：S-Expression 是一个合法的表达式，并且有个多于一个的子节点。对于此种情况，我们使用稍后定义的函数 lval_pop 将第一个元素从表达式中分离开来。
• 而在大多数情况下，它会将输入的 lval* 删除，返回完全不同的东西。注意，如果要返回新的东西，一定要记得将原有的作为输入的 lval* 删除，以此保证内存资源的健康。例如：S-Expression 的任意一个子节点存在错误，我们就使用稍后定义的函数 lval_take 将遇到的第一个错误返回。
  

在对合法的 S-Expression 进行运算时，我们还需要：

• 检查确保它是一个 symbol。然后根据它的具体类型，将它和参数一起传入 builtin_op 函数计算求值。
• 如果它不是 symbol，我们就将它以及传进来的其它参数删除，然后返回一个错误。
  

lval* lval_eval_sexpr(lval* v) {

  /* Evaluate Children */
  for (int i = 0; i < v->count; i++) {
  v->cell[i] = lval_eval(v->cell[i]);
  }

  /* Error Checking */
  for (int i = 0; i < v->count; i++) {
  if (v->cell[i]->type == LVAL_ERR) { return lval_take(v, i); }
  }

  /* Empty Expression */
  if (v->count == 0) { return v; }

  /* Single Expression */
  if (v->count == 1) { return lval_take(v, 0); }

  /* Ensure First Element is Symbol */
  lval* f = lval_pop(v, 0);
  if (f->type != LVAL_SYM) {
  lval_del(f); lval_del(v);
  return lval_err("S-expression Does not start with symbol!");
  }

  /* Call builtin with operator */
  lval* result = builtin_op(v, f->sym);
  lval_del(f);
  return result;
}

lval* lval_eval(lval* v) {
  /* Evaluate Sexpressions */
  if (v->type == LVAL_SEXPR) { return lval_eval_sexpr(v); }
  /* All other lval types remain the same */
  return v;
}

lval* lval_pop(lval* v, int i) {
  /* Find the item at "i" */
  lval* x = v->cell[i];

  /* Shift memory after the item at "i" over the top */
  memmove(&v->cell[i], &v->cell[i+1],
  sizeof(lval*) * (v->count-i-1));

  /* Decrease the count of items in the list */
  v->count--;

  /* Reallocate the memory used */
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  return x;
}

lval* lval_take(lval* v, int i) {
  lval* x = lval_pop(v, i);
  lval_del(v);
  return x;
}

其中，lval_pop 和 lval_take 函数都是用于操作 lval 类型的通用型函数：

• lval_pop 函数：将所操作的 S-Expression 的第 i 个元素取出，并将其后面的子节点向前移动填补空缺，使得这个 S-Expression 不再包含这个子节点。然后将取出的子节点返回。需要注意的是，这个函数并不会将这个 S-Expression 本身删除。它只是从中取出某个子节点，剩下的子节点依旧保持原样。这意味着这两个部分都需要在某个地方通过 lval_del 函数来删除干净。
• lval_take 函数：和 lval_pop 函数类似，不过它在取出了目标子节点之后，就将 S-Expression 本身以及剩下的子节点都删除掉。它利用了 lval_pop 函数并做了一点小小的改变，却使得我们的代码可读性更高了一些。所以，与 lval_pop 相反，我们只需要保证被取出的子节点最终被释放掉即可。
  

我们还需要定义求值函数 builtin_op，它和我们在之前章节中定义的 eval_op 函数类似，但也需要改造成接受 lval * 类型指针形参。该函数对参数应该做更加严格的检查，对任何不是 LVAL_NUM 类型的 lval 结构体变量，都应该返回一个错误。因为是 求值运算 嘛。

lval* builtin_op(lval* a, char* op) {

  /* Ensure all arguments are numbers */
  for (int i = 0; i < a->count; i++) {
  if (a->cell[i]->type != LVAL_NUM) {
    lval_del(a);
    return lval_err("Cannot operate on non-number!");
  }
  }

  /* Pop the first element */
  lval* x = lval_pop(a, 0);

  /* If no arguments and sub then perform unary negation */
  if ((strcmp(op, "-") == 0) && a->count == 0) {
  x->num = -x->num;
  }

  /* While there are still elements remaining */
  while (a->count > 0) {

  /* Pop the next element */
  lval* y = lval_pop(a, 0);

  if (strcmp(op, "+") == 0) { x->num += y->num; }
  if (strcmp(op, "-") == 0) { x->num -= y->num; }
  if (strcmp(op, "*") == 0) { x->num *= y->num; }
  if (strcmp(op, "/") == 0) {
    if (y->num == 0) {
    lval_del(x); lval_del(y);
    x = lval_err("Division By Zero!"); break;
    }
    x->num /= y->num;
  }

  lval_del(y);
  }

  lval_del(a); return x;
}

• 首先，它确保所有的输入参数的类型都为数字。然后将第一个数字弹出开始计算。如果后面没有其它的子节点，并且操作符为减号时，它会对第一个数字进行取反操作。这确保了类似于 (- 5) 这种表达式依旧能够正确工作。
• 如果还有更多的参数，它就不断地从 *lval[] 数组中取出，遍历进行数学运算。如果做除法时遇到被除数为零的情况，就将临时变量 x 和 y 以及参数列表删除，并返回一个错误。
• 如果没有错误，参数列表最终会被删除，并返回一个新的表达式。
  

打印结果至此，Lisp 的 S-Expression 运算过程就基本结束了：

• 先存储：读取并存储输入。
• 再求值：对输入进行求值。
  

当然，最后我们还需要将运算结果打印出来。为了打印 S-Expression，我们创建一个新函数，遍历所有的子表达式，并将它们单独打印出来，以空格隔开，正如输入的时候一样。

void lval_print(lval* v);

void lval_expr_print(lval* v, char open, char close) {
  putchar(open);
  for (int i = 0; i < v->count; i++) {

  /* Print Value contained within */
  lval_print(v->cell[i]);

  /* Don't print trailing space if last element */
  if (i != (v->count-1)) {
    putchar(' ');
  }
  }
  putchar(close);
}

void lval_print(lval* v) {
  switch (v->type) {
  case LVAL_NUM:   printf("%li", v->num); break;
  case LVAL_ERR:   printf("Error: %s", v->err); break;
  case LVAL_SYM:   printf("%s", v->sym); break;
  case LVAL_SEXPR: lval_expr_print(v, '(', ')'); break;
  }
}

void lval_println(lval* v) { lval_print(v); putchar('\n'); }

注意，lval_expr_print 函数和 lval_print 函数互相调用了。C 语言提供了前置声明来解决这个问题。前置声明就是告诉编译器：“我保证有这个函数，你放心调用就是了”。所以，前置声明只定义了函数的形式，而没有函数体。它允许其他函数调用它，而具体的函数定义则在后面。函数声明只要将函数定义的函数体换成 ; 即可。在我们的程序中，应该将前置声明语句放在一个比 lval_expr_print 函数靠前的地方。
最后，次更新一下 main 函数，在其打印表达式之前，先将输入经由求值函数处理即可：

lval* x = lval_eval(lval_read(r.output));
lval_println(x);
lval_del(x);

源代码

#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,
  LVAL_SYM,
  LVAL_SEXPR
};

/* Declare New lval Struct */
typedef struct lval {
  int type;
  long num;

  /* Count and Pointer to a list of "lval*" */
  struct lval** cell;
  int count;

  /* Error and Symbol types have some string data */
  char *err;
  char *sym;
} lval;

/* Construct a pointer to a new Number lval */
lval *lval_num(long x) {
  lval *v = malloc(sizeof(lval));
  v->type = LVAL_NUM;
  v->num = x;
  return v;
}

/* Construct a pointer to a new Error lval */
lval *lval_err(char *msg) {
  lval *v = malloc(sizeof(lval));
  v->type = LVAL_ERR;
  v->err = malloc(strlen(msg) + 1);
  strcpy(v->err, msg);
  return v;
}

/* Construct a pointer to a new Symbol lval */
lval *lval_sym(char *sym) {
  lval *v = malloc(sizeof(lval));
  v->type = LVAL_SYM;
  v->sym = malloc(strlen(sym) + 1);
  strcpy(v->sym, sym);
  return v;
}

/* A pointer to a new empty Sexpr lval */
lval *lval_sexpr(void) {
  lval *v = malloc(sizeof(lval));
  v->type = LVAL_SEXPR;
  v->count = 0;
  v->cell = NULL;
  return v;
}


void lval_del(lval *v) {
  switch (v->type) {
    /* Do nothing special for number type */
    case LVAL_NUM:
      break;

    /* For Err or Sym free the string data */
    case LVAL_ERR:
      free(v->err);
      break;
    case LVAL_SYM:
      free(v->sym);
      break;

    /* If Sexpr then delete all elements inside */
    case LVAL_SEXPR:
      for (int i = 0; i < v->count; i++) {
        lval_del(v->cell[i]);
      }
      /* Also free the memory allocated to contain the pointers */
      free(v->cell);
      break;
  }
  /* Free the memory allocated for the "lval" struct itself */
  free(v);
}

lval *lval_add(lval *v, lval *x) {
  v->count++;
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  v->cell[v->count-1] = x;
  return v;
}

lval *lval_read_num(mpc_ast_t *t) {
  errno = 0;
  long x = strtol(t->contents, NULL, 10);
  return errno != ERANGE
    ? lval_num(x)
    : lval_err("invalid number");
}

lval *lval_read(mpc_ast_t *t) {
   /* If Symbol or Number return conversion to that type */
  if (strstr(t->tag, "number")) {
    return lval_read_num(t);
  }
  if (strstr(t->tag, "symbol")) {
    return lval_sym(t->contents);
  }

  /* If root (>) or sexpr then create empty list */
  lval *x = NULL;
  if (strcmp(t->tag, ">") == 0) {
    x = lval_sexpr();
  }
  if (strstr(t->tag, "sexpr"))  {
    x = lval_sexpr();
  }

  /* Fill this list with any valid expression contained within */
  for (int i = 0; i < t->children_num; i++) {
    if (strcmp(t->children[i]->contents, "(") == 0) { continue; }
    if (strcmp(t->children[i]->contents, ")") == 0) { continue; }
    if (strcmp(t->children[i]->tag,  "regex") == 0) { continue; }
    x = lval_add(x, lval_read(t->children[i]));
  }
  return x;
}

void lval_print(lval *v);

void lval_expr_print(lval *v, char open, char close) {
  putchar(open);
  for (int i = 0; i < v->count; i++) {

    /* Print Value contained within */
    lval_print(v->cell[i]);

    /* Don't print trailing space if last element */
    if (i != (v->count-1)) {
      putchar(' ');
    }
  }
  putchar(close);

}

/* Print an "lval*" */
void lval_print(lval *v) {
  switch (v->type) {
    case LVAL_NUM:   printf("%li", v->num); break;
    case LVAL_ERR:   printf("Error: %s", v->err); break;
    case LVAL_SYM:   printf("%s", v->sym); break;
    case LVAL_SEXPR: lval_expr_print(v, '(', ')'); break;
  }
}

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

lval *lval_pop(lval *v, int i) {

  /* Find the item at "i" */
  lval *x = v->cell[i];

  /* Shift memory after the item at "i" over the top */
  memmove(&v->cell[i], &v->cell[i+1],
      sizeof(lval*) * (v->count-i-1));

  /* Decrease the count of items in the list */
  v->count--;

  /* Reallocate the memory used */
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  return x;
}

lval *lval_take(lval *v, int i) {
  lval *x = lval_pop(v, i);
  lval_del(v);
  return x;
}

lval *builtin_op(lval *a, char *op) {

  /* Ensure all arguments are numbers */
  for (int i = 0; i < a->count; i++) {
    if (a->cell[i]->type != LVAL_NUM) {
      lval_del(a);
      return lval_err("Cannot operate on non-number!");
    }
  }

  /* Pop the first element */
  lval *x = lval_pop(a, 0);

  /* If no arguments and sub then perform unary negation */
  if ((strcmp(op, "-") == 0) && a->count == 0) {
    x->num = -x->num;
  }

  /* While there are still elements remaining */
  while (a->count > 0) {
    /* Pop the next element */
    lval *y = lval_pop(a, 0);

    if (strcmp(op, "+") == 0) { x->num += y->num; }
    if (strcmp(op, "-") == 0) { x->num -= y->num; }
    if (strcmp(op, "*") == 0) { x->num *= y->num; }
    if (strcmp(op, "/") == 0) {
      if (y->num == 0) {
        lval_del(x);
        lval_del(y);
        x = lval_err("Division By Zero!");
        break;
      }
      x->num /= y->num;
    }
    lval_del(y);
  }
  lval_del(a);
  return x;
}

lval *lval_eval(lval *v);

lval *lval_eval_sexpr(lval *v) {
  /* Evaluate Children */
  for (int i = 0; i < v->count; i++) {
    v->cell[i] = lval_eval(v->cell[i]);
  }

  /* Error Checking */
  for (int i = 0; i < v->count; i++) {
    if (v->cell[i]->type == LVAL_ERR) {
      return lval_take(v, i);
    }
  }

  /* Empty Expression */
  if (v->count == 0) { return v; }

  /* Single Expression */
  if (v->count == 1) { return lval_take(v, 0); }

  /* Ensure First Element is Symbol */
  lval *f = lval_pop(v, 0);

  if (f->type != LVAL_SYM) {
    lval_del(f);
    lval_del(v);

    return lval_err("S-expression Does not start with symbol!");
  }

   /* Call builtin with operator */
  lval *result = builtin_op(v, f->sym);
  lval_del(f);
  return result;
}

lval *lval_eval(lval *v) {
  /* Evaluate Sexpressions */
  if (v->type == LVAL_SEXPR) {
    return lval_eval_sexpr(v);
  }

  /* All other lval types remain the same */
  return v;
}


int main(int argc, char *argv[]) {

  /* Create Some Parsers */
  mpc_parser_t *Number   = mpc_new("number");
  mpc_parser_t* Symbol   = mpc_new("symbol");
  mpc_parser_t* Sexpr  = mpc_new("sexpr");
  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]+/ ;               \
    symbol   : '+' | '-' | '*' | '/' ;          \
    sexpr  : '(' <expr>* ')' ;            \
    expr   : <number> | <symbol> | <sexpr> ;      \
    lispy  : /^/ <expr>* /$/ ;            \
    ",
    Number, Symbol, Sexpr, 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 *x = lval_eval(lval_read(r.output));
      lval_println(x);
      lval_del(x);
      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, Symbol, Sexpr, Expr, Lispy);

  return 0;
}

编译：

gcc -g -std=c99 -Wall parsing.c mpc.c -lreadline -lm -o parsing

运行：

# ./parsing
Lispy Version 0.1
Press Ctrl+c to Exit

lispy> + 1 (* 7 5) 3
39
lispy> (- 100)
-100
lispy>
()
lispy> /
/
lispy> (/ ())
Error: Cannot operate on non-number!
lispy> ^C