編譯原理基礎知識

⑴ 編譯原理follow集與first集的計算

下面我將介紹一下我關於LL（1）文法部分的計算文法非終結符First集以及Follow集兩個知識點的理解。

首先是First集的計算部分，計算First集首先看我們原文法的左邊，原文法左邊不重復的都要進行First集的計算，計算時具體有以下三種情況：

（1）先看產生式後面的第一個符號，如果是終結符，那就可以直接把它寫到這個產生式的First集中，例如：產生式為M->nDc,那在First集中我們就可以直接寫上First (M)={ n }；

（2）如果產生式後面的第一個符號是非終結符，就看這個非終結符的產生式，看的時候同樣利用前面的兩種看法；但是當產生式為ε時，則需要把ε帶入到待求First集的元素的產生式中再判斷。例如：A->Bc； B->aM；B->ε，求First(A)時，我們看到A的第一個產生式中的第一個符號是B，B是一個非終結符，所以我們就要接著看B的產生式，B的第一個產生式的第一個符號為a，a是一個終結符，直接把a寫入First(A)，B的第二個產生式為ε，把ε帶入A->Bc中，A->c(注意：如果將B->ε帶入表達式後A的產生式為A->ε，ε不可以忽略)，c是終結符，所以把c也寫入First(A)，最後First (A)={ a，c }。

（3）當產生式右邊全為非終結符，且兩個非終結符又都可以推出ε時，我們需要把這個產生式的所有情況都列出來，再分析。例如：A->BC;B->b|ε;C->c|ε。我們把A的所有產生式利用上述兩種方法列出來就是A->bc,A->b;A->c,A->ε;最後First (A)={b,c, ε}。

接下來介紹一下Follow集的部分，先簡單介紹一下計算Follow集的大致規則。比如我們要求Follow(X)，文法中多個產生式中含有X，則需要考慮多種情況，以下是具體計算時的三種情況：

（1）文法開始符：所有文法開始符的Follow集中都有一個#。

（2）S->αB的形式：求Follow(B)，因為B的後面為空，把Follow(S)寫入B的Follow集中。

（3）S->αBβ的形式：求Follow(B)，B後部不為空。

①當β是終結符時，直接把β寫入Follow(B)。

②當β是非終結符時，將First (β)（如果First(B)中有ε，就把ε刪掉）寫入Follow(B)中。（需要注意的是：如果β->ε，那麼原產生式就變成了S->αB,也就是第二種情況，這兩種情況都要算在Follow(B)中）。

⑵ 學習編譯原理哪本書好

我們學校用的是《編譯原理》與《編譯原理與實踐》這兩本書，這兩本書都是國外的教材。我覺得《編譯原理與實踐》這本書不錯，自學應該能看懂，而且代碼比較多，書最後還有整個小型編譯器的源代碼。
編譯不好學，你就慢慢學吧。

下面的資料請作參考：

當代編譯技術三大聖經級別的教材

1.龍書(Dragon book)
書名是Compilers: Principles,Techniques,and Tools
作者是：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman

內容簡介
《編譯原理》作者Alfred V．Aho、Ravi Sethi和Jeffrey D．Ullman是世界著名的計算機 科學家，他們在計算機科學理論、資料庫等很多領域都做出了傑出貢獻。《編譯原理》 是編譯領域無可替代的經典著作，被廣大計算機專業人士譽為「龍書」。《編譯原理》一 直被世界各地的著名高等院校和科研機構(如貝爾實驗室、哥倫比亞大學、普 林斯頓大學和斯坦福大學等)廣泛用作本科生和研究生編譯原理與技術課程的 教材，《編譯原理》對我國計算機教育界也具有重大影響。 書中深入討論了編譯器設計的重要主題，包括詞法分析、語法分析、語法制 導分析、類型檢查、運行環境、中間代碼生成、代碼生成、代碼優化等，並在 最後兩章中討論了實現編譯器的一些編程問題和幾個編譯器實例，而且每章都 提供了大量的練習和參考文獻。

與上一版相比，《編譯原理》第二版進行了全面的修訂，涵蓋了編譯器開發方面的最新進展。每章中都提供了大量的系統及參考文獻。《編譯原理》是編譯原理課程方面的經典教材，內容豐富，適合作為高等院校計算機及相關專業本科生及研究生的編譯原理課程的教材，也是廣大技術人員的極佳參考讀物。

作者簡介
Alfred V．Aho，美國歌倫比亞大學教授，美國國家工程院院士，ACM和IEEE會士，曾獲得IEEE的馮·諾伊曼獎。著有多部演算法、數據結構、編譯器、資料庫系統及計算機科學基礎方面的著作。
Monica S．Lam，斯坦福大學計算機科學系教授，曾任Tensilica的首席科學家，也是Moka5的首任CEO。曾經主持SUIF項目，該項目產生了最流行的研究用編譯器之一。
Ravi Sethi，Avaya實驗室總裁，曾任貝爾實驗室高級副總裁TLucent Technologies通信軟體的CTO。他曾在賓夕法尼亞州立大學、亞利桑那州立大學和普林斯頓大學任教，是ACM會士。
Jeffrey D．Ullman斯坦福大學計算機科學系教授和Gradiance CEO，他的研究興趣包括資料庫理論、資料庫集成、數據挖掘和利用信息基礎設施教學等。他是美國國家工程院院士、IEEE會士，獲得過ACM的KarIstrom傑出教育家獎和Knuth獎。
第一版中文版
第二版中文版

2.鯨書(Whale book)
書名是：Advanced Compiler Design and Implementation
作者是：Steven S.Muchnick

內容簡介
本書迎接現代語言和體系結構的挑戰，幫助讀者作好准備，去應對將來要遇到的編譯器設計的問題。
本書涵蓋現代微處理器編譯器的設計和實現方面的所有高級主題。本書從編譯設計基礎領域中的高級問題開始，廣泛而深入地闡述各種重要的代碼優化技術，分析各種優化之間的相對重要關系，以及實現這些優化的最有效方法。
本書特點
●為理解高級編譯器設計的主要問題奠定了基礎
●深入闡述優化問題
●用Sun的SPARC、IBM的POWER和PowerPC、DEC的Alpha以及Intel的Pentium和相關商業編譯 器作為案例，說明編譯器結構、中間代碼設計和各種優化方法
●給出大量定義清晰的關於代碼生成、優化和其他問題的演算法
●介紹由作者設計的以清晰、簡潔的方式描述演算法的語言ICAN (非形式編譯演算法表示)。

本書是經典的編譯器著作，與「龍書」齊名，稱為鯨書。書中針對現代語言和體系結構全面介紹了編譯器設計與實現的高級論題，從編譯器的基礎領域中的高級問題開始，然後深入討論了各種重要的代碼優化。本書專為編譯器專業人士和計算機專業本科生，研究生編寫，在設計和實現高度優化的編譯器以及確定優化的重要性和實現優化的最有效的方法等方面，為讀者提供了非常有價值的指導。

作者簡介
Steven S.Muchnick，曾是計算機科學教授，後作為惠普的PA-RISC和SUN的SPARC兩種計算機體系結構的核心開發成員，將自己的知識和經驗應用於編譯器設計，並擔任這些系統的高級編譯器設計與實現小組的領導人。他在研究和開發方面的雙重經驗，對於指導讀者作出編譯器設計決策極具價值。

3.虎書(Tiger book)
書名是：Modern Compiler Implementation in C /Java /ML,Second Edition
作者是：Andrew W.Appel,with Jens Palsberg

內容簡介
《現代編譯原理——C語言描述(英文版)/圖靈原版計算機科學系列》全面講述了現代編譯器的各個組成部分，包括：詞法分析、語法分析、抽象語法、語義檢查、中間代碼表示、指令選擇、數據流分析、寄存器分配以及運行時系統等。與大多數編譯原理的教材不同，《現代編譯原理——C語言描述(英文版)/圖靈原版計算機科學系列》採用了函數語言和面向對象語言來描述代碼生成和寄存器分配，對於編譯器中各個模塊之間的介面都給出了實際的 C 語言頭文件。 全書分成兩部分，第一部分是編譯的基礎知識，適用於第一門編譯原理課程（一個學期）；第二部分是高級主題，包括面向對象語言和函數語言、垃圾收集、循環優化、 SSA（靜態單賦值）形式、循環調度、存儲結構優化等。
本書是一本著名的編譯原理課程的教材。國際上眾多名校均採用本書作為編譯原理課程的教材，包括美國麻省理工學院、加州大學伯克利分校、普林斯頓大學和英國劍橋大學等。本書在國外享有「虎書」的稱號，與有「龍書」之稱的《編譯原理》（Alfred Aho 等編著）齊名。與編譯原理方面的其他名著相比，本書出版時間晚，內容新。 書中專門為學生提供了一個用 C 語言編寫的實習項目，包括前端和後端設計，學生可以在一學期內創建一個功能完整的編譯器。

作者簡介
Andrew W.Appel，美國普林斯頓大學計算機科學系教授，第26屆ACM SIGPLAN-SIGACT程序設計原理年會大會執行主席，1998-1999年在貝爾實驗室做研究工作。主要研究方向是計算機安全、編譯器設計、程序設計語言等。

⑶ 《編譯原理》、《演算法導論》看懂需要什麼基礎知識

編譯原理的話，有一門語言基礎就行，主要涉及到文法相關的知識。
演算法導論需要的是數據結構和數學知識。