wangzaixiang2021-03-17 13:45:58

我的感覺是沒有人能解決你的問題，因為你想的東西很多很多很多，而書又讀得很少很少很少。

所以，如果你願意的話，先學習一下《計算機組成原理》，理解一下記憶體、數字、計算之後，能完成基本的作業題之後，再去問這些又抽象又哲學的問題。

navegador2021-03-17 14:24:53

我解釋一下放箱子那個：

程式設計時候 很難有一種資料結構

同時

滿足

讀

的

快

和

寫

的

快

。

比如你的箱子A，B，C，D，E，

像下面這樣存： #sec1

【頭】->A->B->C->-D-E->【尾】

這樣的話，

寫的快

，比如你要新增一個箱子

O

到 B 和 C 之間，只需要動前後3個數據

……。B->

O

-> C……。。。。 就好了

但是這種讀起來比較慢，比如我想知道 O 的序號，我得從【頭】開始數 數到 2 。

假如像下面這樣存： #sec2

A［0］ B［1］ C［2］ D［3］ E［4］

這樣得話寫的比較慢 ，比如你要新增一個箱子

O

到 B 和 C 之間，需要改 O，C，D，E四個資料

A［0］ B［1］ O［

2

］ C［

3

］ D［

4

］ E［

5

］

但是讀起來很快，比如我想知道 O 的序號，直接讀就行，因為資料本身

攜帶了額外資訊

究竟選擇#sec1 還是 #sec2 與具體情況有關，這個簡單得原理 可以推廣到很多情況，資料庫，列資料庫，圖資料庫。。。。。就是說 你設計首先要有一個 輸入條件 限制，你究竟追求讀的快，還是寫的快。 然後再決定 選擇什麼樣的結構。

總的來說：

攜帶的額外資訊（重在預先計算好，以空間換時間）越多的結構，讀的越快，寫的越慢。

靠延遲計算（只儲存必要邏輯，執行時再推演計算，以時間換空間），寫的越快，但是讀（搜尋查詢）的就會越慢。

置於邏輯轉換到機器是怎麼做，這個你得看書哦，都是細節，繁瑣且用處不大。

自舉不是那個意思，不是讓你用if 寫 if， while寫while， 一個單詞（操作/指令）是沒法自舉的，如果一個不可拆分的操作自己能實現自己 那叫自我指涉，是病句。 但是

一套

單詞是可以的。

比如 {come，go} 可以實現 {來，去}， 然後{來，去} 又可以實現 {come，go} 這是自舉。

但是在{come，go}的世界裡，come就是come，不需要come 再來實現come/解釋come， come就是come沒有道理的，它就在那裡，沒有緣由，沒有第一推動， 就要承認一些東西本來就在那裡。

就是你用 一套世界 {A，B，C，D，E} 推出 另一套等價世界 {a，b，c，d，e}，

世界 {a，b，c，d，e} 形成以後，可以把 世界 {A，B，C，D，E}銷燬，世界 {a，b，c，d，e}已經不知道自己的創世者是世界 {A，B，C，D，E}了。然後再用 世界 {a，b，c，d，e} 造出世界{A，B，C，D，E} ，這是自舉。

{if，while。。。。} 在 {if，while。。。} 這個世界裡，if就是if，不需要去實現。如果你想知道if怎麼來的，那你在這個 {if，while。。。} 的世界是沒法知道的， 要跳到 另一個 實現 {if，while。。。} 的世界 比如 {MOV，JMP。。。} 中去。

就比如 {上帝和神} 在的世界，是 {元素，人類，動物。。。}的世界 不可見的， 但是 {元素，人類，動物。。。}的世界有可能自舉 再造一個 {上帝和神} 在的世界， 只要 上帝和神 能幹的操作，你全部實現了就OK了。

ValK2021-03-17 15:25:28

問題非常多，想要一個個解決仍然需要靠自身提高知識儲備。

如果按照普通計算機系的專業課學習順序來的話，瞭解計算機的執行原理，需要學習： 數位電路設計->計算機組成原理。目的是瞭解如何從簡單的邏輯運算，透過人們的專門設計，變成可以進行二進位制運算的機器，機器是怎麼進行資料的存取的。（計組也有課程設計，我院一專是verilog實現一個MIPS指令集CPU，連結放最下面）

瞭解了中央處理器如何根據電訊號去進行運算後，可以簡單瞭解一下編譯器的發展歷史（切勿深究）。人們在只能打孔給機器計算的情況下，實現一個組合語言的編譯器，利用這個組合語言，實現一個目標高階語言最小子集的編譯器，然後利用這個高階語言子集，自舉高階語言編譯器，從而實現功能增加，隨後慢慢發展至今天。當然並不是每個編譯型語言都是透過自舉來實現新版本的，有的語言的編譯器可能是用另外一個語言實現，而解釋型語言基本上都得基於一個編譯型語言去實現。

想了解編譯原理中詞法分析和語法分析，需要初步瞭解離散數學中關於自動機的部分，這部分其實非常理論和抽象化，簡單瞭解即可，詞法分析可以自學，語法分析最好能透過一個大學專業課程來學習，初學手寫語法分析器一般選擇LL（1）文法，如果程式碼能力缺乏，可以參考一些github上那種程式碼量極少的專案，從這些專案中看LL（1）語法分析器的程式碼框架。（或者可以參考一下我的編譯原理實驗，Pascal子集PL-0，LL（1）文法，有中間程式碼生成和虛擬機器，專案連結我扔最下面）

到了中間程式碼生成這一步的時候，可以嘗試自己動動腦筋，結合之前學過的計算機組成原理，思考如何在程式碼中穿插生成函式，能自動生成中間程式碼。如果實在想不出，大學編譯原理課還是得聽，很有用。在這一步你就能理解if，while這種需要利用分支的語句是利用判斷跳轉指令實現的，並不是你想象中的if寫if，while寫while，

自舉要做的並不是自己解釋自己，而是用自己這個語言，重新寫個編譯器

，最終大家都得到中間程式碼這一步，中間程式碼裡你可看不到if和while了，都被翻譯成最基礎的指令/偽指令了。

當然也有一種情況，有很多的解釋型語言，使用基於語法樹的直譯器，這類直譯器不需要生成中間程式碼，直接在語法分析生成的語法樹上跑，其實現中就會出現用if寫if，while寫while的情況。不過目前很多主流解釋型語言都採用位元組碼虛擬機器，因為語法樹直譯器存在各種方面的缺陷和不足。

接著是實現編譯器和直譯器的區別，如果是直譯器，能到中間程式碼生成這一步，那麼你要著手設計一個高階語言虛擬機器，設計一個垃圾收集器，讓這個虛擬機器能夠將生成的程式碼跑起來（一旦深入是有很多東西要學的）。有的直譯器甚至是支援JIT的，執行效率不輸本地二進位制可執行檔案執行，例如v8和LuaJIT。當然JIT也可以看作一種變相的編譯器實現。

編譯器則在生成中間程式碼這邊要重點關注，編譯原理課會簡單介紹一些透過DAG最佳化的方法，不過只是簡單一提而已。（有的大學可能會講的更詳細，我只是結合自身情況，程式碼最佳化是個很熱門的課題）

接著是彙編/llvm程式碼生成。彙編和llvm也是需要自己專門去學的（可惜我院的彙編教授退休了沒人講課），後面需要呼叫一下彙編器/llvm後端和連結器（當然可能到這裡還沒有完全結束，我對這邊已經瞭解不多，需要其他專業人士來補充）。

最後提一嘴，已經不需要再折磨自己用匯編語言寫編譯器了，如果真想試試自舉，可以先用一個高階語言寫個你設計的語言的子集編譯器，然後用這個子集語言去寫其全集語言的編譯器。

NUAA 2020 計算機組成原理課程設計NUAA 2020 編譯原理實驗

除了上面兩個連結，我的專案中還有兩個直譯器實現，nas#和nasal，程式碼量都不是很大，可以進行參考（或者提出最佳化意見 ：） ）

關於陣列和連結串列的問題，推薦學習一手資料結構，瞭解面對什麼樣的問題，得用什麼樣的結構去儲存資料，這樣的結構有什麼優缺點（空間，時間）。接著可以適當看看簡單演算法，演算法導論大機率會提到，有時候為了時間複雜度降低，空間複雜度反而要上升；空間複雜度降低，時間複雜度反而要上升，兩者在多數情況下是無法都達到最優的。

然後關於變長陣列的問題，你會在資料結構這門課中得到答案：很多的變長陣列實現，在儲存量達到上限且還有新資料存入的時候，會採取重新分配更大的空間+複製原來空間的值的方式進行空間擴充套件，類似實現如C++ STL std：：vector。如果你想刨根問底去問這種記憶體分配是如何實現的話，那就得涉及到一點資料結構+演算法+作業系統的東西了。

推箱子的問題，你同樣會在資料結構這門課中得到答案：實現快速的數值插入，連結串列是最在行的，但是利用索引查詢數值位置的時候，反而是連續結構速度更快。每個資料結構都有其專有的應用場景。

從上往下這麼一講，基本上計算機該學的基礎課全提到了……資料結構，演算法導論，數位電路，計算機組成原理，離散數學，編譯原理。

avoidant2021-03-17 21:05:18

有點走都不會走，就想跑的意思。

想的很多，但似乎每樣東西又都含含糊糊。

忘了編譯器的事，多程式設計，這樣你距離寫編譯器還能近點。

吳德承2021-03-20 13:02:23

如何寫編譯器？為什麼都是用成熟的語言去寫編譯器？

這種問題實際上有賴於對計算機行業以及編譯器應用場景的理解。樓主先要理解編譯器是什麼、我們為什麼要去寫編譯器。

編譯器本身也是一個計算機程式，輸入一種高階語言的文字，轉換為機器語言的可執行程式碼。

當一個新的計算機體系結構出現，機器語言指令集變化了，這個時候就要為這個底層機器編寫新的高階語言編譯器。所以同樣是C語言，最早的編譯器是用匯編語言編寫，編譯成古老的PDP11機器的程式碼；而現代的C語言可以編譯成X86這種通用處理器的程式碼，也可以編譯成嵌入式處理器的程式碼。現在對編譯器專業人才有需求的，相當部分是設計生產CPU/GPU處理器的廠家，就是這個原因。

另外高階語言的演進，也需要重新設計編譯器。比如C語言，它的面向物件版本有C++，這個時候新語言的設計師就需要去構造編譯器。樓主如果將來入了計算機科學專業讀博士，悲劇的命運經常是你導師設計了一個很詭異的新程式語言，估計只有你們課題組用。你和同學要為這個恐怖的語言編寫編譯器。

既然編譯器是程式，當然和其他程式一樣，需要一套工具集，完成編輯、除錯、編譯、連結等等的工作。

樓主感到好奇的可能是，這套工具集中也包含了編譯器。而且要符合另一套語言的規範。

書寫編譯器的語言，可以稱之為“元語言”；而編譯器要處理的語言，可以稱之為“物件語言”。英語老師給我們上課，需要漢語這個母語環境，去解釋英語的構造。編譯器的元語言和物件語言就有點像這個關係。

“元語言”和“物件語言”可以一樣的，比如我要某一種新一代CPU處理器寫C語言編譯器，我的工具環境可以使用X86系統上的C語言系統。這種情況，生成的編譯器又稱“交叉”編譯器。因為編譯出來的目的碼你的本地計算機是不能執行的，需要發到使用新處理器的系統上執行。嵌入式應用開發人員非常熟悉這個套路。他們編寫的程式可能實際執行在微波爐裡、執行在智慧手機裡、甚至航天器上，但就不是本地執行交叉編譯器的本地計算機上：）

更誇張一點，就是樓主說的“自舉”。這種情況下，不僅元語言和物件語言一樣，還要求新編寫的編譯器能夠正確處理工具環境編譯器的程式程式碼。這是測試驗證編譯器程式工作正常與否的手段。

最後如果樓主真的希望玩一玩編譯器及相關東西，有兩種途徑，分別對應上面兩種使用場景：

一種是自底向上，模擬計算機處理器廠商。買一塊FPGA開發板，從設計自己的CPU乃至計算機開始。然後在PC上為這個玩具CPU編寫“交叉”編譯器。最後用你自己設計的語言編譯器，去構造一個玩具作業系統。

另一種是自頂向下，模擬苦逼的計算機科學研究人員。設計一個微型語言，先為它編寫直譯器。然後把直譯器轉換為虛擬機器。最後編寫編譯器，把微型語言程式編譯成虛擬機器程式碼。Lisp/Scheme以及函式程式語言這種社群經常玩這個套路，網上搜一搜很多國外高校的課程網頁。別去看我國高校的編譯原理教材。