自己動手構造編譯系統：編譯、彙編與連結2.1.2 文法分析

<b>2.1.2  文法分析</b>

　　

       詞法分析器的輸入是文本字元串，文法分析器的輸入則是詞法分析器識别的詞法記号序列。文法分析器的輸出不再是一串線性符号序列，而是一種樹形的資料結構，通常稱之為抽象文法樹。見圖2-4。

　　繼續前面指派語句的例子，我們可以先看看它可能對應的抽象文法樹，如圖2-5所示。

圖2-5  抽象文法樹示例

　　從圖2-5中可以看出，所有的詞法記号都出現在樹的葉子節點上，我們稱這樣的葉子節點為終結符。而所有的非葉子節點，都是對一串詞法記号的抽象概括，我們稱之為非終結符，可以将非終結符看作一個單獨的文法子產品（抽象文法子樹）。其實，整個源程式是一棵完整的抽象文法樹，它由一系列文法子產品按照樹結構組織起來。文法分析器就是要獲得源程式的抽象文法樹表示，這樣才能讓編譯器具體識别每個文法子產品的含義，分析出程式的整體含義。

　　在介紹文法分析器的工作之前，需要先獲得進階語言文法的形式化表示，即文法。文法定義了源程式代碼的書寫規則，同時也是文法分析器構造抽象文法樹的規則。如果要定義指派語句的文法，一般可以表達成如下産生式的形式：

　　&lt;指派語句&gt; =&gt; 辨別符 等号 &lt;表達式&gt; 分号

　　被“&lt; &gt;”括起來的内容表示非終結符，終結符直接書寫即可，上式可以讀作“指派語句推導出辨別符、等号、表達式和分号”。顯然，表達式也有相關的文法定義。根據定義好的進階語言特性，可以設計出相應的進階語言的文法，使用文法可以準确地表達進階語言的文法規則。

　　有了進階語言的文法表示，就可以構造文法分析器來生成抽象文法樹。在編譯原理教材中，描述了很多的文法分析算法，有自頂向下的ll（1）分析，也有自底向上的算符優先分析、lr分析等。其中最常使用的是ll（1）和lr分析。相比而言，lr分析器能力更強，但是分析器設計比較複雜，不适合手工構造。我們設計的進階語言文法，隻要稍加限制便能使ll（1）分析器正常工作，是以本書采用ll（1）分析器來完成文法分析的工作。遞歸下降子程式作為ll（1）算法的一種便捷的實作方式，非常适合手工實作文法分析器。

　　遞歸下降子程式的基本原則是：将産生式左側的非終結符轉化為函數定義，将産生式右側的非終結符轉化為函數調用，将終結符轉化為詞法記号比對。例如前面提到的指派語句對應的子程式的僞代碼大緻是這樣的。 

void 指派語句()

{

     match(辨別符);

     match(等号);

     表達式();

     match(分号);

}

　　每次對子程式的調用，就是按照前序的方式對該抽象文法子樹的一次構造。例如在構造指派語句子樹時，會先構造“指派語句”根節點，然後依次比對辨別符、等号子節點。當遇到下一個非終結符時，會進入對應的“表達式”子程式内繼續按照前序方式構造子樹的子樹。最後比對目前子程式的最後一個子節點，完成“指派語句”子樹的構造。整個文法分析就是按照這樣的方式構造“程式”樹的一個過程，一旦在終結符比對過程中出現讀入的詞法記号與預期的詞法記号不吻合的情況，便會産生文法錯誤。

　　在實際文法分析器實作中，并不一定要顯式地構造出抽象文法樹。遞歸下降子程式實作的文法分析器，使得抽象文法樹的文法子產品都蘊含在每次子程式的執行中，即每次子程式的正确執行都表示識别了對應的文法子產品。是以，可以在文法分析子程式中直接進行後續的工作，如語義分析及代碼生成。