編譯原理（2）

06-07

編譯原理（2）

來自專欄編譯原理學習筆記

一、什麼叫編譯程序：

編譯程序是系統軟體中發展最早的成員之一，基礎理論發展很成熟。但是新的編程語言發展很快，編譯理論也需要向前發展；
編譯理論和其它課程關係：基礎是自動機和形式語言，素材有離散數學、數據結構，上層是操作系統。
編譯理論的應用：許多想法和技術用於一般軟體設計。
翻譯程序：輸入某種語言的一系列語句，輸出另一種語言的一系列語句。編譯程序是它的子集。
編譯程序：用高級語言寫的源程序作為數據接收，經過翻譯轉換產生面向機器的代碼作為輸出。可能還涉及彙編。

二、編譯過程概述：

1.編譯過程（先大致）：

老師上課過程中，是和英語文章翻譯過程來類比一下：

斷詞（詞性，本身是什麼意思）：要知道斷詞的規則，比如英語中用逗號分開，用空格分開等等，那高級語言裡面比如for,if，我們不能說f，或者o來斷開。那英語的詞斷了之後，查字典，查這個詞對嗎，錯的話字典查不到，對的話，那我們看到這個詞的性質，它是動詞還是名詞還是其它詞性，那放在高級語言裡面，比如我們看到for，查出來是個定義符還是個標誌符，還有它的意思。接下來，繼續查，查完了整篇文章的詞，類比過來就是高級語言裡面所有其它部分if啊 k啊 i啊等等全部查到了。查好之後知道了這個詞什麼性質，這個詞叫什麼名字。進入第二階段。
分析句子：那麼詞都查對了，根據英語語法規則分析句子，分析段，分析文章對不對。高級語言像英語一樣也有語法規則，需要根據他分析句子。分析完這塊，至少保證形式上這篇英語文章是對的，那對應的，我們的程序在形式是正確的了。
理解含義：語法角度沒有問題之後，那接下來就關心這句話什麼意思，進行差不多的理解，草譯一下。
修飾：由於草草翻譯，那我們發現，這個人英語水平怎麼這麼爛，啰里啰嗦，找個高手來修飾一下，但是要忠實於原文。對應程序，我們要和原來程序的邏輯、功能保持一致，反覆的優化。
成文：最後交差。

以上五個通俗過程的類比，對應下面：

下面分開來詳解：

2.詞法分析：

舉個例子，從頭到尾一個個掃描，得到了如下結果：

比如：他看到的是「F""O""R"，它掃過之後，發現這是個for，是個定義符，（而不是NEXT，而不是運算符）。

3.語法分析：

關心三件事情：第一，每一段每個過程入口是什麼；第二，每個過程產生了什麼；第三，中間怎麼折騰的。

詞法分析的結果是語法分析的入口，詞法分析得到的單詞串轉化為語法單位。

語法單位（語法範疇）的引入是為了層次化表達程序和單詞的關係。單詞構成句子，句子構成程序段，程序段構成程序。我們不能說程序由單詞構成，這樣顯得太粗糙，無法學習，引入語法單位使得程序的表述更有層次，我們知道單詞怎麼寫，句子怎麼寫，程序段怎麼寫，那麼最後也就知道了程序怎麼寫。後面慢慢體會。

最後確定了整個輸入串是否語法正確，也就是形式上是不是正確。比如人上大學。大學上人。這兩個句子從傳統意義上講，後面那個應該是不對的，但從語法角度看，主謂賓都齊全，形式上首先是正確的。

示例如下：

語法分析首先看到了詞法分析的結果（只是形式上用這樣的塊表示一下方便理解）：

他不會去問f是什麼，o是什麼，r是什麼了，因為詞法分析結果已經出來了，不用再「查字典了」。而是根據語言的規則，進行語法分析，下面一步步來看：

下面的規則，它知道什麼地方是表達式：

就把輸入串中符合這條規則的看成表達式，成這樣了：

根據：

又把符合賦值句條件的串，得到了：

然後又有這樣的規則：

於是乎，中間兩個賦值句就合併為了語句塊：

對於循環，有這樣的規則：

那麼進一步分析，把To兩側的表達式就分析的更清楚：

根據規則：

又明確了K：

最後，得到一個高度形式化的循環語句。結果和FOR規定的語法規則是一樣的，符合定義：

需要重點說明的是，我們上面的舉例只是為了便於理解，實際的語法分析過程是掃描，也就是碰到什麼就立刻分析，而不是說找出所有的表達式，找出所有的語句塊等等。我們上面這樣講解只是為了便於理解和分析。

上面兩個部分是死的，標誌符怎麼定義（字元數字串），字母怎麼定義，數字串又是什麼，哪個詞是什麼意思。比如上面他看到F是個字母，O是個字母，R是個字母，然後掃到空格了，然後查了一下表，發現哦，這原來是個FOR標誌符。那賦值語句呢（在這個課舉的這個語言的例子），首先看到個標誌符，然後是等號，然後往後掃是個表達式，最後面一個間隔。查一下表，哦，原來這是個賦值語句。其他運算符，界符，數字都是同理的，這都是有規矩可循的，是完全形式化的，長什麼樣子就是什麼，不符合規則，那就不是，就錯了。

下面就要開始理解含義了，到了語義分析，中間代碼生成環節。

4.中間代碼生成：

識別各種語法範疇，就是說看出這是個子句，是個子句，是個程序段等、然後初步翻譯。

中間代碼是用另一種語言來表述。中間代碼中也有一些規矩可以形式化的。比如看到for之後知道這是個循環語句，對循環語句做翻譯時候，有一些規則，利用這些規則指導翻譯的進行。比如有個for出來，就一定會有個next，他看到for之後，會往下去找這個next，找到這個next之後，然後就知道了這中間一大段就是循環語句：

注意同一個控制變數，for到next是一個循環塊，如果還有i，還有j就有情況了。

步長預設

識別並理解了這個循環塊之後，然後生成四元式（就是個草稿），這些概念後面會著重講解，此處只是引論知道即可：

然後為了方便起見，一一對應，好看一點並且便於講解。我們把四元式重寫成另一種形式的中間代碼：

源程序->四元式

到這裡就完成了草譯了，接下來要修飾一下，進行一番優化。