自制简易解释器

矫情吗；* 2022-03-17 20:40 250阅读 0赞

--------------------

title: 自制简易解释器  
date: 2019-02-18 22:00:01  
tags: interpreter  
categories: compilation  
blog: [https://withas.me][https_withas.me]

--------------------

# 自制简易解释器 #

用C语言写了一个简单的动态语言解释器, 代码放在了github上面:[hedegehog][]. 编译, 运行可以看看github上的readme.

先简单介绍下这门语言. hedgehog 的多数设计和 python 比较相似, 无需声明变量类型, `if`,`for`等语句没有块级作用域. 语法上又有点像 go 语言: `if`, `for`不需要`()`, 但是后面的代码块都必须加`{}`; 没有`while`, 不过有`for condition {}`来替代. 不过行尾必须加`;`这点和 go 不同. 大多数设计都是为了简化实现方式, 比如必须加`{}`, `;`是为了简化语法的解析.

## 已实现的功能 ##

*  数据类型
    
        a = 10;//int
        b = 3.14;//float
        c = true;//boolean
        d = null;//null
        s = "Hello, World!";//string
 *  控制语句
    
        a = 10;
          if a > 10 { // `()` is not necessary.
              b = a+20;
          } elsif a==10 {
              b = a+10;
          } else {
              b = a-10;
          }
          print(b);
          // block has no local environment, 
          // so 'b' is a global variable.
 *  循环
    
        for i=0; i<10; i=i+1 {
              print(i);
              if i>=4 {break;}
          }
          i = 0;
          for i<10 {
              if i<5 {continue;}
              print(i);
          }
 *  函数  
    function也被看作一种值(基本数据类型), 不过目前还没有对它实现垃圾回收, 所以直接以函数赋值或者其他操作会出现内存错误.
    
        // 模仿python首页的函数:)
          func fbi(n) {
              a, b = 0, 1;
              for a<n {
                  print(a);
                  a, b = b, a+b;//支持这种赋值方式
              }
          }
          fbi(100);
    
        func factorial(n) {
              if n==0 {return 1;}
              return n*factorial(n-1);
          }
          print(factorial(5));
    
    目前只实现了一个原生函数`print`. `print`接收一个基本数据类型作为参数, 输出并换行, 或者无参数, 直接换行.
 *  运算符  
    大多数与c保持一致, 除了`&`, `|`. 因为没有提供位运算的功能, 所以直接用这两个符号表示逻辑与和逻辑或.
    
        b = 2;
        a = 10;
        if a>20 & b<10 {
            print("`b` is less than 10 and `a` is greater than 20");
        }
        if a>20 | b<10 {
            print("`b` is less than 10 or `a` is greater than 20");
        }

## 概述 ##

![006xd92jgy1g0axw9jirjj312o0aywg6.jpg][]

首先词法分析和语法分析, 构建分析树. 这里以`a=1+2*3+fn();`为例, 介绍一下表达式分析树的构建.

首先, 它是一个赋值表达式, 把右边的值`1+2*3+fn()`赋给左边的变量`a`. 而`1+2*3+fn()` 又由加法表达式, 乘法表达式, 函数调用表达式构成. yacc中编写的规则会约束表达式构建的顺序, 构建过程大概是这样的:

a = 1 + 2 * 3 + fn()
    identifier = value + value * value + function_call // 词法分析
    identifier = value + value * value + value // function_call 约归为value
    identifier = value + multiply_expression + value // 根据规则, 先生成乘法表达式
    identifier = add_expression + value // 把前两项归约为加法表达式
    identifier = add_expression // 继续归约(加法运算遵循从左到右)
    identifier = expression // 归约为更一般的普通表达式
    assgin_expression // 匹配到赋值表达式的规则, 归约为赋值表达式
    expression // 赋值表达式归约为一般表达式

然后就可以构建了下面的分析树了:

![006xd92jgy1g0ay67plgkj30bp0g80t3.jpg][]

求值的时候从最底层依次往上求值, 就能得到表达式的值.

## 语法与词法分析 ##

这部分直接使用lex做词法分析, yacc做语法分析. 这两个工具在大多数UNIX上都有预装, GUN提供的版本分别叫bison, flex. 直接用bison生成的文件可能和yacc有些区别(需要修改生成文件的的文件名, 或者改c语言文件中包含的头文件名), 不过在Linux下安装了bison可以直接使用yacc命令. flex 与 lex 生成文件没有区别.

yacc与lex网上有大量的资料, 而且使用比较简单, 这里就仅作简单的介绍.

lex可以使用正则表达式做匹配:

"func" return FUNCTION;//func 函数定义关键字
    [A-Za-z_][A-Za-z0-9_]* {
    	//辨识符匹配
        yylval.identifier = initString(yytext);
        return IDENTIFIER;
    }

这里的`FUNCTION`和`IDENTIFIER`被称为token, 一般在yacc的文件中定义. 在生成的C语言文件中token用枚举变量表示.

lex词法分析的结果会交给yacc处理. yacc使用类似BNF的规范来编写规则.

// 加法表达式由乘法表达式归约, 这样可以限制乘法(除法, 取模)优先于
    //加法(减法)运算.
    ADD_EXPRESSION:
        MUL_EXPRESSION
        |
        ADD_EXPRESSION ADD MUL_EXPRESSION {
            $$ = initBinaryExpression(ADD_OPERATOR, $1, $3);
        }
        |
        ADD_EXPRESSION SUB MUL_EXPRESSION {
            $$ = initBinaryExpression(SUB_OPERATOR, $1, $3);
        }
        ;
    
    MUL_EXPRESSION:
        UNARY_EXPRESSION//单个单目运算表达式直接归约到乘法表达式
        |
        MUL_EXPRESSION MUL UNARY_EXPRESSION {
            $$ = initBinaryExpression(MUL_OPERATOR, $1, $3);
        }
        |
        MUL_EXPRESSION DIV UNARY_EXPRESSION {
            $$ = initBinaryExpression(DIV_OPERATOR, $1, $3);
        }
        |
        MUL_EXPRESSION MOD UNARY_EXPRESSION {
            $$ = initBinaryExpression(MOD_OPERATOR, $1, $3);
        }
        ;

词法分析和语法分析属于解释器的前端, 这部分没有自己编写, 主要把精力放在了后端.

## 表达式与语句 ##

表达式与语句是整个后端最重要的两个模块, 大部分的逻辑都在两者中实现. 这里主要介绍一下表达式, 语句与之类似.  
大部分的代码都用C语言实现了面向对象, 这里必须推荐一下刘大的[C语言：春节回家过年，我发现只有我没有对象！][C].

// expression.h
    struct ExpressionTag { 
        void (*free)(Expression *self);
    
        Value (*evaluate)(Expression *self, Environment *env);
    
        Expression *pre;
    };

这是表达式接口的结构体, `free` 和`evaluate`是C语言中的函数指针, 定义了所有表达式都应该具备的方法. 这个`pre`看起来有些突兀, 它其实是为了函数传参和多变量同时赋值时链接表达式使用的. 比如`a, b = 1, 2;`, `1, 2`会分别解析为两个表达式, 通过`pre`链接. 这样的设计可能不符合面向对象, 不过为了实现链表更加简单, 就暂时这样写了.

所有需要释放内存的结构体都有`free`函数指针, 所以可以定义一个简单的宏`#define del(x) x->free(x)`, 使用`del(obj)`就可以释放内存了.

下面以赋值表达式介绍一下赋值表达式的实现过程.

// expression.h
    void *initAssignExpression(String *id, Expression *expression)

向外提供的唯一接口是`initAssignExpression`, 也就是说所有一般的表达式在模块外引用时都会被向上转型为`Expression`, 只有`free`和`evaluate`两个方法.

// expression.c
    typedef struct { 
        Expression base;//base必须放在第一个, 保证类型转换时的正确性.
        String *id;
        Expression *expression;
    } AssignExpression;
    
    static Value evaluateAssignExpression(Expression *_self, Environment *env) { 
        AssignExpression *self = (AssignExpression *) _self;//向下转型为 `AssignExpression`
        Value value = self->expression->evaluate(self->expression, env);
        // 字符串采用引用计数
        on_self(self->id, refer);
        //把变量加到environment, 后文会介绍
        env->addVariable(env, initVariable(self->id, value));
        return value;
    }
    
    static void freeAssignExpression(Expression *_self) { 
        AssignExpression *self = (AssignExpression *) _self;
        del(self->expression);
        on_self(self->id, release);
        free(self);
    }
    
    //绑定函数
    const static Expression AssignExpressionBase = { freeAssignExpression,evaluateAssignExpression};
    
    void *initAssignExpression(String *id, Expression *expression) { 
        AssignExpression *exp = malloc(sizeof(AssignExpression));
        exp->expression = expression;
        //给base赋值, 函数的绑定在new的时候完成.
        exp->base = AssignExpressionBase;
        exp->id = id;
        return exp;
    }

`AssignExpression`的结构体和除`init`外方法都在.c文件中实现, 并且标记为`static`, 从而就实现了封装. 在`init`中实现函数的绑定, 以`Expression`引用的时候就能调用相应的方法, 这就实现了多态.

其他的表达式根据具体的功能如法炮制.

语句的实现也是类似:

struct StatementTag { 
        StatementResult (*execute)(Statement *self, Environment *env);
    
        void (*free)(Statement *self);
    
        Statement *next;
    };

## 解释器与运行环境 ##

### Environment ###

struct EnvironmentTag { 
        void (*addVariable)(Environment *self, Variable *var);
    
        Variable *(*findVariable)(Environment *self, String *id);
    
        void (*free)(Environment *self);
    
        VariableTrie *trie;
    };
    
    void *initEnvironment();

运行环境主要负责变量和函数的保存, 查找. Global environment保存所有的全局变量和函数. 函数有独立于 global environment的local environment. `for`, `if`等语句块没有environment, 它们使用所在函数或者全局的environment.

Environment中的`trie`是字典树, 负责记录变量名和函数名.

### Interpreter ###

typedef struct InterpreterTag { 
        Environment *globalEnv;
        StatementList *list;
    
        void (*free)(struct InterpreterTag *);
    
        void (*compile)(struct InterpreterTag *, FILE *);
    
        void (*interpret)(struct InterpreterTag *);
    } Interpreter;
    
    Interpreter *initInterpreter();
    
    Interpreter *getCurrentInterpreter();

Interpreter 中`compile`实现分析树的构建, `interpret`实现语句的执行. 因为全局只需要一个 interpreter, 所以别的地方可以通过`getCurrentInterpreter`获取当前interpreter.

## 总结 ##

整个解释器的大概构成就是这样. 目前只实现了一些简单的功能, 数组, 字典, 垃圾回收(目前只对字符串做了引用计数回收), 文件IO等特性都还没有写. 而且完全没有优化, 运行效率极低. 不过写这个解释器的时候还是收获不少: 深入学习了C语言, 对编译原理有了大概的了解, 更加深刻地理解了面向对象…

[https_withas.me]: https://withas.me
[hedegehog]: https://github.com/yangtau/hedgehog
[006xd92jgy1g0axw9jirjj312o0aywg6.jpg]: /images/20220318/c801af7b7dfa45a0ab11fbae01c99d96.png
[006xd92jgy1g0ay67plgkj30bp0g80t3.jpg]: /images/20220318/7aa2ab15730b4a39b4d883ee516ca60c.png
[C]: https://mp.weixin.qq.com/s/2ivQ9hcRvZnhk89jzAppSg