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

看板Programming作者tinlans.時間18年前 (2007/04/26 06:01)推噓4(4推 0噓 11→)

留言15則, 4人參與討論串25/38 (看更多)

※ 引述《sniffer@kkcity.com.tw ( )》之銘言： > ※ 引述《tinlans.bbs@whshs.cs.nccu.edu.tw (汀)》之銘言： > > 我印象中 BNF 可以描述 context-sensitive 的 syntax， > > 受到較多限制的 BNF 才會變成 context-free 和 regular expression， > > 所以我才說 BNF 可以高興怎樣寫就怎樣寫， > > 但是 parser 不見得做得出來。 > 舉個例子? 能用 BNF 不能用 machine 做 parse 的語法? > 不能 compile 是有的, 如 int a[100000000000000] > 很多 code gen 和 library 都是直接用 BNF 語法的你好像已經忘記我更前面說「context-free LALR(1) parser」了：一個 grammer 能用 BNF 表示，並不會代表它的 parser 好寫，因為 BNF 可以隨你高興寫，但寫出來的 form 不見得適合 context-free LALR(1) parser 去 parse。換句話說我只要隨便舉個 context-sensitve 的 BNF， context-free LALR(1) parser 就 parse 不出來，這跟「不能用 machine 做 parse」是不一樣的意思。 > > 我講的 80 年代 programming 技術， > 3GL 是 50 年代 programming 技術, template 從 lisp(196x), forth 就有 > OO 語言的歷史比 C 還久, smalltalk(1969) 就有 dynamic typing > yacc 遠比 template, OO 先進得多! 只不過是去 parse 一個 .y file，然後照內訂的機制去產生 .c 和 .h，再擺上一堆 #line 進去輔助 debug 而已，可惜這堆 #line 也拯救不了它產生出來的 code 難 debug 的特性，相信你有用 debugger 跳進去看過的話應該就會有所感想。比較晚寫出來並不代表它比較先進，名詞比較早出來並不代表它永遠比較落後，但是一樣東西從出來到現在都沒有改變，卻顯然是落後的一種證明。何況 parser generator 跟 language 誰早誰晚，並不會代表早的一方比較先進，今天用 C++ 的 boost::spirit library 寫出的 parser，顯然就是比 yacc generator 出來的 parser 容易 debug，因為 boost::spirit 用的技術比較先進 (無關它是否較晚被做出來)，而 yacc 使用的技術卻一直停留在舊時代，如此而已。 > C++ 只是把這些 196x-197x 的東西換個用辭, 大家基本上停留在 3GL > 舊沒有不好, 像 assembly 還不是要學會, 舊的東西本來就沒有不好，但是沒有隨著技術進步而更新實作內容就是不好 (白話就是不長進)，工程上 legacy system 本來就是一個很沈重的負擔。 assembly 永遠不是舊的東西，每當一個新的 CPU 被設計出來，新的 assembly language 也再次出現，一個 8051 assembly 超強的人，看到 ARM 的 assembly code 一樣幾乎等於要重學，看到 IA64 或是其它各種 VLIW architecture 的 assembly code 一樣幾乎要重學，以前寫 assembly code 的人根本管它什麼 pipeline hazard，現在你不管它寫下去跑出來保證答案亂七八糟。 assembly 不是舊的東西，它是一個相當基礎的存在， yacc 和它並不能相提並論，因為有各種和 yacc 同 level 的 tools 可以取代它，但如果沒有 assembly language， compiler 就必須直接跳過 assembler 直接生出 machine code，你很難找出當今世上有什麼東西跟 assembly language 同 level，又可以取代 assembly language 的東西。 > 商用 compiler 也還是在用 4GL, 含 yacc > 很多所謂的 "library" 是 4GL interpreter, 如 SQL > 寫 compiler 用 4GL 很快很省事, bug 好不好抓跟程式架構有關, 這跟我看到的情形差很多，商用的 compiler，如 ACE Cosy、MetaWare 的 C/C++ Compiler Tool Suite、Target 的 CHESS，還有 Altium TASKING 的 Viper，它們的 front-end 都不是 4GL 做出來的。 > 不然 perl 和一堆無法 BNF 的語言 parser 為何大多用 yacc? 這理由很簡單，因為大部分 compiler 教科書都教人用 yacc，而且都不願意更新書本的內容教大家用其它 tools，所以大部分修過 compiler 課程的人，一聽到 parser 第一個反應就是 yacc，如同學過 data structure 的人一聽到 postfix 就會想到 stack 一樣，而沒修過 compiler 課程的人跑去問修過的人，修過的人也如此反應回答 yacc，這是久未更新的教科書所帶來的原罪。事實上講白話一點，你這個問題跟「為什麼現在的 OS kernel 很少用 C++ 撰寫」是相同的，答案其實簡單到不行，因為 C++ 盛行得很晚，大家都用 C 寫完了用 C++ 重寫幹嘛？再說 open source 的 kernel 也是用 C 寫，有現成的 C code 可以拿來抄幹嘛自己設計？就算要自己設計，教人寫 kernel 的書都用 C 跟 ASM，有範例可以抄來改誰會不抄，當然還是用 C 跟 ASM。所以，為什麼一堆人用 yacc 的答案應該再明顯不過了。 > > 指的是 yacc 這個工具 (無論是設計或是產生出來的 code)， > > 跟 C++ 是不是新東西倒沒什麼關聯性， > > 重點是 2007 年用 yacc 去生 parser 的 code 已經非常不合時宜了， > > 做 parser 有更方便更容易除錯的 language-level library 可以使用。 > > 至於 public private protected friend 這類東西， > > 會不懂的大概也只剩下 10 年前還是學生的叔叔伯伯姑姑阿姨了， > 這些東西懂了嗎? 記得了嗎? > 繼承以後的改變背起來了嗎? 我第一次聽說學寫程式要用背的，寫程式是 close-book 的上機考嗎？有書放在旁邊可以翻不翻實在很奇怪， C++ 系列書籍的「原文中譯本」在台灣算是非常齊了，說沒書也實在是很奇怪，這東西跟你知道 double x = 1 / 5; 結果為什麼會是 0 一樣，有用到有遇到過幾次就會熟了，沒有什麼是要特別去背的，寫程式寫到要用背的就很可悲了。 > 不然 java 把 virtual 換成 interface 是為何, 照你上面講的，那還不是要去背 interface 跟 abstract 是什麼東西？還不是要背 interface 跟 abstract 還有啥都沒寫差在哪？事實上在 Java 也不是把 virtual 換成 interface，而是把 C++ 某種 abstract base class 的特例制訂成一個語言機制， interface 在 C++ 就是只含有 pure virtual function，且沒有任何 data members 的 abstract base class，沒有 constructor、有一個 pure virtual destructor (Java 無 destructor)；這只是把一個 C++ 沒有明確描述的東西用明確的語言機制去描述，但同時也是帶給 programmer 一個限制，我想你應該也注意到了， interface 不能有 data members，但是 C++ 可以，這就是所謂的限制。 C++ 跟 Java 的取向不同，賦予 programmers 自由和責任也大相逕庭，要互相比較是很困難的。 > 常常有人 C++ 寫完編不起來去亂 public, 這就是不用功和不讀書的問題，我也常常看到 Java programmer 的初學者，人家寫得好好的 factory method，他當成是垃圾和多餘的東西把它一整個砍下去 (嫌要寫比較多 code)，我也看到一堆人在 Java 想用多重繼承結果用不出 (沒讀書不懂 Java 的精神)，嫌 Java 難用把它丟了換 C++ (相當然爾這種態度一樣學到爛掉)。這根本是學習態度的問題，跟使用哪種語言無關。 > 不然就是不知 call 得是 parent method 還是 child 這也是不看書造成的問題。 > C 語法就一點點還能用啥奇招? > 再奇怪也跳不出 C 語法呀, inline assembly 之類是寫 OS 必需的, > C++ 不能寫 OS, 又有不明確的 memory map, 自然少人用 inline assembly C++ 可以寫 OS，中正大學的 OS lab 就有人在用 C++ 寫 OS，隨便 google 一下也會找到一個叫 unixlite 的 OS 是用 C++ 寫的，不要被無知的 Linus Torvalds 騙了 (有名而且說出這種話的幾乎只有他)，他根本不瞭解 C++。我講的不是什麼 inline assembly，你說再奇怪也跳不出 C syntax 也沒錯，但是偏偏就會出現一堆有的沒的怪招來，重複一次：「新語言機制」是因應「舊語言技巧」而產生的。舉例來說，大家都認為 OO 有必要，所以把 OO 做進了新的語言裡， C 不支援 OO，但是可以模擬 OO (用上極其大量且怪異的設計方法以及 macros)，而且可以用「各式各樣的方法」去模擬 OO，你幾乎可以說是換一個 team 就要重學一套 (如果你有需要擴充它，那會更慘)，可是 OOPL 把它做進語言裡面去，那些莫名其妙又詭異到不行的寫法就不會出現在你眼前。另一個例子，拿以前的 reference counting 實作來講好了，這會有一小塊東西綁在實際 data 前面， malloc 的時候 size 必須是 sizeof(info type) + sizeof(data type)，所以你要另外寫一個 macro or function，去把 malloc 來的東西 cast 成 (info *) 再 + 1 才 return 回去，於是乎 programmer 可以把這 pointer 用得跟平常 malloc 來的一樣，只有 allocate 跟 deallocate 的時候不同，但是所謂的「亂搞」問題也因而產生，他可以不照規矩直接 call free() 去 deallocate。用 C++ 實作相同功能的東西可以防止這個「亂搞」，而如果這個功能是為了 garbage collection，雖然 Java 的原理不是 reference conuting 技術，但是 Java 已經內建在語言，所以更不可能亂搞。比 reference counting 還千奇百怪的 code 到處都是，所以我要強掉的：「C + 一堆 tricks」 == 「C++ + 很少 tricks 」就是這個原因。一個 C project 裡面通常會有一兩個超強的 C programmer，他們寫的神奇東西可能因為其他人太爛所以被「亂搞」，但是這些神奇東西在 C++ 直接被做進語言或標準函式庫，其他人就算再爛也至少「有書可翻」，被亂搞的機率大幅下降 (我想你應該知道我已經排除不讀書的人)，而且出問題的時候，也因為底層的東西是「標準的」，所以你不可能需要 trace 到裡面去，但是 C 就需要，至少 reference counting API 在 C 不是標準的東西，你不可能不懷疑裡面有東西寫錯。 > 比 C 高階的東西用途都是受限的, 這就是為何 C++ 反而萎縮被 java, C# 吃掉 C++ 從來都沒有盛行過，而 Java 和 C# 盛行是因為現在電腦都太好了，跑慢一點 user 也沒差，加上都是大廠在推，尤其是 Sun 還到處幫人家的 OS 寫 VM，所以編出來的執行檔 (為跟 C++ 比較姑且這麼稱呼) 可以直接拿去別家 OS 執行。 C++ 拼不過 Java 和 C# 市場還有一大原因， Java 提供廣泛的 API， C# 提供了功能強大的 .NET framework，這些東西幾乎都是預設就有，而且哪個平台都能用 (.NET 在這方面跟 Java 相比倒是比較弱勢)，但是 C++ 在那邊拼死命的堅持「語言標準與平台無關」，連 thread lib 要進 C++ 都被擋了快 10 年 (其實不看標準制訂日期的話早超過了)，像是 socket lib 這種東西更是不用講了，可惜現實上是現成元件越多的語言越受大家喜愛，就是如此而已。你在用傳統 C++ 搭 MFC 寫 MS 視窗程式，人家開 Java 和 C# 的 IDE 跟你拉元件拉得很高興，某些人因此改用 BCB 去跟他們拼了，但是人家寫出來的東西可以拿去其它機器直接跑，連手機上跟 PDA 都可以，就是你的不行，不會因此跳槽去 Java 跟 C# 的人可說是少之又少，至少寫 application 的都會跳過去，學商的都知道 Java 跟 C# 的這些好處可以省成本，大幅招募會 Java 和 C# 的人來當員工，整個市場一炒作下來 C++ 當然連爬起來都沒機會就被淹了。 > 還會出來拔掉一堆東西的 embedded C++ Embedded C++ 這東西顧名思義，是給 embedded system 用的，事實上這個東西是假設 C++ programmer 都很無知，要不就是制訂 Embedded C++ 的人對 C++ 並不瞭解，我上面列出的 commercial C/C++ compilers 有些會支援 Embedded C++，但是值得注意的一件事情是，它們允許你選擇打開 Embedded C++ 裡被 disable 的 C++ 功能，為什麼 commercial C++ compilers 會幹這種事情？這正是因為 Embedded C++ 有很多失當的地方所致，正常的 C++ programmers 不願意接受這些白癡的限制。 > 要比省打字工, 4GL 更省, 要做 data structure, pascal, java, c# 也可以 > 要效能, 大家都乖乖用 C+asm 寫的 library 去了選 tool 不單是看省打字工跟 performance，容易 maintain 和 debug 的才是好 tool，實際上 C++ 的 layout 非常明確，並不會像你說的那樣，除非你用上了多重繼承。既然你舉了 embedded c++ 的例子，那我順便提一下，以前大家都認為 embedded system 用 C + ASM 就很棒了，要跨平台的彈性也有 Java 跟 C# 可以撐，怎麼會有那麼多家公司想做 for embedded system 的 C++ compiler？這當然是有它的需求存在，你前面說要省打字工可以選一堆 language，要效能可以選 C + ASM，那如果兩個都要呢？ C++ 就是答案之一。 C++ 在 performance 上的問題沒你想的誇張，甚至是 memory 的佔用上；就算是使用純 OOP 撰寫程式也不會比 C 差到 10% 以上，擅長使用 template + OO 的人可以降到 1.5 - 3% 左右，而且 memory space 也不會因為使用 template 佔用太多；使用 template 來搭 OO 可以壓低繼承樹增加 performance，甚至是將 runtime 的 recursive call 改寫成一連串相異函式的 tail-call，懂得如何幫 template 瘦身的人更不會因為 template 而讓程式特別吃記憶體，這些都有書可以學。 > C 連 calling convention 都標準化, 跨 compiler 的 linking 都可以, > C++ 原來 function name encoding 還算有標準, 現在不同家的 obj file 無法互通事實上 C 那個不是標準化，只是 x86 上有特別訂一套而已，你去別的 architectrue 上 try 也是死成一片，除非 architecture 的製作官方有訂出來 (像是 ARM 有訂 APCS，後來還有改版)，不然都是一樣互相 link 通通死光光。 > 更不用說語法撿查都不一樣, gcc3->gcc4 一堆東西不能 compile > visual c 5.1->6.0->.net 也是, 更不用說 borland, ibm 只做了半套 template 那不叫語法檢查不一樣，我之前不是說過了，因為 gcc3 用 bison 做的 parser 實在有夠爛， gcc4 重寫了 parser 實施了正確的檢查，所以 gcc3 會過的 gcc4 才沒有辦法過。我也說過 compiler 的開發是漸進式的，尤其是 parser，當 C++98 標準出現以前，大家遵守的是 ARM (不是前面提到的那個 architecture name)，並隨著各種即將進入 C++98 的標準逐步修改， bison 這個 tool 禁不起這種多變性的需求， GCC 到後來才終於整個重寫。如果你真的熟悉 C++ 標準，你應該知道有很多東西在舊的 compiler 放很鬆，以 eMule 的 source code 來說最大的差異就是 typename 的檢查，如果 T<X>::type 的 T 是一個 class template， type 是 T<X> 裡面的一個 typedef，根據 C++ 標準，你用 T<X>::type 宣告一個變數需要在前面冠上 typename，但許多舊的 compiler 自行放寬了這個限制，這個光 VC 6 (C++98 標準制訂前發售) -> VC 7.1 就會遇上了，大學時代我同學把我叫去幫他編，我就解過一次，其它軟體在 GCC 上也遇到過這個問題。 > C 從來沒發生過舊 code 不能 compile, 或 obj file 不能 link 是嗎？我國 BBS 的 source code 就慘遭以下大地震屠殺：我手上的環境是 GCC 4.3： > gcc43 -v Using built-in specs. Target: i386-portbld-freebsd6.1 Configured with: ./..//gcc-4.3-20070302/configure --disable-nls --with-system-zlib --with-libiconv-prefix=/usr/local --with-gmp=/usr/local --program-suffix=43 --libdir=/usr/local/lib/gcc-4.3.0 --with-gxx-include-dir=/usr/local/lib/gcc-4.3.0/include/c++/ --infodir=/usr/local/info/gcc43 --disable-libgcj --prefix=/usr/local i386-portbld-freebsd6.1 Thread model: posix gcc version 4.3.0 20070302 測試檔： #include <varargs.h> void foo(...) { } int main() { foo(1, 2, 3); return 0; } 錯誤訊息： In file included from test1.c:1: /usr/include/varargs.h:34:2: #error "<varargs.h> is obsolete with this version of GCC." /usr/include/varargs.h:35:2: #error "Change your code to use <stdarg.h> instead." 如果你說這只是 C standard 改了 library header 又沒什麼，那我把它改成 #include <stdarg.h> 好了 (其實這個例子什麼都不用 #include)，結果又出現： test2.c:3: error: ISO C requires a named argument before '...' 很遺憾，這段純 C 程式碼在 15 - 20 年前可以正確無誤的通過編譯，連一個警告訊息都不會有，我從 K&R C 一路玩到 C99， legacy code 會遇上什麼問題都遇過了，說 C 不會遇到 ARM -> C++98 -> C++03 -> C++0x 的問題，那是絕對不可能的。知道 GCC 為什麼會有 -fstrict-aliasing 這個 option 嗎？因為 C standard 後來有放鬆一些 aliasing 的判定方式，讓 compiler 能做出更多的 optimization，以致於有些做過 pointer casting 的老舊 code (GCC 手冊的範例是 union)，在 -O2 以上編譯出來的程式碼，在「執行期」發生了與過去完全不同的意外行為。 > 如 linux kernel 還可用各種不同 compiler, 很多平臺是沒有 gcc 的照標準寫哪怕換了 compiler 就會炸掉？更何況那種東西搭一堆 #ifdef 就好了，如果不是寫 linux kernel (cross-compiling)，那還有 autoconf 可以搭上去用。問題是很多人不懂標準，而且標準也會隨著時間修改， linux kernel 算還好的，雖然沒有直接重寫成 C++，但是至少 code 跟 implementation 有在改進，所以我一直都沒有把它當成 yacc 來罵。 -- 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"的狂狷不馴；屬於年少的輕狂色彩 ◎