編譯原理期末復(fù)習(xí)

1、Lecture02：實(shí)驗(yàn)導(dǎo)引詞法分析簡(jiǎn)介、語(yǔ)法分析簡(jiǎn)介、語(yǔ)法分析樹(shù)（具體語(yǔ)法樹(shù)）、抽象語(yǔ)法樹(shù)Lex&Yacc簡(jiǎn)介L(zhǎng)ecture03：詞法分析詞法分析概述詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)（狀態(tài)轉(zhuǎn)換圖、擴(kuò)展巴克斯范式EBNF 描述詞法規(guī)則）詞法分析程序自動(dòng)構(gòu)造PL/0代碼Lecture04：自頂向下語(yǔ)法分析基本思想（按給定文法和終結(jié)符號(hào)串進(jìn)行推導(dǎo)）確定的自頂向下分析消除第一類不確定（帶回溯的自頂向下分析、最左推導(dǎo)）消除第二類不確定（自頂向下預(yù)測(cè)分析）LL(1) 分析第一個(gè) “L” 代表從左向右掃描單詞符號(hào)，第二個(gè) “L” 代表產(chǎn)生的是最左推導(dǎo)，“1” 代表向前查看（lookahead）一個(gè)單詞符號(hào)。Fir

2、st 集合：一個(gè)句型若可以推導(dǎo)出另一個(gè)以終結(jié)符 a 開(kāi)頭的句型，那么 a 屬于First（）；若可以推導(dǎo)出 ，那么 屬于 First（）Follow 集合：，若 G 中存在一個(gè)包含子串 Xa 的句型，那么 a 屬于 Follow(X)；G 中存在一個(gè)以 X 結(jié)尾的句型，那么 # 屬于 Follow(X)。預(yù)測(cè)集合 PS (A-) 定義如下：如果不屬于First ()，那么 PS (A-) = First () ；如果First ()，那么 PS (A-) = ( First () ) Follow(A)LL（1）分析的實(shí)現(xiàn)遞歸下降 LL（1）分析程序表驅(qū)動(dòng) LL（1）分析程序預(yù)測(cè)分析表：表的每

3、一行對(duì)應(yīng)一個(gè)非終結(jié)符，表的每一列對(duì)應(yīng)某個(gè)終結(jié)符或輸入結(jié)束符#，表中的項(xiàng)是一個(gè)產(chǎn)生式集合。對(duì)文法 G 的每個(gè)產(chǎn)生式，若它的預(yù)測(cè)集合 PS(A-) 中包含 aVT#，那么將A-加入 表項(xiàng)MA,a。當(dāng) M(A,a) 不含產(chǎn)生式時(shí)，就對(duì)應(yīng)一個(gè)出錯(cuò)位置。一個(gè)文法 G 的預(yù)測(cè)分析表中每個(gè)表項(xiàng)最多只包含一個(gè)產(chǎn)生式，當(dāng)且僅當(dāng) G是 LL(1) 文法。對(duì)于LL（1）文法，預(yù)測(cè)分析表也稱為L(zhǎng)L（1）分析表。表驅(qū)動(dòng) LL（1）分析程序的工作原理為：初始時(shí)，下推棧只包含 #；首先將文法開(kāi)始符號(hào)入棧；然后執(zhí)行如下步驟：（1）若棧頂為終結(jié)符，則判斷當(dāng)前讀入的單詞符號(hào)是否與該終結(jié)符相匹配，若匹配，再讀取下一單詞符號(hào)繼續(xù)分析

4、；若不匹配，則進(jìn)行錯(cuò)誤處理。（2）若棧頂為非終結(jié)符，則根據(jù)該非終結(jié)符和當(dāng)前輸入單詞符號(hào)查L(zhǎng)L（1）分析表，若相應(yīng)表項(xiàng)中是產(chǎn)生式（唯一的），則將此非終結(jié)符出棧，并把產(chǎn)生式右部符號(hào)從右至左入棧；若表項(xiàng)為空，則進(jìn)行錯(cuò)誤處理。（3）重復(fù)（1）和（2），直到棧頂為 # 同時(shí)輸入也遇到結(jié)束符 # 時(shí)，分析結(jié)束。 文法變換：消除左遞歸、提取左公因子（構(gòu)造出所期望的文法類型）左遞歸的，直接左遞歸，間接左遞歸。包含左遞歸或左公因子的文法一般不是LL(1) 的。如果對(duì)非終結(jié)符的不同排序方式，依上述步驟消除一般左遞歸后所得到的文法從形式上看可能會(huì)有區(qū)別，但它們之間是相互等價(jià)的。提取左公因子LL(1) 分析中的出錯(cuò)處

5、理一是報(bào)錯(cuò)，發(fā)現(xiàn)錯(cuò)誤時(shí)應(yīng)盡可能準(zhǔn)確指出錯(cuò)誤位置和錯(cuò)誤屬性；二是錯(cuò)誤恢復(fù)，盡可能進(jìn)行校正，使編譯工作可以繼續(xù)下去，提高程序調(diào)試的效率。對(duì)于表驅(qū)動(dòng) LL（1）分析，在以下兩種情況下需要報(bào)錯(cuò)：棧頂?shù)慕K結(jié)符與當(dāng)前輸入符號(hào)不匹配；非終結(jié)符A 位于棧頂，面臨的輸入符號(hào)為a，但分析表 M 的表項(xiàng) MA , a 為空。短語(yǔ)層恢復(fù)Lecture05：自底向上語(yǔ)法分析基本思想（按給定文法和終結(jié)符號(hào)串進(jìn)行歸約）兩種不確定（在每一步歸約中，選擇哪個(gè)產(chǎn)生式，以及匹配哪個(gè)位置上的子串）對(duì)于文法的某個(gè)句型或句子，如果一個(gè)子串根據(jù)某個(gè)產(chǎn)生式歸約后，得到文法的另一個(gè)句型，那么我們稱這樣的子串為可歸約串；如果沒(méi)有這樣的產(chǎn)生式，那

6、么它就是不可歸約的串?？偸沁x擇某個(gè)“可歸約串”進(jìn)行歸約，可大大減少回溯。短語(yǔ)和直接短語(yǔ)某個(gè)句型的短語(yǔ)：先給出以所考慮的句型為果實(shí)的分析樹(shù)，每個(gè)非葉子結(jié)點(diǎn)（的子樹(shù)果實(shí)串）與該句型的一個(gè)短語(yǔ)是一一對(duì)應(yīng)的。直接短語(yǔ)：在句型的分析樹(shù)中，只包含直接子孫的非葉子結(jié)點(diǎn)（的子樹(shù)果實(shí)串）與該句型的直接短語(yǔ)是一一對(duì)應(yīng)的。句柄（只適合于右句型，如果文法無(wú)二義，則句柄是唯一的）句型的直接短語(yǔ)不唯一，通常的做法是選擇最左邊的直接短語(yǔ)進(jìn)行歸約。一個(gè)終結(jié)符串是合法的，即屬于 L(G)，當(dāng)且僅當(dāng)它是一個(gè)右句型?？梢栽谧缘紫蛏戏治龅拿恳徊街兄皇褂镁浔M(jìn)行歸約，如果我們把這種按照句柄進(jìn)行歸約的過(guò)程逆過(guò)來(lái)，實(shí)際上就相當(dāng)于一個(gè)最右推

7、導(dǎo)過(guò)程。某個(gè)句型的句柄：任何一個(gè)句子一定是右句型，做它的最右推導(dǎo)，最后一步產(chǎn)生式的右邊即是句柄?；蛘?，畫(huà)分析樹(shù)，先找出所有的直接短語(yǔ)，最左邊的直接短語(yǔ)就是句柄。移進(jìn)-歸約分析（實(shí)現(xiàn)自底向上分析最常用的技術(shù)）基于有限狀態(tài)控制的分析引擎根據(jù)當(dāng)前狀態(tài)、分析棧當(dāng)前內(nèi)容、余留的輸入符號(hào)串來(lái)唯一確定如下動(dòng)作之一，然后進(jìn)入新?tīng)顟B(tài)：Reduce: 依確定的產(chǎn)生式序列對(duì)位于棧頂?shù)亩陶Z(yǔ)進(jìn)行歸約。Shift: 從輸入序列移進(jìn)一個(gè)單詞符號(hào)。Error: 發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，進(jìn)行錯(cuò)誤處理/恢復(fù)。Accept：分析成功。在進(jìn)行Reduce 動(dòng)作時(shí)可將短語(yǔ)、直接短語(yǔ)、或句柄替換為某個(gè)非終結(jié)符。LR 分析方法中，是對(duì)句柄進(jìn)行歸約。

8、移進(jìn)-歸約分析過(guò)程確定化的關(guān)鍵是解決好兩類沖突：移進(jìn)-歸約沖突和歸約-歸約沖突。移進(jìn)-歸約沖突是指到達(dá)一個(gè)不能確定下一步應(yīng)該移進(jìn)還是應(yīng)該歸約的狀態(tài)。歸約-歸約沖突是指到達(dá)一個(gè)可以對(duì)多個(gè)短語(yǔ)進(jìn)行歸約的狀態(tài)。為解決這些沖突，經(jīng)常采用向前查看確定數(shù)目的單詞符號(hào)、規(guī)定特定優(yōu)先關(guān)系等技術(shù)。然而，不可能找到通用的解決方法適合于任何文法。為簡(jiǎn)化狀態(tài)控制，通常會(huì)借助于一張分析表，稱之為表驅(qū)動(dòng)的移進(jìn)-歸約分析方法。LR 分析方法LR 中的“L” 代表從左向右掃描單詞符號(hào)，“R” 代表產(chǎn)生的是最右推導(dǎo)。最右推導(dǎo)的逆過(guò)程對(duì)應(yīng)于自底向上的每一步對(duì)句柄進(jìn)行歸約。分析過(guò)程中使用的分析表稱為 LR分析表，分析棧稱為狀態(tài)分析

9、棧，簡(jiǎn)稱狀態(tài)棧。（之前的分析棧稱為符號(hào)分析棧，簡(jiǎn)稱符號(hào)棧）ACTION表：告訴分析引擎，棧頂狀態(tài)為k, 當(dāng)前輸入單詞符號(hào)是 a 時(shí)應(yīng)該完成的動(dòng)作。ACTION k,a = si， Shift：狀態(tài) i 移進(jìn)棧頂ACTION k,a = rj， Reduce：按第 j 條產(chǎn)生式歸約ACTION k,a = acc， Accept：分析完成ACTION k,a = err，Error：發(fā)現(xiàn)錯(cuò)誤 （常標(biāo)為空白）GOTO表：GOTOi,A = j ，告訴分析引擎，在依產(chǎn)生式 A-歸約之后，位于棧頂?shù)臓顟B(tài)如何改變。依產(chǎn)生式 A-歸約時(shí)，要將棧頂?shù)膢個(gè)狀態(tài)彈出，假設(shè)此時(shí)位于棧頂?shù)臓顟B(tài)是 i，那么就將新?tīng)顟B(tài)

10、為 j 移進(jìn)棧頂。LR分析表的每行對(duì)應(yīng)分析引擎的一個(gè)狀態(tài)；初始狀態(tài)通常表示為0。ACTION 表的每一列對(duì)應(yīng)一個(gè)輸入單詞符號(hào)或#，表項(xiàng)取值為 err 時(shí)用空白表示。GOTO 表的每一列對(duì)應(yīng)一個(gè)文法非終結(jié)符。LR（0）、SLR（1）、LR（1） 和LALR（1） 等分析方法有著不同的分析能力，所適合的文法分別稱為 LR（0） 文法、SLR（1） 文法、LR（1） 文法和 LALR（1） 文法。這些方法采用了結(jié)構(gòu)上是一致的分析表，即LR 分析表，只是構(gòu)造方法上存在差異?！?” 代表向前查看 0 個(gè)符號(hào)，“1” 代表向前查看 1 個(gè)符號(hào)，SLR（1）代表 Simple LR（1），LALR（1） 代

11、表Look Ahead LR（1）。LR（0） 分析文法G = (VN , VT , P , S )增加產(chǎn)生式S-S，S不屬VNVT，得增廣文法G = (VN , VT , P , S )。增廣文法的開(kāi)始符號(hào)不會(huì)出現(xiàn)在任何產(chǎn)生式的右部，若原文法的開(kāi)始符號(hào)已經(jīng)滿足這個(gè)條件，那么可以不作這樣的改造?；钋熬YLR（0）有限狀態(tài)機(jī)一個(gè)LR（0） 項(xiàng)目是在右端某一位置有圓點(diǎn)的產(chǎn)生式。圓點(diǎn)標(biāo)志著已分析過(guò)的串與該產(chǎn)生式匹配的位置，根據(jù)該位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符或?yàn)榭?，把?xiàng)目分為以下幾種：移進(jìn)項(xiàng)目: 形如A-.a，其中a為終結(jié)符，、為（非）終結(jié)符或空。待約項(xiàng)目: 形如A-.B歸約項(xiàng)目: 形如A-.接受項(xiàng)

12、目: 形如S-S.LR（0）有限狀態(tài)機(jī)的任一狀態(tài)是某個(gè)LR（0）項(xiàng)目集 I 的閉包CLOSURE(I)。該方法構(gòu)造的 LR（0）有限狀態(tài)機(jī)可以看作一個(gè)以（非）終結(jié)符為字母表的 DFA。如果假定除了（沒(méi)有繪出的）死狀態(tài)是非終態(tài)外，其余都是終態(tài)，那么可有結(jié)論：該DFA的語(yǔ)言是文法 G 的所有活前綴的集合。，即任何句型按該DFA不會(huì)錯(cuò)過(guò)任何可歸約的句柄，該DFA 的所有可接受的符號(hào)串都是活前綴。LR（0）分析表LR（0）分析表可以直接從LR（0）有限狀態(tài)機(jī)得到LR（0） 分析表的一些表項(xiàng)可能會(huì)被多重定義，即被不止一個(gè) rj 或 sj 賦值。這種情況下不合適進(jìn)行LR 分析過(guò)程。如果各表項(xiàng)均無(wú)多重定義，

13、則稱它為相應(yīng)文法 G的一張 LR（0）表，并稱 G 為一個(gè) LR（0）文法。文法 G 是 LR（0）文法，當(dāng)且僅當(dāng)它 的LR（0）有限狀態(tài)機(jī)中的每個(gè)狀態(tài)都滿足：不同時(shí)含有移進(jìn)項(xiàng)目和歸約項(xiàng)目，即不存在移進(jìn)-歸約沖突；不含有兩個(gè)以上歸約項(xiàng)目，即不存在歸約-歸約沖突。SLR（1） 分析通過(guò)向前查看一個(gè)輸入符號(hào)，可以根據(jù)這一符號(hào)是否屬于要?dú)w約的非終結(jié)符的Follow 集來(lái)決定是否進(jìn)行歸約。如果可以使LR（0） 有限狀態(tài)機(jī)中所有狀態(tài)的沖突問(wèn)題得到解決，那么就可以進(jìn)行正常LR 分析。稱這種方法為SLR（1）分析方法，它的基本原理是檢查L(zhǎng)R（0） 有限狀態(tài)機(jī)的所有狀態(tài)是否有沖突，并借助于以下兩個(gè)方面來(lái)解決沖

14、突問(wèn)題：如果每一狀態(tài)歸約項(xiàng)中要?dú)w約的非終結(jié)符的 Follow 集互不相交，則可解決歸約-歸約沖突。如果每一狀態(tài)歸約項(xiàng)中要?dú)w約的非終結(jié)符的 Follow 集與該狀態(tài)所有移進(jìn)項(xiàng)要移進(jìn)的符號(hào)集互不相交，則可以解決移進(jìn)-歸約沖突。只需對(duì) LR（0）分析表進(jìn)行簡(jiǎn)單修改，使得歸約表項(xiàng)只適用于相應(yīng)非終結(jié)符Follow 集中的輸入符號(hào)，就可得到 SLR（1） 分析表。SLR（1） 分析表中一些表項(xiàng)可能會(huì)被多重定義，即被不止一個(gè) rj 或 sj 賦值。這種情況不合適進(jìn)行 LR 分析。如果各表項(xiàng)均無(wú)多重定義，則稱它為相應(yīng)文法 G的一張 SLR（1） 表，并稱 G 為一個(gè) SLR（1） 文法。文法 G 是 SLR（

15、1） 文法，當(dāng)且僅當(dāng)它 的LR（0） 有限狀態(tài)機(jī)中的每個(gè)狀態(tài)都滿足：對(duì)該狀態(tài)的任何項(xiàng)目A-.a（a為終結(jié)符），不存在項(xiàng)目 B-.，使得a屬于Follow(B)，即不存在移進(jìn)-歸約沖突。對(duì)該狀態(tài)的項(xiàng)目A-.和 B-.，滿足Follow(A)交Follow(B) =空，即不存在歸約-歸約沖突。SLR（1）分析和LR（0）分析區(qū)別在歸約句柄時(shí)，前者要向前查看一個(gè)輸入符號(hào)，看是否屬于要?dú)w約的非終結(jié)符的 Follow集，若是則歸約，否則出錯(cuò)處理。而后者無(wú)論下一個(gè)輸入符號(hào)是什么都進(jìn)行歸約。LR（0）分析出錯(cuò)處理會(huì)比SLR（1）分析晚一些。區(qū)別體現(xiàn)在表上：在 LR（0） 表的 ACTION 表中，歸約表項(xiàng)總

16、是整行出現(xiàn)的，即每一個(gè)歸約動(dòng)作都是對(duì)應(yīng)所有輸入符；同時(shí)，在任何一行，不會(huì)既有移進(jìn)表項(xiàng)又有歸約表項(xiàng)。在 SLR（1） 表的 ACTION 表中，歸約表項(xiàng)只適用于相應(yīng)非終結(jié)符 Follow 集中的輸入符號(hào)；在同一行，可以既有移進(jìn)表項(xiàng)又有歸約表項(xiàng)。LR（1）分析SLR（1）分析方法只考慮到所歸約非終結(jié)符的 Follow 符號(hào)。但一個(gè)輸入符號(hào)屬于所歸約非終結(jié)符的 Follow集合，未必就是句柄可以后跟的符號(hào)。LR（1）項(xiàng)目是在 LR（0）項(xiàng)目基礎(chǔ)上增加一個(gè)終結(jié)符，稱為向前搜索符，表示產(chǎn)生式右端完整匹配后所允許在余留符號(hào)串中的下一個(gè)終結(jié)符。LR（1） 分析表一個(gè)文法的 LR（1） 分析表中的一些表項(xiàng)有可

17、能會(huì)被不止一個(gè) rj 或 sj 賦值。這種情況不合適進(jìn)行 LR分析的。如果各表項(xiàng)均無(wú)多重定義，則稱它為相應(yīng)文法 G 的一張 LR（1） 表，并稱 G 為一個(gè) LR（1） 文法。文法 G 是 LR（1） 文法，當(dāng)且僅當(dāng)它 的LR（1） 有限狀態(tài)機(jī)中的每個(gè)狀態(tài)都滿足：如果該狀態(tài)含有項(xiàng)目 A-.a, b （a為終結(jié)符），那么就不會(huì)有項(xiàng)目B-., a ；反之亦然。這表明該狀態(tài)不存在移進(jìn)-歸約沖突。該狀態(tài)中的所有歸約項(xiàng)目的向前搜索符互不相交，即不同時(shí)含有項(xiàng)目 B-., a 和 B-., a。這表明該狀態(tài)不存在歸約-歸約沖突。LALR（1） 分析可以采用 SLR（1） 分析的文法一定可以采用 LR（1）

18、分析；但反之不成立。表明：在所有以確定方式工作的分析程序中，LR（1） 分析程序已經(jīng)達(dá)到了最強(qiáng)的分析能力。通過(guò)合并 LR（1）有限狀態(tài)機(jī)中的同芯狀態(tài)，可得到相應(yīng)的 LALR（1） 有限狀態(tài)機(jī)。LR（1）項(xiàng)目 A-., a 中的A-.部分稱為該項(xiàng)目的芯。對(duì)于兩個(gè)狀態(tài)，如果只考慮每個(gè)項(xiàng)目的芯時(shí)它們是完全相同的項(xiàng)目集合，那么這兩個(gè)狀態(tài)就是同芯狀態(tài)。合并同芯狀態(tài)是將相互之間是同芯的狀態(tài)合并為同一個(gè)狀態(tài)，即將所有這些狀態(tài)的項(xiàng)目集合全部并起來(lái)。（合并向前搜索符）對(duì)于兩個(gè)同芯狀態(tài)，由 GO 函數(shù)得到的針對(duì)任何符號(hào)的后繼狀態(tài)仍然同芯。所有合并后的新?tīng)顟B(tài)、未合并的狀態(tài)以及改造后的GO 函數(shù)，一起構(gòu)成了一個(gè)新的L

19、R（1） 有限狀態(tài)機(jī)，稱之為 LALR（1） 有限狀態(tài)機(jī)。合并同芯狀態(tài)后，不會(huì)產(chǎn)生新的移進(jìn)-歸約沖突，但有可能產(chǎn)生新的歸約-歸約沖突。一個(gè) LR（1） 文法，如果將其LR（1） 有限狀態(tài)機(jī)的同芯狀態(tài)合并后所得到的LALR（1） 有限狀態(tài)機(jī)中的全部狀態(tài)無(wú)歸約-歸約沖突，則該文法是一個(gè) LALR（1） 文法。 LALR（1）狀態(tài)數(shù)目實(shí)際上與LR（0） 有限狀態(tài)機(jī)相同，分析要強(qiáng)于SLR（1） 分析。二義文法在LR 分析中的應(yīng)用如果對(duì)語(yǔ)義（即可以產(chǎn)生的語(yǔ)言）進(jìn)行一些合限定，那么有可能構(gòu)造出相應(yīng)的LR 分析程序。規(guī)定*的優(yōu)先級(jí)高于 +，以及* 和 + 都服從左結(jié)合性。規(guī)定最近嵌套匹配原則。LR 分析中的

20、錯(cuò)誤處理自底向上分析處理語(yǔ)法錯(cuò)誤更準(zhǔn)確。原因在于推導(dǎo)時(shí)僅觀察可推導(dǎo)出的輸入串的一部分，而歸約時(shí)可歸約的輸入串整體已全部出現(xiàn)，并且輸入符號(hào)是在查看后才被移進(jìn)的。應(yīng)急恢復(fù)即興恢復(fù)幾類分析文法之間的關(guān)系所有的LR（0）文法都是SLR（1）文法。所有的SLR（1）文法都是 LALR（1）文法。所有的LALR（1）文法都是 LR（1）文法。所有的LL（1）文法都是 LR（1）文法。所有的LR（1）文法都是 無(wú)二義文法。這些結(jié)論的逆命題是不成立的。如果已知一個(gè)文法是二義的，那么它一定不是 LR（1）文法或者 LL（1）文法。Lecture06：符號(hào)表符號(hào)表的作用符號(hào)表自創(chuàng)建后便開(kāi)始被用于收集符號(hào)（標(biāo)識(shí)符）

21、的屬性信息。在語(yǔ)義分析中，符號(hào)表所登記的內(nèi)容將用于上下文語(yǔ)義的合法性檢查的依據(jù)。同一標(biāo)識(shí)符可能在程序不同地方出現(xiàn)，而有關(guān)該符號(hào)的屬性是在不同情況下收集的，需檢查標(biāo)識(shí)符屬性在上下文中的一致性和合法性。在目標(biāo)代碼生成階段，符號(hào)表是對(duì)符號(hào)名進(jìn)行地址分配的依據(jù)。符號(hào)表的組織與結(jié)構(gòu)還需要體現(xiàn)符號(hào)的作用域與可見(jiàn)性信息。表的常見(jiàn)屬性符號(hào)的名字、符號(hào)的類別、符號(hào)的類型（決定存儲(chǔ)格式與運(yùn)算操作）、符號(hào)的存儲(chǔ)類別和存儲(chǔ)分配信息、符號(hào)的作用范圍與可見(jiàn)性等等。符號(hào)表的實(shí)現(xiàn)創(chuàng)建符號(hào)表、釋放符號(hào)表空間；插入、查詢、修改、刪除表項(xiàng)。體現(xiàn)符號(hào)表的功能和作用，考慮符號(hào)表操作的方便性和高效性，考慮節(jié)省內(nèi)存空間。線性表、有序表、二

22、叉樹(shù)、Hash表。符號(hào)表至少應(yīng)該在靜態(tài)語(yǔ)義分析之前已經(jīng)創(chuàng)建，最常見(jiàn)的情況是在語(yǔ)法分析的同時(shí)創(chuàng)建。符號(hào)表體現(xiàn)作用域與可見(jiàn)性作用域之間可以嵌套，不會(huì)交錯(cuò)對(duì)于程序的某一特殊點(diǎn)而言，該點(diǎn)所在的作用域稱為當(dāng)前作用域當(dāng)前作用域與包含它的程序單元所構(gòu)成的作用域稱為開(kāi)作用域不屬于開(kāi)作用域的作用域稱為閉作用域可見(jiàn)性是指在程序的某一特定點(diǎn)，哪些符號(hào)是可訪問(wèn)的?？梢?jiàn)性規(guī)則：1、在程序的任何一點(diǎn)，只有在該點(diǎn)的開(kāi)作用域中聲明的符號(hào)才是可訪問(wèn)的。2、若符號(hào)在多個(gè)開(kāi)作用域聲明，則把離該符號(hào)的某個(gè)引用最近的聲明作為該引用的解釋。3、新的聲明只能出現(xiàn)在當(dāng)前作用域。多符號(hào)表組織：每個(gè)作用域都有各自的符號(hào)表單符號(hào)表組織：所有嵌套的

23、作用域共用一個(gè)全局符號(hào)表作用域與單符號(hào)表組織：所有嵌套的作用域共用一個(gè)全局符號(hào)表。每個(gè)作用域都對(duì)應(yīng)一個(gè)作用域號(hào)僅記錄開(kāi)作用域中的符號(hào)。當(dāng)某個(gè)作用域成為閉作用域時(shí)，從符號(hào)表中刪除該作用域中所聲明的符號(hào)。 作用域與多符號(hào)表組織每個(gè)作用域都有各自的符號(hào)表。需要維護(hù)一個(gè)符號(hào)表的作用域棧，每個(gè)開(kāi)作用域?qū)?yīng)棧中的一個(gè)入口，當(dāng)前的開(kāi)作用域出現(xiàn)在該棧的棧頂當(dāng)一個(gè)新的作用域開(kāi)放時(shí)，新符號(hào)表將被創(chuàng)建，并將其入棧。在當(dāng)前作用域成為閉作用域時(shí)，從棧頂彈出相應(yīng)的作用域。Lecture07：實(shí)驗(yàn)導(dǎo)引二Lecture08：語(yǔ)法制導(dǎo)的語(yǔ)義計(jì)算基礎(chǔ)詞法和語(yǔ)法正確的源程序，編譯程序就可以對(duì)它進(jìn)行語(yǔ)義分析。若發(fā)現(xiàn)程序存在靜態(tài)一致性

24、或完整性方面的問(wèn)題，則報(bào)告靜態(tài)語(yǔ)義錯(cuò)誤。否則稱它通過(guò)了靜態(tài)語(yǔ)義檢查，編譯程序可將其翻譯到后續(xù)的中間表示形式，即中間代碼生成。在編譯程序的實(shí)現(xiàn)中，一種經(jīng)典的方法是由語(yǔ)法分析程序的分析過(guò)程來(lái)主導(dǎo)語(yǔ)義分析的過(guò)程，本課程將其稱為語(yǔ)法制導(dǎo)的語(yǔ)義計(jì)算。為描述完成什么樣的語(yǔ)義計(jì)算，需要我們?cè)谡Z(yǔ)法定義的基礎(chǔ)上建立適當(dāng)?shù)恼Z(yǔ)義計(jì)算模型?；趯傩晕姆ǖ恼Z(yǔ)義計(jì)算不存在任何上下文無(wú)關(guān)文法接受某語(yǔ)言。如果對(duì) GS 附加某種限定條件，使其只產(chǎn)生滿足這一限定條件的字符串，則可能接受該語(yǔ)言。在文法 GS 基礎(chǔ)上，為文法符號(hào)關(guān)聯(lián)有特定意義的屬性，并為產(chǎn)生式關(guān)聯(lián)相應(yīng)的語(yǔ)義動(dòng)作或條件謂詞，稱之為屬性文法，并稱文法 GS 是這一屬性文

25、法的基礎(chǔ)文法。設(shè)文法符號(hào) X 關(guān)聯(lián)一個(gè)屬性 a，我們用 X.a 來(lái)表示對(duì)這個(gè)屬性的訪問(wèn)。為明確指出一個(gè)屬性對(duì)應(yīng)于當(dāng)前產(chǎn)生式中哪個(gè)位置的文法符號(hào)，在書(shū)寫(xiě)同一文法符號(hào)時(shí)會(huì)用到文法符號(hào)的下標(biāo)形式。A - A1a每個(gè)產(chǎn)生式A都關(guān)聯(lián)一個(gè)語(yǔ)義計(jì)算規(guī)則的集合（花括號(hào)內(nèi)的部分），每個(gè)語(yǔ)義計(jì)算規(guī)則或者是一個(gè)語(yǔ)義動(dòng)作，或者是一個(gè)條件謂詞。語(yǔ)義動(dòng)作一般形式為b := f(c1, c2, ck)（語(yǔ)義函數(shù)）形如 X.a := Y.b 的語(yǔ)義動(dòng)作稱為復(fù)寫(xiě)規(guī)則。對(duì)于給定的屬性文法，在基于語(yǔ)法分析過(guò)程進(jìn)行語(yǔ)義計(jì)算時(shí)，使用某個(gè)產(chǎn)生式完成一步分析時(shí)將執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作，而前提是必須滿足相應(yīng)的條件謂詞。對(duì)關(guān)聯(lián)于產(chǎn)生式A-的語(yǔ)義動(dòng)

26、作 b := f(c1, c2, ck)，如果 b 是 A 的某個(gè)屬性, 則稱 b 是 A 的綜合屬性。計(jì)算綜合屬性是對(duì)父結(jié)點(diǎn)的屬性賦值，“自底向上”傳遞信息。對(duì)關(guān)聯(lián)于產(chǎn)生式A-的語(yǔ)義動(dòng)作 b := f(c1, c2, ck)，如果 b 是產(chǎn)生式右部某文法符號(hào)X 的某屬性, 則稱 b 是X 的繼承屬性。計(jì)算它是對(duì)子結(jié)點(diǎn)的屬性賦值，“自頂向下”傳遞信息。遍歷分析樹(shù)進(jìn)行語(yǔ)義計(jì)算構(gòu)造輸入串的語(yǔ)法分析樹(shù)，構(gòu)造依賴圖。若該依賴圖是無(wú)圈的，則按造此無(wú)圈圖的一種拓?fù)渑判驅(qū)Ψ治鰳?shù)進(jìn)行遍歷，從而計(jì)算所有的屬性值；若依賴圖含有圈，則這一步驟失效。依賴圖是一個(gè)有向圖。可以用帶標(biāo)注語(yǔ)法分析樹(shù)表示屬性的計(jì)算結(jié)果。通過(guò)遍

27、歷分析樹(shù)進(jìn)行屬性計(jì)算的方法有一定通用性，但它是在語(yǔ)法分析遍之后進(jìn)行的。實(shí)際編譯程序中，語(yǔ)法制導(dǎo)的語(yǔ)義計(jì)算大都采取單遍過(guò)程，即語(yǔ)法分析過(guò)程的同時(shí)就完成相應(yīng)的語(yǔ)義動(dòng)作。屬性計(jì)算僅對(duì)應(yīng)一個(gè)自頂向下或是自底向上的簡(jiǎn)單過(guò)程。要求對(duì)屬性文法進(jìn)行某種限制。S-屬性文法和L-屬性文法只包含綜合屬性的屬性文法稱為S-屬性文法。L-屬性文法既可以包含綜合屬性，也可以包含繼承屬性，但要求產(chǎn)生式右端某文法符號(hào)的繼承屬性的計(jì)算只取決于該符號(hào)左邊符號(hào)的（繼承）屬性S-屬性文法是L-屬性文法的一個(gè)特例。基于S-屬性文法的語(yǔ)義計(jì)算（自底向上）若S-屬性文法的基礎(chǔ)文法可用LR 分析進(jìn)行語(yǔ)法分析，那么可通過(guò)擴(kuò)充分析棧中的域，形成

28、語(yǔ)義棧來(lái)存放綜合屬性的當(dāng)前取值。若該符號(hào)有多屬性，可對(duì)應(yīng)多元組的形式?；贚-屬性文法的語(yǔ)義計(jì)算（自頂向下深度優(yōu)先從左至右遍歷分析樹(shù)）將L-屬性文法描述的語(yǔ)義計(jì)算融入到LL(1)預(yù)測(cè)分析過(guò)程之中基于翻譯模式的語(yǔ)義計(jì)算翻譯模式在形式上類似于屬性文法，但允許由括起來(lái)的語(yǔ)義動(dòng)作出現(xiàn)在產(chǎn)生式右端的任何位置，以此顯式地表達(dá)屬性計(jì)算的次序。S-翻譯模式：僅涉及綜合屬性，通常將語(yǔ)義動(dòng)作集合置于相應(yīng)產(chǎn)生式右端的末尾。L-翻譯模式：包含綜合屬性和繼承屬性，需滿足：（1）產(chǎn)生式右端某個(gè)符號(hào)繼承屬性的計(jì)算必須位于該符號(hào)之前，其語(yǔ)義動(dòng)作不訪問(wèn)位于它右邊符號(hào)的屬性，只依賴于該符號(hào)左邊符號(hào)的（繼承）屬性；（2）產(chǎn)生式左部

29、非終結(jié)符的綜合屬性的計(jì)算只能在所用到的屬性都已計(jì)算出來(lái)后進(jìn)行，通常將相應(yīng)的語(yǔ)義動(dòng)作置于產(chǎn)生式的尾部?；赟-翻譯模式的語(yǔ)義計(jì)算，形式上與S-屬性文法一致，自底向上。為進(jìn)一步解釋基于自底向上分析（如LR分析）的語(yǔ)義計(jì)算過(guò)程，要討論每個(gè)產(chǎn)生式歸約時(shí)需要執(zhí)行的語(yǔ)義計(jì)算代碼片斷：假設(shè)語(yǔ)義棧由向量v表示，歸約前棧頂位置為top，棧上第i個(gè)位置所對(duì)應(yīng)符號(hào)的綜合屬性值x用vi. x表示?；贚-翻譯模式的自頂向下語(yǔ)義計(jì)算將L-翻譯模式描述的語(yǔ)義計(jì)算過(guò)程融入遞歸下降分析程序的改造過(guò)程之中稱改造后的分析子函數(shù)（過(guò)程）為語(yǔ)義計(jì)算子函數(shù)（過(guò)程），并稱改造后的遞歸下降分析程序稱為遞歸下降（預(yù)測(cè)）語(yǔ)義計(jì)算程序，或遞歸下

30、降（預(yù)測(cè)）翻譯程序。相應(yīng)于分析子函數(shù)的設(shè)計(jì)，改造后子函數(shù)代碼的流程不同之處是要將語(yǔ)義動(dòng)作嵌入其中，具體可描述為：若遇到一個(gè)終結(jié)符 X，首先將其綜合屬性x的值保存至專為 X.x 而聲明的變量；然后，判斷當(dāng)前讀入的輸入符號(hào)是否與該終結(jié)符相匹配，若匹配，則繼續(xù)讀取下一個(gè)輸入符號(hào)；若不匹配，則報(bào)告和處理語(yǔ)法錯(cuò)誤。若遇到一個(gè)非終結(jié)符B，利用相應(yīng)于 B 的子函數(shù)ParseB產(chǎn)生賦值語(yǔ)句c := ParseB(b1，b2，bk)，其中參量 b1，b2，bk 對(duì)應(yīng)于 B的各繼承屬性，變量c對(duì)應(yīng)B的綜合屬性（若有多個(gè)綜合屬性，則可使用記錄類型的變量）。若遇到一個(gè)語(yǔ)義動(dòng)作集合，則直接復(fù)制其中每一語(yǔ)義動(dòng)作所對(duì)應(yīng)的代

31、碼，只是需要注意將屬性的訪問(wèn)替換為相應(yīng)變量的訪問(wèn)?；贚-翻譯模式的自底向上語(yǔ)義計(jì)算慮解決繼承屬性的普通函數(shù)求值問(wèn)題，再解決其訪問(wèn)一致性，我們的目標(biāo)是：通過(guò)變換翻譯模式（如增加新的文法符號(hào)，增加相應(yīng)的復(fù)寫(xiě)規(guī)則和產(chǎn)生式），使嵌在產(chǎn)生式中間的語(yǔ)義動(dòng)作集中僅含復(fù)寫(xiě)規(guī)則，并使得在自底向上的語(yǔ)法分析過(guò)程中，文法符號(hào)的所有繼承屬性均可以通過(guò)歸約前已出現(xiàn)在分析棧中的綜合屬性唯一確定地進(jìn)行訪問(wèn)。需要注意的是：不可以改變L-翻譯模式的特性。若不是L-翻譯模式，則不能保證歸約前需要訪問(wèn)的綜合屬性已出現(xiàn)在分析棧中。Lecture09：實(shí)驗(yàn)導(dǎo)引（三）Lecture10：靜態(tài)語(yǔ)義分析與中間代碼生成語(yǔ)法制導(dǎo)的靜態(tài)語(yǔ)義分析

32、語(yǔ)法制導(dǎo)的中間代碼生成Lecture11：運(yùn)行時(shí)存儲(chǔ)組織運(yùn)行時(shí)存儲(chǔ)組織的作用與任務(wù)程序運(yùn)行時(shí)存儲(chǔ)空間的布局存儲(chǔ)分配策略活動(dòng)記錄過(guò)程調(diào)用與參數(shù)傳遞Lecture12：:代碼優(yōu)化和目標(biāo)代碼生成基本塊、流圖和循環(huán)基本塊（Basic Block）是指程序中一個(gè)順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。執(zhí)行時(shí)只能從其入口語(yǔ)句進(jìn)入，從其出口語(yǔ)句退出。最大基本塊基本塊的入口語(yǔ)句可以是下面任意三類語(yǔ)句：（1）程序的第1條語(yǔ)句；或者，（2）條件跳轉(zhuǎn)語(yǔ)句或無(wú)條件跳轉(zhuǎn)語(yǔ)句的跳轉(zhuǎn)目標(biāo)語(yǔ)句；或者，（3）條件跳轉(zhuǎn)語(yǔ)句后面的相鄰語(yǔ)句。劃分基本塊的方法：（1）先求出各個(gè)基本塊的入口語(yǔ)句；（2）對(duì)每一入口語(yǔ)句，構(gòu)造其所屬的基本塊。它是由該語(yǔ)句到下一入口語(yǔ)句（不包括下一入口語(yǔ)句），或者到某個(gè)跳轉(zhuǎn)語(yǔ)句（包括該跳轉(zhuǎn)語(yǔ)句），或者到某個(gè)停語(yǔ)句（包括該停語(yǔ)句）之間的語(yǔ)句序列組成的?？梢詾闃?gòu)成程序的基本塊增加控制流程信息，方法是構(gòu)造一個(gè)有向圖，稱之為流圖或控制流圖（CFG，Control-Flow Graph）。流圖以基本塊集為結(jié)點(diǎn)集的有向圖；第一個(gè)結(jié)點(diǎn)為含有程序第一條語(yǔ)句的基本塊，稱為首結(jié)點(diǎn)。流圖中，某一個(gè)基本塊運(yùn)行之后可以到達(dá)的所有基本塊是該基本塊的后繼基本塊，可以直接運(yùn)行并到達(dá)某一個(gè)基本塊的所有基本塊是