【編譯原理】第一章 引論

一，語言處理器

        1）一個內建的軟體開發環境，其中包括很多種類的語言處理器，比如編譯器、解釋器、彙編器、連接配接器、加載器、調試器以及程式概要提取工具。

        2）編譯器：把源程式的每一條語句都編譯成機器語言,并儲存成二進制檔案,這樣運作時計算機可以直接以機器語言來運作此程式,速度很快;  包括編譯器，反編譯器，交叉編譯器

        3）解釋器：能夠執行用其他計算機語言編寫的程式的系統軟體，它是一種翻譯程式。它的執行方式是一邊翻譯一邊執行，是以其執行效率一般偏低，但是解釋器的實作較為簡單，而且編寫源程式的進階語言可以使用更加靈活和富于表現力的文法

              編譯器産生的機器語言目标程式，比解釋器快很多。解釋器的錯誤診斷通常比編譯器更好。

        4）彙編器：是将彙編語言翻譯為機器語言的程式。一般而言，彙編生成的是目标代碼，需要經連結器（Linker）生成可執行代碼才可以執行

        5）連接配接器：連結函數和全局變量，是以，我們可以使用編譯器生成的中間目标檔案（O檔案或是OBJ文 件）來連結我們的應用程式。連結器并不管函數所在的源檔案，隻管函數的中間目标檔案（Object File），在大多數時候，由于源檔案太多，編譯生成的中間目标檔案太多，而在連結時需要明顯地指出中間目标檔案名，這對于編譯很不友善，是以，我們要給 中間目标檔案打個包，在Windows下這種包叫“庫檔案”（Library File)，也就是 .lib 檔案，在UNIX下，是Archive File，也就是 .a 檔案

        6）加載器：把所有可執行目标檔案放到記憶體中執行

        7）調試器：工作原理是基于中央處理器的異常機制，并由作業系統的異常分發\事件分發的子系統（或子產品）負責将其封裝處理後，以比較友好的方式與調試器進行實時互動

二，一個編譯器的結構

        1）編譯器能把源程式映射為在語義上等價的目标程式。此映射過程由兩部分組成：分析部分和綜合部分

        2）分析部分（編譯器前端）：把源程式分解成多個組成要素，并在這些要素之上加上文法結構，然後它使用這個結構來建立該源程式的一個中間表示。如果檢查出源程式文法或語義有誤，則提供有用資訊告知使用者。分析部分還手機有關源程式的資訊，并把資訊放到一個稱為符号表的資料結構中。

        3）綜合部分（編譯器後端）：根據中間部分和符号表中的資訊來構造使用者期待的目标程式。

        4）詞法分析：詞法分析階段是編譯過程的第一個階段，是編譯的基礎。這個階段的任務是從左到右一個字元一個字元地讀入源程式，即對構成源程式的字元流進行掃描然後根據構詞規則識别單詞(也稱單詞符号或符号)。詞法分析程式實作這個任務。詞法分析程式可以使用Lex等工具自動生成。

       5）文法分析：文法分析是編譯過程的一個邏輯階段。文法分析的任務是在詞法分析的基礎上将單詞序列組合成各類文法短語，如“程式”，“語句”，“表達式”等等.文法分析程式判斷源程式在結構上是否正确。源程式的結構由上下文無關文法描述。

       6）語義分析：語義分析是編譯過程的一個邏輯階段. 語義分析的任務是對結構上正确的源程式進行上下文有關性質的審查。例如重要的是進行類型審查，數組下标必須是整數，

            例如一個C程式片斷:

　　           int arr[2],b;

　　           b = arr * 10;

　　     源程式的結構是正确的.

　　     語義分析将審查類型并報告錯誤:不能在表達式中使用一個數組變量,指派語句的右端和左端的類型不比對。

      7）中間代碼生成：在進行了文法分析和語義分析階段的工作之後，有的編譯程式将源程式變成一種内部表示形式，這種内部表示形式叫做中間語言或中間表示或中間代碼。所謂“中間代碼”是一種結構簡單、含義明确的記号系統，這種記号系統複雜性介于源程式語言和機器語言之間，容易将它翻譯成目标代碼。另外，還可以在中間代碼一級進行與機器無關的優化。産生中間代碼的過程叫中間代碼生成。

     8）代碼優化：程式代碼進行等價（指不改變程式的運作結果）變換。程式代碼可以是中間代碼（如四元式代碼），也可以是目标代碼。等價的含義是使得變換後的代碼運作結果與變換前代碼運作結果相同。優化的含義是最終生成的目标代碼短（運作時間更短、占用空間更小），時空效率優化。原則上，優化可以再編譯的各個階段進行，但最主要的一類是對中間代碼進行優化，這類優化不依賴于具體的計算機。

     9）代碼生成：代碼生成器，以源程式的中間代碼表示作為輸入，并把它映射到目智語言。如果目智語言為機器語言，則必須為程式使用的每個變量指明寄存器或記憶體位置，然後中間指令翻譯成能完成相同任務的機器指令序列。代碼生成的至關重要的方面是合理配置設定寄存器

     10）符号表管理：

         在編譯過程中,編譯程式用來記錄源程式中各種名字的特性資訊, 是以也稱為名字特性表。

          名        字:   程式名、過程名、函數名、使用者定義類型名、變量名、常量名、枚舉值名、标号名等。

          特性資訊:  上述名字的種類、類型、維數、參數個數、數值及目标位址（存儲單元位址）等。                 

          填表：當分析到程式中的說明或定義語句時，應将說明或定義的名字，以及與之有關的資訊填入符号表中。

                     例：Procedure  P( )

           查表：(1)  填表前查表，檢查在程式的同一作用域内名字是否重複定義；

                      (2)  檢查名字的種類是否與說明一緻；

                      (3)  對于強類型語言，要檢查表達式中各變量的類型是否一緻；

                      (4)  生成目标指令時，要取得所需要的位址。

三，編譯技術的應用

        1）編譯時間也是運作開銷的一部分，一個常用的技術就是隻編譯和優化那些經常運作的程式片段。

        2）針對計算機體系結構的優化：并行（指令并行，多個運算并行，在處理器層次：同一應用的不同線程并行）

                                                            記憶體層次結構（記憶體由幾層不同速度和大小的存儲器組成，離處理器最近的層速度最快但是容量小）

        3）新計算機體系結構的設計

              RISC(Reduced Instruction-Set Computer）精簡指令系統

              CISC(Complex Instruction-Set  Computer）複雜指令系統：使彙程式設計式更容易

              ARM（Advanced RISC Machines）是微處理器行業的一家知名企業，設計了大量高性能、廉價、耗能低的RISC處理器、相關技術及軟體。技術具有性能高、成本低和能耗省的特點。适用于多種領域，比如嵌入控制、消費/教育類多媒體、DSP和移動式應用等

              X86 Intel首先開發制造的一種微處理器體系結構的泛稱

四，程式設計語言基礎

        1）環境：名字和記憶體位置（變量）的映射

             狀态：記憶體位置到它們的值得映射   C中成把左值映射為右值

        2）辨別符：一個字元串，指向一個實體（資料對象、過程、類、類型）。所有辨別符都是名字，但并不是所有名字都是辨別符比如  x.y 表示x結構中y字段

              變量：指向存儲中的某個特定的位置

        3）聲明：int a       定義：a=2;

        4）動态作用域：一個作用域依賴于一個或多個隻有在程式執行時刻才能知道的因素，他就是動态的

        5）參數傳遞機制：1>值調用          傳遞指針或數組會改變原來 值

                                       2>引用調用      實在參數的位址  作為形參。被調用的代碼中沿着指針找到調用者指明的記憶體位置，改變形參就像改變實在參數

                                       3>名調用         棄用