变量就是字面上的意思, 写程式的都知道, 但知道 interpreter 怎么把这功能做出来的
程式员可能就不多了。
list 1
1 x=1;
2 x+5;
list 1 L2 怎么把 x, 1 做个对应的呢? 就是靠《环境》, 他不是什么神祕的东西, 用
c++ 来说明什么是环境的话就是:
std::map<std::string, ASTNode *> env;
然后把 env["x"]=1 就完成 x=1 这个运算式。
不管你用什么资料结构, 反正就是把 x 和 1 的关系存起来就对了。感觉很简单, 但真实
世界上可没这么简单, 不过教学就是要化繁为简, 先知道这样就够了。
再来的 list 1 L2 在 x+5 要做 eval 时, eval 5 就回传 5 ASTNode 本身, x 就到
env 去把他对应的数字找出来, 也就是 1， 所以传回 1 的 ASTNode, 然后 + 就可以把
1, 5 作相加的运算, 6 就这么算出来了。
那《环境》困难在哪里呢? 在 function call。
p1
1 int x;
2 int f1()
3 {
4 2*3;
5 12+13;
6 }
7
8 int f2(int i)
9 {
9.5 int cc;
10 5*i;
11 }
12 int main()
13 {
14 int z;
15 61+2;
16 z=5;
17 f1();
18 f2(z);
19 }
如果像 p1 这样, 扫描到 L1 时, 把 x 加入 global_env (table 1), 在 call main
时, 要产生 main_env (table 2), main_env 的上层 up_env 要指到 global_env, 当扫
描到 L 14 时, 把 z:0 加入到 main_env, 而扫描到 L 16 时, 把 5 的值至换到 z
(table 3), 在 call f2(z) 时 (L 18), 又要产生 f2_env (table 4), 再把 up_env 指
到 main_env, 并把 z/i 的对应存到 f2_env, cc 的对应也要存到 f2_env, 疑, cc 没对
应的值阿, 随便塞一个就好了, 这不就是 c 语言 auto 变量的行为吗? 而上层 env 要指
到 main_env, 这样层层下去, 让整个环境建立起所有的变量名称/变量值的对应关系。大
概像 env class 那样。
table 1. global_env
up_env 0
x 0
table 2. main_env
up_env global_env
z 0
table 3 main_env
up_env global_env
z 5
table 4. f2_env
up_env main_env
i z
cc 0
所以在 f2() 里头用到 cc, i 时, 就去查 f2_env, 把对应的值找出来, 就可以知道这个
变量的值, 而在这层找不到, 就要去 up_env 找, 都找不到就发出错误讯息。
env class
14 class Environment
15 {
16 public:
17 Environment(Environment *outer=0, const char *name=0): outer_(outer)
18 {
21 }
22 Environment *outer_;
31 int free_frame_index_;
32 private:
33 std::map<std::string, ASTNode *> frame_;
34 };
观念很简单, 但实作还是会困难一点, 可参考以下范例程式码。以下程式码只有实作最简
单的环境, 我还没完成 function call 那复杂的环境。目前的版本我已经完成了
function call 和 return, 真是有种觉得自己很不简单的感觉呢!
source code:
https://github.com/descent/simple_compiler ( https://goo.gl/FBON5s )
commit: 0452c23b770dad99b1d503e0f417cae45879ce72
除了加入变量, 函式的定义也一样要加入环境, 当呼叫一个函式时, 就到环境来找这个函
式, 找到后把 parameter, argument 配对后, 就去执行该函式了。
至于函式的传回值, 那又是另外一件事情了。
因为使用了“环境”来处理“变量”, 这便是“环境变量”名称的由来。
打通整个 interpreter 流程并不容易, 当我满怀好奇心将所有疑问抽丝剥茧, 最后接触
到本质的那一刻, 我知道这些努力与坚持是值得的, 纵使我无法因为这样而在工作上有立
即的帮助, 但满足自己的好奇心就是驱使我这么做的最大动力。
// 本文使用 Blog2BBS 自动将Blog文章转成缩址的BBS纯文字 http://goo.gl/TZ4E17 //
blog 原文
http://descent-incoming.blogspot.tw/2016/07/compiler-4.html