《編譯原理》復(fù)習(xí)要點(diǎn)

1、學(xué)習(xí)好資料歡迎下載考試安排：7月13日（20周周三），15:00-17:00,20208填空10X1分、選擇10X2分、簡答4X5分、大題5X10分考試大題：循環(huán)優(yōu)化LL（1）.定義之類的算符優(yōu)先算法自下而上分析法（20分，選擇、填空、大題）第一章引論一.編譯程序（compiler）:（如匯編語言或機(jī)器語言程序）把某一種高級(jí)語言程序等價(jià)地轉(zhuǎn)換成另一種低級(jí)語言程序的程序.編譯程序的工作的五個(gè)階段：1.詞法分析、語法分析、中間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼產(chǎn)生詞法分析任務(wù)：輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞符號(hào)。依循的原則：構(gòu)詞規(guī)則描述工具：有限自動(dòng)機(jī)FOR I1 TO 1

2、00 DO2.保留字標(biāo)識(shí)符等符整常數(shù)保留字整常數(shù)保留字語法分析任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把單詞符號(hào)串分解成各類語法單位。3.依循的原則：語法規(guī)則述工具：上下文無關(guān)文法語義分析與中間代碼產(chǎn)生任務(wù)：對(duì)各類不同語法范疇按語言的語義進(jìn)行初步翻譯。（變量是否定義、類型是否正確等）依循的原則：語義規(guī)則中間代碼：三元式，四元式，逆波蘭記號(hào)，樹形結(jié)構(gòu)等。是一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)。例:Z:=X + 0.618 * Y(2)0.618XT1(3):=T2翻譯成四元式為T1T24.優(yōu)化任務(wù):對(duì)于前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生更高效的目標(biāo)代碼。依循的原則：程序的等價(jià)變換規(guī)

3、則FORK:=1TO100DOBEGINM:=I+10*K;N:=J+10*K;END4.目標(biāo)代碼產(chǎn)生任務(wù)：把中間代碼變換成特定機(jī)器上的目標(biāo)代碼。依賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義目標(biāo)代碼三種形式：a） b） c） 編譯程序結(jié)構(gòu)編譯程序總框絕對(duì)指令代碼：可直接運(yùn)行可重新定位指令代碼：需要連接裝配匯編指令代碼：需要進(jìn)行匯編（簡答題5分）第二章高級(jí)語言及其語法描述2.1.1 語法詞法規(guī)則：單詞符號(hào)的形成規(guī)則。a）單詞符號(hào)是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。b）描述工具：正規(guī)式和有限自動(dòng)機(jī)語法規(guī)則：語法單位的形成規(guī)則。a）語法單位通常包括：表達(dá)式、語句、分

4、程序、過程、函數(shù)、程序等；c）描述工具：上下文無關(guān)文法2.1.2 語義語義:一組規(guī)則，用它可以定義一個(gè)程序的意義。描述方法：a）自然語言描述：隱藏錯(cuò)誤、二義性和不完整性b）形式描述：無二義性完整性多數(shù)語言中，算符的優(yōu)先順序如下：乘哥（*或T）一元負(fù)（-）乘、除力口、減關(guān)系符（<,=,>,<=,>=,<>）非（？，not）與（A,&,and）或（？,®）隱含（或imp）等值（或epui,或2.3程序語言的語法描述1.幾個(gè)概念：優(yōu)先級(jí)由高自低不同的語言對(duì)算符優(yōu)先級(jí)的規(guī)定有差異，甚至差異很a）考慮一個(gè)有窮字母表匯字符集b）其中每一個(gè)元素稱為一個(gè)空

5、跳c）匯上的空（也叫字符串）是指由匯中的字符所構(gòu)成的一個(gè)有窮序列d）不包含任何字符的序列稱為空字，記為£e）用匯*表示匯上的所有字的全體，包含空字£例如：設(shè)匯=a,b,則匯=e,a,b,aa,ab,ba,bb,aaa,f）匯*的子集U和V的連接（積）定義為UV=ab|aWU&bV例如：設(shè)：U=a,aa,V=b,bb那么：U=ab,abb,aab,aabbg）V自身的n次積記為V=W-Vh）規(guī)定V0=3，令V*=V0uVuV2uMu稱v*是v的閉包；記v+=vV,稱V是v的正規(guī)閉包。例如：設(shè)：U=a,aa*那么：U=z,a,aa,aaa,aaaa,U=a,aa,aaa

6、,aaaa,i）0型（短語文法，圖靈機(jī)）：產(chǎn)生式形如：atP其中：心（Vt=Vn）*且至少含有一個(gè)非終結(jié)符；Pw（VtuVn）*任彳510型語言都是遞歸可枚舉的。j）1型（上下文有關(guān)文法，線性界限自動(dòng)機(jī)）：產(chǎn)生式形如：3TB其中：|豆|<|和，僅ST8例外。意味著對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必考慮上下文,并且，一般不允許替換成空k） 2型（上下文無關(guān)文法，非確定下推自動(dòng)機(jī)產(chǎn)生式形如：AtP其中：AWVn；pw（Vt2Vn）*。非終結(jié)符的替換可以不必考慮上下文。l） 3型（正規(guī)文法，有限自動(dòng)機(jī)）：產(chǎn)生式形如：Ato（B或Ata其中：aWVt*;aB三Vn右線性文法左線性文法產(chǎn)生式形如：ATBot

7、或At其中：«Vt*;aBeVn正規(guī)文法的能力要比上下文無關(guān)文法弱得多。四種類型描述能力比較m)上下文無關(guān)文法的定義：一個(gè)上下文無關(guān)文法G是一個(gè)四元式G=(Vt,Vn,S,P),其中Vt：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VtCV誨S:文法的開始符號(hào)，SVnP:產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為*P-jot,PEVn,a(Vt=Vm)開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。例：文法G(A):Atc|AbG(A)的語言？解：L(Gi)=c,cb,cbb,以c開頭，后繼若干個(gè)bn)定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩顆不同的語法樹，則說這個(gè)文法是二義的。G(E):Et

8、i|E+E|E*E|(E)是二義文法。o)語言的二義性：一個(gè)語言是二義性的，如果對(duì)它不存在無二義性的文法?？赡艽嬖贕和G,一個(gè)為二義的，一個(gè)為無二義的。但L(G尸L(G)2.狀態(tài)轉(zhuǎn)換圖a)概念：狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。b)結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。c)狀態(tài)之間用箭弧連結(jié)，箭弧上的標(biāo)記(字符)代表射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。d)一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)為初態(tài)，至少要有一個(gè)終態(tài)3 .正規(guī)運(yùn)算符優(yōu)先順序在不致混淆時(shí)，括號(hào)可以省去，但規(guī)定算符的優(yōu)先順序?yàn)?*(閉包).(連接)|(或)4 .3型文法-正規(guī)式G的任何產(chǎn)生式為AttxB或Ata其中：“WVt*；aB三Vn3型文

9、法等價(jià)于正規(guī)式，所以也稱正規(guī)文法。3.3.2 確定有限自動(dòng)機(jī)(DFA)對(duì)狀態(tài)圖進(jìn)行形式化，則可以下定義：自動(dòng)機(jī)M是一個(gè)五元式M=(S,£,f,So,F),其中:a) S：有窮狀態(tài)集，b) I：輸入字母表(有窮)，c) f:狀態(tài)轉(zhuǎn)換函數(shù)，為SmtS的單值部分映射，f(s,a尸s'表示：當(dāng)現(xiàn)行狀態(tài)為s,輸入字符為a時(shí)，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s'。我們把s'稱為s的一個(gè)后繼狀態(tài)。d) SoWS是唯一的一個(gè)初態(tài)；e) F三S:終態(tài)集(可空)。例如：DFAM=(0,1,2,3,a,b,f,0,3),其中：f定義如下：f(0,a)=1f(0,b)=2f(1,a)=3f(1,

10、b)=2f(2,a)=1f(2,b)=33.3.3 非確定有限自動(dòng)機(jī)(NFA)定義：一個(gè)非確定有限自動(dòng)機(jī)(NFA)M是一個(gè)五元式M=(S,I,f,So,F)，其中：1 S:有窮狀態(tài)集；2工：輸入字母表(有窮)；3 f:狀態(tài)轉(zhuǎn)換函數(shù)，為SxfT2s的部分映射(非單值)；4 S0=S是非空的初態(tài)集；5 F=S:終態(tài)集(可空)。從狀態(tài)圖中看NFA和DFA的區(qū)別：1 弧上的標(biāo)記可以是工中的一個(gè)字，而不一定是單個(gè)字符；2 同一個(gè)字可能出現(xiàn)在同狀態(tài)射出的多條弧上。DFA是NFA的特例。定義：對(duì)于任何兩個(gè)有限自動(dòng)機(jī)M和M,如果L(M)=L(M'),則稱M與M等價(jià)。自動(dòng)機(jī)理論中一個(gè)重要的結(jié)論：判定兩個(gè)

11、自動(dòng)機(jī)等價(jià)性的算法是存在的。對(duì)于每個(gè)NFAM存在一個(gè)DFAM,使得L(M尸L(M')。亦即DFA與NFA描述能力相同。把上述NFA確定化一一采用子集法.設(shè)I是M的狀態(tài)集的一個(gè)子集，定義I的*閉包&closure(I)為：i) 若sI,貝Usw&-closure(I);ii) 若sWI,則從s出發(fā)經(jīng)過任意條源而能到達(dá)的任何狀態(tài)s'都屬于-closure(I)即&closure(I)=I=s'|從某個(gè)s=I出發(fā)經(jīng)過任意條飆能到達(dá)s'例：設(shè)a是工中的一個(gè)字符，定義Ia=&closure(J)其中，J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過一條a弧而到達(dá)

12、的狀態(tài)集合。XA1544匿乩1(5S4A1A)5,241,6,Y)0,6,1,£5,3,115,2J,6,Y5315434AV爆 363Y(5361Y)(SJJ.IAVIMJJ- 5.4,1. (524,1,A,Y) 5d,1小E&L&'J041,6.V；“1V)13136630 12 3 4 5 63.3.4正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性定理：1. 對(duì)每一個(gè)右線T正規(guī)文法G或左線性正規(guī)文法G,都存在一個(gè)有限自動(dòng)機(jī)(FA)M,使得L(M)=L(G)。2.對(duì)每一個(gè)FAM,都存在一個(gè)右線性正規(guī)文法號(hào)和左線性正規(guī)文法G,使得L(M)=L(Gr)=L(Gl)。3.3.5

13、 正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性定理：1 .對(duì)任何FAM,都存在一個(gè)正規(guī)式r,使得L(r尸L(M)。2 .對(duì)任何正規(guī)式r,都存在一個(gè)FAM,使得L(M)=L(r)。對(duì)轉(zhuǎn)換圖概念拓廣，令每條弧可用一個(gè)正規(guī)式作標(biāo)記。(對(duì)一類輸入符號(hào))3.3.6 確定有限自動(dòng)機(jī)的化簡對(duì)DFAM的化簡：尋找一個(gè)狀態(tài)數(shù)比M少的DFAM',使得L(M)=L(M)假設(shè)s和t為M的兩個(gè)狀態(tài)，稱s和t笠化：如果從狀態(tài)s出發(fā)能讀出某個(gè)字a而停止于終態(tài)，那么同樣，從t出發(fā)也能讀出a而停止于終態(tài)；反之亦然。兩個(gè)狀態(tài)不等價(jià)，則稱它們是可區(qū)別的。對(duì)一個(gè)DFAM最少化的基本思想：把M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集

14、的狀態(tài)是可區(qū)別的，而同一子集的任何兩個(gè)狀態(tài)是等價(jià)的。最后，讓每個(gè)子集選出一個(gè)代表，同時(shí)消去其他狀態(tài)。1(1) =0, 1,2 I 出=3, 4, 5, 6Ia(1) =1,3I(11)=0,2I(12)=1I平,4,5,6I(11)=0,2Ia(11)=1Ib(11)=2,5I(111)=0I(112)=2I(12)=1I出=3,4,5,6Ia(2)=3,6I2出=4,5第四章語法分析一一自上而下分析語法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找匹配”的推導(dǎo)。遞歸下降分析法：對(duì)每一語法變量(非終結(jié)

15、符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。預(yù)測分析程序優(yōu)點(diǎn)：直觀、簡單和宜于手工實(shí)現(xiàn)。3.3.7 LL(1)分析法構(gòu)造不帶回溯的自上而下分析算法要消除文法的左遞歸性克服回溯4.3.1 左遞歸的消除P的規(guī)則為直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P*-P|:其中P不以P開頭。我們可以把P的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：左遞歸變右遞歸-PP,P;一般而言，假定P關(guān)于的全部產(chǎn)生式是PP|P停|.IPOtm|陽均Ipn其中，每個(gè)a都不等于&每個(gè)沸B不以P開頭那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成：P-

16、PlP1P|PnP*p“p|ei|sPs提取公共左因子：假定關(guān)于A的規(guī)則是(其中，每個(gè)Y不以M頭)Af那1|郤2|邵n|71|飛2|臣那么，可以把這些規(guī)則改寫成Z於'|X|丁2|YmA*1p1|p2|pn經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。4.3.3LL(1)分析條件假定S是文法G的開始符號(hào)，對(duì)于G的任何非終結(jié)符A,我們定義*FOLLOWA)=a|S=.Aa.,aVT*特別是，若s=,A,則規(guī)定#WFOLLOW(A)構(gòu)造不帶回溯的自上而下分析的文法條件1 .文法不含左遞歸，2 .對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩

17、不相交。即，若Za11a21,|an則FIRST(ai)nFIRST(o(j)=©(i卻i=1,2,.,n3 .對(duì)文法中的每個(gè)非終結(jié)符A,若它存在某個(gè)候選首符集包含；，則FIRST(A)AFOLLOW(A)=如果一個(gè)文法G滿足以上條件，則稱該文法G為LL(1)文法。第五章語法分析一一自下而上分析語法分析的方法：自下而上分析法(Bottom-up)基本思想：從輸入串開始，逐步進(jìn)行“歸約”，直到文法的開始符號(hào)。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語法分析。適合分析表達(dá)式。LR分析法：

18、規(guī)范歸約5.1.2規(guī)范歸約1 .定義：令G是一個(gè)文法，S是文法的開始符號(hào)，假定口的是文法G的一個(gè)句型，如果有*且SnaASA=P則稱口是句型口的相對(duì)于非終結(jié)符A的短語。特別是，如果有,則稱B是句型oP而寸于規(guī)則jp的直接短語。一個(gè)句型的最左直接短語稱為該句型的句柄。2 .歸約采用“移進(jìn)歸約”思想進(jìn)行自下而上分析?；舅枷耄河靡粋€(gè)寄存符號(hào)的先進(jìn)后出枝，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的候選式時(shí)，即把棧頂?shù)倪@一部分替換成(組約_為)該產(chǎn)生式的左部符號(hào)。5.2算符優(yōu)先分析四則運(yùn)算的優(yōu)先規(guī)則：先乘除后加減，同級(jí)從左到右考慮二義文法文法G(E):G(E):Eti|E+E|E-E|E*

19、E|E/E|(E)它的句子有幾種不同的規(guī)范規(guī)約。歸約即計(jì)算表達(dá)式的值。歸約順序不同，則計(jì)算的順序也不同，結(jié)果也不一樣。如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進(jìn)行歸約，則歸約過程是唯一的。起決定作用的是相鄰的兩個(gè)算符之間的優(yōu)先關(guān)系。所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關(guān)系,借助于這種關(guān)系尋找“M歸約串”和進(jìn)行歸約。5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造一個(gè)文法，如果它的任一產(chǎn)生式的右部都不含兩個(gè)相繼(并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式右部：QR-則我們稱該文法為算符文法。約定：a、b代表任意終結(jié)符；P、QR代表任意非終結(jié)符；代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。假定G是一個(gè)不

20、含承產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符a、b,我們說：1. a=b當(dāng)且僅當(dāng)文法G中含有形如ab或PaQb的產(chǎn)生式；+2. a<b當(dāng)且僅當(dāng)G中含有形如4aR的產(chǎn)生式，而R=b或產(chǎn)Qb；+3. a>b當(dāng)且僅當(dāng)G中含有形如4Rb的產(chǎn)生式，而R=-a或1-aCl如果一個(gè)算符文法G中的任何終結(jié)符對(duì)(a,b)至多只滿足下述三關(guān)系之一：a=b,a<b,a>bo則稱G是一個(gè)算符優(yōu)先文法。從算符優(yōu)先文法G構(gòu)造優(yōu)先關(guān)系表的算法。通過檢查G的每個(gè)產(chǎn)生式的每個(gè)候選式，可找出所有滿足a=b的終結(jié)符對(duì)。確定滿足關(guān)系<和>的所有終結(jié)符對(duì)：首先需要對(duì)G的每個(gè)非終結(jié)符P構(gòu)造兩個(gè)集合FIRS

21、TVT(P)和LASTVT(P):+FIRSTVT(P)=a|P=a，P=Qa,aVTQVN+a<b當(dāng)且僅當(dāng)G中含有形如P一aR的產(chǎn)生式，而-b或Qb1+LASTVTP)=a|Pna,或PnaQ,awVT而QwVN+a>b當(dāng)且僅當(dāng)G中含有形如FRb的產(chǎn)生式，而R=-a或2-aCl有了這兩個(gè)集合之后，就可以通過檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系和>的所有終結(jié)符對(duì)。假定有個(gè)產(chǎn)生式的一個(gè)候選形為aP-那么，對(duì)任何bwFIRSTVT(P)，有a<b。假定有個(gè)產(chǎn)生式的一個(gè)候選形為Pb-那么，對(duì)任何aWLASTVT(P),有a>b。按其定義，可用下面兩條規(guī)則來構(gòu)造集合FIRS

22、TVT(P):1 .若有產(chǎn)生式a或-Qa,則awFIRSTVT(P);2 .若aWFIRSTVT(Q),且有產(chǎn)生式-Q-,則aWFIRSTVT(P)。練習(xí)：P133-2計(jì)算它的FIRSTVT和LASTVT計(jì)算G的優(yōu)先關(guān)系。并確定G是否是一個(gè)算符優(yōu)先文法？唯一確定每一步工作LR分析器的核心是一張分析表：ACTIONS,a：當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)，應(yīng)采取什么動(dòng)作GOTOS,X:狀態(tài)s面對(duì)文法符號(hào)X時(shí)，下一狀態(tài)是什么文法G的每個(gè)產(chǎn)生式的右部添加一個(gè)圓點(diǎn)稱為G的LR(0)項(xiàng)目例：如：AtXYZ有四個(gè)項(xiàng)目：a>.xyza-；x.yza-；xy.za_；xyz.f.稱為"歸約項(xiàng)目&quo

23、t;歸約項(xiàng)目S'TX.稱為“接受項(xiàng)目"i.aP(a三Vt)稱為"移進(jìn)項(xiàng)目"A-jot.BP(BWVn)稱為"待約項(xiàng)目".例：文法G(S)SEE一aA|bBZcA|dB一cB|d該文法的項(xiàng)目有：1.SjE2.SE-3.E一aA4.EfaA5.aA6.KcA7.Zc-A8.ZcA9.Z-d10.Kd-11.EfbB12.bB13.E-bB14.BfcB15.BfcB16. BfcB-17.B-d18.B-d-構(gòu)造識(shí)別文法所有活前綴的NFA方法1. 若狀態(tài)i為XXXi-1.XiXn,狀態(tài)j為-X1Xi-1X.Xi+1Xn,則從狀態(tài)i畫一條標(biāo)志

24、為Xi的有向邊到狀態(tài)j;2. 若狀態(tài)i為Xr.AP,A為非終結(jié)符，則從狀態(tài)i畫一條也到所有狀態(tài)j工把識(shí)別文法所有活前綴的NFA確定化。4: A-c-A A*l<AA2: FAcAA * <13 Erb BAd0: £ jRE nAE-v bBt Si B- -c bB-k rB B-r-dA11: B-*(l 想別活前攀的構(gòu)成識(shí)別一個(gè)文法活前綴的DFA的項(xiàng)目集(狀態(tài))的全體稱為文法的LR(0)項(xiàng)目集規(guī)范族。LR(0)分析表的構(gòu)造假若一個(gè)文法G的拓廣文法G的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)(項(xiàng)目集)不存在下述情況：1) 既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目，2) 含有多個(gè)歸約項(xiàng)目則稱G是一

25、個(gè)LR(0)文法。分析表的ACTIONS口GOTO?表構(gòu)造方法：1 .若項(xiàng)目A-口邛屬于Ik且GO(Ik,a)=Ij,a為終結(jié)符，則置ACTIONk,a為“sj”。2 .若項(xiàng)目Afa屬于屋，那么，對(duì)任何終結(jié)符a(或結(jié)束符#),置ACTIONk,a為“rj”(假定產(chǎn)生式A-a是文法G的第j個(gè)產(chǎn)生式)。3 .若項(xiàng)目S-S屬于Ik,則置ACTIONk,#為“acc”。4 .若GO(Ik,A)=Ij,A為非終結(jié)符，則置GOTOk,A=j。5 .分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“報(bào)錯(cuò)標(biāo)志”。M卬2)弁新在ACTIONgotc狀恁Abc<1*EA(1s21_J1acc12s4sl(&

26、gt;63all7J4s4slO815s5slli6rlrlrlrlrl71r2r2r2r2r28i'3r3rJr3r39r5r5r5r-5f510r4r4r4r4r4111161-61616d1按上述方法構(gòu)造出的ACTIONGOTOB口果不含多重入口，則稱該文法為SLR文性。使用SLR表的分析器叫做一個(gè)SLR分析器。每個(gè)SLR(1)文法都是無二義的。但也存在許多無二義文法不是SLR(1)的.這個(gè)文嶷的LR0哪4臬機(jī)龜臻為;Io：S'E及FTE)I7：T-T*F豆E->E+T甘一HEE1，TEfTIFiI1、I2和I9都含有“移進(jìn)歸約”沖突。FOLLOW(E)=#,),+

27、I;:r一 I 25.3.4規(guī)范LR分析表的構(gòu)造我們需要重新定義項(xiàng)目，使得每個(gè)項(xiàng)目都附帶有k個(gè)終結(jié)符。每個(gè)項(xiàng)目的一般形式是A-crP,aia2-ak，這樣的一個(gè)項(xiàng)目稱為一個(gè)LR(k)項(xiàng)目。項(xiàng)目中的aia2嘰稱為它的向前搜索符串(或展望串)。向前搜索符串僅對(duì)歸約項(xiàng)目A-ot,aia2”有意義。對(duì)于任何移進(jìn)或待約項(xiàng)目A一ct,P,aia2ak,隹令,搜索符串a(chǎn)ia2ak沒有作用。按上述算法構(gòu)造的分析表，若不存在多重定義的入口(即，動(dòng)作沖突)的情形，則稱它是文法G的一張規(guī)范的LR(1)分析表。使用這種分析表的分析器叫做一個(gè)規(guī)范的LR分析器。具有規(guī)范的LR(1)分析表的文法稱為一個(gè)LR(1)文法。LR

28、(1)狀態(tài)比SLR多，LR(0)cSLR=LR(1)心無二義文法。第六章屬性文法和語法制導(dǎo)翻譯6.1屬性文法屬性文法(也稱屬性翻譯文法)在上下文無關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)(終結(jié)符或非終結(jié)符)配備若干相關(guān)的“值”(稱為星匡)。屬性代表與文法符號(hào)相關(guān)信息，如類型、值、代碼序列、符號(hào)表內(nèi)容等屬性可以進(jìn)行計(jì)算和傳遞語義規(guī)則:對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則屬性綜合屬性：“自下而上”傳遞信息繼承屬性：“自上而下”傳遞信息綜合屬性在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則計(jì)算綜合屬性的值僅僅使用綜合屬性的屬性文法稱S-屬性文法

29、繼承屬性在語法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定用繼承屬性來表示程序設(shè)計(jì)語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便6.2.3一遍掃描的處理方法一遍掃描的處理方法是在語法分析的同時(shí)計(jì)算屬性值所采用的語法分析方法屬性的計(jì)算次序L一屬性文法適合于一遍掃描的自上而下分析S-屬性文法適合于一遍掃描的自下而上分析6.4L-屬性文法和自頂向下翻譯通過深度優(yōu)先的方法對(duì)語法樹進(jìn)行遍歷，計(jì)算屬性文法的所有屬性值LL(1):自上而下分析方法，深度優(yōu)先建立語法樹第七章語義分析和中間代碼產(chǎn)生靜態(tài)語義檢查類型檢查控制流檢查一致性檢查相關(guān)名字檢查名字的作用域分析7.1中間語言常用的中間語言：后綴式，

30、逆波蘭表示圖表示：DAG抽象語法樹三地址代碼四元式間接三元式逆波蘭表示法不用括號(hào)。只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它進(jìn)行唯一分解。后綴式的計(jì)算用一個(gè)棧實(shí)現(xiàn)。一般的計(jì)算過程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。7.4布爾表達(dá)式的翻譯布爾表達(dá)式的兩個(gè)基本作用：用于邏輯演算，計(jì)算邏輯值；用于控制語句的條件式.產(chǎn)生布爾表達(dá)式的文法：Ef E or E | E andE |一E | (E) | i rop i | ia<borc<dande<f1OO(j%a,b,0)*101

31、也102)102(j<pc,d,104)1030.、0)104(j*aet£100)tru#list105Or103)Iselis第十章優(yōu)化優(yōu)化:對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼。等價(jià):指不改變程序的運(yùn)行結(jié)果。有效:指目標(biāo)代碼運(yùn)行時(shí)間短，占用的存儲(chǔ)空間小。Ij,口:藕譯者靖！*代碼優(yōu)化春*毓玲后端ijflI!_,_-_L一一i建制洗介析謹(jǐn)分析代科正兼2*10.1 概述優(yōu)化的三個(gè)不同級(jí)別：局部優(yōu)化循環(huán)優(yōu)化全局優(yōu)化優(yōu)化的種類：刪除多余運(yùn)算（或稱刪除公用子表達(dá)式）代碼外提強(qiáng)度消弱變換循環(huán)控制條件合并已知量復(fù)寫傳播刪除無用賦值10.2 局部優(yōu)化局限

32、于基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi)的優(yōu)化,或稱局部優(yōu)化。在一個(gè)基本塊內(nèi)通?？梢詫?shí)行下面的優(yōu)化：刪除公共子表達(dá)式刪除無用賦值合并已知量臨時(shí)變量改名交換語句的位置代數(shù)變換劃分四元式程序?yàn)榛緣K的算法：1.求出四元式程序中各個(gè)基本塊的入口語句：1）程序第一個(gè)語句，或2）能由條件轉(zhuǎn)移語看或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或附明|1) X由 ITHfl Y3）緊跟在條件轉(zhuǎn)移語句后面的語句。（l）rrmlX（2）rea.YR:-XmodYifR=O|Mb（8）X:=V（4）Y:=R靜1。（J）畫vHteYhull10.3循環(huán)優(yōu)化對(duì)循環(huán)中的代碼，可以實(shí)行：代碼外提強(qiáng)度消弱刪除歸納變量（變換循環(huán)控制條件）循環(huán)展開循環(huán)合并10.3.1 代碼外提循環(huán)不變運(yùn)算：對(duì)四元式A:=BopC,若B和C是常數(shù)，或者到達(dá)它們的B和C的定值點(diǎn)都在循環(huán)外。所謂變量A在某點(diǎn)d的定值到達(dá)另一點(diǎn)u（或稱變量A的定值點(diǎn)d到達(dá)另一點(diǎn)u）,是指流圖中從d有一通路到達(dá)u且該通路上沒有A的其它定值。d:A:=BopCu:D:=AopE把循環(huán)不變運(yùn)算提到循環(huán)體外。PlI。）】尸】*=1r】的TM+TiTrflddr(A) IIT-