MyLisp项目日志：S表达式

2024-03-18

项目

3.2k words

S表达式

Lisp列表

Lisp的程序代码也是数据形式的一种，这个结构被称之为S表达式，他存在一个Lisp列表中，我们需要用这个列表结构递归的表示出数字、操作符号和其他的列表，因此我们需要扩展MLval的内容，同时会重构之前写过的函数

我们需要将求值过程分为读取存入，求值两个过程

解析表达式

这里就要由波兰表达式扩展到S表达式，因此首先需要更新一下语法解析器，这里笔者在创建的时候会有一部分内存泄漏的问题，但是重新写一遍这个解析器问题就消失了，也不会报错，可能是正则表达式的部分有出问题

除此之外我们需要把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* MyLisp = mpc_new("mylisp");

// 定义
mpca_lang(MPCA_LANG_DEFAULT,
    "                                          \
  number : /-?[0-9]+(\\.[0-9]*)?/ ;                    \
  symbol   : '+' | '-' | '*' | '/' | '%' | '^' | /add|sub|mul|div|min|max|mod/ ;  \
  sexpr  : '(' <expr>* ')' ;               \
  expr   : <number> | <symbol> | <sexpr> ; \
  mylisp : /^/ <expr>* /$/ ;               \
",
    Number, Symbol, Sexpr, Expr, MyLisp);

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

表达式结构

之前我们只有数字和错误两个类型，这里我们直接将这些全部整合起来

如下

// 数据类型
enum
{
    MLVAL_ERR, // 表示错误
    MLVAL_NUM, // 表示数字
    MLVAL_SYM, // 表示符号
    MLVAL_SEXPR // 表示S表达式
};

这样的话，那我们的结构体也要重新设计了，除了之前的类型和数字，把错误直接改成了char*，可以存储具体的错误内容，符号也可以直接存储，最后的cell表示列表结构，使用count表示列表元素的数量

typedef struct MLval 
{
    int type; // 表示类型
    double num; 

    char* err;
    char* sym;

    int count; //列表元素数量
    struct MLval** cell;
} MLval;

构造函数与析构函数

构造函数

因为这里我们没有C++中好用的内存管理和对象管理内容，只能用最原始的手搓方法了

首先要分别写四种类型的构造函数，返回值是MLval*这样外部调用函数就可以直接用了

MLval* MLval_num(double x)
{ // 数字类型初始化
    MLval* v = (MLval*)malloc(sizeof(MLval));
    assert(v);
    v->type = MLVAL_NUM;
    v->num = x;
    return v;
}


MLval* MLval_err(char* m) 
{ // 错误类型初始化
    MLval* v = (MLval*)malloc(sizeof(MLval));
    assert(v);
    v->type = MLVAL_ERR;
    v->err = (char*)malloc(strlen(m) + 1);
    assert(v->err);
    strcpy(v->err, m);
    return v;
}


MLval* MLval_sym(char* s) 
{ // 符号类型初始化
    MLval* v = (MLval*)malloc(sizeof(MLval));
    assert(v);
    v->type = MLVAL_SYM;
    v->sym = (char*)malloc(strlen(s) + 1);
    assert(v->sym);
    strcpy(v->sym, s);
    return v;
}

MLval* MLval_sexpr()
{ // S表达式初始化
    MLval* v = (MLval*)malloc(sizeof(MLval));
    assert(v);
    v->type = MLVAL_SEXPR;
    v->count = 0;
    v->cell = NULL;
    return v;
}

这里需要注意在malloc或者realloc之后需要判断是否申请内存成功，我这里直接暴力assert了，一般情况下可以温和提示然后直接返回就行，当然我们这个小项目也不涉及太大的内存申请

析构函数

在内存申请之后，如果我们不进行内存释放，就会出现内存泄漏的问题，还有空指针野指针，这里我们需要手动写一个

void MLval_del(MLval* v) // 析构函数
{

    switch (v->type) 
    {
    case MLVAL_NUM: break;

    case MLVAL_ERR: free(v->err); break;
    case MLVAL_SYM: free(v->sym); break;

    case MLVAL_SEXPR:
        for (int i = 0; i < v->count; i++) 
        {
            MLval_del(v->cell[i]);
        }
        free(v->cell);
        break;
    default:
        break;
    }
    free(v);
}

读取表达式

整个程序的过程分成两个阶段，第一阶段负责把AST转化为S表达式，第二段根据我们定义的规则对S表达式遍历求值

这一整个S表达式全部存在一个MLisp*结构中，我们还是像之前一样查看语法分析树种的每个节点，然后根据tag和contents构造出不同的MLisp*

如果节点被标记为root或者sexpr，那么就要构造出一个空的MLisp*然后继续导入内容

如果节点被标记为number或者symbol，那么我们直接调用对应的构造函数即可

为了方便向S表达式种添加元素，我们可以写一个MLval_add函数，功能是直接新增一个节点并且初始化

如下

MLval* MLval_add(MLval* v, MLval* x) // 列表添加元素
{
    v->count++;
    MLval** temp = (MLval**)realloc(v->cell, sizeof(MLval*) * v->count);
    if (temp == NULL) {
        printf("realloc fail!!\n");
        free(v->cell);
        return NULL;
    }
    v->cell = temp;
    v->cell[v->count - 1] = x;
    return v;
}


MLval* MLval_read_num(mpc_ast_t* t) 
{
    errno = 0;
    double x = strtod(t->contents, NULL);
    return errno != ERANGE ?
        MLval_num(x) : MLval_err("invalid number");
}

MLval* MLval_read(mpc_ast_t* t)
{

    if (strstr(t->tag, "number")) { return MLval_read_num(t); }
    if (strstr(t->tag, "symbol")) { return MLval_sym(t->contents); }

    MLval* x = NULL;
    if (strcmp(t->tag, ">") == 0) { x = MLval_sexpr(); }
    if (strstr(t->tag, "sexpr")) { x = MLval_sexpr(); }

    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 = MLval_add(x, MLval_read(t->children[i]));
    }

    return x;
}

打印表达式

最后我们需要修改打印函数，使其能够正确打印出S表达式

void MLval_print(MLval* v);

void MLval_expr_print(MLval* v, char open, char close) 
{
    putchar(open);
    for (int i = 0; i < v->count; i++)
    {
        MLval_print(v->cell[i]);

        if (i != (v->count - 1)) {
            putchar(' ');
        }
    }
    putchar(close);
}

void MLval_print(MLval* v) 
{
    switch (v->type) 
    {
    case MLVAL_NUM:   printf("%g", v->num); break;
    case MLVAL_ERR:   printf("Error: %s", v->err); break;
    case MLVAL_SYM:   printf("%s", v->sym); break;
    case MLVAL_SEXPR: MLval_expr_print(v, '(', ')'); break;
    default:
        break;
    }
}

void MLval_println(MLval* v) { MLval_print(v); putchar('\n'); }

表达式求值

表达式求值和之前的差异不大，但是具体思路需要想清楚

首先读取一个MLisp*作为输入，通过运算之后，再作为MLisp*返回，需要注意的是，我们需要将原来的MLisp*释放，否则会内存泄漏

对于不同的输入类型，处理的方式也不同

如果输入的是S表达式，遍历所有子节点，如果遇到错误，则报错，如果没有子节点，则直接返回他的内容即可

在遍历子节点的过程中，将元素从表达式中取出，传入计算函数求值

MLval* MLval_eval(MLval* v);

MLval* MLval_eval_sexpr(MLval* v) 
{

    for (int i = 0; i < v->count; i++) // 遍历所有子节点
    {
        v->cell[i] = MLval_eval(v->cell[i]);
    }

    for (int i = 0; i < v->count; i++) // 遇到错误则报错
    {
        if (v->cell[i]->type == MLVAL_ERR) { return MLval_take(v, i); }
    }

    if (v->count == 0) { return v; } // 没有子节点则直接返回

    if (v->count == 1) { return MLval_take(v, 0); }

    MLval* f = MLval_pop(v, 0);
    if (f->type != MLVAL_SYM) 
    {
        MLval_del(f); MLval_del(v);
        return MLval_err("S-expression Does not start with symbol.");
    }

    MLval* result = builtin_op(v, f->sym);
    MLval_del(f);
    return result;
}

MLval* MLval_eval(MLval* v)
{
    if (v->type == MLVAL_SEXPR) { return MLval_eval_sexpr(v); }
    return v;
}

这上面有一些函数我们还没有定义，我们先看他们的功能


```MLval_take```函数与pop类似，只是在取出之后会删除

```c
MLval* MLval_pop(MLval* v, int i) // 列表删除元素
{
    // 找到第i个元素
    MLval* x = v->cell[i];

    memmove(&v->cell[i], &v->cell[i + 1],
        sizeof(MLval*) * (v->count - i - 1));

    v->count--;
    v->cell = (MLval**)realloc(v->cell, sizeof(MLval*) * v->count);
    return x;
}

MLval* MLval_take(MLval* v, int i) // 取出元素
{
    MLval* x = MLval_pop(v, i);
    MLval_del(v);
    return x;
}


```c
MLval* builtin_op(MLval* a, char* op) 
{

    // 确保操作数为数字
    for (int i = 0; i < a->count; i++) 
    {
        if (a->cell[i]->type != MLVAL_NUM) {
            MLval_del(a);
            return MLval_err("Cannot operate on non-number!");
        }
    }

    // 得到第一个操作数
    MLval* x = MLval_pop(a, 0);

    // 如果只有一个负号则为负数
    if ((strcmp(op, "-") == 0) && a->count == 0) 
    {
        x->num = -x->num;
    }

    
    while (a->count > 0) 
    {

        // 得到第二个操作数
        MLval* y = MLval_pop(a, 0);

        // 计算
        if (strcmp(op, "+") == 0 || strcmp(op, "add") == 0) { x->num += y->num; }
        if (strcmp(op, "-") == 0 || strcmp(op, "sub") == 0) { x->num -= y->num; }
        if (strcmp(op, "*") == 0 || strcmp(op, "mul") == 0) { x->num *= y->num; }
        if (strcmp(op, "/") == 0 || strcmp(op, "div") == 0)
        {
            if (y->num == 0)
            {
                MLval_del(x);
                MLval_del(y);
                x = MLval_err("Division By Zero.");
            }
            x->num /= y->num;
        }

        if (strcmp(op, "%") == 0 || strcmp(op, "mod") == 0)
        {
            if (y->num == 0)
            {
                MLval_del(x);
                MLval_del(y);
                x = MLval_err("Division By Zero.");
                break;
            }
            x->num = fmod(x->num, y->num);
        }

        if (strcmp(op, "^") == 0) { x->num = pow(x->num, y->num); }
        if (strcmp(op, "min") == 0) { x->num = (x->num < y->num) ? x->num : y->num; }
        if (strcmp(op, "max") == 0) { x->num = (x->num > y->num) ? x->num : y->num; }

        MLval_del(y);
    }

    MLval_del(a);

    return x;
}

v0.2.1

#define _CRT_SECURE_NO_WARNINGS 1
#include "mpc.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<assert.h>
void PrintPrompt()
{
    printf("MyLisp Version 0.2.1\n");
    printf("By jasmine-leaf\n");
    printf("Press Ctrl+c to Exit\n\n\n");
}

// v0.0.1
// 实现了用户输入和读取功能
// v0.0.2
// 增加了波兰表达式的解析功能
// v0.1.0
// 增加了波兰表达式的求值功能
// 增加了min、max、乘方运算
// v0.1.1
// 增加了运算报错
// v0.2.0
// 增加了S表达式
// v0.2.1
// 修复了mpca_lang内存泄漏的bug

#ifdef _WIN32 

// 为实现跨平台功能
// 在windows平台下定义实现editline和history的同名函数

#define INPUT_MAX 2048 // 缓冲区最大值

static char Buffer[INPUT_MAX]; // Buffer输入缓冲区


char* readline(char* prompt) // 模拟实现readline
{
    fputs(prompt, stdout);
    fgets(Buffer, INPUT_MAX, stdin);


    char* tmp = malloc(strlen(Buffer) + 1);
    if (tmp != NULL)
    {
        strcpy(tmp, Buffer);
        tmp[strlen(tmp) - 1] = '\0';
    }
    return tmp;
}

void add_history(char* unused)
{}

#else
#ifdef __linux__ // 在linux平台下
#include<editline/readline.h>
#include<editline.history.h>
#endif

#ifdef __MACH__ // 在mac平台下
#include<editline/readline.h>
#endif
#endif 

// 数据类型
enum
{
    MLVAL_ERR, // 表示错误
    MLVAL_NUM, // 表示数字
    MLVAL_SYM, // 表示符号
    MLVAL_SEXPR // 表示S表达式
};

typedef struct MLval 
{
    int type; // 表示类型
    double num; 

    char* err;
    char* sym;

    int count; //列表元素数量
    struct MLval** cell;
} MLval;


MLval* MLval_num(double x)
{ // 数字类型初始化
    MLval* v = (MLval*)malloc(sizeof(MLval));
    assert(v);
    v->type = MLVAL_NUM;
    v->num = x;
    return v;
}


MLval* MLval_err(char* m) 
{ // 错误类型初始化
    MLval* v = (MLval*)malloc(sizeof(MLval));
    assert(v);
    v->type = MLVAL_ERR;
    v->err = (char*)malloc(strlen(m) + 1);
    assert(v->err);
    strcpy(v->err, m);
    return v;
}


MLval* MLval_sym(char* s) 
{ // 符号类型初始化
    MLval* v = (MLval*)malloc(sizeof(MLval));
    assert(v);
    v->type = MLVAL_SYM;
    v->sym = (char*)malloc(strlen(s) + 1);
    assert(v->sym);
    strcpy(v->sym, s);
    return v;
}

MLval* MLval_sexpr()
{ // S表达式初始化
    MLval* v = (MLval*)malloc(sizeof(MLval));
    assert(v);
    v->type = MLVAL_SEXPR;
    v->count = 0;
    v->cell = NULL;
    return v;
}

void MLval_del(MLval* v) // 析构函数
{

    switch (v->type) 
    {
    case MLVAL_NUM: break; 

    case MLVAL_ERR: free(v->err); break;
    case MLVAL_SYM: free(v->sym); break;

    case MLVAL_SEXPR:
        for (int i = 0; i < v->count; i++) 
        {
            MLval_del(v->cell[i]);
        }
        free(v->cell);
        break;
    default:
        break;
    }
    free(v);
}

MLval* MLval_add(MLval* v, MLval* x) // 列表添加元素
{
    v->count++;
    MLval** temp = (MLval**)realloc(v->cell, sizeof(MLval*) * v->count);
    if (temp == NULL) 
    {
        printf("realloc fail!!\n");
        free(v->cell);
        return NULL;
    }
    v->cell = temp;
    v->cell[v->count - 1] = x;
    return v;
}


MLval* MLval_pop(MLval* v, int i) // 列表删除元素
{
    // 找到第i个元素
    MLval* x = v->cell[i];

    memmove(&v->cell[i], &v->cell[i + 1],
        sizeof(MLval*) * (v->count - i - 1));

    v->count--;
    v->cell = (MLval**)realloc(v->cell, sizeof(MLval*) * v->count);
    return x;
}

MLval* MLval_take(MLval* v, int i) // 取出元素
{
    MLval* x = MLval_pop(v, i);
    MLval_del(v);
    return x;
}

void MLval_print(MLval* v);

void MLval_expr_print(MLval* v, char open, char close) 
{
    putchar(open);
    for (int i = 0; i < v->count; i++)
    {
        MLval_print(v->cell[i]);

        if (i != (v->count - 1)) {
            putchar(' ');
        }
    }
    putchar(close);
}

void MLval_print(MLval* v) 
{
    switch (v->type) 
    {
    case MLVAL_NUM:   printf("%g", v->num); break;
    case MLVAL_ERR:   printf("Error: %s", v->err); break;
    case MLVAL_SYM:   printf("%s", v->sym); break;
    case MLVAL_SEXPR: MLval_expr_print(v, '(', ')'); break;
    default:
        break;
    }
}

void MLval_println(MLval* v) { MLval_print(v); putchar('\n'); }

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

    // 确保操作数为数字
    for (int i = 0; i < a->count; i++) 
    {
        if (a->cell[i]->type != MLVAL_NUM) {
            MLval_del(a);
            return MLval_err("Cannot operate on non-number!");
        }
    }

    // 得到第一个操作数
    MLval* x = MLval_pop(a, 0);

    // 如果只有一个负号则为负数
    if ((strcmp(op, "-") == 0) && a->count == 0) 
    {
        x->num = -x->num;
    }

    
    while (a->count > 0) 
    {

        // 得到第二个操作数
        MLval* y = MLval_pop(a, 0);

        // 计算
        if (strcmp(op, "+") == 0 || strcmp(op, "add") == 0) { x->num += y->num; }
        if (strcmp(op, "-") == 0 || strcmp(op, "sub") == 0) { x->num -= y->num; }
        if (strcmp(op, "*") == 0 || strcmp(op, "mul") == 0) { x->num *= y->num; }
        if (strcmp(op, "/") == 0 || strcmp(op, "div") == 0)
        {
            if (y->num == 0)
            {
                MLval_del(x);
                MLval_del(y);
                x = MLval_err("Division By Zero.");
            }
            x->num /= y->num;
        }

        if (strcmp(op, "%") == 0 || strcmp(op, "mod") == 0)
        {
            if (y->num == 0)
            {
                MLval_del(x);
                MLval_del(y);
                x = MLval_err("Division By Zero.");
                break;
            }
            x->num = fmod(x->num, y->num);
        }

        if (strcmp(op, "^") == 0) { x->num = pow(x->num, y->num); }
        if (strcmp(op, "min") == 0) { x->num = (x->num < y->num) ? x->num : y->num; }
        if (strcmp(op, "max") == 0) { x->num = (x->num > y->num) ? x->num : y->num; }

        MLval_del(y);
    }

    MLval_del(a);

    return x;
}

MLval* MLval_eval(MLval* v);

MLval* MLval_eval_sexpr(MLval* v) 
{

    for (int i = 0; i < v->count; i++)
    {
        v->cell[i] = MLval_eval(v->cell[i]);
    }

    for (int i = 0; i < v->count; i++)
    {
        if (v->cell[i]->type == MLVAL_ERR) { return MLval_take(v, i); }
    }

    if (v->count == 0) { return v; }

    if (v->count == 1) { return MLval_take(v, 0); }

    MLval* f = MLval_pop(v, 0);
    if (f->type != MLVAL_SYM) 
    {
        MLval_del(f); MLval_del(v);
        return MLval_err("S-expression Does not start with symbol.");
    }

    MLval* result = builtin_op(v, f->sym);
    MLval_del(f);
    return result;
}

MLval* MLval_eval(MLval* v)
{
    if (v->type == MLVAL_SEXPR) { return MLval_eval_sexpr(v); }
    return v;
}

MLval* MLval_read_num(mpc_ast_t* t) 
{
    errno = 0;
    double x = strtod(t->contents, NULL);
    return errno != ERANGE ?
        MLval_num(x) : MLval_err("invalid number");
}

MLval* MLval_read(mpc_ast_t* t)
{

    if (strstr(t->tag, "number")) { return MLval_read_num(t); }
    if (strstr(t->tag, "symbol")) { return MLval_sym(t->contents); }

    MLval* x = NULL;
    if (strcmp(t->tag, ">") == 0) { x = MLval_sexpr(); }
    if (strstr(t->tag, "sexpr")) { x = MLval_sexpr(); }

    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 = MLval_add(x, MLval_read(t->children[i]));
    }

    return x;
}

void Lisp()
{
    // 创建解析器
    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* MyLisp = mpc_new("mylisp");

    // 定义
    mpca_lang(MPCA_LANG_DEFAULT,
        "                                          \
      number : /-?[0-9]+(\\.[0-9]*)?/ ;                    \
      symbol   : '+' | '-' | '*' | '/' | '%' | '^' | /add|sub|mul|div|min|max|mod/ ;  \
      sexpr  : '(' <expr>* ')' ;               \
      expr   : <number> | <symbol> | <sexpr> ; \
      mylisp : /^/ <expr>* /$/ ;               \
    ",
        Number, Symbol, Sexpr, Expr, MyLisp);

    while (1) 
    {

        char* input = readline("MyLisp> ");
        add_history(input);

        // 分析用户输入
        mpc_result_t r;
        if (mpc_parse("<stdin>", input, MyLisp, &r)) 
        {
            MLval* x = MLval_eval(MLval_read(r.output));
            MLval_println(x);
            MLval_del(x);
            mpc_ast_delete(r.output);
        }
        else 
        {
            // 打印其他失败情况
            mpc_err_print(r.error);
            mpc_err_delete(r.error);
        }

        free(input);

    }

    mpc_cleanup(5, Number, Symbol, Sexpr, Expr, MyLisp);
}

int main()
{

    PrintPrompt();
    Lisp();
    return 0;
}

Categories

Archives

Recent Posts