【正文】 4 自下而上分析 1. 分析方法： 歸約 (推導(dǎo)的逆過(guò)程 )，從葉子到根構(gòu)造分析樹； 2. 基本概念： 短語(yǔ)、直接短語(yǔ)、句柄、歸約、規(guī)范歸約； 3. 采用的方法 : 用移進(jìn) 歸約方法實(shí)現(xiàn)剪句柄（格局中的兩個(gè)關(guān)鍵動(dòng)作），關(guān)鍵問(wèn)題是如何確定棧頂已經(jīng)形成句柄，當(dāng)句柄形成時(shí)，如何判定采用哪個(gè)產(chǎn)生式進(jìn)行規(guī)約； 4. 識(shí)別活前綴的 DFA： 活前綴與 LR(0)項(xiàng)目 (NFA狀態(tài) )，拓廣文法與子集法構(gòu)造 DFA； T → . T * F. . .αT → T . * FTT → T * . F*T → T * F .F? 一個(gè)產(chǎn)生式是一個(gè)識(shí)別活前綴的 NFA ? 一個(gè) LR(0)項(xiàng)目是 NFA的一個(gè)狀態(tài) 15 4 自下而上分析（續(xù)） 5. DFA分析輸入序列： 有效項(xiàng)目、可移進(jìn)項(xiàng)目、可規(guī)約項(xiàng)目、移進(jìn) /歸約沖突、歸約 /歸約沖突；解決沖突的方法－SLR(1)：簡(jiǎn)單向前看一個(gè)終結(jié)符（計(jì)算歸約項(xiàng)非終結(jié)符的FOLLOW，與可移進(jìn)終結(jié)符比較）； 6. 移進(jìn) 歸約分析表： 動(dòng)作表＋轉(zhuǎn)移表； 7. LR文法與 LR分析： LR(0)、 SLR(1)、 LALR(1)、 LR(1)。 A → β1. β2B → β1. α β1習(xí)題與試題 （ 略過(guò)語(yǔ)法制導(dǎo)翻譯 ） 16 第四章 語(yǔ)法制導(dǎo)翻譯生成中間代碼 本章討論程序設(shè)計(jì)語(yǔ)言的靜態(tài)語(yǔ)義分析 ， 并且在語(yǔ)法分析的基礎(chǔ)上生成中間代碼 ， 采用的基本方法是語(yǔ)法制導(dǎo)翻譯 。 與前兩章詞法分析和語(yǔ)法分析不同的是 ， 詞法分析和語(yǔ)法分析的討論側(cè)重于理論 ， 而本章則側(cè)重于結(jié)合程序設(shè)計(jì)語(yǔ)言的實(shí)際例子討論語(yǔ)言結(jié)構(gòu)的具體翻譯方法和一些實(shí)用的技術(shù) 。 主要內(nèi)容 1 語(yǔ)法制導(dǎo)翻譯與中間代碼 2 符號(hào)表的組織 3 聲明語(yǔ)句的翻譯 4 可執(zhí)行語(yǔ)句的翻譯 17 1 語(yǔ)法制導(dǎo)翻譯與中間代碼 1. 語(yǔ)法與語(yǔ)義：語(yǔ)法和語(yǔ)義描述語(yǔ)言的不同方面、二者之間沒(méi)有嚴(yán)格界線、語(yǔ)義形式化描述的困難性； 2. 屬性：用屬性表示語(yǔ)義特征（語(yǔ)義值），屬性的計(jì)算和屬性之間的依賴關(guān)系； 3. 語(yǔ)法制導(dǎo)翻譯：為產(chǎn)生式配上 “ 語(yǔ)義規(guī)則 ” 并在適當(dāng)?shù)臅r(shí)刻執(zhí)行；語(yǔ)義規(guī)則的兩種形式； 4. 分析方法與翻譯方案：以語(yǔ)法分析為基礎(chǔ)，分析樹的作用； 5. 中間代碼：為什么生成中間代碼，中間代碼的特征，各種形式的中間代碼及它們之間的關(guān)系，最常用中間代碼形式。 18 3 聲明語(yǔ)句的翻譯 1. 定義與聲明：類型定義與變量聲明，過(guò)程定義與過(guò)程聲明 2. 變量聲明：符號(hào)表信息的填寫 3. 過(guò)程聲明： ? 左值與右值 ? 參數(shù)傳遞：參數(shù)傳遞的不同形式 ? 名字的作用域：靜態(tài)作用域與最近嵌套原則 ? 聲明中作用域信息的保存 1. 符號(hào)表的條目與信息的存儲(chǔ)（關(guān)鍵字＋內(nèi)容） 2. 作用域信息的保存（棧結(jié)構(gòu)） 3. 線性表與散列表 2 符號(hào)表的組織 19 4 可執(zhí)行語(yǔ)句的翻譯 1. 簡(jiǎn)單算術(shù)表達(dá)式和賦值句的翻譯：語(yǔ)法制導(dǎo)翻譯的設(shè)計(jì)，類型轉(zhuǎn)換； 2. 數(shù)組元素的引用：數(shù)組元素地址計(jì)算的遞推公式，地址的可變部分與不變部分，可變部分計(jì)算的語(yǔ)法制導(dǎo)翻譯； 3. 布爾表達(dá)式短路計(jì)算的翻譯：為什么需要短路計(jì)算，短路計(jì)算的控制流，真出口與假出口，真值鏈與假值鏈； 4. 控制語(yǔ)句的翻譯：控制語(yǔ)句的分類，無(wú)條件轉(zhuǎn)移與條件轉(zhuǎn)移，拉鏈 /回填技術(shù)； 習(xí)題與試題 ? 認(rèn)真復(fù)習(xí)，重點(diǎn)是掌握基本概念?；靖拍钫莆樟?，相當(dāng)一部分試題的解就有了。 ? 習(xí)題與試題的目的區(qū)別：習(xí)題的目的是通過(guò)反復(fù)的練習(xí)理解、掌握所學(xué)知識(shí)，會(huì)有不少繁、難、大量步驟的題；試題的目的是考察對(duì)本課程綜合掌握的情況，特點(diǎn)是短時(shí)間內(nèi)覆蓋大量?jī)?nèi)容。太繁瑣步驟或太難等需要耗費(fèi)大量時(shí)間的題是不可能出的，大部分應(yīng)該是基本概念題，但也會(huì)有一些綜合性的題目。 ? 自己要會(huì)辨別什么是主要的什么是次要的，抓什么丟什么?！?基本概念要嚴(yán)謹(jǐn)（清楚），基本方法要靈活 ” 。 ? 總之一句話，學(xué)習(xí)方法的掌握是個(gè)人努力的結(jié)果，單純靠別人教是學(xué)不會(huì)的。 21 關(guān)于考試 ? 題目類型： 簡(jiǎn)答題 (25分 )、 填空題 (25分 )、 計(jì)算題 (50分 ) ? 考試范圍： 1－ 4章講過(guò)的內(nèi)容 ? 側(cè)重考察： 基本概念與基本方法的掌握 易犯的錯(cuò)誤 1. 不認(rèn)真審題（對(duì)題目的要求理解錯(cuò)誤：意思理解錯(cuò)、難題想容易、容易題想難。關(guān)鍵問(wèn)題是基本概念不清楚） 2. 所答非所問(wèn) (例如：沒(méi)有要求 LL分析卻將文法改為 LL的 ) 3. 畫蛇添足 (例如：僅問(wèn)有無(wú)沖突卻將分析表先構(gòu)造出來(lái) ) 4. 偷工減料 (例如：有若干問(wèn)，僅回答部分或問(wèn)題僅答一半 ) 警示 千萬(wàn)不要作弊！命運(yùn)掌握在自己的手中！ 實(shí)際試題舉例 一、簡(jiǎn)答題 1（ 2分 ） 有哪些方法可以去除文法的二義性 。 2（ 2分 ） 寫出 ((a+b)*c)+d 的后綴式 。 3（ 4分 ） 試證明正規(guī)式 (ab)*a與 a(ba)*是等價(jià)的 。 1 （ 1） 改寫文法 （ 2） 規(guī)定文法符號(hào)的優(yōu)先級(jí)和結(jié)合性 2 ab+c*@d+（ 或 ab+c*d+） 3 證明： 考慮 L((ab)*a)中的任意一個(gè)串 ababab...aba， 由串連接的結(jié)合性可得： a(ba)(ba)(b...a)(ba)，它恰好是 L(a(ba)*)，即 L((ab)*a)= L(a(ba)*)。 也可以用歸納法證明（提示：以 ab重復(fù) 0次、 1次作為歸納基礎(chǔ)，假設(shè) ab重復(fù) n次成立，證明 ab重復(fù) n+1次也成立）。 二、填空題（ 30分） 1（ 6分 ） 編譯程序的基本組成有：詞法分析 、 、 、中間代碼生成 、 、 、 和 。 2（ 1分 ） 正規(guī)式 r和 s等價(jià)說(shuō)明 相同 。 3（ 2分 ） 不含子串 baa的所有 a、 b符號(hào)串的正規(guī)式是 。 4（ 4分） 已知文法 G定義如下： S→eT|RT T→DR|ε R→dR|ε D→a|bd 則 FIRST(S)= ， FIRST(D)= ， FIRST(T)= ， FIRST(R)= 。 1 語(yǔ)法分析 、 語(yǔ)義分析 、 代碼優(yōu)化 、 目標(biāo)代碼生成 、 符號(hào)表管理 和 出錯(cuò)處理 2 r和