2017年3月17日 星期五

compiler [2.9] - 建立 function call AST

有匪君子, 如切如磋, 如琢如磨。
有了函式定義之後, 再來就是要呼叫這個函式。function call 的 AST 應該長什麼樣子呢? 像 list 1 這樣。

list 1. function call AST
21 int f1(char c, int i)
22 {
23 }
24 
25 int main()
26 {
27   f1('c', 6);  
28   return 0;
29 }
30
31
 5                                   root
 6                                    |
 7                                   prog
 8            ________________________|________________________
 9            |                       |                       |
10  f1 |int |func |global  main |int |func |global           main
11        ____|_____                  |
12        |        |              func_body
13       para  func_body           ___|___
14    ____|____                    |     |
15    |       |                    f1  return
16 c |char  i |int                _|__   |
17                                |  |   0
18                                c  6

list 2, list 3 是我早期的版本, 那時候還可以這樣寫, 現在已經不行了。得用 list 1 的寫法才行, 也更像 c 語言了。

list 2. test_pattern/fc1.tree
 1 f1(1)
 2 token: f1
 3 token: (
 4 token: 1
 5 token: )
 6 
 7    root
 8     |
 9    prog
10     |
11 func call
12     |
13     1

list 3. test_pattern/fc2.tree
 1 f1(1, 2, x+y, "abc", 1+2*3)
 2 token: f1
 3 token: (
 4 token: 1
 5 token: ,
 6  token: 2
 7 token: ,
 8  token: x
 9 token: +
10 token: y
11 token: ,
12  token: abc
13 token: ,
14  token: 1
15 token: +
16 token: 2
17 token: *
18 token: 3
19 token: )
20 
21        root
22         |
23        prog
24         |
25     func call
26 ________|________
27 |   |   |   |   |
28 1   2   +  abc  +
29        _|__    _|__
30        |  |    |  |
31        x  y    1  *
32                  _|__
33                  |  |
34                  2  3

test_pattern/fc3.tree
 1 f1()
 2 token: f1
 3 token: (
 4 token: )
 5 
 6    root
 7     |
 8    prog
 9     |
10 func call

c_parser.cpp L334 是 function call 的 EBNF, 比較麻煩的是 function 的參數可不見得只是變數或是整數, 還可能是一個 function 或是運算式。當然, 如果想簡化, 就不要處理這些, 程式會簡單些, 不過我就是不爽不能用 function 或是運算式, 堅持把這個加了進去。

一樣對照著 ebnf 看, ebnf 怎麼寫, 程式就怎麼寫, 難不倒你的。

一開始先判斷目前的 token 是不是 NAME (變數名稱), 再來的 token 是不是 (, 再來有點麻煩, 因為參數可以沒有, 若接下來的 token 是 ), 表示沒有參數, 這個就簡單了, parse 完成。

如果不是 ), 表示有參數, 看看是不是 function call 還是運算式, 再接著判斷是不是還有下一個參數 (L371), 再來看下一個 token 是不是 ',', 再來就和前面一樣, 看看是不是 function call 還是運算式, 我寫得很輕鬆, 你應該混亂了, 請慢慢欣賞, 不要心急, 平心靜氣一定看得懂, 在看不懂就出動 gdb 吧!

c_parser.cpp
 159 /*!
 160  * primary   : "(" expr ")" | NUMBER | IDENTIFIER | STRING | func_call
 161  */
 162 ASTNode* primary()
 163 {
 164   Token token = peek_token(); 
 165   if (is_func_call())
 166   {
 167     ASTNode *e = func_call();
 168     return e;
 169   }
 170   ...

 321 bool is_func_call()
 322 {
 323   Token t = peek_token();
 324   if (t.ast_type() == NAME)
 325   {
 326     t = peek_token(1);
 327     if (t.str() == "(") // func_call
 328       return true;
 329   }
 330 
 331   return false;
 332 }
 334 /// func_call: NAME '(' [ (expr | func_call)  { ',' (expr | func_call) } ] ')' // 這是左遞迴嗎?
 335 ASTNode* func_call()
 336 {
 337   ASTNode *fc = 0;
 338   Token t = peek_token();
 339 
 340   if (t.ast_type() == NAME)
 341   {
 342     fc = new ASTNode(func_call_token);
 343     fc->set_str(t.str());
 344 
 345     ASTNode *e=0;
 346     pop_token();
 347     t = peek_token();
 348     if (t.str() == ("("))
 349     {
 350       pop_token();
 351 
 352       //if((e = expr()) != 0)
 353       t = peek_token();
 354       if(t.str() != ")")
 355       {
 356 
 357         if (is_func_call())
 358         {
 359           e = func_call();
 360         }
 361         else
 362         {
 363           e = expr();
 364         }
 365 
 366         if (e)
 367           fc->add_child(e);
 368 
 369         Token t = peek_token();
 370 
 371         while (t.str() != ")")
 372         {
 373 
 374 
 375             if (t.str() == ",")
 376             {
 377               pop_token();
 378 
 379               if (is_func_call())
 380               {
 381                 e = func_call();
 382               }
 383               else
 384               {
 385                 e = expr();
 386               }
 387 
 388               if (e);
 389                 fc->add_child(e);
 390             }
 391             else
 392             {
 393               err("func_call: should ','", t.str());
 394             }
 395             t = peek_token();
 396         } 
 397 
 398       }
 399       else // function call passes no argument
 400       {
 401 
 402       }
 403 
 404       t = peek_token();
 405       if (t.str() == (")"))
 406       {
 407         pop_token();
 408       }
 409       else
 410       {
 411         err("func_call: should )", t.str());
 412       }
 413     }
 414     else
 415     {
 416       err("func_call: should (", t.str());
 417     }
 418   }
 419   else
 420   {
 421     err("func_call: should NAME", t.str());
 422   }
 423 
 424   return fc;
 425 }

https://github.com/descent/simple_compiler/blob/master/c_parser.cpp
source code:
git commit: 8fcfec025156ca9196c03433867fb4132acac0bd

2017年3月11日 星期六

ttyd - 從瀏覽器以 ssh 登入 linux 主機

一個 daemon, 可以從瀏覽器用 ssh 登入主機。

編譯與執行
https://github.com/tsl0922/ttyd

apt-get install libwebsockets-dev
apt-get install libjson-c-dev
cmake .

192.168.1.9 是我的 eth0 ip, 預設 port 是 7681, 紅色是執行的指令
run
descent@u64:ttyd$ ./ttyd ssh descent@192.168.1.9
[1474856081:4555] NOTICE: Initial logging level 7
[1474856081:4556] NOTICE: Libwebsockets version: 1.7.1 unknown-build-hash
[1474856081:4556] NOTICE: IPV6 not compiled in
[1474856081:4557] NOTICE: libev support compiled in but disabled
[1474856081:4560] NOTICE:  Threads: 1 each 1024 fds
[1474856081:4560] NOTICE:  mem: platform fd map:  8192 bytes
[1474856081:4561] NOTICE:  mem: per-conn:          808 bytes + protocol rx buf
[1474856081:4561] NOTICE:  canonical_hostname = u64
[1474856081:4562] NOTICE:  Compiled with OpenSSL support
[1474856081:4562] NOTICE:  Using non-SSL mode
[1474856081:4847] NOTICE:  SSL ECDH curve 'prime256v1'
[1474856081:4848] NOTICE:  Listening on port 7681
[1474856081:4848] NOTICE: TTY configuration:
[1474856081:4848] NOTICE:   start command: ssh descent@192.168.1.9
[1474856081:4848] NOTICE:   reconnect timeout: 10s
[1474856081:4848] NOTICE:   close signal: SIGHUP (1)
[1474856105:2092] NOTICE: HTTP connect from 192.168.1.9 (192.168.1.9), path: /
[1474856105:2781] NOTICE: HTTP connect from 192.168.1.9 (192.168.1.9), path: /auth_token.js
[1474856105:3081] NOTICE: client connected from 192.168.1.9 (192.168.1.9), total: 1
[1474856105:3085] NOTICE: started process, pid: 19400
[1474856218:7906] NOTICE: HTTP connect from 192.168.1.9 (192.168.1.9), path: /
[1474856218:8341] NOTICE: HTTP connect from 192.168.1.9 (192.168.1.9), path: /auth_token.js
[1474856218:9817] NOTICE: client connected from 192.168.1.9 (192.168.1.9), total: 2
[1474856218:9820] NOTICE: started process, pid: 19546

從瀏覽器輸入 http://192.168.1.9:7681/ 就會出現 ssh 登入畫面。

從瀏覽器登入

ref:
ttyd 1.0.0 发布,C 语言编写的命令行程序

2017年3月4日 星期六

[books] 後段班辣妹應屆考上慶應大學的故事

若要人前顯貴, 就要人後受罪。
這是後段班辣妹應屆考上慶應大學的故事, 日文原文是:学年ビリのギャルが1年で偏差値を40上げて慶應大学に現役合格した話

20161016 購於墨林 120nt。能買到這本書真是太好了, 這是一本很溫暖的書, 坪田老師的溫暖, 彩加媽咪的溫暖, 到處給人一種溫暖的感覺, 我也期許自己能給別人一種溫暖的感覺。

這是坪田老師投稿到 story jp 後才出版的書籍。

漫畫版本:
ビリギャル〜学年ビリからの慶應大学合格記〜 (花とゆめCOMICS)

當然也有電影版本, 我是看了電影之後才知道這本書的, 電影的坪田老師就給人一種溫暖的感覺, 我喜歡被人家這樣對待, 相信很多人也是喜歡這樣被對待的感覺, 和這樣的人交談, 會讓自己擁有原本沒有的自信心。

中文版本沒有又臭又長的推薦序, 推薦序其實很困擾我, 我是一個習慣把書從頭看到尾的人, 我會去看版權頁, 看看這本書什麼時候出版, 有幾刷了, 這些內容都讓我覺得有趣。

坪田老師和彩加的對話, 讓我在在都覺得有趣, 真希望我也可以和別人這樣對話, 充滿樂趣, 帶給別人力量。

p59 彩加不願意供出違反校規的同夥, 而老師卻用一些語言技巧, 企圖逼彩加供出同夥, 媽媽知道這件事情之後, 反而稱讚彩加, 妳好了不起。是的, 不畏語言暴力威脅, 能勇敢反對這樣的暴力, 這樣的勇氣不值得稱讚嗎? 你做得到嗎? 但有多少父母親能這麼做呢? 彩加真是幸福, 有這樣的母親。

第四章坪田老師介紹了一些學習方式, 在對付相關的科目時, 應該怎麼對應, 我認為很有參考價值。像是作筆記的方法、背誦的技巧、有效的學習英文之類的 ...

書籍封面的女孩不是彩加本人, 是模特兒石川戀小姐。

附錄 - 坪田流人才培育術也介紹了不少與人之間的互動, 長官與部屬、老師與學生, 都是很好的人際互動方式, 值得參考。

看著別人考上的喜悅, 也要想著背後所付出的辛勞, 沒有過類似的努力, 可能很能想像所要付出的代價, 彩加到最後是讀書到天亮, 上學的時候在睡覺, 不用我說明, 就知道這麼需要多麼大的毅力才能達成。

有位朋友曾經告訴我一句話 - 若要人前顯貴, 就要人後受罪。你的努力有到達受罪的程度嗎? 最近又看到這句話,「你必須要非常的努力, 才會看起來毫不費力」彩加已經這樣努力了, 但看起來還是很費力, 如果你遇到什麼難題都能毫不費力解決的人, 恭喜你, 你育到了一個超級努力的人, 趕緊偷偷學習他的努力精神。

ref:
讀完這些吐槽再決定是否看《墊底辣妹》

2017年2月25日 星期六

[嘴炮] 寫 os kernel 這件事


你必須要非常的努力
才會看起來毫不費力
Tifa 很漂亮吧, 這次沒有專業技術, 純嘴炮, 什麼是嘴炮呢? 就是聽起來很厲害, 實際上完全沒幫助的東西, 偏偏大家又很愛看, 這技能很重要, 我要來練習一下。

強者我朋友這篇文章: 別被 kernel 嚇到了。我和這位朋友的等級大概差了十倍, 之前差很大, 現在縮小一點, 大概是 9.99 的差距吧, 真的只有一點。

但其實我不這麼認為, 知識是有難易等級之分, 用 printf 印出 hello world 很容易, 改用 system call 難一點, 完全靠自己的程式碼寫出來呢? 難度一下子來到幾十倍的等級。

專業知識我自己把它分成幾個等級:
  • 很容易就找到的知識
  • 很容易就能理解的知識
  • 別人告訴你才懂的知識
  • 很難找到的知識
  • 別人告訴你, 你還是無法理解的知識
  • 別人告訴你你還是無法理解的知識, 又很容易忘記的知識
程式有難有易, os 被分類為難寫的程式, 相信沒太大爭議。演算法課本上或是某些公司的面試題目當然也不會很簡單, 但是能在 os 下寫程式已經是個小確性。

os 是屬於難度偏高的程式, 要學習寫 os 需要一些不太容易找到的知識, 像 compiler 一樣, 是屬於比較不流行的程式, 而這些程式總是有些神祕感。

而有一個最根本的困難點是: 寫 os kernel 沒有 library 可用。紅黑樹不會寫有 library 可用, xml parser 不會寫有 library 可以用, compiler 也都還有 lex/yacc 可用, 但有什麼 library link 一下後, 這隻程式就變成 os kernel 了嗎? 沒有! 寫 os kernel 程式意味著得自己打造所有的輪子。

而 os 程式的其他困難點是:

能使用的語言有限: 大部份都是組合語言和 c 語言。有「本事】的人還可以用他喜歡的語言來寫 OS, 例如 os by go, by Haskell, 《這篇文章》則是討論用來寫 os 的語言。而我相信大多數人並不是屬於有「本事】的這一族群, 所以我們還是用組合語言和 c 語言就好, 這已經足以難倒我們了。

JNode 則是用 java 寫的 os, 覺得很神奇嗎? 作者用組合語言開發 jvm, 再來就可以用 java 寫 os 了。算作弊嗎? 當然不算, 用 c 也是要用組合語言的。

要怎麼開始呢? 我能寫個 int main(void) 作為開始嗎? 要怎麼讓 pc/或其他硬體平台一開機就執行我的程式, 光這一小步 (bare metal) 就足以讓人辛苦一陣子。而寫 os 無可避免一定要用到組合語言, 所以還有個組合語言的門檻。要載入 os kernel 到記憶體中再 jump 去執行, 也是在 os 下少做的事情, 也需要對所謂的可執行檔有所熟悉。

除錯: os 下有各式各樣的 debugger 可用, 寫 os kernel 雖然也可以透過 bochs, qemu 等模擬器除錯, 但這些模擬器的結果並非是真的結果, 總是會有些出入, 這時候就得自己想辦法找出 bug, 那可不是普通的痛苦。以前沒有 bochs, qemu 等模擬器那辛苦程度就更不在話下。出動 ice 等級的工具也不是容易的事情, bios/uefi 開發公司, 就有這些 ice 工具。

了解執行檔格式/純粹的機器碼檔案: 這也是需要下點功夫才能理解。像 elf 這麼有趣的執行檔格式, 把它載入並執行, 絕對是很好玩的一件事情。

toolchin 的用法: 其他平台我不知道, 至少使用 gnu toolchain 開發 os 的程式有不一樣的用法, 也是要花點時間學習。linker script 就足以花上不少時間。

cpu 架構的知識: 這不會有人認為很簡單吧? 當然有簡單的 cpu, 但一樣不是速成知識。

c runtime: 一開始是用組合語言撰寫, 但在某個時機會想用 c, 要怎麼樣才能開始用 c 呢?每個平台可能不太一樣。這可是書上或網路上難找的資料。當然如果你想用組合語言完成 os kernel, 那就沒這問題, BareMetal-OS 就是用組合語言寫的。在這個知識上, 我跌了好幾次跤, 總算讓我獲得此技能, 這過程可不是普通的痛苦。

中斷程式: 這也是在 os 下很少練習的程式, 怎麼處理好中斷程式, 事實上它也是一大難題, 寫個一次, 你才真能理解 linux 上提到的 Interrupt Context, 而不是只有名詞上的理解。

context switch, 這個名詞資訊人個個琅琅上口, 不過要寫出這個功能可就不是每個人都做得到, 有了個這功能, 才有 os 的味道, os 有一個很重要的能力就是控制 process, 我要你怎麼跑你就怎麼跑, 不讓這個 process 執行就是不讓你執行, 這需要硬體相關知識才能完成, 很有趣的。

其他難題我沒提到: 因為我覺得不一定要有這些。檔案系統、記憶體管理、硬體資源的管理 ... 但有了才感覺比較像 os kernel 吧, 所以還有得忙。spin lock, mutex, semaphore, 這些東西要理解/使用都不容易了, 寫 os kerne 可是要實作出這些功能。

硬體的話還有: 你想存取硬碟吧, 只用 ramdisk 總是有點虛虛的, 你也想支援 mmu 分頁功能吧, 而這兩個加起來才能支援虛擬記憶體這麼潮的功能。網路時代你也許還想搞定那張網路卡。

這裡提到的東西都不是在書店中或是網路上很容易就能得到的知識, 就算找到了也要花費很大的心力去消化, 不是能輕易搞懂的東西, 而且很容易就會忘記這些知識。有些難度沒那麼高, 但是在 os 環境下很少練習到。

透過練習就可熟悉一件事情, 雖然我不是 100% 贊同這句話, 我認為有些事不是靠努力練習就一定成的, 還需要有天才般的頭腦。不過很幸運的是, 寫 os 程式不在那範圍裡, 它是可以靠努力練習而完成的。

但我同意強者我朋友中的一個論點, 不用把會寫 os kernel 的人看得比較「厲害」, 只要你願意花時間往這個領域發展, 一定能有某種程度上的成就。破解軟體也是, 若你往這方面發展, 也一定能有些小成就。你不會, 那只是因為你的學習領域在別的地方, 在你所會的領域, 會寫 os kernel, 或是破解系統的人不見得比你厲害。現在很流行的 web programming/手機 app 我幾乎一竅不通; 如何處理大型網站的流量, 我也沒有概念 (看過淘宝技术这十年後, 我已達略懂的境界); 對於破解/保護的議題我也不熟, 大家都是學有專精的程式員, 無需自抬身價也無需自卑。

而和一般的應用程式相比, 成就感可能也不高, 一般人不會欣賞 os 程式, process switch 交戶印出兩個字串, 懂的人會覺得「哇! 好厲害!!」一般人可能覺得就是印出兩個字串, 無三小路用, 成就感不高, 拿這時間去寫個 ios app 說不定得到的成就感還比較大。

為什麼要自己開發個 os kernel 呢?
Why develop an OS?》有個不錯的答案。

2017年2月17日 星期五

vscode for linux 把 make, gcc/g++, gdb, git 都整合起來吧!

你對於在 linux 要搞 vim + ctag + cscope + gtag + gdb + git, emacs + ctag + cscope + gtag + gdb + git 很苦惱嗎? 在網路上找了好幾十篇的文章, 一一試過之後還是搞不定嗎? 正常的, 我也是, vscode 現在來拯救 linux 開發人員了。

看到這篇《為什麼我從 Sublime Text 跳槽 Visual Studio Code?》才注意到 vscode 的, 平常我不太會去嘗試 vim, emacs 之外的工具。哥是正統 unix 開發人員, 只用那種很難用會折磨自己的工具。

但 vscode 真的整合的不錯, 可以當第二開發工具。把 git, make, gcc, gdb 整合起來吧!

fig 1 extensions
本來打算從 source code build, 哥是正統 unix 開發人員, 習慣從 source code 建構程式, 但是 build 不起來, 很快就放棄了。直接到 https://code.visualstudio.com/download 下載, 我是下載 tar ball。

不過在我第一次執行 vscode 就出問題, 整個畫面黒黑的看不到任何東西。

找到這連結後 https://github.com/Microsoft/vscode/issues/6379
執行 code --disable-gpu 解決執行的問題。
現在連開發工具 IDE 都要支援 GPU 阿!

vscode 裝起來之後就會有基本看程式碼的功能:
  • 跳到函式定義
  • 跳到變數定義

但如果要看哪些程式碼用到了這個函式, 需要 C++ Intellisense extension 還有 global (gtags) 6.5 的版本, 在程式碼目錄打 gtags 產生 gtag。這樣在函式按右鍵就會看到 Find All References 這個選項, 就會列出呼叫這個函式的程式碼。

第一步先來安裝 fig1 上的 extensions, 在 View/extensions 上選 extensions 視窗, fig1 就是我裝的 extensions。重開 vscode 或是在 extensions 上選擇 reload 即可生效。使用 GDB 需要安裝 Native Debug 這個 extension。

那個 c++ complete 的 extension 就是你想的那樣, vim + YouCompleteMe 是不是折磨死你了, 搞了半天就是搞不定, 我看到那麼長的文章就放棄了, 哥是正統 unix 開發人員, 沒在 complete 程式碼的, 遇到這麼難的設定很快就放棄了。

先來搞定怎麼用 gcc 編譯程式碼, 以 simple_compiler 為範例, 以下說明是參考《C/C++ for VS Code (Preview)》。

If you want to build your application from VS Code, you will need to generate a tasks.json file:

  • Open the Command Palette (Ctrl+Shift+P). [按下 Ctrl+Shift+P 開啟 command palette。]
  • Select the Tasks: Configure Task Runner command and you will see a list of task runner templates. [有好幾個列表, 選Tasks: Configure Task Runner]
  • Select Othersto create a task which runs an external command. [再選 Tasks: Configure Task Runner 裡頭的 Others]
  • 這裡會跳出 tasks.json 的修改視窗
  • Change the command to the command line expression you use to build your application (e.g. g++ -g main.cpp). 和連結例子不同, 由於我寫了 makfile, 所以在 tasks.json L5 我改為 make 即可。 args 那些通通不用了。
  • Add any required args (e.g. -g to build for debugging).
  • You can now build your application with (Ctrl+Shift+B)

修改 tasks.json

tasks.json
1 {
2     // See https://go.microsoft.com/fwlink/?LinkId=733558
3     // for the documentation about the tasks.json format
4     "version": "0.1.0",
5     "command": "make",
6     "isShellCommand": true,
7     "args": ,
8     "showOutput": "always"
9 }

C/C++ for VS Code (Preview)》原本的 tasks.json 範例, 直接填上 g++ 命令, 參考 command, args 這兩個欄位
{
    "version": "0.1.0",
    "command": "g++",
    "isShellCommand": true,
    "showOutput": "always",
    "args": ["-g", "main.cpp"]
}

[整合 GDB]

View/debug 秀出 debug 視窗,

fig 2 按下齒輪圖示


fig 3 選 c++ (GDB/LLDB)



fig 4 將 program 修改為產生的執行檔名稱 - c_parser
若是執行檔後面要接參數, 參考 launch_argument L10 的寫法。

launch_argument
 1 {
 2     "version": "0.2.0",
 3     "configurations": [
 4         
 5         {
 6             "name": "C++ Launch",
 7             "type": "cppdbg",
 8             "request": "launch",
 9             "program": "c_parser",
10             "args": ["<", "/git/simple_compiler/test_pattern/add_1.c"],
11             "stopAtEntry": false,
12             "cwd": "${workspaceRoot}",
13             "environment": [],
14             "externalConsole": true,
15             "linux": {
16                 "MIMode": "gdb",
17                 "setupCommands": [
18                     {
19                         "description": "Enable pretty-printing for gdb",
20                         "text": "-enable-pretty-printing",
21                         "ignoreFailures": true
22                     }
23                 ]
24             },
25             "osx": {
26                 "MIMode": "lldb"
27             },
28             "windows": {
29                 "MIMode": "gdb",
30                 "setupCommands": [
31                     {
32                         "description": "Enable pretty-printing for gdb",
33                         "text": "-enable-pretty-printing",
34                         "ignoreFailures": true
35                     }
36                 ]
37             }
38         },
39         {
40             "name": "C++ Attach",
41             "type": "cppdbg",
42             "request": "attach",
43             "program": "enter program name, for example ${workspaceRoot}/a.out",
44             "processId": "${command.pickProcess}",
45             "linux": {
46                 "MIMode": "gdb",
47                 "setupCommands": [
48                     {
49                         "description": "Enable pretty-printing for gdb",
50                         "text": "-enable-pretty-printing",
51                         "ignoreFailures": true
52                     }
53                 ]
54             },
55             "osx": {
56                 "MIMode": "lldb"
57             },
58             "windows": {
59                 "MIMode": "gdb",
60                 "setupCommands": [
61                     {
62                         "description": "Enable pretty-printing for gdb",
63                         "text": "-enable-pretty-printing",
64                         "ignoreFailures": true
65                     }
66                 ]
67             }
68         }
69     ]
70 }

已經可以編譯執行檔, gdb 也設定完成, 要怎麼 debug 呢?

fig 5, 設定中斷點, 也可以按下 F9 來設定中斷點

fig 6. 按下去, 開始 debug
參考以下整合 gdb 畫面


[整合 git]
很簡單, 什麼都不用設定, 若原本就有使用 git 管理程式碼, 開啟那個目錄, 打開 View/git 就可以看到 git 操作畫面。可以打開 git output 視窗, 還可以知道對應的 git command 是怎麼執行的。

fig 7 顯示 git output 視窗 (按下 Show Git Output)
fig 8 將修改過的檔案加入 stage (index)
fig 9 將加入到 stage (index) 撤銷

有修改的檔案旁邊的 '+' 就是加入 stage (我習慣稱 index, git help 是使用 index 這個詞), '-' 就是反向操作。基本上還是要一點點的 git 知識才能好好使用這些功能, 但學起來比 command line 簡單不少。

安裝 git history 這個 extension, 看 git log 會有好看的樹節點。ctrl+shift+p 選 git history (log)

git history extension

我還裝了 vim extension, 在 vscode 上用 vim, 真是一種奇妙的感覺。

vscode 是用 Electron 寫的, 執行速度令人驚訝的快, 不會有 java 應用程式那種鈍鈍的感覺。而 extension 是用 typescript 寫的, 應該是很容易上手的語言。

所有設定檔都可以在程式碼目錄的 .vscode 找到。

ls simple_compiler/.vscode/
extensions.json 
launch.json 
tasks.json

ref:

2017年2月11日 星期六

compiler [2.6] - 建立 variable, function declare/definition AST

Bene qui latuit, bene vixit
var_func.c
 1 #include <stdio.h>
 2
 3 int test(int i);
 4
 5 int test(int i)
 6 {
 7   printf("i: %d\n", i);
 8 }
 9
10 int main()
11 {
12   test(5);
13   printf("abc\n");
14   return 0;
15 }

繼四則運算、if/else/while 之後, 登場的是函式宣告/定義, 不是函式呼叫, 得先有了函式宣告/定義才能呼叫, 所以先處理函式宣告/定義。當然也要提一提變數的宣告。

我參考的是《手把手教你构建 C 语言编译器(5)- 变量定义》 ebnf, 不過後來我才注意到我把函式宣告和定義搞在一起了, 這個 ebnf 並沒有區分函式宣告和定義, 雖然有點遺憾, 不過這樣可以簡化整個函式相關的 parser。

所以無法寫 var_func.c L3 的語法, 只能寫 var_func.c L5 ~ 8 這樣的語法, 其實也還好, 所以就先這樣吧! 精簡版的 c 語法嘛!

note
後來發現這樣有個問題, 無法處理標準程式庫的 function prototype, 例如: printf, 無法 parse printf 的 type, 這在 code generator 上有點麻煩, 我無法知道 function 離開時, 如何把 stack 還原, 雖然知道傳入參數的個數, 但不知道傳入的參數 type, 無法計算要還原幾個 bytes。

c_parser.c
 747 // function_decl ::= type {'*'} id '(' parameter_decl ')' '{' body_decl '}'

 748 ASTNode* func_decl()
 749 {
 750   ASTNode *func_node = new ASTNode(func_token);
 751   func_node->set_obj_type(obj_type);
 752   obj_type.clear();
 753 
 754   while(is_token("*"))
 755   {
 756     pop_token();
 757   }
 758   if (is_token(NAME))
 759   {
 760     Token t = pop_token();
 761     func_node->set_str(t.str());
 762     func_map[t.str()] = func_node;
 763   }
 764   else
 765   {
 766     Token t = peek_token();
 767     err("func_decl: should NAME\n", t.str());
 768   }
 769 
 770   if (is_token("("))
 771   {
 772     Token t = pop_token();
 773   }
 774   else
 775   {
 776     Token t = peek_token();
 777     err("func_decl: should (\n", t.str());
 778   }
 779 
 780   ASTNode *func_para = parameter_decl();
 781 
 782   if (is_token(")"))
 783   {
 784     Token t = pop_token();
 785   }
 786   else
 787   {
 788     Token t = peek_token();
 789     err("func_decl: should )\n", t.str());
 790   }
 791 
 792   if (is_token("{"))
 793   {
 794     Token t = pop_token();
 795   }
 796   else
 797   {
 798     Token t = peek_token();
 799     err("func_decl: should {\n", t.str());
 800   }
 801   if (func_para)
 802     func_node->add_child(func_para);
 803 
 804   ASTNode *func_body = body_decl();
 805   if (func_body)
 806     func_node->add_child(func_body);
 807     
 808 
 809   if (is_token("}"))
 810   {
 811     Token t = pop_token();
 812   }
 813   else
 814   {
 815     Token t = peek_token();
 816     err("func_decl: should }\n", t.str());
 817   }
 818 
 819   return func_node;
 820 }

 822 // variable_decl ::= type {'*'} id { ',' {'*'} id } ';'
 823 ASTNode* var_decl(bool is_global)
 824 {
 825   ASTNode *var_node = 0;
 826 
 827   if (is_global)
 828     var_node = new ASTNode(g_var_token);
 829   else
 830     var_node = new ASTNode(var_token);
 831 
 832   int ptr_num=0;
 833   while(is_token("*")) // 處理 0 ~ 多個的 *
 834   {
 835     ++ptr_num;
 836     pop_token();
 837   }
 838   if (ptr_num > 0)
 839     obj_type.set_pointer(ptr_num);
 840 
 841   if (is_token(NAME)) // 判斷是不是 id
 842   {
 843     Token t = pop_token();
 844     ASTNode *v = new ASTNode(t);
 845 
 846     v->set_obj_type(obj_type);
 847 
 848     var_node->add_child(v);
 849   }
 850 
 851   while(is_token(",")) // 判斷 0 ~ 多個的 ,
 852   {
 853     pop_token();
 854     int ptr_num = 0;
 855     while(is_token("*")) // 判斷 0 ~ 多個的 *
 856     {
 857       ++ptr_num;
 858       pop_token();
 859     }
 860 
 861   if (ptr_num > 0)
 862     obj_type.set_pointer(ptr_num);
 863 
 864     if (is_token(NAME)) // 判斷是不是 id
 865     {
 866       Token t = pop_token();
 867       ASTNode *v = new ASTNode(t);
 868       v->set_obj_type(obj_type);
 869       var_node->add_child(v);
 870     }
 871   }
 872 
 873   if (is_token(";")) // 判斷是不是 ;
 874   {
 875     pop_token();
 876     obj_type.clear();
 877   }
 878   else
 879   {
 880     Token token = peek_token(); 
 881     err("var_decl: should ;", token.str_);
 882   }
 883   return var_node;
 884 }

不過先談一般的變數宣告, 像 int a; 就是變數宣告, char (*(*x[3])())[5] 這種也是變數宣告, 不過很抱歉, 本篇的 ebnf 無法解析這麼複雜的宣告, 也沒打算支援這麼恐怖的宣告, 頂多是 int *********i; 這種。

c_parser.c L823 的 var_decl() 就已經很長了, 已經不容易和 ebnf 對應了, 這是因為我加了不少的東西, 掩蓋了本質, 我需要區分 global/local variable, 並且用一個資料結構紀錄這個變數的型別, 這不容易, 你要怎麼紀錄 char (*(*x[3])())[5] 的型別呢? 我沒想到好方法, 先用個 ObjType 檔一檔。

本質就是
ex1
int i;
char c;
char *pc;
int *pi;

這樣而已, 感覺沒那麼難, 應該寫的出來, 但就算只有支援指標, 也很困難, 看看 ex2 的例子:

ex2
int *******i;
int ********************i;

這就有點難了吧! 你說沒什麼多個迴圈去跑而已, 但要怎麼把型別記錄下來呢?

* 是指標
** 是指標的指標
***
****

要用怎麼樣的方式紀錄這是幾顆星的指標呢?

這便是 {'*'} ebnf 對應的部份, L833 的程式碼就是在對付這個 ebnf, L851 開始的部份則是在對付 { ',' {'*'} id } ebnf, 再來一次而已, 如果這樣的程式碼對你來說很難看, 試試用 gdb 跑一次, 邊跑邊觀察 ASTNode 怎麼長出來, 就會有感覺了, 我也是這樣開始的, 當然如果你找得到朋友詢問, 那是最好的, 如果你在某聚會上遇到我, 也歡迎找我聊聊。

如果還是看不懂, 那該怎麼辦, 沒辦法了, 先放棄吧, 編譯器沒那麼重要, 可以先玩玩別的東西, 等過了一段時間記得回來, 也許就看懂了。有這麼好的事情嗎? 難說, 搞不好就有這樣的好事發生在你身上。

ex1, ex2 解決之後, 就可以來處理函式宣告與定義了。

和變數比較起來, 函式多了後面的 (), 以及 () 裡頭的變數宣告, 所以得要先能處理變數宣告才行。

L748 func_decl() 在處理函式宣告, 和變數不同的是多了

'(' parameter_decl ')' '{' body_decl '}'

L780 parameter_decl() 在處理 parameter, 和變數有點像, 只是沒有 ';' 結尾, 再來是 function body, 裡頭可以想成由變數宣告、四則運算、if/else、while 的組成結構, 越來越複雜了哦, 不過這些之前都對付過了, 把他們組合起來即可。


這就是為什麼我是依照這樣的順序來學習這些項目, 他們有一點點的相互關聯, 而拆解這些項目, 才能專住在某一個小部份, 也才能用零散的時間來學習, 感覺上也沒有那麼難了。

list 1 是這次的成果, 有了函式/變數的 AST, 酷吧!

list 1, function myfun declare/definition, variable declare AST
51 
52 int myfun(int ***p3, int a, char *p1)
53 {
54   int i,j;
55 
56   1+2;
57 }
58 
59 
60  ./c_parser < test_pattern/var_1.c | ./tree
 1                                           root
 2                                            |
 3                                           prog
 4                                    ________|________
 5                                    |               |
 6                         myfun |int |func |global  main
 7                     _______________|_______________
 8                     |                             |
 9                    para                       func_body
10        _____________|_____________           _____|______
11        |            |            |           |          |
12 p3 |ptr<3> |int   a |int  p1 |ptr<1> |char  var         +
13                                          ____|____     _|__
14                                          |       |     |  |
15                                        i |int  j |int  1  2

function 分為 para, func_body; func_body 又分為 "變數宣告" 和 "執行的程式碼" (可以想成四則運算) 兩部份。

list 1 L12 myfunc parameter 的部份是:
變數名稱是 p3, type 是 3 顆星的 int 指標
變數名稱是 a, type 是 int
變數名稱是 p1, type 是 1 顆星的 char 指標

list 1 L12 myfunc func body 的部份是:
變數宣告:
變數名稱是 i, type 是 int
變數名稱是 j, type 是 int

執行的程式碼的部份:
1+2

這樣就把 function, variable 用 AST 表示出來了。

ref:

2017年2月4日 星期六

c++ 11 的 chrono, 時間程式庫

chrono 應該是個令人陌生的單字, 通常我們熟悉的是 time, date 之類的單字, 這個單字是 "時間" 的意思。所以這個系列的 class 是用來處理日期與時間。

chrono 還真不是普通複雜, 我只不過是要把 system_clock::now(); 以數值的方式印出來, 結果花了 3 小時才完成目的。 除了概念上的抽象外, template 語法也讓這個程式庫的難度增加不少。

auto 很好用, 但它隱藏了複雜的型別宣告, 對於理解 chrono 的這些東西造成了阻礙, 書上介紹都用 auto, 這讓真相又模糊了一些。

先介紹 chrono 的相關名詞, 很重要, 一定要搞懂這些概念, 否則會覺得 chrono 怎麼這麼難用。

system_clock::now() 會傳回 time_point, 所以目標是怎麼把這個 time_point 印出來。

time_point 是 duration + epoch, 所以要搞懂這 2 個。

duration 是 (tick, 秒)的組合, 而秒是用 ratio class 表示, 所以順便要知道 ratio 的用法。

t2.cpp L14 定義了一個 duration, tick 單位是 int, 1 個 tick 是 0.001 (1/1000) 秒。

14 duration<int, ratio<1, 1000>> du{2};
15 cout << du.count() << endl;

du{2} 表示有 2 個 tick, 所以這個 du (duration) 表示 0.001 * 2 = 0.002 秒。

clock 則是定義一個 epoch 和 tick 週期, epoch 是起始點, 每個 clock 都可以有不同的起始點, unix 可能是 1970/1/1, 0 時 0 分 0 秒。

好了, 知道了這些, 那該怎麼印出 system_clock::now() 呢?

減去 epoch 求出 duration, 再印出這個 duration 即可。

所以這個 now 並不是直接印出 now 的值, 而是從 now 到 epoch 的 duration, 如果 now 是 1970/1/1 - 0 時 0 分 1 秒, epoch 是 1970/1/1, 0 時 0 分 0 秒, 那這個 duration 的數值是多少呢?

不見得是 1, 有可能是 1000, 有可能是 1000000, 因為 duration 還有一個 ?? 秒的單位。
這個時間是 "秒", 如果 duration 是以 1 秒為單位, 這個數值就是 1, 如果以 0.001 秒為單位, 就是 1000。

2 個 time_point 可以相減, 得到的是什麼呢? 是 time_point 嗎? 不是, 是 duration, 但是這個 duration 的單位是什麼呢? 不知道沒關係, 透過 duration_cast 轉成我們要的單位即可。

L46 就是在做這樣的轉換, 我把它轉成 us 為單位。

沒有使用 auto 的 template 變數看來嚇人, 不過 template 語法就是這麼嚇人。

標準程式庫的 header file 定義了 (/usr/include/c++/6/ratio, /usr/include/c++/6/chrono) microseconds, micro

ratio:517: typedef ratio<1, 1000000> micro;
chrono:530: typedef duration<int64_t, micro> microseconds;

為了搞懂這些單位, 我沒有使用標準程式庫的 micro, microseconds, 這樣讓我更清楚 duration 的單位表示法。

t2.cpp
 1 #include <iostream>
 2 #include <chrono>
 3 #include <vector>
 4 #include <string>
 5 
 6 using namespace std;
 7 using namespace std::chrono;
 8 
 9 #include <unistd.h>
10 #include <ctime>
11 
12 string as_string(const system_clock::time_point &tp)
13 {
14   time_t t = system_clock::to_time_t(tp);
15   string ts = ctime(&t);
16   ts.resize(ts.size()-1);
17   cout << "time_t t: " << t << endl;
18   cout << "ts: " << ts << endl;
19   return ts;
20 }
21 
22 int main(int argc, char *argv[])
23 {
24   //duration<int, ratio<1, 1000>> d{2};
25   //cout << d.count() << endl;
26   time_point<system_clock> epoch = time_point<system_clock>{};
27   time_point<system_clock> tp = system_clock::now();
28 
29   as_string(epoch);
30 
31   time_t t = system_clock::to_time_t(tp);
32 
33   string ts = ctime(&t);
34   cout << "now: " << ts << endl;
35 
36   time_point<steady_clock> tp1 = steady_clock::now();
37 
38   time_point<steady_clock> steady_epoch = time_point<steady_clock>{};
39 
40   //duration<int, ratio<1,1000000>> d = duration_cast<microseconds>(epoch - tp);
41   //duration<int, ratio<1,1000000>> d = duration_cast<microseconds>(tp - epoch);
42  
43   typedef duration<unsigned long long, ratio<1,1000000>> unit;
44   //typedef duration<int, ratio<1,1000000>> unit;
45   //typedef microseconds unit;
46   unit d = duration_cast<unit>(tp - epoch);
47   cout << d.count() << endl;
48 
49   return 0;
50 }

那可以印出 epoch 或是一個 time point 的值嗎? 可以的, epoch 其實對應到一個 time_t 值, 這個值不用印也知道是 0, 但你還是想印出來確認吧? 該怎麼印出這個值呢?

L14 在做這樣的轉換。time_t 的時間單位是什麼呢? 通常是以 unix epoch 19700101 為計算基準的秒數, 由於 time point 就是 19700101, 所以就是 0。

test env:
debian x86_64

ref:
Why is the Win32 epoch January 1, 1601? (win32 的 epoch 和 unix 不同)
C++ 標準庫 5.7 p 143
The C++ Programming Language國際中文版 第四版