好書一起讀(143)：編譯原理

編譯器，一言以蔽之，源代碼進，目標代碼出。

細點說，分兩個階段，第一階段源代碼進，語法樹出，第二階段語法樹進，目標代碼出。第一階段稱為分析，處理者統稱前端；第二階段稱為綜合，處理者統稱後端。

具體階段劃分，每本書說得都不一樣。大致是前端包括詞法分析、語法分析、語義分析，後端包括中間代碼生成和目標代碼生成，還有個貫穿各個階段的優化。

前端是源代碼進語法樹出，以語法分析為核心。詞法分析與語法分析的關係可以有兩種：一是先做詞法分析，源代碼進詞串出，再做語法分析，詞串進語法樹出；二是詞法分析作為語法分析的子過程，直接把源代碼給到語法分析，詞法分析在語法分析內部被調用，如墨提斯在宙斯體內被調用一般。

詞法分析的工具是正則表達式，有限狀態自動機，匹配源代碼串中的每個部分，把源代碼串切成一小段一小段，每小段視作一個單元，是個二元組，由單詞和語義值組成，這小單元們構成的詞串就是詞法分析的成果。

語法分析使用上下文無關文法的產生式，把拿到的詞串做成語法樹。具體的藉助產生式解析語法樹的演算法有多種，如自頂向下、自底向上，這些演算法會產生語法解析樹，但這樹多餘信息太多，進一步做成抽象語法樹，以方便後續動作。

語法樹有了，但還不知道它是否合語義，就把它交給語義分析，進行例如類型檢查、變數聲明檢查等。檢查方法是藉助符號表來遍歷該樹，如果發現了錯誤，準確詳細地報告錯誤信息，以幫助程序員改正。

通過了語義分析，程序在形式上是確保沒錯了，那就進行中間代碼生成，以便下一步方便地生成目標代碼，之所以要多這一步，是因為假如有源代碼語言甲種，目標代碼語言乙種，如果直接生成目標代碼，則需要寫演算法數量為甲乘以乙，而先轉為統一的中間代碼，則需要寫演算法數量為甲加乙，節省很多工作。生成中間代碼，還是遍歷語法樹，為語法樹的各個節點指定產生規則，以使在遍歷到各個節點時生成正確的代碼。

中間代碼有了，最後一步進行目標代碼生成，目標代碼語言的指令和寄存器都有限，需要小心地編寫演算法使語義不被改變。

語義不被改變是編譯器的紅線，語義如果可能被改變，別的方面再好這編譯器也毫無意義。代碼優化時也要注意這一點。

寫在後面：

編譯原理，之前沒重視，這陣子才學。

用的資料是網易雲課堂上中國科學技術大學華保健老師的視頻教程、優酷上西安交通大學馮博琴老師的視頻、編譯原理龍書、書籍《編譯原理及實踐》及《自製編譯器》。個人感覺華保健視頻配合龍書做主力資料就很好，其他的可以做參考補充。

編譯過程，其本質就是文本到樹再到文本，有結構化思維的人會很容易想到，這其實就是閱讀和寫作的過程，從書里的文本建立你腦海中的知識結構，再把這知識結構用你自己的語言表達出來。

你腦海中的知識結構，用金字塔原理的話講就是金字塔。而從辯論的角度看，是以總結論為根、各層中間結論為非葉子節點、各個前提假設為葉子節點構成的一棵數據結構意義上的樹。有這種把攝取到的內容組織整理成樹的習慣的人，他看到的書和文章就不是表面的線性結構，而是立體的有層次和結構的，這樣就可能鞏固理解、準確地找到質疑和反駁的點。

沒有前端就沒有後端，沒有分析就沒有綜合，沒有閱讀就沒有寫作，沒有腦海中的一棵樹，輸出文字就只能靠直覺或抄寫，那顯然無論是寫出的文字，還是寫作鞏固閱讀的目的——記憶效果，都不會好。

所以拆解源文本就很關鍵。先理清文章中各個詞的意思，這算是詞法分析；再梳理整篇文章的脈絡，這算是語法分析；再檢查文章的議論是否邏輯正確、敘述是否前後連貫、抒情是否價值觀一致，這算是語義分析。這樣檢查完了，你的腦海中就有清晰的中間代碼了。

所謂外行看熱鬧，就是只能看到流水線的文字和其中一兩個出彩漂亮的點，卻看不到整體的謀篇布局。而內行看門道，則是眼光銳利如庖丁解牛的尖刀，視線所到之處如X光線，能看清骨骼和肌腱的結構。

當你有了中間代碼，想寫作的時候就心中有數，核心論點是什麼，論據是什麼，文章就有個層次。這樣當你寫的文章被別人閱讀，成為別人要編譯的「源代碼」時，因為你文章結構良好，對他的「編譯器」友好，他理解起來就容易，你輸出信息的目的就達到了。而當你複習的時候，你自己讀自己的文章，當然理解起來是最容易的，一下子就能進入你腦海喚醒沉睡的樹，如是幾番，就再也忘不掉了。

從高級語言到機器語言，從書本語言到筆記語言，編譯器的好壞，決定了翻譯的質量。語義不變是紅線，在此前提下要盡量簡潔清楚不說廢話，讓人好懂。互聯網時代消磨人的閱讀長篇文章的能力，寫文章的人也就面臨挑戰，怎樣在信息豐富和形式簡明之間找到和諧的點，是每個寫作的人都該揣摩實踐的重要問題。