作者descent (「雄辯是銀,沉默是金」)
看板C_and_CPP
標題[心得] interpreter 環境與變數
時間Fri Nov 25 11:09:20 2016
變數就是字面上的意思, 寫程式的都知道, 但知道 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
--
紙上得來終覺淺,絕知此事要躬行。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 113.196.174.254
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1480043372.A.661.html
1F:噓 Ommm5566: 排版 11/25 19:22
排版有什麼問題嗎?
* 該有的標點符號都有
* 英文和中文字有留空白
* 半形逗號後面也留一個空白
* () 前後也留空白
* 程式碼也有行號
如果 bbs 版本不好看, 也可以參考網頁版本。
2F:推 wtchen: 推回來,我覺得排版沒問題阿 11/25 20:22
3F:推 art1: 掃到 L14 那裡有點看不懂,那一行是int z,但你的說明是把 11/26 08:31
4F:→ art1: x:0 加到 main環境 11/26 08:31
感謝, 筆誤, 己修正
5F:→ MOONRAKER: ptt的排版就是 我看得順眼才叫排版 我看不順眼就噓排版 11/26 13:06
6F:→ MOONRAKER: 一堆連報紙都沒看過的○○滿口排版 強! 11/26 13:06
7F:推 EdisonX: 請問有機會介紹 conditions 嗎? 11/26 21:08
conditions 是指 if/else 嗎?
8F:推 youtuuube000: 看不懂感覺很厲害先推再說XD 11/27 11:13
9F:推 EdisonX: 是的 我說的conditions 泛指條件判斷 含if else elsif s 11/27 13:05
10F:→ EdisonX: witch case 11/27 13:05
會的, 目前的實作有
if/else
while
funcion call
當然還有 c 最具代表性的指標, 只不過是 interpreter 的指標版本。
11F:推 EdisonX: 期待您的 part 2 11/27 20:21
12F:推 Ommm5566: 那很抱歉 補回來推 11/27 22:06
13F:推 eye5002003: 這專案是用C++實現一個直譯器採用C做為腳本語言嗎? 11/28 09:55
是的, 本來打算寫編譯器的, 不過發現有點難, 只好先改成直譯器的版本。
14F:推 eye5002003: 喔!我有做過類似的事,建議使用C++11的特性 11/28 19:02
15F:→ eye5002003: 匿名函式用來寫parser很有幫助,個人意見 11/28 19:04
有沒有什麼建議的寫法, 我那程式碼醜的要命。
16F:推 EdisonX: goo.gl/b70T6m 11/29 14:53
感謝分享, c++ 程度不太好, 看不懂用 匿名函式 的好處。
我的 AST 沒有使用物件導向, 所以沒有很多 node type,
但 eval() 裡頭就有一大堆的 switch/case, 這部份相當醜陋,
但用物件導向我也不覺得有比較好, 這是個困難的選擇。
四則運算解析器那篇沒把 ebnf 列出來, 要看懂那個程式會相當困難。
※ 編輯: descent (175.98.141.254), 11/29/2016 17:23:03
17F:推 CoNsTaR: 這種時候就會覺得有 pattern matching 的語言真好 XDD 11/29 17:53
18F:推 littleshan: functional language 拿來做這種事超愉悅的 XD 12/02 00:11
19F:→ littleshan: 推薦coursera上由UW提供的programming languages課程 12/02 00:12
20F:→ littleshan: 從此人生打開了另一扇窗 12/02 00:12