关键词搜索

源码搜索 ×
×

用 C 语言开发一门编程语言 — 符号表达式解析器

发布2023-03-12浏览3020次

详情内容

目录

文章目录

前言

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

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

前文列表

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

符号表达式

符号表达式（Symbolic Expression，S-Expression）是一种通过 Symbol（符号）来表示数学表达式的方法，以灵活性著称，常用于实现人工智能领域的代数运算系统。例如：Python SymPy 库等。我们接下来将会使用 S-Expression 来支撑 Lispy 的函数式编程范式。

值得注意的是，区别于波兰表达式（算术表达式）会对 Number（操作数）直接进行处理，S-Expression 并不用于 Numbers 的存储和运算，而是更专注于 Symbols 的存储。例如：算术表达式关注 “3 + 4” 的值是 7，而 S-Expression 关注的是 “x + y” 这一条代数式的存储，而不是计算它们的值。

基于这样的特性，S-Expression 可以用于表示任何一组数学公式，而不仅仅是特定的数值。

在这里插入图片描述

S-Expression 的语法规则定义

S-Expression 的语法规则非常简单：

  1. 使用小括号包括一条 S-Expression。
  2. 一条 S-Expression 由若干个 Symbols 或 Other S-Expression 组成。

所以 S-Expression 和波兰表达式一样，本质是一种适用于计算机迭代处理的树结构。

在这里插入图片描述

符号表达式解析器

实现 S-Expression 解析器，需要对 “表达式存储“ 和 “运算求值“ 这 2 个核心部分进行解构，从原来简单的 “输入 => 运算 => 输出” 流程，拆分为：

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

所以，S-Expression 解析器的实现分为 3 大部分：

  1. 首先，Lispy 读取到了用户的输入后，S-Expression 语法解析器首先会将输入的字符序列解析为 S-Expression AST（抽象语法树）；
  2. 然后，Lispy 需要递归 AST 的每个节点，根据节点的 tag 和 contents 成员，将相应的数据储存到 Lispy Values（数值存储器）；
  3. 最后，Lispy 才可能通过对 Lispy Values 进行遍历求值而来得到最终的运行结果。

1、读取并存储输入

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 由 2 个核心部分组成：

    1. Symbol（符号）：定义为一种特殊的数值类型，可以用来表示 Key Word（关键字）、Variable（变量）、Operator（操作符）、Function（函数）等元素。
    2. Expression（表达式）：是由 Symbol 和 Other Expressions 组成的一个列表，使用 ‘()’ 括号包围。

    所以，首先添加 2 个新的 Value Types，分别表示 Symbols 和 S-Expression。

    enum { LVAL_ERR, LVAL_NUM, LVAL_SYM, LVAL_SEXPR };

    • 1
    1. LVAL_SYM：表示输入的符号。
    2. LVAL_SEXPR：表示 S-Expression。

    然后，正如上文所说，S-Expression 本质是一颗递归遍历的树，我们将 lval（Lispy Values）结构体改造为树形数据结构，使其 “可变长、且可递归“。

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    1. 改造 err 成员，为 String 类型，可直接存储具体的 Error Message，而不只是一个 Error code。

    2. 添加 sym 成员，为 String 类型，存储 Symbols。

    3. 添加 count 成员，为 int 类型，存储递归嵌套的 Expression 个数。

    4. 添加 cell 成员，为指针数据类型，可变长，指向下一个 Expression，可递归。

    最终实现了一个具有父子节点结构的树状数据结构。

    存储器构造函数实现

    为了避免 C 语言值传递的性能损耗，我们将构造函数的返回值都定义为指针类型。所以，我们改造以往的 lval 结构体类型变量的构造函数，让其返回 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;
}

      18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    注意，在 C 语言中，String 的本质是一个以 “\0"（null）空字符做为终止标记的字符数组，字符串的最后一个字符必须是 \0。而 strlen 函数返回的是字符串的实际长度，并不包含 “\0"，所以为了保证有足够的空间存储所有字符，我们需要在额外 +1。

    存储器析构函数实现

    既然我们在构造函数中大量使用了 malloc 内存分配，那么在析构函数中就要完成内存空间的回收。

    当某个 lval 变量完成使命之后，我们不仅需要删除它本身所指向的堆内存，还要轮询着依次删除它的指针成员所指向的堆内存。这样就不会导致内存的泄露了。

    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);
}

      18
    • 19
    • 20
    • 21
    • 22
    • 23

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

    读取并存储 S-Expression

    定义好表达式存储器之后，我们就可以将经过语法解析器处理的数据储存到存储器中了。

    结合以往解析波兰表达式抽象语法树的经验，我们对 S-Expression AST 进行描述：

    1. 如果给定节点的被标记为 number 或 symbol，则我们可以调用对应的构造函数直接返回一个 lval *。
    2. 如果给定的节点被标记为 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;
}

      18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

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

    1. 将 S-Expression 子表达式的数量加 1。
    2. 使用 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    2、对输入进行求值

    通过以上的过程，我们就完成了接受输入并存储的步骤，接下来就是进行运算求值。

    S-Expression 的运算和波兰表达式的运算并无本质区别，都是对 AST 的遍历。但代码实现上肯定存在着差别：

    1. 首先取列表第一个元素为操作符。
    2. 然后遍历所有剩下的元素，将它们作为操作数。
    lval* lval_eval_sexpr(lval* v);
lval* lval_pop(lval* v, int i);
lval* lval_take(lval* v, int i);
lval* builtin_op(lval* a, char* op);


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_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++) {
    /* 如果是 Error 类型，就直接将其取走。*/
    if (v->cell[i]->type == LVAL_ERR) { return lval_take(v, i); }
  }

  if (v->count == 0) { return v; }  // 没有子节点，空表达式 `{}`，原封不动的将其返回。
  if (v->count == 1) { return lval_take(v, 0); }  // 只有一个子节点，直接将其取走。

  /**
   * 后续为合法的表达式，并且有个多于一个的子节点。
   * 使用 lval_pop 函数将第一个元素从表达式中分离开来。
   */
  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!");
  }

  /* 开始最终对 Number 操作数的运算处理。*/
  lval* result = builtin_op(v, f->sym);
  lval_del(f);
  return result;
}


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


/**
 * builtin_op 求值函数
 */
lval* builtin_op(lval* a, char* op) {

  /* 该函数对参数应该做更加严格的检查，对任何不是 LVAL_NUM 类型的 lval 结构体变量，都应该返回一个错误。*/
  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!");
    }
  }

  /* 将第一个数字弹出开始计算。*/
  lval* x = lval_pop(a, 0);

  /* 后如果后面没有其它的子节点，并且操作符为减号时，它会对第一个数字进行取反操作。*/
  if ((strcmp(op, "-") == 0) && a->count == 0) {
    x->num = -x->num;
  }

  /* 如果还有更多的节点，它就不断地从 cell 数组中取出，遍历进行数学运算。*/
  while (a->count > 0) {
    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) {
      /* 如果做除法时遇到被除数为零的情况，就将临时变量 x 和 y 以及参数列表删除，并返回一个错误。*/
      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;
}

      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

    3、打印运算结果

    至此，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'); }

      18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    最后，次更新一下 main 函数，在其打印表达式之前，先将输入经由求值函数处理即可：

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

    • 1
    • 2
    • 3

    源代码

    #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;
}

      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
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363

    编译：

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

    • 1

    运行：

    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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    相关技术文章

    最新源码

    下载排行榜
    点击QQ咨询
    开通会员
    返回顶部
    ×
    微信扫码支付 元
    微信扫码支付
    确定支付下载
    请使用微信描二维码支付
    ×

    提示信息

    ×

    选择支付方式

    • 微信支付
    • 支付宝付款
    确定支付下载