編譯原理

第一章 引言

1.從面向機(jī)器的語(yǔ)言到面向人類的語(yǔ)言

匯編指令：用符號(hào)表示的指令被稱為匯編指令
匯編語(yǔ)言：匯編指令的集合稱為匯編語(yǔ)言

2.語(yǔ)言之間的翻譯

轉(zhuǎn)換(也被稱為預(yù)處理)：高級(jí)語(yǔ)言之間的翻譯亿鲜，如FORTRAN到ADA的轉(zhuǎn)換
編譯：高級(jí)語(yǔ)言可以直接翻譯成機(jī)器語(yǔ)言祟偷，也可以翻譯成匯編語(yǔ)言粒蜈，這兩個(gè)翻譯過(guò)程稱為編譯
匯編：從匯編語(yǔ)言到機(jī)器語(yǔ)言的翻譯被稱為匯編
交叉匯編：將一個(gè)匯編語(yǔ)言程序匯編成為可在另一機(jī)器上運(yùn)行的機(jī)器指令成為交叉匯編
反匯編：把機(jī)器語(yǔ)言翻譯成匯編語(yǔ)言
反編譯：把匯編語(yǔ)言翻譯成高級(jí)語(yǔ)言

3. 編譯器與解釋器

（1）語(yǔ)言翻譯的兩種基本形態(tài)

解釋器與編譯器的主要區(qū)別:運(yùn)行目標(biāo)程序時(shí)的控制權(quán)在解釋器而不在目標(biāo)程序.

（2）各自特點(diǎn)

• 編譯器:工作效率高,即時(shí)間快耙厚、空間试逼肌；交互性與動(dòng)態(tài)性差,可移植性差.
• 解釋器:工作效率低,,即時(shí)間慢链烈、空間費(fèi)援奢；交互性與動(dòng)態(tài)性好,可移植性好.

共同點(diǎn):均完成對(duì)源程序的翻譯.
差異:編譯器采用先翻譯后執(zhí)行,解釋器采用邊翻譯邊執(zhí)行.

4. 編譯器的工作原理與基本組成

（0）通用程序設(shè)計(jì)語(yǔ)言的主要成份 聲明＋操作＝完整定義

（1）以過(guò)程為基本結(jié)構(gòu)的程序設(shè)計(jì)語(yǔ)言的組成

• 聲明性語(yǔ)句：提供操作對(duì)象的性質(zhì)，如數(shù)據(jù)類型珍语、值锤岸、作用域等；
• 操作性語(yǔ)句：確定操作的計(jì)算次序板乙，完成實(shí)際操作是偷。
• 過(guò)程定義 = 過(guò)程頭＋過(guò)程體

（2）以階段劃分編譯器

注：符號(hào)表管理器和出錯(cuò)處理貫穿編譯器工作的各個(gè)階段.

（3）編譯器各階段工作

1> 詞法分析：詞法分析的輸入是源程序,輸出是識(shí)別出的記號(hào)流.目的是識(shí)別單詞. 至少分以下幾類：關(guān)鍵字(保留字)、標(biāo)識(shí)符募逞、字面量晓猛、特殊符號(hào)

2> 語(yǔ)法分析： 輸入是詞法分析器返回的記號(hào)流,輸出是語(yǔ)法樹(shù).目的是得到語(yǔ)言結(jié)構(gòu)并以樹(shù)的形式表示.對(duì)于聲明性語(yǔ)句,進(jìn)行符號(hào)表的查填,對(duì)于可執(zhí)行語(yǔ)句,檢查結(jié)構(gòu)合理的表達(dá)式運(yùn)算是否有意義.

3> 語(yǔ)義分析：根據(jù)語(yǔ)義規(guī)則對(duì)語(yǔ)法樹(shù)中的語(yǔ)法單元進(jìn)行靜態(tài)語(yǔ)義檢查,如類型檢查和轉(zhuǎn)換等,目的在于保證語(yǔ)法正確的結(jié)構(gòu)在語(yǔ)義分析上也是合法的.

4> 中間代碼生成(可選)：生成一種既接近目標(biāo)語(yǔ)言,又與具體機(jī)器無(wú)關(guān)的表示,便于代碼優(yōu)化與代碼生成.

(到目前為止，編譯器與解釋器可以一致)

5> 中間代碼優(yōu)化(可選)：局部?jī)?yōu)化凡辱、循環(huán)優(yōu)化戒职、全局優(yōu)化等；優(yōu)化實(shí)際上是一個(gè)等價(jià)變換透乾，變換前后的指令序列完成同樣的功能洪燥，但在占用的空間上和程序執(zhí)行的時(shí)間上都更省、更有效

6> 目標(biāo)代碼生成：不同形式的目標(biāo)代碼—匯編語(yǔ)言形式乳乌、可重定位二進(jìn)制代碼形式捧韵、內(nèi)存形式(Load-and-Go)

7> 符號(hào)表管理：合理組織符號(hào),便于各階段查找\填寫(xiě)等.

8> 出錯(cuò)處理：

動(dòng)態(tài)錯(cuò)誤：源程序中的邏輯錯(cuò)誤，發(fā)生在程序運(yùn)行的時(shí)候汉操。也稱為動(dòng)態(tài)語(yǔ)義錯(cuò)誤
靜態(tài)錯(cuò)誤：靜態(tài)錯(cuò)誤分為語(yǔ)法錯(cuò)誤和靜態(tài)語(yǔ)義錯(cuò)誤.  
<1> 語(yǔ)法錯(cuò)誤：有關(guān)語(yǔ)言結(jié)構(gòu)上的錯(cuò)誤再来，如單詞拼寫(xiě)錯(cuò)誤、表達(dá)式缺少操作數(shù)磷瘤、begin和end不匹配
<2> 靜態(tài)語(yǔ)義錯(cuò)誤：分析源程序時(shí)可以發(fā)現(xiàn)的語(yǔ)言意義上的錯(cuò)誤芒篷，如加法的兩個(gè)操作數(shù)一個(gè)是整形變量，另一個(gè)是數(shù)組名

（4）編譯器的分析\綜合模式

邏輯上把編譯器分為分析(前端)部分和綜合(后端)部分.
1> 分析(前端)：語(yǔ)言結(jié)構(gòu)和意義的分析采缚； 從詞法分析到中間代碼生成各階段的工作
2> 綜合(后端)：語(yǔ)言意義處理针炉；從中間代碼生成到目標(biāo)代碼生成的各階段的工作
3> 編譯器和解釋器的區(qū)別往往是在形成中間代碼之后開(kāi)始的.

5. 編譯器掃描的遍數(shù)

每個(gè)階段將程序完整分析一遍的工作模式稱為一遍掃描。
(將源程序或源程序的某種形式的中間表示完整分析一遍扳抽，亦稱作一遍掃描)

第二章 詞法分析

1. 詞法分析中的若干問(wèn)題

(1) 記號(hào)篡帕、模式與單詞

單詞的分類：關(guān)鍵字(保留字)、標(biāo)識(shí)符贸呢、字面量镰烧、特殊符號(hào)
模式（pattern）：產(chǎn)生/識(shí)別單詞的規(guī)則
記號(hào)（token）：按照某個(gè)模式(或規(guī)則)識(shí)別出的元素(一組)
單詞（lexeme）：被識(shí)別出的元素的值(字符串本身) ，也稱為詞值

(2) 詞法分析器的作用與工作方式

詞法分析器的作用：

1> 識(shí)別記號(hào)并交給語(yǔ)法分析器(根據(jù)模式識(shí)別記號(hào))
2> 濾掉源程序中的無(wú)用成分,如注釋楞陷、空格和回車等
3> 處理與具體平臺(tái)有關(guān)的輸入(如文件結(jié)束符的不同表示等)
4> 調(diào)用符號(hào)表管理器和出錯(cuò)處理器怔鳖，進(jìn)行相關(guān)處理

工作方式：
1.單獨(dú)一遍掃描
2.作為語(yǔ)法分析器的子程序
3.并行方式

2. 模式的形式化描述

(1) 字符串與語(yǔ)言

語(yǔ)言L是有限字母表∑上有限長(zhǎng)度字符串的集合.
定義中強(qiáng)調(diào)兩個(gè)有限，因?yàn)橛?jì)算機(jī)的表示能力有限 ：
1> 字母表是有限的猜谚，即字母表中元素是有限多個(gè)败砂；
2> 字符串的長(zhǎng)度是有限的赌渣，即字符串中字符個(gè)數(shù)是有限多個(gè)魏铅。

(字符串與字符串集合相關(guān)的概念與運(yùn)算,如前綴昌犹、后綴、子串览芳、子序列等斜姥，字符串的并、交沧竟、連接铸敏、差、閉包)

(2) 正規(guī)式與正規(guī)集

令Σ是一個(gè)有限字母表悟泵，則Σ上的 正規(guī)式 及其表示的集合遞歸定義如下:
    1. ε是正規(guī)式杈笔，它表示集合  L(ε) = {ε}
    2. 若a是Σ上的字符，則a是正規(guī)式糕非，它表示集合L(a)={a}
    3. 若正規(guī)式r和s分別表示集合L(r)和L(s)蒙具，則
       （a） r|s是正規(guī)式，表示集合L(r)∪L(s)朽肥，
       （b） rs是正規(guī)式禁筏，表示集合L(r)L(s)，
       （c） r*是正規(guī)式衡招，表示集合(L(r))*篱昔，
       （d）(r)是正規(guī)式，表示的集合仍然是L(r)始腾。                                   
       括弧用來(lái)改變運(yùn)算的先后次序州刽！

可用正規(guī)式描述(其結(jié)構(gòu))的語(yǔ)言稱為 正規(guī)語(yǔ)言 或 正規(guī)集 。

若運(yùn)算的優(yōu)先級(jí)和結(jié)合性做下述約定:
    1. 三種運(yùn)算均具有左結(jié)合性質(zhì)浪箭；
    2. 優(yōu)先級(jí)從高到低順序排列為:閉包運(yùn)算怀伦、連接運(yùn)算、或運(yùn)算山林。
則正規(guī)式中不必要的括號(hào)可以被省略房待。

若正規(guī)式P和Q表示了同一個(gè)正規(guī)集，則稱P和Q是等價(jià)的驼抹，記為P=Q

(3) 簡(jiǎn)化正規(guī)式描述(主要是簡(jiǎn)化書(shū)寫(xiě)上的復(fù)雜)

(a) 正閉包 若r是表示L(r)的正規(guī)式桑孩，則r+是表示(L(r))+的正規(guī)式，且下述等式成立:r+ = rr* = rr框冀，r = r+|ε;
          +與*具有相同的運(yùn)算結(jié)合性和優(yōu)先級(jí)
(b) 可缺省  若r是正規(guī)式流椒，則r?是表示L(r)∪{ε}的正規(guī)式，且下述等式成立:r? = r|ε
           ? 與 * 具有相同的運(yùn)算結(jié)合性和優(yōu)先級(jí)
(c) 串    若r是若干字符進(jìn)行連接運(yùn)算構(gòu)成的正規(guī)式明也，則:串“r” =  r 宣虾，且: ε= “”惯裕，   a = “a”（a是Σ的任一字符）
(d) 字符組 若r是若干字符進(jìn)行|運(yùn)算構(gòu)成的正規(guī)式蜻势，則可改寫(xiě)為  [r’]甫菠，其中r’可以有如下兩種書(shū)寫(xiě)形式：
             枚舉:      如  a|b|e|h，可寫(xiě)為 [abeh]：
             分段:   如0|1|2|3|4|5|6|7|8|9|a|b|c|d|e , 可寫(xiě)為： [0-9a-e]
(e) 非字符組 若[r]是一個(gè)字符組形式的正規(guī)式瓢棒，則[^r]是表示∑- L([r])的正規(guī)式。 

3. 記號(hào)的識(shí)別——有限自動(dòng)機(jī)

(1) 不確定的有限自動(dòng)機(jī)（NondeterministicFinite Automaton, NFA）

NFA是一個(gè)五元組（5-tuple）：M =（S，∑，move，s0，F(xiàn)）袁辈，其中
（1） S是有限個(gè)狀態(tài)（state）的集合；
（2） ∑是有限個(gè)輸入字符（包括ε）的集合；
（3） move是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)签夭，move(si慎宾，ch)=sj表示券犁，當(dāng)前狀態(tài)si下若遇到輸入字符ch粘衬，則轉(zhuǎn)移到狀態(tài)sj褂删；
（4） s0是唯一的初態(tài)（也稱開(kāi)始狀態(tài)）；
（5） F是終態(tài)集（也稱接受狀態(tài)集）祭陷，它是S的子集宣肚，包含了所有的終態(tài)。

<1> 直觀的表示方式

① 狀態(tài)轉(zhuǎn)換圖：用一個(gè)有向圖來(lái)直觀表示NFA
② 狀態(tài)轉(zhuǎn)換矩陣：用一個(gè)矩陣來(lái)直觀表示NFA (矩陣中，狀態(tài)對(duì)應(yīng)行戒突，字符對(duì)應(yīng)列)

<2> NFA(識(shí)別記號(hào))的特點(diǎn)
NFA識(shí)別記號(hào)的最大特點(diǎn)是它的不確定性嗡载，即在當(dāng)前狀態(tài)下對(duì)同一字符有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移享幽。

具體體現(xiàn)：
定義： move函數(shù)是1對(duì)多的搭盾；
狀態(tài)轉(zhuǎn)換圖：從同一狀態(tài)出發(fā)何之，可通過(guò)多于一條標(biāo)記相同字符的邊轉(zhuǎn)移到不同的狀態(tài)跟畅；
狀態(tài)轉(zhuǎn)換矩陣： M[si,a]是一個(gè)狀態(tài)的集合

<3> NFA識(shí)別記號(hào)存在的問(wèn)題

1.只有嘗試了全部可能的路徑,才能確定一個(gè)輸入序列不被接受,而這些路徑的條數(shù)隨著路徑長(zhǎng)度的增長(zhǎng)成指數(shù)增長(zhǎng)
2.識(shí)別過(guò)程中需要進(jìn)行大量回朔，時(shí)間復(fù)雜度升高且算法復(fù)雜

(2) 確定的有限自動(dòng)機(jī)（Deterministic Finite Automaton, DFA）

定義: DFA是NFA的一個(gè)特例帝美，其中： 
  （1）沒(méi)有狀態(tài)具有ε狀態(tài)轉(zhuǎn)移(ε-transition)碍彭，即狀態(tài)轉(zhuǎn)換圖中沒(méi)有標(biāo)記ε的邊晤硕；
  （2）對(duì)每個(gè)狀態(tài)s和每個(gè)字符a悼潭，最多有一個(gè)下一狀態(tài)。
  
特點(diǎn)：與NFA相比舞箍，DFA的特征：確定性
    定義：move（si, a)函數(shù)都是 1對(duì)1 的舰褪；
    轉(zhuǎn)換圖 從一個(gè)狀態(tài)出發(fā)的任2條邊上的標(biāo)記均不同；
    轉(zhuǎn)換矩陣：M[si,a]是一個(gè)狀態(tài)   且字母表不包括ε疏橄。
提示：正規(guī)式和有限自動(dòng)機(jī)從兩個(gè)側(cè)面表示正規(guī)式占拍。正規(guī)式是描述，自動(dòng)機(jī)是識(shí)別捎迫。

4. 從正規(guī)式到詞法分析器

構(gòu)造詞法分析器的一般方法和步驟：
1. 用正規(guī)式描述模式（為記號(hào)設(shè)計(jì)正規(guī)式）晃酒；
2. 為每個(gè)正規(guī)式構(gòu)造一個(gè)NFA，它識(shí)別正規(guī)式所表示的正規(guī)集窄绒；
3. 將構(gòu)造的NFA轉(zhuǎn)換成等價(jià)的DFA贝次，這一過(guò)程也被稱為確定化；
4. 優(yōu)化DFA彰导，使其狀態(tài)數(shù)最少蛔翅，這一過(guò)程也被稱為最小化；
5. 根據(jù)優(yōu)化后的DFA構(gòu)造詞法分析器位谋。

(1) 從正規(guī)式到NFA

Thompson 算法

(2) 從NFA到DFA

- smove(S, a)：從狀態(tài)集S出發(fā)山析，標(biāo)記為a的下一狀態(tài)全體。與move(s, a)的唯一區(qū)別：用狀態(tài)集取代狀態(tài)
- ε-閉包(T)：從狀態(tài)集T出發(fā)掏父，不經(jīng)任何字符達(dá)到的狀態(tài)全體
- “子集法”構(gòu)造DFA

(3) 最小化DFA

? ① 對(duì)于任何兩個(gè)狀態(tài)t和s笋轨，若從一狀態(tài)出發(fā)接受輸入字符串ω，而從另一狀態(tài)出發(fā)不接受ω.

或者，② 從t出發(fā)和從s出發(fā)到達(dá)不同的接受狀態(tài)爵政，則稱ω對(duì)狀態(tài)t和s是可區(qū)分的.

? 不可區(qū)分的狀態(tài)位于一個(gè)組內(nèi)鸟款，可以合并成一個(gè)狀態(tài).

主要步驟：
? 1.初始劃分：終態(tài)組 ， 非終態(tài)組茂卦；
? 2.利用可區(qū)分的概念何什，反復(fù)分裂劃分中的組Gi，直到不可再分裂等龙；
? 3.由最終劃分構(gòu)造D'处渣，關(guān)鍵是選代表和修改狀態(tài)轉(zhuǎn)移；
? 4.消除可能的死狀態(tài)和不可達(dá)狀態(tài)蛛砰。

5. 從DFA構(gòu)造詞法分析器

分類：表驅(qū)動(dòng)型的詞法分析器罐栈；直接編碼的詞法分析器
比較：

第三章 語(yǔ)法分析

詞法分析：記號(hào)的集合，字符串由字母組成泥畅，線性結(jié)構(gòu)
語(yǔ)法分析：句子的集合荠诬，句子由記號(hào)組成，非線性結(jié)構(gòu)（樹(shù)）

語(yǔ)法分析的雙重含義：

• 語(yǔ)法規(guī)則：上下文無(wú)關(guān)文法（子集：LL文法或LR文法）
• 語(yǔ)法分析：下推自動(dòng)機(jī)（LL或LR分析器）位仁、自上而下分析柑贞、自下而上分析

1. 語(yǔ)法分析的若干問(wèn)題

許多編譯器，特別是由自動(dòng)生成工具構(gòu)造的編譯器聂抢，往往其前端的中心部件就是語(yǔ)法分析器

（1）語(yǔ)法分析器的作用

• 根據(jù)詞法分析器提供的記號(hào)流钧嘶，為語(yǔ)法正確的輸入構(gòu)造分析樹(shù)（或語(yǔ)法樹(shù)）
• 檢查輸入中的語(yǔ)法（可能包括詞法）錯(cuò)誤，并調(diào)用出錯(cuò)處理器進(jìn)行適
  當(dāng)處理

（2）語(yǔ)法錯(cuò)誤的處理原則

源程序中可能出現(xiàn)的錯(cuò)誤

語(yǔ)法(包括詞法)錯(cuò)誤和語(yǔ)義錯(cuò)誤(靜態(tài)語(yǔ)義錯(cuò)誤和動(dòng)態(tài)語(yǔ)義錯(cuò)誤)

注：跟第一章的分類角度不同琳疏，第一章是從靜態(tài)錯(cuò)誤(語(yǔ)法錯(cuò)誤有决，靜態(tài)語(yǔ)義錯(cuò)誤)和動(dòng)態(tài)錯(cuò)誤(動(dòng)態(tài)語(yǔ)義錯(cuò)誤)分類的，但是殊途同歸空盼。

詞法錯(cuò)誤：指非法字符或拼寫(xiě)錯(cuò)關(guān)鍵字书幕、標(biāo)識(shí)符等
語(yǔ)法錯(cuò)誤：指語(yǔ)法結(jié)構(gòu)出錯(cuò)，如少分號(hào)揽趾、括號(hào)不匹配台汇、begin/end不配對(duì)等
靜態(tài)語(yǔ)義錯(cuò)誤：如類型不一致、參數(shù)不匹配等
動(dòng)態(tài)語(yǔ)義錯(cuò)誤(邏輯錯(cuò)誤)：如死循環(huán)但骨、變量為零時(shí)作除數(shù)等

2. 上下文無(wú)關(guān)文法(CFG)

（1）上下文無(wú)關(guān)文法(Context Free Grammar,CFG)

 CFG是一個(gè)四元組G =（N励七，T，P奔缠，S）掠抬，其中
（1） N是非終結(jié)符（Nonterminals）的有限集合；
（2） T是終結(jié)符（Terminals）的有限集合校哎，且N∩T=Φ两波；
（3） P是產(chǎn)生式（Productions）的有限集合瞳步，A→α，其中A∈N(左部),α∈(N∪T)*(右部),若α=ε腰奋，則稱A→ε為空產(chǎn)生式(也可以記為A →);
（4） S是非終結(jié)符单起，稱為文法的開(kāi)始符號(hào)（Start symbol）
 注： S ∈ N , N可以出現(xiàn)在產(chǎn)生式左邊和右邊，T絕不出現(xiàn)在產(chǎn)生式左邊.

（2）CFG產(chǎn)生語(yǔ)言的基本方法－推導(dǎo)

CFG（產(chǎn)生式）通過(guò)推導(dǎo)的方法產(chǎn)生語(yǔ)言劣坊，即（通俗地講）從開(kāi)始符號(hào)S開(kāi)始嘀倒，反復(fù)使用產(chǎn)生式：將產(chǎn)生式左部的非終結(jié)符替換為右部的文法符號(hào)序列(展開(kāi)產(chǎn)生式，用=>表示)局冰，直到得到一個(gè)終結(jié)符序列测蘑。

1> 直接推導(dǎo)：利用產(chǎn)生式產(chǎn)生句子的過(guò)程中，將用產(chǎn)生式A→γ的右部代替文法符號(hào)序列αAβ中的A得到αγβ的過(guò)程康二，稱αAβ直接推導(dǎo)出αγβ碳胳，記作：αAβ=>αγβ

2> 零步或多步推導(dǎo)：若對(duì)于任意文法符號(hào)序列α1，α2沫勿，...αn挨约，有α1=>α2=>...=>αn，則稱此過(guò)程為零步或多步推導(dǎo)产雹，記為：α1 =*> αn诫惭，其中α1=αn的情況為零步推導(dǎo)。

3> 至少一次推導(dǎo)：若α1≠αn洽故，即推導(dǎo)過(guò)程中至少使用一次產(chǎn)生式,則稱此過(guò)程為至少一步推導(dǎo)贝攒，記為：α1 =+> αn

(推導(dǎo)具有自反性和傳遞性)

4> 由 CFGG 所產(chǎn)生的語(yǔ)言L(G)被定義為: L(G) = { ω┃S ωand ω∈T* }，
? L(G)稱為上下文無(wú)關(guān)語(yǔ)言(Context Free Language, CFL)时甚，ω稱為句子。
? 若S =* > α哈踱，α∈(N∪T)*荒适，則稱α為G的一個(gè)句型。句子一定是句型开镣，反之不是刀诬。

5> 在推導(dǎo)過(guò)程中，若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符邪财，則稱為最左推導(dǎo)陕壹，由最左推導(dǎo)產(chǎn)生的句型被稱為左句型。 類似的可以定義最右推導(dǎo)與右句型树埠，最右推導(dǎo)也被稱為規(guī)范推導(dǎo)糠馆。

（3）推導(dǎo)、分析樹(shù)與語(yǔ)法樹(shù)

1怎憋、分析樹(shù)既反映語(yǔ)言結(jié)構(gòu)的實(shí)質(zhì)又碌，也反映推導(dǎo)過(guò)程九昧。

2、對(duì)CFGG的句型毕匀，分析樹(shù)被定義為具有下述性質(zhì)的一棵樹(shù)铸鹰。

（1） 根由開(kāi)始符號(hào)所標(biāo)記；
（2） 每個(gè)葉子由一個(gè)終結(jié)符皂岔、非終結(jié)符蹋笼、或ε標(biāo)記；
（3） 每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記躁垛；
（4） 若A是某內(nèi)部節(jié)點(diǎn)的標(biāo)記姓建，且X1，X2缤苫，...速兔，Xn是該節(jié)點(diǎn)從左到右所有孩子的標(biāo)記，則A→X1X2...Xn是一個(gè)產(chǎn)生式活玲。若A→ε涣狗，則標(biāo)記為A的結(jié)點(diǎn)可以僅有一個(gè)標(biāo)記為ε的孩子。

注：分析樹(shù)的葉子舒憾，從左到右構(gòu)成G的一個(gè)句型镀钓。若葉子僅由終結(jié)符標(biāo)記，則構(gòu)成一個(gè)句子镀迂。

3丁溅、對(duì)CFG G的句型，表達(dá)式的語(yǔ)法樹(shù)被定義為具有下述性質(zhì)的一棵樹(shù):

（1） 根與內(nèi)部節(jié)點(diǎn)由表達(dá)式中的操作符標(biāo)記探遵；
（2） 葉子由表達(dá)式中的操作數(shù)標(biāo)記窟赏；
（3）用于改變運(yùn)算優(yōu)先級(jí)和結(jié)合性的括號(hào)，被隱含在語(yǔ)法樹(shù)的結(jié)構(gòu)中箱季。

• 語(yǔ)法樹(shù)是表示表達(dá)式結(jié)構(gòu)的最好形式

（4）二義性與二義性的消除

二義性：若文法G對(duì) 同 一句子產(chǎn)生不止一棵分析樹(shù)涯穷，則稱G是二義的.

結(jié)論：
1> 一個(gè)句子有多于一棵分析樹(shù)，僅與文法和句子有關(guān)藏雏，與采用的推導(dǎo)方法無(wú)關(guān)拷况；
2> 造成文法二義的根本原因：文法中缺少對(duì)文法符號(hào)優(yōu)先級(jí)和結(jié)合性的規(guī)定

二義性消除的方法：
① 改寫(xiě)二義文法為非二義文法；
② 規(guī)定二義文法中符號(hào)的優(yōu)先級(jí)和結(jié)合性掘殴，使僅產(chǎn)生一棵分析樹(shù)赚瘦。

3. 語(yǔ)法與文法簡(jiǎn)介

（1）正規(guī)式與上下文無(wú)關(guān)文法

• 記號(hào)可以用正規(guī)式描述，正規(guī)式適合描述線性結(jié)構(gòu)奏寨，如標(biāo)識(shí)符起意、關(guān)鍵字、注釋等.
• 句子可以用CFG描述服爷，CFG適合描述具有嵌套(層次)性質(zhì)的非線性結(jié)構(gòu)杜恰，如不同結(jié)構(gòu)的句子if-then-else\while-do等

正規(guī)式所描述的語(yǔ)言結(jié)構(gòu)均可以用CFG描述获诈，反之不一定.

（2）上下文有關(guān)文法CSG

典型的這類語(yǔ)言結(jié)構(gòu)包含：計(jì)數(shù)問(wèn)題的抽象、變量的聲明與引用心褐、過(guò)程調(diào)用時(shí)形參與實(shí)參的一致性檢查等.描述它們的文法被稱為上下文有關(guān)文法(Context Sensitive Grammar舔涎，CSG).這些語(yǔ)言結(jié)構(gòu)無(wú)法用上下文無(wú)關(guān)文法CSG來(lái)描述.

（3）形式語(yǔ)言與自動(dòng)機(jī)簡(jiǎn)介

? 若文法G=(N，T逗爹，P亡嫌，S)的每個(gè)產(chǎn)生式α→β中，均有α∈(N∪T)掘而，且至少含有一個(gè)非終結(jié)符挟冠，β∈(N∪T)，則稱G為0型文法.

? 對(duì)0型文法施加以下第i條限制袍睡，即得到i型文法知染。

? 1> G的任何產(chǎn)生式α→β（S→ε除外）滿足|α|≤|β|；
? 2> G的任何產(chǎn)生式形如A→β斑胜，其中A∈N控淡，β∈(N∪T)*；
? 3> G的任何產(chǎn)生式形如A→a或者A→aB(或者A→Ba)止潘，其中A和B∈N掺炭，a∈T。

4. 自上而下語(yǔ)法分析

分為：遞歸下降分析法凭戴、預(yù)測(cè)分析法

基本思想：對(duì)任何一個(gè)輸入序列ω涧狮，從S開(kāi)始進(jìn)行最左推導(dǎo)，直到得到一個(gè)合法的句子或發(fā)現(xiàn)一個(gè)非法結(jié)構(gòu)么夫。整個(gè)自上而下分析是一個(gè)試探的過(guò)程者冤，是反復(fù)使用不同產(chǎn)生式謀求與輸入序列匹配的過(guò)程。

提前準(zhǔn)備——重寫(xiě)文法：1.消除左遞歸魏割，以避免陷入死循環(huán)譬嚣； 2.提取左因子，以避免回溯.

（1）消除左遞歸

定義：若文法G中的非終結(jié)符A钞它，對(duì)某個(gè)文法符號(hào)序列α存在推導(dǎo)A =+> Aα，則稱G是左遞歸的殊鞭。若G中有形如A→Aα的產(chǎn)生式遭垛，則稱該產(chǎn)生式對(duì)A直接左遞歸。

<1> 消除文法的直接左遞歸

A→Aα|β     替換為     A →βA'
                    A'→αA'|ε

首先操灿，整理A產(chǎn)生式為如下形式：A→ Aα1|Aα2|...|Aαm|β1|β2|...|βn
然后用下述產(chǎn)生式代替A產(chǎn)生式：A→ β1 A'|β2 A'| ...|βn A'
? A'→ α1 A' | α2 A' | ... | αm A' |ε

<2> 消除文法的左遞歸

核心思想：將無(wú)直接左遞歸的非終結(jié)符展開(kāi)到其他產(chǎn)生式,然后消除其他產(chǎn)生式中的直接左遞歸(如果有的話)

若G產(chǎn)生句子的過(guò)程中出現(xiàn)A=+A的推導(dǎo)锯仪，則無(wú)法消除左遞歸(出現(xiàn)回路)

（2）提取左因子

<1> 提取文法的左因子

左因子產(chǎn)生原因：公共前綴：A → αβ1|αβ2
方法：將 A → αβ1|αβ2|γ
? 替換為 A→αA'|γ A'→β1|β2

（3）遞歸下降分析

直接以程序代碼（的方式）模擬產(chǎn)生式產(chǎn)生語(yǔ)言的過(guò)程:

基本思想：每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)子程序（函數(shù)），過(guò)程體中：

• 產(chǎn)生式右部的非終結(jié)符：對(duì)應(yīng)子程序調(diào)用趾盐，
• 產(chǎn)生式右部的終結(jié)符： 與輸入記號(hào)序列進(jìn)行匹配庶喜。

特點(diǎn)：
1> 子程序是遞歸的（因?yàn)槲姆ㄊ沁f歸的）小腊；
2> 程序與文法相關(guān)；
3> 它對(duì)文法的限制是不能有公共左因子和左遞歸久窟；
4> 它是一種非形式化的方法秩冈，只要能寫(xiě)出子程序，用什么樣的方法和步驟均可斥扛。

（4）預(yù)測(cè)分析器

☆ 預(yù)測(cè)分析器由一張預(yù)測(cè)分析表入问、一個(gè)符號(hào)棧和一個(gè)驅(qū)動(dòng)器組成，數(shù)學(xué)模型是下推自動(dòng)機(jī)稀颁。
☆ 對(duì)文法的限制是不能有公共左因子和左遞歸

預(yù)測(cè)分析器的核心概念：
1> 分析方法：格局與格局變換
2> 分析表+驅(qū)動(dòng)器（模擬算法）
3> 預(yù)測(cè)分析表的構(gòu)造
4> LL（文法芬失、語(yǔ)言、分析器）

☆ 開(kāi)始格局的剩余輸入是全部輸入序列匾灶，而接收格局中剩余輸入應(yīng)該為空阶女，任何其他格局或出錯(cuò)格局中的剩余輸入應(yīng)該是全部輸入序列的一個(gè)后綴.

☆ 改變格局的動(dòng)作：

① 匹配終結(jié)符： 若top^=ip(但≠#)，則pop且next(ip)；
② 展開(kāi)非終結(jié)符：若top^= X且M[X,ip^]=α(X→α)惯疙，則pop且push(α)霉颠；
③ 報(bào)告分析成功： 若top ^= ip^ = #怀读，則分析成功并結(jié)束啤誊；
④ 報(bào)告出錯(cuò)：其它情況岳瞭，調(diào)用錯(cuò)誤恢復(fù)例程.

☆ 驅(qū)動(dòng)器算法

☆ 構(gòu)造預(yù)測(cè)分析表

步驟：1. 構(gòu)造文法符號(hào)X的FIRST集合和非終結(jié)符的FOLLOW集合孟抗；2. 根據(jù)兩個(gè)集合構(gòu)造預(yù)測(cè)分析表.

通俗地講摊沉，α的FIRST集合就是從α開(kāi)始可以導(dǎo)出的文法符號(hào)序列中的開(kāi)頭終結(jié)符试吁。而A的FOLLOW集合，就是從開(kāi)始符號(hào)可以導(dǎo)出的所有含A的文法符號(hào)序列中緊跟A之后的終結(jié)符.

<1> 計(jì)算X的FIRST集合 -----自下而上計(jì)算
<2> 計(jì)算所有非終結(jié)符的FOLLOW集合 —— 自上而下計(jì)算
<3> 構(gòu)造預(yù)測(cè)分析表
<4> LL(1)文法

文法G被稱為是LL(1)文法，當(dāng)且僅當(dāng)為它構(gòu)造的預(yù)測(cè)分析表中不含多重定義的條目铐然。由此分析表所組成的分析器被稱為LL(1)分析器蔬崩，它所分析的語(yǔ)言被稱為LL(1)語(yǔ)言恶座。

☆ 第一個(gè)L代表從左到右掃描輸入序列，第二個(gè)L表示產(chǎn)生最左推導(dǎo)沥阳，1表示在確定分析器的每一步動(dòng)作時(shí)向前看一個(gè)終結(jié)符.

推論3.2 G是LL(1)的跨琳，當(dāng)且僅當(dāng)G的任何兩個(gè)產(chǎn)生式A→α|β滿足:
1. 對(duì)任何終結(jié)符a，α和β不能同時(shí)推導(dǎo)出以a開(kāi)始的串桐罕；即First(α) ∩ First(β) = ?
2. α和β最多有一個(gè)可以推導(dǎo)出ε脉让；
3. 若β =*> ε,則α不能導(dǎo)出以FOLLOW(A)中終結(jié)符開(kāi)始的任何串. 即First(α) ∩ Follow(A) = ?

☆ 無(wú)論是遞歸下降子程序法還是非遞歸的預(yù)測(cè)分析法，他們都只能處理LL(1)文法.

5. 自下而上語(yǔ)法分析

☆ 自上而下分析采用的是推導(dǎo);自下而上分析采用的是歸約(規(guī)范歸約—剪句柄—移進(jìn)/歸約分析—SLR(1)分析器).

（1）自下而上分析的基本方法

☆ 基本思想：最左歸約.

對(duì)于每個(gè)輸入序列ω：從左到右掃描ω; 從ω開(kāi)始,反復(fù)用產(chǎn)生式的左部替換產(chǎn)生式的右部(即當(dāng)前句型中的句柄)功炮、謀求對(duì)ω的匹配,最終得到文法的開(kāi)始符號(hào)溅潜，或者發(fā)現(xiàn)一個(gè)錯(cuò)誤。

☆ 基本概念：

a) > 設(shè)αβδ是文法G的一個(gè)句型薪伏，若存在S=*>αAδ滚澜，A=+>β， 則稱β是句型αβδ相對(duì)于A的"短語(yǔ)".
   > 特別的嫁怀，若 有A→β设捐，則 稱β是句型αβδ相對(duì)于產(chǎn)生式A→β的"直接短語(yǔ)".
   > 一個(gè)句型的最左直接短語(yǔ)被稱為"句柄".

   特征：
    1.  短語(yǔ)：以非終結(jié)符為根子樹(shù)中所有從左到右的葉子；
    2.  直接短語(yǔ)：只有父子關(guān)系的子樹(shù)中所有從左到右排列的葉子（樹(shù)高為2）塘淑；
    3.  句柄：最左邊父子關(guān)系樹(shù)中所有從左到右排列的葉子（句柄是唯一的）
    
    
b)最左歸約：若 α是文法G的句子且滿足下述條件萝招，則稱序列αn，αn-1存捺，...槐沼，α0是α的一個(gè)最左歸約。
   1) αn = α
   2) α0 = S（S是G 的開(kāi)始符號(hào)）
   3) 對(duì)任何i(0<i<=n)召噩，αi-1是將αi中句柄替換為相應(yīng)產(chǎn)生式左部非終結(jié)符得到的
   
 ☆ 最左歸約的逆過(guò)程是一個(gè)最右推導(dǎo)母赵，分別稱最右推導(dǎo)和最左歸約為規(guī)范推導(dǎo)和規(guī)范歸約.
 
 c）移進(jìn)-歸約分析器
 1. 工作方式：格局與格局變換
 2. 分析表
 3. 驅(qū)動(dòng)器（模擬算法）
 4. SLR分析表的構(gòu)造
 5. LR（文法、語(yǔ)言具滴、分析器）

☆ 改變格局的動(dòng)作：
1. 移進(jìn)(shift)：當(dāng)前剩余輸入的下一終結(jié)符進(jìn)棧凹嘲。
2.歸約(reduce)：將棧頂句柄替換為對(duì)應(yīng)非終結(jié)符(最左歸約)
3.接受(accept)：宣告分析成功
4. 報(bào)錯(cuò)(error)：發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程

(2) LR分析

a) LR分析與LR文法
LR分析：允許左遞歸构韵，但不能有二義

定義3.15 若為文法G構(gòu)造的移進(jìn)-歸約分析表中不含多重定義的條目周蹭，則稱G為"LR(k)文法"，分析器被稱為是"LR(k)分析器"疲恢，它所識(shí)別的語(yǔ)言被稱為"LR(k)語(yǔ)言"凶朗。"L"表示從左到右掃描輸入序列，"R"表示逆序的最右推導(dǎo)显拳，"k"表示為確定下一動(dòng)作向前看的終結(jié)符個(gè)數(shù)棚愤，一般情況下k<=1。當(dāng)k=1時(shí)，簡(jiǎn)稱"LR"宛畦。             

構(gòu)造SLR(1)分析器

<1> 活前綴與LR(0)項(xiàng)目

出現(xiàn)在移進(jìn)-歸約分析器棧中的右句型的前綴瘸洛，被稱為文法G的活前綴(viable prefix).
LR(0)項(xiàng)目(簡(jiǎn)稱項(xiàng)目)是這樣一個(gè)產(chǎn)生式，在它右邊的某個(gè)位置有一個(gè)點(diǎn)"."次和。對(duì)于A→ε反肋，它僅有一個(gè)項(xiàng)目A→.。
項(xiàng)目A→α.β顯示了分析過(guò)程中看到(移進(jìn))了產(chǎn)生式的多少踏施。
β不為空的項(xiàng)目稱為可移進(jìn)項(xiàng)目石蔗，β為空的項(xiàng)目稱為可歸約項(xiàng)目.

<2> 拓廣文法與識(shí)別活前綴的DFA

G' = G ∪ {S' → S}
其中：S' → S是識(shí)別S的初態(tài)，S' → S. 是識(shí)別S的終態(tài). 目的是使最終構(gòu)造的DFA狀態(tài)集中具有唯一的初態(tài)和終態(tài). ① closure(I)：從項(xiàng)目集I不經(jīng)任何文法符號(hào)到達(dá)的項(xiàng)目全體畅形；

② goto(I养距，x)：所有從I經(jīng)文法符號(hào)x能直接到達(dá)的項(xiàng)目全體。

項(xiàng)目[S’→.S]和所有“.”不在產(chǎn)生式右部最左邊的項(xiàng)目稱為核心項(xiàng)目(kernel items)束亏，
其它“.”在產(chǎn)生式右部最左邊的項(xiàng)目(不包括[S’→.S])稱為非核心項(xiàng)目(nonkernel items).

核心項(xiàng)目：J=goto(I铃在，X)，S'→.S（作為項(xiàng)目集的代表）
非核心項(xiàng)目：closure(J)-J（特點(diǎn)：可由J某中某項(xiàng)目算得） 

<3> 識(shí)別活前綴

定義3.21 若存在最右推導(dǎo)S’=*> αAω => αβ1β2ω碍遍，則稱項(xiàng)目[A→β1.β2] 對(duì)活前綴αβ1有效定铜。

當(dāng)一個(gè)項(xiàng)目集中同時(shí)存在：
    1. A→β1.β2和B→β.：既可移進(jìn)又可歸約，移進(jìn)/歸約沖突
    2.A→α.和B→β.：均可指導(dǎo)下一步分析怕敬，歸約/歸約沖突

解決方法：簡(jiǎn)單向前看一個(gè)終結(jié)符：
    1. 移進(jìn)/歸約沖突：若FIRST(β2)∩FOLLOW(B)=Φ揣炕，沖突可解決
    2. 歸約/歸約沖突：若FOLLOW(A)∩FOLLOW(B)=Φ，沖突可解決

若沖突可以解決东跪，則稱文法為SLR(1)文法畸陡，構(gòu)造的分析表為SLR(1)分析表。
SLR(1)文法：簡(jiǎn)單向前看一個(gè)終結(jié)符即可解決沖突
☆ 二義文法不是SLR(1)文法

第四章 靜態(tài)語(yǔ)義分析

采用語(yǔ)法制導(dǎo)翻譯生成中間代碼

1. 語(yǔ)法制導(dǎo)翻譯簡(jiǎn)介

（1）語(yǔ)法與語(yǔ)義的關(guān)系

語(yǔ)法是指語(yǔ)言的結(jié)構(gòu)虽填、即語(yǔ)言的“樣子”丁恭；
語(yǔ)義是指附著于語(yǔ)言結(jié)構(gòu)上的實(shí)際含意，即語(yǔ)言的“意義”.
一個(gè)語(yǔ)法上正確的句子斋日，它所代表的意義并不一定正確.

☆ 語(yǔ)義分析的作用

? 檢查結(jié)構(gòu)正確的句子所表示的意思是否合法牲览；
? 執(zhí)行規(guī)定的語(yǔ)義動(dòng)作，如：表達(dá)式求值恶守、符號(hào)表的查詢/填寫(xiě)第献、中間代碼生成等

☆ 應(yīng)用最廣的語(yǔ)義分析方法是語(yǔ)法制導(dǎo)翻譯，他的基本思想是將語(yǔ)言結(jié)構(gòu)的語(yǔ)義以屬性的形式賦予代表此結(jié)構(gòu)的文法符號(hào)兔港，而屬性的計(jì)算以語(yǔ)義規(guī)則的形式賦予由文法符號(hào)組成的產(chǎn)生式.

（2）屬性/語(yǔ)義規(guī)則的定義

定義4.1 對(duì)于產(chǎn)生式A→α庸毫，其中α是由文法符號(hào)X1X2...Xn組成的序列，它的語(yǔ)義規(guī)則可以表示為(4.1)所示關(guān)于屬性的函數(shù)f：
          b := f(c1, c2, ..., ck)                  (4.1)
語(yǔ)義規(guī)則中的屬性存在下述性質(zhì)與關(guān)系：
      (1)   稱(4.1)中屬性b依賴于屬性c1, c2, ..., ck。
      (2) 若b是A的屬性，c1, c2, ..., ck是α中文法符號(hào)的屬性，或者A的其它屬性捶惜，則稱b是A的綜合屬性盒揉。
      (3) 若b是α中某文法符號(hào)Xi的屬性晋被，c1, c2, ..., ck是A的屬性，或者是α中其它文法符號(hào)的屬性刚盈，則稱b是Xi的繼承屬性。
      (4) 若語(yǔ)義規(guī)則的形式如下述(4.2)挂脑，則可將其想像為產(chǎn)生式左部文法符號(hào)A的一個(gè)虛擬屬性藕漱。屬性之間的依賴關(guān)系，在虛擬屬性上依然存在崭闲。
          f(c1, c2, ..., ck)                (4.2)          ■

☆ 繼承屬性從前輩和兄弟的屬性計(jì)算得到,綜合屬性從子孫和自身的其他屬性計(jì)算得到.

即,繼承屬性"自上而下,包括兄弟",綜合屬性"自下而上,包括自身".

（3）語(yǔ)義規(guī)則的兩種形式

☆ 語(yǔ)義規(guī)則的兩種形式（忽略實(shí)現(xiàn)細(xì)節(jié)肋联，二者作用等價(jià)）

<1> 語(yǔ)法制導(dǎo)定義(Syntax Directed Definition)

用抽象的屬性和運(yùn)算表示的語(yǔ)義規(guī)則；(公式刁俭，做什么)

<2> 翻譯方案(Translation Scheme)

用具體的屬性和運(yùn)算表示的語(yǔ)義規(guī)則橄仍。(程序段，如何做)

☆ 繼承屬性是自上而下計(jì)算的牍戚，綜合屬性是自下而上計(jì)算的.

（4）LR分析翻譯方案的設(shè)計(jì)

☆ LR分析中的語(yǔ)法制導(dǎo)翻譯實(shí)質(zhì)上是對(duì)LR語(yǔ)法分析的擴(kuò)充：

1. 擴(kuò)充LR分析器的功能

當(dāng)執(zhí)行歸約產(chǎn)生式的動(dòng)作時(shí)侮繁，也執(zhí)行相應(yīng)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。由于是歸約時(shí)執(zhí)行語(yǔ)義動(dòng)作如孝，

? 因此限制語(yǔ)義動(dòng)作僅能放在產(chǎn)生式右部的最右邊宪哩；

2. 擴(kuò)充分析棧

? 增加一個(gè)與分析棧并列的語(yǔ)義棧，用于存放分析棧中文法符號(hào)所對(duì)應(yīng)的屬性值第晰。

☆ 擴(kuò)充后的LR分析最適合對(duì)綜合屬性的計(jì)算锁孟，而對(duì)于繼承屬性的計(jì)算還需要進(jìn)行適當(dāng)?shù)奶幚?

2. 中間代碼簡(jiǎn)介

☆ 中間代碼應(yīng)具備的特性
1）便于語(yǔ)法制導(dǎo)翻譯
2）既與機(jī)器指令的結(jié)構(gòu)相近,又與具體機(jī)器無(wú)關(guān).

使用中間代碼的好處:一是便于編譯器程序的開(kāi)發(fā)和移植,二是代碼進(jìn)行優(yōu)化處理.

☆ 中間代碼的主要形式：后綴式、樹(shù)茁瘦、三地址碼等.最基本的中間代碼形式是樹(shù)??品抽；最常用的中間代碼形式是三地址碼，它的實(shí)現(xiàn)形式常采用四元式形式甜熔。

☆ 符號(hào)表是幫助聲明語(yǔ)句實(shí)現(xiàn)存儲(chǔ)空間分配的重要數(shù)據(jù)結(jié)構(gòu)圆恤。

（1）后綴式

操作數(shù)在前，操作符緊隨其后纺非，無(wú)需用括號(hào)限制運(yùn)算的優(yōu)先級(jí)和結(jié)合性哑了；便于求值.

（2）三地址碼

① 三元式 形式： (i) (op, arg1, arg2)

? 三地址碼：(i):= arg1 op arg2

序號(hào)的雙重含義：既代表此三元式，又代表三元式存放的結(jié)果

存放方式：數(shù)組結(jié)構(gòu)烧颖，三元式在數(shù)組中的位置由下標(biāo)決定

弱點(diǎn)：給代碼的優(yōu)化帶來(lái)困難

② 四元式 形式： ( i ) (op弱左，arg1，arg2炕淮，result)

? 所表示的計(jì)算： result:= arg1 op arg2

1. 四元式與三元式的唯一區(qū)別：將由序號(hào)所表示的運(yùn)算結(jié)果改為：用(臨時(shí))變量來(lái)表示拆火。

2. 此改變使得四元式的運(yùn)算結(jié)果與其在四元式序列中的位置無(wú)關(guān).為代碼的優(yōu)化提供了極大方便，因?yàn)檫@樣可以刪除或移動(dòng)四元式而不會(huì)影響運(yùn)算結(jié)果.

③ 樹(shù)形表示

1> 語(yǔ)法樹(shù)真實(shí)反映句子結(jié)構(gòu)，對(duì)語(yǔ)法樹(shù)稍加修改（加入語(yǔ)義信息）们镜，即可以作為中間代碼的一種形式(注釋語(yǔ)法樹(shù))
2> 樹(shù)的優(yōu)化表示－DAG
3> 樹(shù)與其他中間代碼的關(guān)系

☆ 樹(shù)表示的中間代碼與后綴式和三地址碼之間有內(nèi)在聯(lián)系

1. 樹(shù) → 后綴式

? 方法：對(duì)樹(shù)進(jìn)行深度優(yōu)先后序遍歷币叹，得到的線性序列就是后綴式，或者說(shuō)后綴式是樹(shù)的一個(gè)線性化序列模狭；

2. 樹(shù) → 三元式/四元式

特點(diǎn)：樹(shù)的每個(gè)非葉子節(jié)點(diǎn)和它的兒子對(duì)應(yīng)一個(gè)三元式或四元式颈抚；

方法：對(duì)樹(shù)的非葉子節(jié)點(diǎn)進(jìn)行深度優(yōu)先后序遍歷，即得到一個(gè)三元式或四元式序列嚼鹉。

3. 符號(hào)表簡(jiǎn)介

• 符號(hào)表的作用：連接聲明與引用的橋梁贩汉，記住每個(gè)符號(hào)的相關(guān)信息，如作用域和類型等锚赤，幫助編譯的各個(gè)階段正確有效地工作匹舞。
• 符號(hào)表的基本目標(biāo)：有效記錄信息、快速準(zhǔn)確查找线脚。
• 符號(hào)表設(shè)計(jì)的基本要求：
  • 正確存儲(chǔ)各類信息赐稽；
  • 適應(yīng)不同階段的需求；
  • 便于有效地進(jìn)行查找浑侥、插入姊舵、刪除和修改等操作；
  • 空間可以動(dòng)態(tài)擴(kuò)充.

（1）構(gòu)成名字的字符串

構(gòu)成名字的字符串的存儲(chǔ)方式：直接存儲(chǔ)---定長(zhǎng)數(shù)據(jù)(直接將構(gòu)成名字的字符串放在符號(hào)表?xiàng)l目中)和間接存儲(chǔ)---變長(zhǎng)數(shù)據(jù)(將構(gòu)成名字的字符串統(tǒng)一存放在一個(gè)大的連續(xù)空間內(nèi)锭吨，字符串與字符串之間采用特殊的分隔符隔開(kāi)蠢莺，符號(hào)表?xiàng)l目中僅存放指向該字符串首字符的指針).

（2）名字的作用域

☆ 程序語(yǔ)言范圍的劃分可以有兩種劃分范圍的方式：并列和嵌套

☆ 名字的作用域規(guī)則：規(guī)定一個(gè)名字在什么樣的范圍內(nèi)應(yīng)該表示什么意義.

<1> 靜態(tài)作用域規(guī)則（static-scope rule）：編譯時(shí)就可以確定名字的作用域,即僅從靜態(tài)讀程序就可確定名字的作用域
<2> 最近嵌套規(guī)則（most closely nested）：名字的聲明在離其最近的內(nèi)層起作用

（3）線性表

符號(hào)表以棧(線性表)的方式組織.

線性表上的操作：查找、插入零如、刪除躏将、修改

查找：從表頭(棧頂)開(kāi)始，遇到的第一個(gè)符合條件的名字考蕾；插入：先查找祸憋，再加入在表頭（棧頂）；

關(guān)鍵字 = 名字＋作用域肖卧；

（4）散列表

名字掛在兩個(gè)鏈上(便于刪除操作)：

1. 散列鏈(hash link)： 鏈接所有具有相同hash值的元素蚯窥，表頭在表頭數(shù)組中；
2. 作用域鏈(scope link)：鏈接所有在同一作用域中的元素塞帐，表頭在作用域表中.

☆ 操作：查找拦赠、插入、刪除

4. 聲明語(yǔ)句的翻譯

（1）變量的聲明

☆ 一個(gè)變量的聲明應(yīng)該由兩部分來(lái)完成：類型的定義和變量的聲明

• 類型定義：為編譯器提供存儲(chǔ)空間大小的信息
• 變量聲明：為變量分配存儲(chǔ)空間
• 組合數(shù)據(jù)的類型定義和變量聲明：定義與聲明在一起葵姥，定義與聲明分離.

1> 簡(jiǎn)單數(shù)據(jù)類型的存儲(chǔ)空間是預(yù)先確定的荷鼠，如int可以占4個(gè)字節(jié)，double可以占8個(gè)字節(jié)榔幸，char可以占1個(gè)字節(jié)等

2> 組合數(shù)據(jù)類型變量的存儲(chǔ)空間允乐，需要編譯器根據(jù)程序員提供的信息計(jì)算而定.

（2） 過(guò)程

1．過(guò)程（procedure）：過(guò)程頭(做什么) ＋  過(guò)程體(怎么做)矮嫉；
   - 函數(shù):  有返回值的過(guò)程
   - 主程序:  被操作系統(tǒng)調(diào)用的過(guò)程/函數(shù)

2．過(guò)程的三種形式：過(guò)程定義、過(guò)程聲明和過(guò)程調(diào)用牍疏。
   過(guò)程定義：過(guò)程頭+過(guò)程體蠢笋；
   過(guò)程聲明：過(guò)程頭；

3. 左值與右值 
   1> 直觀上鳞陨，出現(xiàn)在賦值號(hào)左邊和右邊的量分別稱為左值和右值昨寞；
   2> 實(shí)質(zhì)上，左值必須具有存儲(chǔ)空間炊邦，右值可以僅是一個(gè)值编矾，而沒(méi)有存儲(chǔ)空間.
   3> 形象地講，左值是容器馁害，右值是內(nèi)容.
   
4. 參數(shù)傳遞
   1> 形參與實(shí)參
        - 聲明時(shí)的參數(shù)稱為形參(parameter或formal parameter)
        - 引用時(shí)的參數(shù)稱為實(shí)參(argument或actual parameter)
   2> 常見(jiàn)的參數(shù)傳遞形式：（不同的語(yǔ)言提供不同的形式）
        - 值調(diào)用（call by value）---過(guò)程內(nèi)部對(duì)參數(shù)的修改，不影響作為實(shí)參的變量原來(lái)的值.
        - 引用調(diào)用（call by reference）--- 過(guò)程內(nèi)部對(duì)形參的修改蹂匹，實(shí)質(zhì)上是對(duì)實(shí)參的修改.
        - 復(fù)寫(xiě)－恢復(fù)（copy-in/copy-out）--- ① 過(guò)程內(nèi)對(duì)參數(shù)的修改不直接影響實(shí)參碘菜，避免了副作用;
                                        ② 返回時(shí)將形參內(nèi)容恢復(fù)給實(shí)參，實(shí)現(xiàn)參數(shù)值的返回.
        - 換名調(diào)用（call by name）--- 宏調(diào)換
   3> 參數(shù)傳遞方法的本質(zhì)區(qū)別： 實(shí)參是代表左值限寞、右值忍啸、還是實(shí)參本身的正文.
   
5. 作用域信息的保存
☆ 能夠畫(huà)出嵌套過(guò)程的嵌套關(guān)系樹(shù)(P191 4.33),根據(jù)語(yǔ)法制導(dǎo)翻譯(P193 4.35)畫(huà)出分析樹(shù),寫(xiě)出推導(dǎo)步驟,構(gòu)造的符號(hào)表

5. 簡(jiǎn)單算術(shù)表達(dá)式與賦值句

P197 例4.36 主要是變量類型的轉(zhuǎn)換

6. 數(shù)組元素的引用

（1）數(shù)組元素的地址計(jì)算

• 注意是行主存儲(chǔ)還是列主存儲(chǔ)

（2）☆數(shù)組元素引用的語(yǔ)法制導(dǎo)翻譯(考試熱點(diǎn)之一)

• P201 例4.37

7. 布爾表達(dá)式

布爾表達(dá)式的計(jì)算有兩種方法：數(shù)值表示的直接計(jì)算和邏輯表示的短路計(jì)算

☆ 布爾表達(dá)式短路計(jì)算的翻譯：短路計(jì)算的控制流，真出口與假出口履植，真出口鏈與假出口鏈计雌，拉鏈回填技術(shù)(P207 例4.41)（考試熱點(diǎn)之一）

8. 控制語(yǔ)句

控制語(yǔ)句的分類：①無(wú)條件轉(zhuǎn)移、②條件轉(zhuǎn)移玫霎、③循環(huán)語(yǔ)句凿滤、④分支語(yǔ)句

• 無(wú)條件轉(zhuǎn)移(goto)\條件轉(zhuǎn)移(if、while)
• 條件轉(zhuǎn)移的語(yǔ)法制導(dǎo)翻譯：P213 例4.42

多看課件PPT庶近，多做題練手