Re: [問題] 如何學寫COMPILER? [純拋磚引玉]

看板Programming作者tinlans.時間18年前 (2007/04/27 21:32)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串30/38 (看更多)

※ 引述《sniffer@kkcity.com.tw ( )》之銘言： > ※ 引述《tinlans.bbs@whshs.cs.nccu.edu.tw (汀)》之銘言： > > 你好像已經忘記我更前面說「context-free LALR(1) parser」了： > BNF is context-free only 不好意思，這個的確是我記錯了， BNF 有規定 ::= 左邊只有一個 symbol， KNF (Kuroda Normal Form) 才可以那樣玩，我誤會你了。 > 如果所用的 yacc 可靠, 你也不該追進去看 > 只應該看人寫的部份的 C, 好的 debugger 是支援 yacc 的 debugger 其實不是直接支援 yacc，而是跟著那個 #line 對應的行號跑；而 yacc 本身當然是可靠的，但是有一個缺點在於， programmer 本身寫的文法不見得可靠，或許你會說 spirit 也是有這種現象，但是你換個角度想想，現代的程式重視的是能「共同合作」和「容易交接」，如果「讀程式碼」和「debug 的人」都不是「原作者」，會是什麼樣的情景呢？ debugger 在 yacc 的狀況是，會混著 .y 跟 .c 在跳，這是因為 yacc 在 .c file 裡面插入了一堆 #line 123 "xxx.y" 這種東西，可是這時你就會有一個麻煩，相信你也知道 .y 常常是這樣寫的： rule1: xxxx yyyy zzzz { /* 超大一片 C code */ } | aaa bbb { /* 又是超大一片 C code */ } | ... yacc 會把 #line 插在每個 { 的下面，所以當 debugger 跑進去看的時候固然能看到原本作者寫的 .y file 內容，但是... 通常 debug 的人跳進去會看到的東西是長這樣： /* 上面一大片 code 的末幾行 */ } | aaa bbb { /* 下面一大片 code 的前幾行 */ 就算 debugger 有辦法讓你直接輸入那些 $$ $1 $2 幫你展開好了，你看到的東西仍然是一個 grammar 的片段，但是 spirit 就不會有這種現象，你很容易看到完整的 grammar，大概會是長這個樣子： rule1 = (xxxx >> yyyy >> zzzz)[&action1] | (aaa >> bbb)[&action2] | ... ; 雖然在更複雜的情形下 spirit 的版本會看起來亂一點，但是 programmer 用 debugger 跳進去的時候大都可以看到完整的 rule，而且他們也有辦法選擇要不要 step into 到裡面去， debug 起來自然容易，不是作者的人看起來也比較簡明易懂。 > spirit 是 boost 之中特別容易讓 compiler 掛點的東西之一, 這年頭會因為這樣就掛掉的 compiler 不多了，除非你還在用 VC6 跟 gcc 2.95.x。 > 光 boost 要編起來就很麻煩, 遇到 compile error 比 yacc 更頭大嗯，關於這一點， *nix 上通常有一種東西叫做套件管理系統，譬如： pkg_add boost-1.33.1.tbz apt-get install boost emerge boost cd /usr/ports/devel/boost; make install clean 然後去吃個飯就好了，當然偶爾會碰到一些地雷，但是這些套件的 maintainer 會負責搞定它，這個大可放心。 > 只因為是 C++ 就一定好 debug? error message 的數量就可說明當然不可能是這樣，理由在上面就有描述了一部份囉。 > > 今天用 C++ 的 boost::spirit library 寫出的 parser， > > 顯然就是比 yacc generator 出來的 parser 容易 debug， > > 因為 boost::spirit 用的技術比較先進 (無關它是否較晚被做出來)， ^^^^^^^^^^^^^^^^ > 看起來跟 yacc 很像, 卻是 C++, 比較先進是說用 C++ 就先進? 上面已經不是說了，是用的「技術」比較先進，讓該在一起的東西在一起，不該混在一起的就分開來 (grammar 跟 action)，進而獲得不想 step into 就可以 next 掉的 debugging 優勢。 > xxx = a|b; > yyy = xxx|c; > 因 C++ 語法限制所以還不能像 yacc 用 LR, spirit 是 LL only > 從來沒有比 yacc 先進的說法不對，這是因為 spirit 故意選擇了 recursive descent parsing，為什麼？因為合乎人類的直覺，所以也因此更容易 debug (容易 debug 的理由又多了一個)。 GCC 4.x 也選擇了「純手工」打造的 LL(1) parser， boost::spirit 則選擇了「半手工」打造的途徑，並不能說 LL 在課本上比 LR 早出現，而 LR 可以比 LL 少改一些文法，就說 LL 比較落後， LL 跟 LR 各有優缺點，而它們的優劣差異可以大到讓人們分成兩大派系，所以拿 LL 跟 LR 來區分先進與落後是不恰當的。 > PPC, MIPS, x86 assembly 不夠舊? > 為了 binary 相容一個指另集最少活 20 年重點不是一個指令集活了多少年，而是新的指令集有沒有持續出現。 > CPU 效能看法也一直在變, 古代 ram 少, cisc>>risc, risc 不划算 > 民初 ram 多, risc>>cisc, 工作站用 RISC 成王道 > 近代 cache 少, ram 慢, cisc >> risc, x86 幹掉 PPC,SPARC,MIPS > 現代多核心 vliw>>cisc>>risc, 只是 compiler 難搞 ^^^^^^^^^^^^^^^^^^ 真的嗎？事實上連寫 assembly code 的人都很難搞，他們必須重新學習一套設計哲學，使得自己寫出來的 asm code 可以「正確」而且「比 compiler 編出來的快」， VLIW 可以擴增到 5-way issue、8-way issue 甚至更多，你一個 cycle 最多可以平行 issue 那麼多指令出去，不但要想辦法解決 dependency 的問題，還要想辦法盡可能的把指令排在最少量的 bundle 裡， VLIW 跟 superscalar 的差異我想你應該知道，它是不會幫你解決 hazards 的，大部分為了節省成本連偵測都不偵測，而且 programmer 甚至可以利用不偵測的特性，做到一些以往在 RISC 和 CISC 都做不到的最佳化，譬如因為 MEM 指令的結果要在 2 個 cycles 後能給 ALU 指令用，這時我們可以將使用舊值的 ALU 指令排在 MEM 指令跟 ALU 指令之間，會自動偵測和 stall 的 architecture 辦不到這一點，因為你一插到中間去， hardware 就會幫你 stall 起來保證拿到的是新值；很多觀念都越來越不一樣了。加上每個 ISA 都會有各自的特異功能，有時還會為了一些奇奇怪怪的理由讓指令有諸多限制， asm code 的設計哲學也會因此大幅轉變，重點是 asm language 本來就是綁 ISA 的， asm syntax 也會因為 ISA 的特殊性而有所改變，它們時常都在變化。 > 何種 CPU instruction 叫先進? 所以說你搞錯重點了，重點是 asm 一直都在變，而我已經說過長期不變的東西往往是落後，這沒有什麼奇怪，技術這種東西本來就是不進則退，技術跟工具這兩種東西與理論不同，它們本來就是非常物質面的東西，很難像理論一樣永遠能以不變應萬變。 > microchip c18, m$ visual c 都是 bsd yacc > 只要在檔案中有很大的非人寫成的 table, 都是 code gen 產生的 > 不一定是 yacc, 但是通常 compiler/interpreter 走兩個極端: > 1. 4GL, 最快速完成 > 2. 用 3GL 硬幹, 執行最快速, 如 turbo pascal, 大多 interpreter > visual c 有 "grammar.y", c18 有 "yacc stack overflow" > 在 compiler 執行檔找 yacc 的收獲會不少世上仍存在使用 yacc 寫成的 compiler 是正常的，就如同我前篇所說的，久未更新的教科書留下的遺毒其實很恐怖。 4GL 確實不是壞東西，而我一開始也只有說 yacc/bison 一直不變所以很不好。 > 照這樣說, 那 yacc 跟 spirit 比 C++ 和 java 之間差更多 > 要互相比較是更困難囉, 為啥不能比較 C++ & java 答案很簡單，因為 C++ 和 Java 一直還有在改進，但是 yacc 停住了， spirit 不但使用了新技術且確實達到了使用該技術的目的 (好寫好 debug)，而且它仍然在不斷改進當中 (要注意是技術面的改進，可以比較看看它的歷史紀錄)。 > C++ 的 template 不算 tricks 的話, 比 template 更簡單的 C 語法何來 tricks > C 的語法能作的變化更簡單 C 語法能作的變化太簡單，就達不到 C++ 完全不用變化就能做到的功能，所以 C 語法在要達成跟 C++ 相同功能的狀況下 (享受相同/相似的好處)，語法會相當不簡單。不少人曾經用純 C 來模擬 OO，使用了大量且特異的 data structures，以及千奇百怪的 macros，相信你應該有見識過才對。語言的 tricks 最終可能變成標準，但是如果語言機制實在太少，那麼這些 tricks 就會變成另一個語言的標準，在 C99 制訂以前這種東西也叫 trick： typedef struct t { int x; char y[1]; } T; void foo() { T *data = malloc(sizeof(T) + sizeof(char) * N - 1); ... } 至於你問 template 是不是 trick，答案當然是 NO， template 是 C++ 原有的機制，它不是什麼 trick，因 template 而生的 generic programming 也是本來就存在的；如果你要說的是 template metaprogramming，很遺憾，它跟上述的 trick 一樣「曾經是 trick」，因為 2005 年 C++ TR1 的出現，已經不再是 trick，參考參考吧： http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf 遺憾的是 C 的 syntax 就是沒辦法直接支援 OO，不能直接支援的不單是 OO 而已， template metaprogramming 的 turning-complete 性質也是，要模擬它們的確不是完全沒辦法，但那些方法要從 trick 變成標準實在是難上加難，這都是因為 C 實在太簡單的關係，上面的例子之所以可以進入 C99 標準 (其實 C99 有把外觀稍微改了一下)，是因為它還沒有太奇怪。 > > C++ 在 performance 上的問題沒你想的誇張， > > 甚至是 memory 的佔用上； > > 就算是使用純 OOP 撰寫程式也不會比 C 差到 10% 以上， > > 擅長使用 template + OO 的人可以降到 1.5 - 3% 左右， > template 為何會比 C 省 memory, 舉個例吧上面第三行跟第四行是一組的，第三行說「比 C 差到 10% 以上」，第四行是說「降到比 C 差 1.5 至 3% 左右」。實際上我這種說法還是在不公平的狀態下比較，如果你真的把 C 用 OO 的樣子來寫， C++ 反而會佔有優勢，因為 C code 是由人手工去撰寫那些 code，但 C++ 是由 compiler 來產生那些 C 必須以手工方式撰寫的 code， compiler 的最佳化對於不確定的事情非常膽小，但是當整件事情都是 compiler 決定的時候， compiler 就有辦法很大膽的做最佳化。用 C 模擬 OO 還有一個非常致命的地方， C 只能用 function pointer 這種東西， C++ 卻能用 functor (function object) 這種東西，而 functor 的好處就在於它可以 inline，以致於獨有這個「以空間換時間」的好處，如果發生位置在於 80/20 法則中的 20% 部分，那可以說犧牲那一點點空間是非常值得的，這個好處 C 沒有模擬的餘地， C 只能模擬相似的行為而已。 > C 一定可以做出和 C++ 產生的 machine code 一樣的東西, 最多就是 source 大點姑且不論產生 machine code 完全一樣是否辦得到 (其實不行，上面有說原因)，「最多就是 source 大點」這句話顯然考慮不夠周詳，這也代表了許多事情： 1. compiler 能做的最佳化減少 (compiler 100% 確信的事情變少) 2. debug 和 maintain 成本增加 (compiler 不會生錯 code，人會寫錯 code) ... (剩下的請自由發揮) > obj C 的 dynamic typing 才是 C 一類 static typing 不能比的 C++ 的爸爸對於 C++ 的效率有所堅持，過大的彈性被 C++ 捨棄，換來的就是遠高於 C 的彈性、便利性，且僅以微小的效率/空間損失做為交換。 obj C 這樣做也是一種 trade-off，出發點跟 C++ 差太多了，如果你不清楚「為什麼 C++ 有提供某某機制」或「為什麼 C++ 不提供某某機制」，這世界上確實存在一本書可以告訴你答案，那本書叫做 The Design and Evolution of C++，這是 C++ 的爸爸寫的，從 C++ 一開始存在一直到 1994 年的心路歷程全部都記在上面，也正因為這本書存在而且我讀過它，所以我有辦法很篤定的這樣說；設計出 Java 跟 C# 的公司，總是忽略了這些考量而刻意以片面的方式攻擊 C++，說一些不著邊際的廣告詞，在這背後其實還存在許多商業因素考量，然而這些說詞影響世人甚鉅，所以在討論的雙方都弄清楚事實之前，比較它們是沒有意義的，也因此我前一篇才刻意簡短的說因為面向不同難以比較，要比較當然可以，但是在比較之前大家都有不少功課要做 (包括我自己)，可是我不想為了戰語言而再做更多的功課，語言是一種工具，在不同的環境明智的選擇適當的工具才是正確的態度，一開始我就這麼說了，何況你目前為止所做的比較並不是優劣的比較，而是輸贏的比較，這種比較的意義確實不大。 > > 而且 memory space 也不會因為使用 template 佔用太多； > > 使用 template 來搭 OO 可以壓低繼承樹增加 performance， > > 甚至是將 runtime 的 recursive call 改寫成一連串相異函式的 tail-call， > > 懂得如何幫 template 瘦身的人更不會因為 template 而讓程式特別吃記憶體， > > 這些都有書可以學。 > > 事實上 C 那個不是標準化， > > 只是 x86 上有特別訂一套而已， > > 你去別的 architectrue 上 try 也是死成一片， > MIPS, ARM, PPC, FR 都有標準, 但 C++ 各家 compiler 差太多, 怎麼定 > 一個 pointer to class method 就有 n 種作法這是因為 C++ 保留給編譯器廠商實作的彈性，不過這東西其實跟 C 一樣有辦法針對各 architecture 制訂公約，只是 C++ 從來就不曾如 C 這麼盛行過，所以設計 arch. 的公司也沒有什麼興趣去訂。標準規格書說「保留給編譯器實作」這件事，並不是真正代表「什麼都看 compiler 高興怎樣就怎樣」，只要 C++ 能跟 C 一樣深具影響力， arch. 的廠商還是會像 C 那樣訂出一套公約讓大家遵循。 > > 因為 gcc3 用 bison 做的 parser 實在有夠爛， > bison is a version of yacc, bison != yacc > 一堆 compiler 用 byacc 我知道它們的差異， FreeBSD 從以前到現在 man bison 都會在第一頁前幾行看到，我也讀過 O'Reilly 的 lex & yacc，這本書也簡略的比較了 yacc 和 bison 的異同，所以倒是不必擔心我不知道這件事，然而正因為我知道它們的共通點在哪， GCC 遇到的問題又落在共通點上，所以我才會直接這麼說。 > 如果用了非標準的 pointer access, 是寫的人有問題 > 就如 ++i 的問題一樣嗯，其實事情也沒你想的這麼簡單，看看這個 link 在「Run-time issues」中的第一點： http://nchc.dl.sourceforge.net/sourceforge/open64/gcc3-build.pdf 這種 code 在 C 可以說是常見的寫法了， 10 幾年前大家用 GCC 2.x 的時代都用得順到不行，結果一上 GCC 3.x 就炸了， GCC 2.x 可是活了非常久的時間 (甚至到現在還到處凌虐各國的研究生和玩板子的)，大家的習慣都養成了，現實就是這麼殘酷。另外，雖然這 link 裡面是 C++ code，但這是 C 本身就存在的問題。 > 較少人使用 (...) 的 function, 這是個很少出現的問題, 也很好改 search/replace > 舊的 binary 和新的還是能相容如果你看過真正的 legacy code，你可能就不會這麼說，過去為了 K&R C 跟 C89 的 function prototype 大地震，各家 compiler 對 C89 的支援性不一，為了相容兩種 function prototype，曾經出現過這樣的 function declaration 遍布於所有 source code： array_t *allocate_class_by_size P1(int, size); array_t *allocate_class P2(class_def_t *, cld, int, has_values); char *read_buffer P4(buffer_t *, b, int, start, int, len, int *, rlen); 注意是「遍布於所有 source code」喔，要 replace 當然傳統的 sed 就能辦到，但是大家當時選擇的是在 coding 的時候就先 keyin 了；還有更多例子可以舉，舉都舉不完。至於 ellipsis (...) 的問題並不是很少出現的問題，小有規模的系統程式和應用軟體都會用上，這種東西也不是光靠 editor 就能 search/replace 的，因為「第一個 type 是什麼」這件事 editor 不知道，沒稍微看一下 function body 在寫什麼的人也不會知道，所以事情並沒有你想的這麼簡單， BBS server 這種小小程式就夠你改到手酸了，不信去抓個老舊版本的 BBS source code 來試試。 > C++ 的問題如 pointer to class method != fucntion pointer, > callback 剛好是 function pointer 主要用途, 又常是 class method C++ 的 non-static member function pointer 設計概念，是希望 member function pointer 跟 object 能分離，所以出現了 .* 和 ->* 這種 operators，加上 non-static member function 本來就會跟某個 obj 綁，如果不是自己製造的 platform (如 CLR 跟 JVM)，扯到最後幾乎就等於是要自己去寫一個 OS。 native 的東西本來就會面臨到「要自己寫一個 OS 才能支援」的問題，問題是「新的 OS 要能盛行」是一件不容易的事情，首當其衝的就是 driver 的支援，寫出王道的 OS 但是各家硬體廠商不甩你， 2007 年的現在要說服這些硬體廠商 support 你實在很難，要說服眾多懂得寫各家 hardware driver 的 hackers 來 support 更難，最後不管寫得多王道最後都只會被埋沒而已，這也是為什麼要 VM 執行的語言跟 native 執行的語言不應比輸贏的原因之一，只能說各有利弊，在正確的場合選擇對的就好了。 > 造成很多 GUI 程式的 callback 大改, 又無法 binary 相容這是一開始就存在且已知的問題，並不是要「大改」，還是一開始就要花費成本去「設計」，但是久了也會變成一個設計階段的經驗，成為 maintain 成本的只有「無法 binary 相容」，但這本來就是 native code 的宿命，除非先去炸了 Microsoft 跟各家 *nix 大廠。 > include, export 等讓書上的 hello world 都要改, 程度上很不同 header files 的問題用 autoconf 就能解決， export 目前沒什麼 compiler 支援，書上也有教 workaround 的方法，這方法也沒有慘到跟上面的 P1 P2 P3 P4 ... 一樣可憐，所以這個成本其實還蠻低的。 > OS 不能用 C++ 寫, 因為會有 compiler/archiecture 相依性, > object 的 memory allocation, method calling 不同 compiler 都做不一樣 > dynamic linking 也完全沒定義, 這種東西不能寫 portable 的 OS kernel > 古早的 OS 有用 PL/I 等高階語言寫, 都不好 port, 才會弄出萬用的 C 設計 architecture 的是老大，如果他不想當老大，那做 OS 的就是老大， architecture 沒規定 compiler 要怎樣， OS 就不能規定 compiler 要怎樣？ C 也是沒規定在標準規格書上，願意當老大的人出來講一句話就會遵守了，只是現在當老大的只管 C 不太管 C++ 而已。當然想當老大也是要有本錢，在 2007 年的今天不是設計出 architecture 寫出 OS 就能當眾人的老大，還存在非常多天時地利人和等等非技術性因素的問題，否則也只能當成兩三隻小貓的老大而已，有本錢當眾人老大的說 NO，那我們也沒有辦法；然而，這絕對不代表「OS 不能用 C++ 寫」，那是完全不一樣的意思。 -- Name: Tseng, Ling-hua E-mail Address: uranus@it.muds.net School: National Tsing Hua University Department: Computer Science Interesting: C++, Compiler, PL/PD, OS, VM, Large-scale software design Researching: Software pipelining for VLIW architectures Homepage: https://it.muds.net/~uranus -- ╔═══╗ ┼────────────────────────╮ ║狂狷 ║ │＊ Origin：[ 狂狷年少 ] whshs.cs.nccu.edu.tw ╰─╮ ║ 年少║ ┼╮ < IP：140.119.164.252 > ╰─╮ ╚╦═╦╝ ╰ ＊ From：61-230-220-241.dynamic.hinet.net ─╨─╨─ ＫＧＢＢＳ ─ ◎ 遨翔"BBS"的狂狷不馴；屬於年少的輕狂色彩 ◎