編譯原理及實踐教程(第3版)（簡體書）

前言

編譯程序在計算機科學與技術的發展歷史中發揮著巨大作用，是計算機系統的核心支撐軟件。編譯原理蘊含著計算機學科中解決問題的思路、形式化問題和解決問題的方法，對應用軟件和系統軟件的設計和開發有一定的啟發和指導作用。構造編譯程序所涉及的方法和技術在軟件工程、語言轉換等許多領域中有廣泛的應用。
本書主要講述設計和構造編譯程序的一般原理、基本方法和主要實現技術，貫穿高級語言、系統環境、體系結構和目標代碼，體現了從軟件到硬件的整機概念。以高級語言程序編譯的6個主要階段——詞法分析、語法分析、語義分析、中間代碼生成、代碼優化和目標代碼生成為線索，闡述了各階段的主要功能、原理、設計技術和實現方法。
為適應新工科建設的需要，本書的修訂基於OBE的理念，將編譯的基本理論與具體實現技術有機地結合起來，既注重理論的完整性，又將理論融於具體實例中。書中的實例具有連貫性，力求讓讀者建立一個完整的編譯系統的模型，加深對程序設計語言的理解，掌握常用的編譯技術和方法，構建一個具有一定規模的完整的編譯程序，為今後從事應用軟件和系統軟件的開發打下一定的理論和實踐基礎。
本書第3版延續了前兩個版本的風格和主體內容，與前兩個版本銜接得比較好； 同時對一些章節進行了適當的充實、刪減和重新組織，力求在各主要知識點之間達到較為合理的均衡，使讀者對編譯程序的構造方法和實現技術能從整體上全面地掌握。第3版修改的內容主要有：
(1) 由於C語言的廣泛使用，本書選用的源語言改為C語言的子集。
(2) 在第1章中增加了對高級語言的認識。在後面的章節中逐步對源語言進行分析，以便讀者在瞭解編譯方法的基礎上，從高級語言的使用者過渡到高級語言的實現者和設計者。
(3) 增加了語義分析的內容及方法，使編譯程序的結構更清晰。
(4) 細化了目標代碼生成。目標代碼選用Intel 80x86彙編代碼，降低學習的難度； 生成的彙編代碼能直接通過常見彙編器(masm)彙編成可執行文件，直觀看到運行結果，加深對整個編譯過程的理解。
(5) 函數是C語言的精髓，本書增加了函數的聲明、定義和調用的編譯過程，並以實例展示了C語言函數的詳細執行過程及內存的變化，使讀者對程序的運行環境有更透徹的認識，加深對計算機系統的理解。
本書主要面向以工程實踐、應用為主的本科院校，建議理論學時為32~40學時，實驗學時為16~24學時，根據需要可安排專門的課程設計。本書中加*的章節為較難的可選內容，教師可根據具體情況選擇。本書也可作為工程技術人員的參考書。
本書參考和引用了國內外大量優秀編譯教材和著作中的相關內容，也參考了網絡上的相關內容，在此謹向原書作(譯)者深表敬意和感謝； 感謝中國科學技術大學物理學院張智浩同學，他根據本書內容完整地實現了一個編譯程序，驗證了本書的所有算法和思想； 同時感謝劉恒洋老師在本書配套的教學輔助系統的可視化方面所做的工作； 感謝重慶理工大學研究生陽安志、劉野和劉廣峰等對本書提出的寶貴意見和建議。
本書獲得了重慶理工大學教材出版基金的資助。使用本書第1版、第2版的院校的教師和學生也為本書的改版提出了寶貴意見和建議，在此也表示衷心的感謝。
由於作者水平有限，書中難免存在疏漏之處，懇請廣大讀者批評指正。
本書的配套課件和源代碼等資源可以從清華大學出版社網站下載，如果遇到資源下載與使用的問題，請聯繫本書的編輯，郵箱為。

編者
2018年12月

第3章語法分析

語法分析就是根據高級語言的語法規則對程序的語法結構進行分析，是編譯過程的核心。它的任務是判斷讀入的單詞符號串是否符合語言的語法規則，為語義分析和代碼生成做準備。執行語法分析的程序稱為語法分析程序，也稱為語法分析器。
為了能夠更精確地描述高級語言程序的語法結構，需要對高級語言的語法規則進行形式化描述，這種描述稱為文法，適合描述高級語言語法規則的文法是上下文無關文法。因此本章首先介紹文法的相關概念。
語法分析的方法很多，不同的語法分析方法適用于不同的文法，有不同的使用場合和限制條件。語法分析不僅可以手工構造，也可以自動生成，本章最後介紹自動生成器YACC的基本原理和使用方法。

3.1語法分析概述
語法分析在編譯過程中處於核心地位，如圖3.1所示。其任務是在詞法分析識別出正確的單詞符號串的基礎上，根據語言定義的語法規則，分析並識別出各種語法成分，同時進行語法檢查和錯誤處理。根據第1章的介紹，語法分析程序的輸入是token串，輸出是語法樹。實際上，有時並不需要顯式地構造語法樹，因為很多時候，語法分析可能會和後續的翻譯交錯進行。

圖3.1語法分析器在編譯程序中的地位

每一種程序設計語言都有描述其語法結構的規則，如C語言程序由一個或多個函數構成，至少包含一個main()函數，每個函數定義為一個複合語句，每個複合語句定義為由一對花括號{和}括起來的多個順序執行的語句，語句有多種類型，多數語句由表達式組成，表達式由表達式、標識符、常量和運算符等構成。如果僅僅用文字這樣表述，不便於計算機精確處理和判斷。因此，需要對程序設計語言的語法構成規則進行形式化描述。程序設計語言的語法規則一般用上下文無關文法來描述。
上下文無關文法用遞歸的方式描述語法規則。語法分析的過程就是按文法規則對讀入的token串(又稱為輸入符號串)進行分析的過程。token串中的每個單詞符號對應于文法中的一個符號。
根據文法可以手工或自動生成一個有效的語法分析程序，用來判斷輸入的符號串在語法上是否正確。判斷的依據就是對給定的輸入符號串能否根據文法規則建立起一棵語法樹。
按照語法樹的建立方法，可以粗略地把語法分析方法分成兩類： 自上而下分析法和自下而上分析法。
自上而下分析法是在自左至右掃描輸入符號串的過程中，從樹根開始逐步向下建立語法樹。使用自上而下的語法分析的困難在於表示源語言語法結構的文法需要滿足特定的要求，但由於多數程序設計語言的控制流結構具有不同的關鍵字，如if、while、for，因此這種方法的優勢在於一旦檢測出關鍵字，就知道哪個文法規則是唯一的選擇，實現起來簡單、直觀，便於手工構造或自動生成語法分析器，它仍是目前常用的方法之一。常用的自上而下的分析方法有遞歸下降分析和預測分析兩種方法，我們將在3.3節詳細介紹。
自下而上分析法是在自左至右掃描輸入符號串的過程中，沿著從樹葉向樹根的方向逐步建立語法樹，直到樹根結點。自下而上的語法分析方法對文法的限制條件少，對大多數常見的高級語言的語法分析都能使用。常用的自下而上的語法分析方法有算符優先分析和LR分析兩種，多數商業化的編譯器和語法分析的自動生成器也都採用自下而上的語法分析方法。算符優先分析方法是多數編譯器中用來分析算術表達式的方法； 對於幾乎所有的程序設計語言，只要能夠構造出它的上下文無關文法，就能夠構造出識別它的LR語法分析器，語法分析的自動生成器YACC採用的是LR分析方法，將在3.4節詳細介紹自下而上的語法分析方法，並在3.5節介紹語法分析自動生成器YACC的原理和使用。

3.2上下文無關文法
對於高級程序設計語言而言，程序的語法結構是基於語法規則的，因此語法規則的定義和描述非常重要。程序設計語言的語法規則的形式化描述稱為文法。本節主要介紹文法及其產生語言的方法——推導，並用語法樹的方式描述推導過程。

3.2.1文法的定義
文法(Grammar)是描述語言的語法結構的形式規則(即語法規則)，這些規則必須準確而且可理解。文法是從產生語言中的句子的觀點來描述一個語言，也就是說語言中的每個句子都可以用嚴格定義的規則來產生。
下面以自然語言為例，用語法規則來分析句子，從而得出文法的形式化定義。
例3.1有如下規則：
(1) <句子>→<主語><謂語>
(2) <主語>→<代詞>|<名詞>
(3) <代詞>→我
(4) <名詞>→大學生
(5) <謂語>→<動詞><直接賓語>
(6) <動詞>→是
(7) <直接賓語>→<代詞>|<名詞>
其中，“<句子>”表示該應用規則的開始； “→”表示“由……組成”或“定義為”； “|”表示“或”，具有相同左部的幾個規則可以用“|”寫在一起，如上述第2條和第7條規則實際各自代表了兩條規則。
現在根據上述規則可以得到一個符合<句子>定義的規則的句子： 我是大學生。分析過程如下。
<句子><主語><謂語>應用規則(1)

<代詞><謂語>應用規則(2)

我<謂語>應用規則(3)

我<動詞><直接賓語>應用規則(5)

我是<直接賓語>應用規則(6)

我是<名詞>應用規則(7)

我是大學生應用規則(4)
這說明，從<句子>出發，反復使用上述規則中“→”右邊的成分替換左邊的成分，產生“我是大學生”這樣一個句子，從而說明按照上述規則“我是大學生”在語法上是正確的。
上述自然語言的定義就是一個文法。根據上述實例可以抽象出如下一些概念。
(1) 非終結符(Nonterminator)： 在上述規則中用尖括號括起來的符號，它們各自代表一個語法範疇，表示一類具有某種性質的語法單位，有時也稱為語法變量。可以通過它們替換出其他句子成分，它們不會出現在最終的句子中，如例3.1中的<句子>、<主語>等。在程序設計語言中的非終結符有“算術表達式”“賦值語句”等。用VN表示非終結符的集合。非終結符給出了語言的層次和結構，這種層次化結構是語法分析和翻譯的關鍵。
(2) 終結符(Terminator)： 出現在最終的句子中的符號，它是一個語言的基本單位的集合，如例3.1中不帶尖括號的符號“我”“是”“大學生”。在程序設計語言的語法規則中終結符就是單詞符號，如關鍵字、標識符和界符等。用VT表示終結符的集合。
V=VN∪VT，構成文法G的字母表，是該文法中可以使用的全部符號，VN∩VT=Φ。
(3) 產生式(Production)： 按一定格式書寫的、用於定義語法範疇的規則，又稱為規則或生成式，說明了終結符和非終結符組合成符號串的方式。形如α→β或α∷=β，稱α為左部，α∈V+，α至少包含一個非終結符； β為右部，β∈V*。如例3.1中“<句子>→<主語><謂語>”是一個產生式。用P表示產生式的集合，如例3.1中有9個產生式。

(4) 開始符號(Starter)： 是一個特殊的非終結符，至少在一個產生式的左部出現。用S表示，代表該文法定義的語言最終要得到的語法範疇，如例3.1中的<句子>。在程序設計語言中，開始符號就是<程序>，文法定義的其他語法範疇都為此服務。
由此，給出文法的形式化定義： 文法G是一個四元組，G=(VN，VT，P，S)，VN是非終結符集，VT是終結符集，S是開始符號，P是產生式集合。
對例3.1的文法可表示為： G=(VN，VT，P，<句子>)，其中VN＝{<句子>，<主語>，<謂語>，<直接賓語>，<代詞>，<動詞>，<名詞>}，VT＝{我，是，大學生}，P就是例3.1中給出的9條規則。