title: 自制簡易解釋器
date: 2019-02-18 22:00:01
origin: 自制簡易解釋器

自制簡易解釋器

用C語言寫了一個簡單的動態(tài)語言解釋器, 代碼放在了github上面:hedegehog. 編譯, 運行可以看看github上的readme.

先簡單介紹下這門語言. hedgehog 的多數(shù)設計和 python 比較相似, 無需聲明變量類型, if,for等語句沒有塊級作用域. 語法上又有點像 go 語言: if, for不需要(), 但是后面的代碼塊都必須加{}; 沒有while, 不過有for condition {}來替代. 不過行尾必須加;這點和 go 不同. 大多數(shù)設計都是為了簡化實現(xiàn)方式, 比如必須加{}, ;是為了簡化語法的解析.

已實現(xiàn)的功能

• 數(shù)據(jù)類型

  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.
  

• 循環(huán)

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

• 函數(shù)
  function也被看作一種值(基本數(shù)據(jù)類型), 不過目前還沒有對它實現(xiàn)垃圾回收, 所以直接以函數(shù)賦值或者其他操作會出現(xiàn)內(nèi)存錯誤.

    // 模仿python首頁的函數(shù):)
    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));
  

  目前只實現(xiàn)了一個原生函數(shù)print. print接收一個基本數(shù)據(jù)類型作為參數(shù), 輸出并換行, 或者無參數(shù), 直接換行.

• 運算符
  大多數(shù)與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");
  }
  

概述

image

首先詞法分析和語法分析, 構(gòu)建分析樹. 這里以a=1+2*3+fn();為例, 介紹一下表達式分析樹的構(gòu)建.

首先, 它是一個賦值表達式, 把右邊的值1+2*3+fn()賦給左邊的變量a. 而1+2*3+fn() 又由加法表達式, 乘法表達式, 函數(shù)調(diào)用表達式構(gòu)成. yacc中編寫的規(guī)則會約束表達式構(gòu)建的順序, 構(gòu)建過程大概是這樣的:

a = 1 + 2 * 3 + fn()
identifier = value + value * value + function_call // 詞法分析
identifier = value + value * value + value // function_call 約歸為value
identifier = value + multiply_expression + value // 根據(jù)規(guī)則, 先生成乘法表達式
identifier = add_expression + value // 把前兩項歸約為加法表達式
identifier = add_expression // 繼續(xù)歸約(加法運算遵循從左到右)
identifier = expression // 歸約為更一般的普通表達式
assgin_expression // 匹配到賦值表達式的規(guī)則, 歸約為賦值表達式
expression // 賦值表達式歸約為一般表達式

然后就可以構(gòu)建了下面的分析樹了:

image

求值的時候從最底層依次往上求值, 就能得到表達式的值.

語法與詞法分析

這部分直接使用lex做詞法分析, yacc做語法分析. 這兩個工具在大多數(shù)UNIX上都有預裝, GUN提供的版本分別叫bison, flex. 直接用bison生成的文件可能和yacc有些區(qū)別(需要修改生成文件的的文件名, 或者改c語言文件中包含的頭文件名), 不過在Linux下安裝了bison可以直接使用yacc命令. flex 與 lex 生成文件沒有區(qū)別.

yacc與lex網(wǎng)上有大量的資料, 而且使用比較簡單, 這里就僅作簡單的介紹.

lex可以使用正則表達式做匹配:

"func" return FUNCTION;//func 函數(shù)定義關(guān)鍵字
[A-Za-z_][A-Za-z0-9_]* {
    //辨識符匹配
    yylval.identifier = initString(yytext);
    return IDENTIFIER;
}

這里的FUNCTION和IDENTIFIER被稱為token, 一般在yacc的文件中定義. 在生成的C語言文件中token用枚舉變量表示.

lex詞法分析的結(jié)果會交給yacc處理. yacc使用類似BNF的規(guī)范來編寫規(guī)則.

// 加法表達式由乘法表達式歸約, 這樣可以限制乘法(除法, 取模)優(yōu)先于
//加法(減法)運算.
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);
    }
    ;

詞法分析和語法分析屬于解釋器的前端, 這部分沒有自己編寫, 主要把精力放在了后端.

表達式與語句

表達式與語句是整個后端最重要的兩個模塊, 大部分的邏輯都在兩者中實現(xiàn). 這里主要介紹一下表達式, 語句與之類似.
大部分的代碼都用C語言實現(xiàn)了面向?qū)ο? 這里必須推薦一下劉大的C語言：春節(jié)回家過年，我發(fā)現(xiàn)只有我沒有對象算凿！.

// expression.h
struct ExpressionTag {
    void (*free)(Expression *self);

    Value (*evaluate)(Expression *self, Environment *env);

    Expression *pre;
};

這是表達式接口的結(jié)構(gòu)體, free 和evaluate是C語言中的函數(shù)指針, 定義了所有表達式都應該具備的方法. 這個pre看起來有些突兀, 它其實是為了函數(shù)傳參和多變量同時賦值時鏈接表達式使用的. 比如a, b = 1, 2;, 1, 2會分別解析為兩個表達式, 通過pre鏈接. 這樣的設計可能不符合面向?qū)ο? 不過為了實現(xiàn)鏈表更加簡單, 就暫時這樣寫了.

所有需要釋放內(nèi)存的結(jié)構(gòu)體都有free函數(shù)指針, 所以可以定義一個簡單的宏#define del(x) x->free(x), 使用del(obj)就可以釋放內(nèi)存了.

下面以賦值表達式介紹一下賦值表達式的實現(xiàn)過程.

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

向外提供的唯一接口是initAssignExpression, 也就是說所有一般的表達式在模塊外引用時都會被向上轉(zhuǎn)型為Expression, 只有free和evaluate兩個方法.

// expression.c
typedef struct {
    Expression base;//base必須放在第一個, 保證類型轉(zhuǎn)換時的正確性.
    String *id;
    Expression *expression;
} AssignExpression;

static Value evaluateAssignExpression(Expression *_self, Environment *env) {
    AssignExpression *self = (AssignExpression *) _self;//向下轉(zhuǎn)型為 `AssignExpression`
    Value value = self->expression->evaluate(self->expression, env);
    // 字符串采用引用計數(shù)
    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);
}

//綁定函數(shù)
const static Expression AssignExpressionBase = {freeAssignExpression,evaluateAssignExpression};

void *initAssignExpression(String *id, Expression *expression) {
    AssignExpression *exp = malloc(sizeof(AssignExpression));
    exp->expression = expression;
    //給base賦值, 函數(shù)的綁定在new的時候完成.
    exp->base = AssignExpressionBase;
    exp->id = id;
    return exp;
}

AssignExpression的結(jié)構(gòu)體和除init外方法都在.c文件中實現(xiàn), 并且標記為static, 從而就實現(xiàn)了封裝. 在init中實現(xiàn)函數(shù)的綁定, 以Expression引用的時候就能調(diào)用相應的方法, 這就實現(xiàn)了多態(tài).

其他的表達式根據(jù)具體的功能如法炮制.

語句的實現(xiàn)也是類似:

struct StatementTag {
    StatementResult (*execute)(Statement *self, Environment *env);

    void (*free)(Statement *self);

    Statement *next;
};

解釋器與運行環(huán)境

Environment

struct EnvironmentTag {
    void (*addVariable)(Environment *self, Variable *var);

    Variable *(*findVariable)(Environment *self, String *id);

    void (*free)(Environment *self);

    VariableTrie *trie;
};

void *initEnvironment();

運行環(huán)境主要負責變量和函數(shù)的保存, 查找. Global environment保存所有的全局變量和函數(shù). 函數(shù)有獨立于 global environment的local environment. for, if等語句塊沒有environment, 它們使用所在函數(shù)或者全局的environment.

Environment中的trie是字典樹, 負責記錄變量名和函數(shù)名.

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實現(xiàn)分析樹的構(gòu)建, interpret實現(xiàn)語句的執(zhí)行. 因為全局只需要一個 interpreter, 所以別的地方可以通過getCurrentInterpreter獲取當前interpreter.

總結(jié)

整個解釋器的大概構(gòu)成就是這樣. 目前只實現(xiàn)了一些簡單的功能, 數(shù)組, 字典, 垃圾回收(目前只對字符串做了引用計數(shù)回收), 文件IO等特性都還沒有寫. 而且完全沒有優(yōu)化, 運行效率極低. 不過寫這個解釋器的時候還是收獲不少: 深入學習了C語言, 對編譯原理有了大概的了解, 更加深刻地理解了面向?qū)ο?..