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

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

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

3、進(jìn)行加工變換，以期在最后階段產(chǎn)生更高效的目標(biāo)代碼。依循的原則：程序的等價(jià)變換規(guī)則FOR K:=1 TO 100 DO BEGIN M := 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) 絕對(duì)指令代碼: 可直接運(yùn)行 b) 可重新定位指令代碼: 需要連接裝配c) 匯編指令代碼: 需要進(jìn)行匯編三. 編譯程序結(jié)構(gòu)u 編譯程序總框 (簡答題5分)第二章 高級(jí)語言及其語法描述2.1.1語法詞法規(guī)則：單詞符號(hào)的形成規(guī)則。a) 單詞符號(hào)是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一

4、般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。b) 描述工具：正規(guī)式和有限自動(dòng)機(jī)語法規(guī)則：語法單位的形成規(guī)則。a) 語法單位通常包括：表達(dá)式、語句、分程序、過程、函數(shù)、程序等;c) 描述工具：上下文無關(guān)文法2.1.2語義語義：一組規(guī)則，用它可以定義一個(gè)程序的意義。描述方法：a) 自然語言描述：隱藏錯(cuò)誤、二義性和不完整性b) 形式描述：F 無二義性F 完整性多數(shù)語言中，算符的優(yōu)先順序如下：u 乘冪（*或）優(yōu)先級(jí)由高自低u 一元負(fù)（-）u 乘、除u 加、減不同的語言對(duì)算符優(yōu)先級(jí)的規(guī)定有差異，甚至差異很大！u 關(guān)系符（<,=,>,<=,>=,<>）u 非（¬

5、;，not）u 與(，&，and )u 或(,|,or,)u 隱含( 或imp)u 等值（ 或epui，或 ）2.3 程序語言的語法描述1. 幾個(gè)概念:a) 考慮一個(gè)有窮 字母表 字符集b) 其中每一個(gè)元素稱為一個(gè)字符c) 上的字(也叫字符串) 是指由中的字符所構(gòu)成的一個(gè)有窮序列d) 不包含任何字符的序列稱為空字，記為e) 用*表示上的所有字的全體,包含空字例如: 設(shè) =a， b，則 *=,a,b,aa,ab,ba,bb,aaa,.f) *的子集U和V的連接（積）定義為UV ab | aÎU & bÎV 例如: 設(shè)：U a, aa ,V b, bb 那么：U

6、V= ab, abb, aab, aabb g) V自身的 n次積記為Vn=VVVh) 規(guī)定V0=e，令V*=V0V1V2V3 稱V*是V的閉包;記 VVV* ，稱V+是V的正規(guī)閉包。例如: 設(shè)：U a, aa 那么：U* = e , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, i) 0型(短語文法，圖靈機(jī))： 產(chǎn)生式形如： a ® b 其中：aÎ (VT È VN)*且至少含有一個(gè)非終結(jié)符；bÎ (VT È VN)* 任何0型語言都是遞歸可枚舉的。j) 1型(上下文有關(guān)文法，線性界限自動(dòng)機(jī))： 產(chǎn)生式形如：

7、 a ® b 其中：|a| £ |b|，僅 S®e 例外。意味著對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必考慮上下文，并且，一般不允許替換成空串e 。k) 2型(上下文無關(guān)文法，非確定下推自動(dòng)機(jī))： 產(chǎn)生式形如： A ® b 其中：AÎ VN；bÎ (VT È VN)*。非終結(jié)符的替換可以不必考慮上下文。l) 3型(正規(guī)文法，有限自動(dòng)機(jī))：右線性文法 產(chǎn)生式形如： A ® aB 或 A ® a 其中： aÎ VT*；A，BÎVN左線性文法 產(chǎn)生式形如： A ® Ba 或 A ® a

8、其中： aÎ VT*；A，BÎVN正規(guī)文法的能力要比上下文無關(guān)文法弱得多。四種類型描述能力比較 m) 上下文無關(guān)文法的定義： 一個(gè)上下文無關(guān)文法G是一個(gè)四元式 G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT Ç VN=ÆS：文法的開始符號(hào)，SÎVNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為P®a， PÎVN， a Î (VT È VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。例：文法G1(A)： A ® c|AbG1(A)的語言?解：L(G1)=c

9、，cb，cbb，¼，以c開頭，后繼若干個(gè)bn) 定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩顆不同的語法樹，則說這個(gè)文法是二義的。G(E)： E ® 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)

10、算符優(yōu)先順序在不致混淆時(shí)，括號(hào)可以省去，但規(guī)定算符的優(yōu)先順序?yàn)椋?（閉包） .（連接） |（或）4. 3型文法-正規(guī)式 G的任何產(chǎn)生式為 A ® aB 或 A ® a 其中： aÎ VT*；A，BÎVN 3型文法等價(jià)于正規(guī)式，所以也稱正規(guī)文法。3.3.2 確定有限自動(dòng)機(jī)(DFA)對(duì)狀態(tài)圖進(jìn)行形式化，則可以下定義：自動(dòng)機(jī)M是一個(gè)五元式M=(S, S, f, S0, F),其中：a) S: 有窮狀態(tài)集，b) S：輸入字母表(有窮)，c) f: 狀態(tài)轉(zhuǎn)換函數(shù)，為S´S®S的單值部分映射，f(s，a)=s表示：當(dāng)現(xiàn)行狀態(tài)為s，輸入字符為a時(shí)，

11、將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s。我們把s稱為s的一個(gè)后繼狀態(tài)。d) S0ÎS是唯一的一個(gè)初態(tài)； e) FÍS ：終態(tài)集(可空)。例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：f定義如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3 3.3.3 非確定有限自動(dòng)機(jī)(NFA)定義：一個(gè)非確定有限自動(dòng)機(jī)(NFA) M是一個(gè)五元式M=(S, S, f, S0, F)，其中：1 S: 有窮狀態(tài)集；2 S ：輸入字母表(有窮)；3 f: 狀態(tài)轉(zhuǎn)換函數(shù)，為S´S*®2S的

12、部分映射(非單值)；4 S0ÍS是非空的初態(tài)集；5 F ÍS ：終態(tài)集(可空)。從狀態(tài)圖中看NFA 和DFA的區(qū)別： 1 弧上的標(biāo)記可以是S*中的一個(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è)自動(dòng)機(jī)等價(jià)性的算法是存在的。對(duì)于每個(gè)NFA M存在一個(gè)DFA M，使得 L(M)=L(M)。亦即DFA與NFA描述能力相同。把上述NFA確定化采用子集法.設(shè)I是M的狀態(tài)集的一個(gè)子集，定義I的e-閉包e-closure(I)為:

13、 i) 若sÎI，則sÎe-closure(I)； ii) 若sÎI，則從s出發(fā)經(jīng)過任意條e弧而能到達(dá)的任何狀態(tài)s都屬于e-closure(I) 即 e-closure(I)=IÈs|從某個(gè)sÎI出發(fā)經(jīng)過任意條e弧能到達(dá)s例：設(shè)a是S中的一個(gè)字符，定義 Ia= e-closure(J)其中，J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過一條a弧而到達(dá)的狀態(tài)集合。 3.3.4 正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性定理： 1.對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)(FA) M，使得L(M)L(G)。2.對(duì)每一個(gè)FA M，都存在一個(gè)右線性正規(guī)文法GR和

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

15、對(duì)一個(gè)DFA M最少化的基本思想: 把M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個(gè)狀態(tài)是等價(jià)的。最后，讓每個(gè)子集選出一個(gè)代表，同時(shí)消去其他狀態(tài)。I(1)=0, 1, 2 I(2)=3, 4, 5, 6 Ia(1) =1, 3 I(11) =0, 2 I(12) =1 I(2)=3, 4, 5, 6 I(11) =0, 2Ia(11) =1 Ib(11) =2, 5 I(111) =0 I(112) =2 I(12) =1 I(2)=3, 4, 5, 6 Ia(2) =3, 6 Ia(2) =4, 5 第四章 語法分析自上而下分析u 語法分析的方法

16、：u 自下而上分析法(Bottom-up)u 自上而下分析法(Top-down)u 基本思想：它從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找"匹配"的推導(dǎo)。u 遞歸下降分析法：對(duì)每一語法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。u 預(yù)測(cè)分析程序F 優(yōu)點(diǎn)：直觀、簡單和宜于手工實(shí)現(xiàn)。4.3 LL(1)分析法u 構(gòu)造不帶回溯的自上而下分析算法u 要消除文法的左遞歸性u(píng) 克服回溯4.3.1 左遞歸的消除u 直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為PPa | b 其中b不以P開頭。 我們

17、可以把P的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：PbP¢左遞歸變右遞歸P¢aP¢|eu 一般而言，假定P關(guān)于的全部產(chǎn)生式是 PPa1 | Pa2 | | Pam | b1 | b2|bn其中，每個(gè)a都不等于e，每個(gè)b都不以P開頭 那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： Pb1P¢ | b2P¢ | | bnP¢ P¢a1P¢ | a2P¢ | | amP¢ | eu 提取公共左因子: 假定關(guān)于A的規(guī)則是 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm

18、 (其中，每個(gè)g 不以d開頭) 那么，可以把這些規(guī)則改寫成AdA¢ | g 1 | g 2 | | g mA¢b 1 | b 2 | | b nu 經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。4.3.3 LL(1)分析條件u 假定S是文法G的開始符號(hào)，對(duì)于G的任何非終結(jié)符A，我們定義特別是，若，則規(guī)定ÎFOLLOW(A)n 構(gòu)造不帶回溯的自上而下分析的文法條件1. 文法不含左遞歸，2. 對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若 Aa 1|a 2|a n 則 FIRST(a i)FIRST(a

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

20、是文法的開始符號(hào)，假定abd是文法G的一個(gè)句型，如果有 且 ，則稱b是句型abd相對(duì)于非終結(jié)符A的短語。特別是，如果有AÞb,則稱b是句型abd相對(duì)于規(guī)則A® b的直接短語。一個(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)先分析u 四則運(yùn)算的優(yōu)先規(guī)則： 先乘除后加減，同級(jí)從左到右u 考慮二義文法文法G(E)：G(E)： E ® i| E+E|E-E|E*E|E

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

22、的任意序列，包括空字。u 假定G是一個(gè)不含e-產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符a、b，我們說：1. a=b當(dāng)且僅當(dāng)文法G中含有形如Pab或PaQb的產(chǎn)生式；2. a<b當(dāng)且僅當(dāng)G中含有形如PaR的產(chǎn)生式， 而Rb或RQb；3. a>b 當(dāng)且僅當(dāng)G中含有形如PRb的產(chǎn)生式，而 Ra或RaQ。n 如果一個(gè)算符文法G中的任何終結(jié)符對(duì)(a，b)至多只滿足下述三關(guān)系之一：a=b，a<b， a>b。 則稱G是一個(gè)算符優(yōu)先文法。u 從算符優(yōu)先文法G構(gòu)造優(yōu)先關(guān)系表的算法。u 通過檢查G的每個(gè)產(chǎn)生式的每個(gè)候選式，可找出所有滿足a=b的終結(jié)符對(duì)。u 確定滿足關(guān)系<和>的所有

23、終結(jié)符對(duì)：u 首先需要對(duì)G的每個(gè)非終結(jié)符P構(gòu)造兩個(gè)集合FIRSTVT(P)和LASTVT(P)：a<b當(dāng)且僅當(dāng)G中含有形如PaR的產(chǎn)生式， 而Rb或RQb；a>b 當(dāng)且僅當(dāng)G中含有形如PRb的產(chǎn)生式，而 Ra或RaQ。q 有了這兩個(gè)集合之后，就可以通過檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系<和>的所有終結(jié)符對(duì)。Ø 假定有個(gè)產(chǎn)生式的一個(gè)候選形為aP 那么，對(duì)任何bÎFIRSTVT(P)，有 a<b。Ø 假定有個(gè)產(chǎn)生式的一個(gè)候選形為Pb 那么，對(duì)任何aÎLASTVT(P)，有 a>b。u 按其定義，可用下面兩條規(guī)則來構(gòu)造集合F

24、IRSTVT(P)：1. 若有產(chǎn)生式Pa或PQa，則aÎFIRSTVT(P)；2. 若aÎFIRSTVT(Q)，且有產(chǎn)生式PQ，則aÎFIRSTVT(P)。練習(xí)：P133-2 計(jì)算它的FIRSTVT和LASTVT； 計(jì)算G的優(yōu)先關(guān)系 。并確定G是否是一個(gè)算符優(yōu)先文法？u LR分析方法：把"歷史"及"展望"綜合抽象成狀態(tài)；由棧頂?shù)臓顟B(tài)和現(xiàn)行的輸入符號(hào)唯一確定每一步工作u LR分析器的核心是一張分析表：u ACTIONs，a：當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)，應(yīng)采取什么動(dòng)作.u GOTOs，X：狀態(tài)s面對(duì)文法符號(hào)X時(shí)，下一狀態(tài)是什么u

25、文法G的每個(gè)產(chǎn)生式的右部添加一個(gè)圓點(diǎn)稱為G的LR(0)項(xiàng)目例：如:A®XYZ有四個(gè)項(xiàng)目：A®.XYZ A®X.YZ A®XY.Z A®XYZ. F A®a . 稱為"歸約項(xiàng)目"F 歸約項(xiàng)目 S®a . 稱為"接受項(xiàng)目"F A®a .ab (aÎVT) 稱為"移進(jìn)項(xiàng)目"F A®a .Bb (BÎVN) 稱為"待約項(xiàng)目".例：文法G(S¢) S¢E EaA|bB AcA|d BcB|d 該文

26、法的項(xiàng)目有：1.S¢·E 2.S¢E· 3.E·aA 4.Ea·A 5.EaA· 6.A·cA 7.Ac·A 8.AcA· 9.A·d 10.Ad· 11.E·bB 12.Eb·B 13.EbB· 14.B·cB 15.Bc·B 16.BcB· 17.B·d 18.Bd·u 構(gòu)造識(shí)別文法所有活前綴的NFA方法 1. 若狀態(tài)i為X®X1 Xi-1.Xi Xn ，狀態(tài)j為X®X1

27、Xi-1Xi .Xi+1 Xn ，則從狀態(tài)i畫一條標(biāo)志為Xi的有向邊到狀態(tài)j； 2. 若狀態(tài)i為X®a .Ab ，A為非終結(jié)符，則從狀態(tài)i畫一條e邊到所有狀態(tài)A®.g。u 把識(shí)別文法所有活前綴的NFA確定化。u 構(gòu)成識(shí)別一個(gè)文法活前綴的DFA的項(xiàng)目集(狀態(tài))的全體稱為文法的LR(0)項(xiàng)目集規(guī)范族。LR(0)分析表的構(gòu)造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是一個(gè)LR(0)文法。u 分析表的ACTION和GOTO子表構(gòu)造方法：1. 若項(xiàng)目Aa·

28、;ab屬于Ik且GO(Ik, a)Ij，a為終結(jié)符，則置ACTIONk,a 為“sj”。2. 若項(xiàng)目Aa·屬于Ik，那么，對(duì)任何終結(jié)符a(或結(jié)束符#)，置ACTIONk,a為 “rj”(假定產(chǎn)生式Aa是文法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)志”。u 按上述方法構(gòu)造出的ACTION與GOTO表如果不含多重入口，則稱該文法為SLR(1)文法。u 使用SLR表的分析器叫做一個(gè)S

29、LR分析器。u 每個(gè)SLR(1)文法都是無二義的。但也存在許多無二義文法不是SLR(1)的.I1、I2和I9都含有“移進(jìn)歸約”沖突。FOLLOW(E)#, ), +，5.3.4 規(guī)范LR分析表的構(gòu)造u 我們需要重新定義項(xiàng)目，使得每個(gè)項(xiàng)目都附帶有k個(gè)終結(jié)符。每個(gè)項(xiàng)目的一般形式是Aa·b, a1a2ak ，這樣的一個(gè)項(xiàng)目稱為一個(gè)LR(k)項(xiàng)目。項(xiàng)目中的 a1a2ak 稱為它的向前搜索符串(或展望串)。u 向前搜索符串僅對(duì)歸約項(xiàng)目Aa·，a1a2ak有意義。對(duì)于任何移進(jìn)或待約項(xiàng)目Aa·b, a1a2ak, b¹e，搜索符串 a1a2ak 沒有作用。按上述算法構(gòu)

30、造的分析表，若不存在多重定義的入口(即，動(dòng)作沖突)的情形，則稱它是文法G的一張規(guī)范的LR(1)分析表。使用這種分析表的分析器叫做一個(gè)規(guī)范的LR分析器。具有規(guī)范的LR(1)分析表的文法稱為一個(gè)LR(1)文法。LR(1)狀態(tài)比SLR多，LR(0)ÌSLR Ì LR(1) Ì無二義文法。第六章 屬性文法和語法制導(dǎo)翻譯6.1 屬性文法u 屬性文法（也稱屬性翻譯文法）u 在上下文無關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)（終結(jié)符或非終結(jié)符）配備若干相關(guān)的“值”（稱為屬性）。u 屬性代表與文法符號(hào)相關(guān)信息，如類型、值、代碼序列、符號(hào)表內(nèi)容等u 屬性可以進(jìn)行計(jì)算和傳遞u 語義規(guī)則：對(duì)于文

31、法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則u 屬性u(píng) 綜合屬性：“自下而上”傳遞信息u 繼承屬性：“自上而下”傳遞信息u 綜合屬性u(píng) 在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。u 使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則計(jì)算綜合屬性的值u 僅僅使用綜合屬性的屬性文法稱S屬性文法u 繼承屬性u(píng) 在語法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定u 用繼承屬性來表示程序設(shè)計(jì)語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便6.2.3 一遍掃描的處理方法u 一遍掃描的處理方法是在語法分析的同時(shí)計(jì)算屬性值 u 所采用的語法分析方法u 屬性的計(jì)算次序u L屬性文法適合于一遍掃描的

32、自上而下分析u S屬性文法適合于一遍掃描的自下而上分析 6.4 L-屬性文法和自頂向下翻譯u 通過深度優(yōu)先的方法對(duì)語法樹進(jìn)行遍歷，計(jì)算屬性文法的所有屬性值u LL(1)：自上而下分析方法，深度優(yōu)先建立語法樹第七章 語義分析和中間代碼產(chǎn)生u 靜態(tài)語義檢查u 類型檢查u 控制流檢查u 一致性檢查 u 相關(guān)名字檢查u 名字的作用域分析 7.1 中間語言u(píng) 常用的中間語言：u 后綴式，逆波蘭表示u 圖表示： DAG、抽象語法樹u 三地址代碼u 三元式u 四元式u 間接三元式u 逆波蘭表示法不用括號(hào)。只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它進(jìn)行唯一分解。u 后綴式的計(jì)算u 用一個(gè)棧實(shí)現(xiàn)。u 一般的計(jì)算過程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。7.4 布爾表達(dá)式的翻譯u 布爾表達(dá)式的兩個(gè)基本作用:u 用于邏輯演算,計(jì)算邏輯值;u 用于控制語句的條件式.u 產(chǎn)生布爾表達(dá)式的文法: EE or E | E andE | Ø E | (E) | i rop i | i第十章 優(yōu)化u 優(yōu)