《編譯原理》復習要點

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

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

3、進行加工變換，以期在最后階段產(chǎn)生更高效的目標代碼。依循的原則：程序的等價變換規(guī)則FOR K:=1 TO 100 DO BEGIN M := I + 10 * K; N := J + 10 * K; END4. 目標代碼產(chǎn)生任務: 把中間代碼變換成特定機器上的目標代碼。依賴于硬件系統(tǒng)結(jié)構(gòu)和機器指令的含義目標代碼三種形式:a) 絕對指令代碼: 可直接運行 b) 可重新定位指令代碼: 需要連接裝配c) 匯編指令代碼: 需要進行匯編三. 編譯程序結(jié)構(gòu)u 編譯程序總框 (簡答題5分)第二章 高級語言及其語法描述2.1.1語法詞法規(guī)則：單詞符號的形成規(guī)則。a) 單詞符號是語言中具有獨立意義的最基本結(jié)構(gòu)。一

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

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

6、V0V1V2V3 稱V*是V的閉包;記 VVV* ，稱V+是V的正規(guī)閉包。例如: 設(shè)：U a, aa 那么：U* = e , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, i) 0型(短語文法，圖靈機)： 產(chǎn)生式形如： a b 其中：a (VT VN)*且至少含有一個非終結(jié)符；b (VT VN)* 任何0型語言都是遞歸可枚舉的。j) 1型(上下文有關(guān)文法，線性界限自動機)： 產(chǎn)生式形如： a b 其中：|a| |b|，僅 Se 例外。意味著對非終結(jié)符進行替換時務必考慮上下文，并且，一般不允許替換成空串e 。k) 2型(上下文無關(guān)文法，非確定下推自動機)： 產(chǎn)生

7、式形如： A b 其中：A VN；b (VT VN)*。非終結(jié)符的替換可以不必考慮上下文。l) 3型(正規(guī)文法，有限自動機)：右線性文法 產(chǎn)生式形如： A aB 或 A a 其中： a VT*；A，BVN左線性文法 產(chǎn)生式形如： A Ba 或 A a 其中： a VT*；A，BVN正規(guī)文法的能力要比上下文無關(guān)文法弱得多。四種類型描述能力比較 m) 上下文無關(guān)文法的定義： 一個上下文無關(guān)文法G是一個四元式 G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT VN=S：文法的開始符號，SVNP：產(chǎn)生式集合(有限)，每個產(chǎn)生式形式為Pa， PVN， a (VT

8、 VN)*開始符S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。例：文法G1(A)： A c|AbG1(A)的語言?解：L(G1)=c，cb，cbb，以c開頭，后繼若干個bn) 定義：如果一個文法存在某個句子對應兩顆不同的語法樹，則說這個文法是二義的。G(E)： E i|E+E|E*E|(E) 是二義文法。o) 語言的二義性：一個語言是二義性的，如果對它不存在無二義性的文法?？赡艽嬖贕和G，一個為二義的，一個為無二義的。但L(G)=L(G) 2. 狀態(tài)轉(zhuǎn)換圖 a) 概念：狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。b) 結(jié)點代表狀態(tài)，用圓圈表示。c) 狀態(tài)之間用箭弧連結(jié)，箭弧上的標記(字符)代表射出結(jié)狀態(tài)下可能出現(xiàn)的輸

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

10、s，輸入字符為a時，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s。我們把s稱為s的一個后繼狀態(tài)。d) S0S是唯一的一個初態(tài)； e) FS ：終態(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 非確定有限自動機(NFA)定義：一個非確定有限自動機(NFA) M是一個五元式M=(S, S, f, S0, F)，其中：1 S: 有窮狀態(tài)集；2 S ：輸入字母表(有窮)；3 f: 狀態(tài)轉(zhuǎn)換函數(shù)，為SS*2S的部分映射(非單值)；4 S0

11、S是非空的初態(tài)集；5 F S ：終態(tài)集(可空)。從狀態(tài)圖中看NFA 和DFA的區(qū)別： 1 弧上的標記可以是S*中的一個字，而不一定是單個字符； 2 同一個字可能出現(xiàn)在同狀態(tài)射出的多條弧上。DFA是NFA的特例。定義：對于任何兩個有限自動機M和M，如果L(M)=L(M)，則稱M與M等價。自動機理論中一個重要的結(jié)論：判定兩個自動機等價性的算法是存在的。對于每個NFA M存在一個DFA M，使得 L(M)=L(M)。亦即DFA與NFA描述能力相同。把上述NFA確定化采用子集法.設(shè)I是M的狀態(tài)集的一個子集，定義I的e-閉包e-closure(I)為: i) 若sI，則se-closure(I)； ii

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

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

14、同一子集的任何兩個狀態(tài)是等價的。最后，讓每個子集選出一個代表，同時消去其他狀態(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 語法分析的方法：u 自下而上分析法(Bottom-up)u 自上而下分析法(Top-down)u 基本思想：它從文法的開始符號

15、出發(fā)，反復使用各種產(chǎn)生式，尋找匹配的推導。u 遞歸下降分析法：對每一語法變量(非終結(jié)符)構(gòu)造一個相應的子程序，每個子程序識別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實現(xiàn)對輸入串的識別。u 預測分析程序F 優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。4.3 LL(1)分析法u 構(gòu)造不帶回溯的自上而下分析算法u 要消除文法的左遞歸性u 克服回溯4.3.1 左遞歸的消除u 直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為PPa | b 其中b不以P開頭。 我們可以把P的規(guī)則等價地改寫為如下的非直接左遞歸形式：PbP左遞歸變右遞歸PaP|eu 一般而言，假定P關(guān)于的全部產(chǎn)生式是 PPa1 | P

16、a2 | | Pam | b1 | b2|bn其中，每個a都不等于e，每個b都不以P開頭 那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： Pb1P | b2P | | bnP Pa1P | a2P | | amP | eu 提取公共左因子: 假定關(guān)于A的規(guī)則是 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm (其中，每個g 不以d開頭) 那么，可以把這些規(guī)則改寫成AdA | g 1 | g 2 | | g mAb 1 | b 2 | | b nu 經(jīng)過反復提取左因子，就能夠把每個非終結(jié)符(包括新引進者)的所有候選首符集變成為兩兩不相交。4.3.3 LL(1)

17、分析條件u 假定S是文法G的開始符號，對于G的任何非終結(jié)符A，我們定義特別是，若，則規(guī)定FOLLOW(A)n 構(gòu)造不帶回溯的自上而下分析的文法條件1. 文法不含左遞歸，2. 對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若 Aa 1|a 2|a n 則 FIRST(a i)FIRST(a j)f (ij) i=1,2,.,n3. 對文法中的每個非終結(jié)符A，若它存在某個候選首符集包含e，則FIRST(A)FOLLOW(A)=f如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。第五章 語法分析自下而上分析語法分析的方法：自下而上分析法(Bottom-up)u 基本思想：

18、從輸入串開始，逐步進行“歸約”，直到文法的開始符號。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。u 算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進行語法分析。適合分析表達式。u LR分析法：規(guī)范歸約5.1.2 規(guī)范歸約1.定義：令G是一個文法，S是文法的開始符號，假定abd是文法G的一個句型，如果有 且 ，則稱b是句型abd相對于非終結(jié)符A的短語。特別是，如果有Ab,則稱b是句型abd相對于規(guī)則A b的直接短語。一個句型的最左直接短語稱為該句型的句柄。2.歸約采用“移進歸約”思想進行自下而上分析?；舅枷耄河靡粋€寄存符號的先進后出棧，把輸入符號

19、一個一個地移進到棧里，當棧頂形成某個產(chǎn)生式的候選式時，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符號。5.2 算符優(yōu)先分析u 四則運算的優(yōu)先規(guī)則： 先乘除后加減，同級從左到右u 考慮二義文法文法G(E)：G(E)： E i| E+E|E-E|E*E|E/E|(E)u 它的句子有幾種不同的規(guī)范規(guī)約。u 歸約即計算表達式的值。歸約順序不同，則計算的順序也不同，結(jié)果也不一樣。u 如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進行歸約，則歸約過程是唯一的。u 起決定作用的是相鄰的兩個算符之間的優(yōu)先關(guān)系。u 所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找“可歸約串”和進行歸約。5.2.

20、1 算符優(yōu)先文法及優(yōu)先表構(gòu)造u 一個文法，如果它的任一產(chǎn)生式的右部都不含兩個相繼(并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式右部：QR 則我們稱該文法為算符文法。u 約定：u a、b代表任意終結(jié)符；u P、Q、R代表任意非終結(jié)符；u 代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。u 假定G是一個不含e-產(chǎn)生式的算符文法。對于任何一對終結(jié)符a、b，我們說：1. a=b當且僅當文法G中含有形如Pab或PaQb的產(chǎn)生式；2. ab 當且僅當G中含有形如PRb的產(chǎn)生式，而 Ra或RaQ。n 如果一個算符文法G中的任何終結(jié)符對(a，b)至多只滿足下述三關(guān)系之一：a=b，ab。 則稱G是一個算符優(yōu)先文法。

21、u 從算符優(yōu)先文法G構(gòu)造優(yōu)先關(guān)系表的算法。u 通過檢查G的每個產(chǎn)生式的每個候選式，可找出所有滿足a=b的終結(jié)符對。u 確定滿足關(guān)系的所有終結(jié)符對：u 首先需要對G的每個非終結(jié)符P構(gòu)造兩個集合FIRSTVT(P)和LASTVT(P)：ab 當且僅當G中含有形如PRb的產(chǎn)生式，而 Ra或RaQ。q 有了這兩個集合之后，就可以通過檢查每個產(chǎn)生式的候選式確定滿足關(guān)系的所有終結(jié)符對。 假定有個產(chǎn)生式的一個候選形為aP 那么，對任何bFIRSTVT(P)，有 ab。u 按其定義，可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P)：1. 若有產(chǎn)生式Pa或PQa，則aFIRSTVT(P)；2. 若aFIRSTVT

22、(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P)。練習：P133-2 計算它的FIRSTVT和LASTVT； 計算G的優(yōu)先關(guān)系 。并確定G是否是一個算符優(yōu)先文法？u LR分析方法：把歷史及展望綜合抽象成狀態(tài)；由棧頂?shù)臓顟B(tài)和現(xiàn)行的輸入符號唯一確定每一步工作u LR分析器的核心是一張分析表：u ACTIONs，a：當狀態(tài)s面臨輸入符號a時，應采取什么動作.u GOTOs，X：狀態(tài)s面對文法符號X時，下一狀態(tài)是什么u 文法G的每個產(chǎn)生式的右部添加一個圓點稱為G的LR(0)項目例：如:AXYZ有四個項目：A.XYZ AX.YZ AXY.Z AXYZ. F Aa . 稱為歸約項目F 歸約項目 Sa .

23、稱為接受項目F Aa .ab (aVT) 稱為移進項目F Aa .Bb (BVN) 稱為待約項目.例：文法G(S) SE EaA|bB AcA|d BcB|d 該文法的項目有：1.SE 2.SE 3.EaA 4.EaA 5.EaA 6.AcA 7.AcA 8.AcA 9.Ad 10.Ad 11.EbB 12.EbB 13.EbB 14.BcB 15.BcB 16.BcB 17.Bd 18.Bdu 構(gòu)造識別文法所有活前綴的NFA方法 1. 若狀態(tài)i為XX1 Xi-1.Xi Xn ，狀態(tài)j為XX1 Xi-1Xi .Xi+1 Xn ，則從狀態(tài)i畫一條標志為Xi的有向邊到狀態(tài)j； 2. 若狀態(tài)i為Xa

24、 .Ab ，A為非終結(jié)符，則從狀態(tài)i畫一條e邊到所有狀態(tài)A.g。u 把識別文法所有活前綴的NFA確定化。u 構(gòu)成識別一個文法活前綴的DFA的項目集(狀態(tài))的全體稱為文法的LR(0)項目集規(guī)范族。LR(0)分析表的構(gòu)造u 假若一個文法G的拓廣文法G的活前綴識別自動機中的每個狀態(tài)(項目集)不存在下述情況： 1) 既含移進項目又含歸約項目， 2) 含有多個歸約項目 則稱G是一個LR(0)文法。u 分析表的ACTION和GOTO子表構(gòu)造方法：1. 若項目Aaab屬于Ik且GO(Ik, a)Ij，a為終結(jié)符，則置ACTIONk,a 為“sj”。2. 若項目Aa屬于Ik，那么，對任何終結(jié)符a(或結(jié)束符#)

25、，置ACTIONk,a為 “rj”(假定產(chǎn)生式Aa是文法G的第j個產(chǎn)生式)。3. 若項目SS屬于Ik，則置ACTIONk,#為 “acc”。4. 若GO(Ik,A)Ij，A為非終結(jié)符，則置GOTOk,A=j。5. 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“報錯標志”。u 按上述方法構(gòu)造出的ACTION與GOTO表如果不含多重入口，則稱該文法為SLR(1)文法。u 使用SLR表的分析器叫做一個SLR分析器。u 每個SLR(1)文法都是無二義的。但也存在許多無二義文法不是SLR(1)的.I1、I2和I9都含有“移進歸約”沖突。FOLLOW(E)#, ), +，5.3.4 規(guī)范LR分析表的構(gòu)

26、造u 我們需要重新定義項目，使得每個項目都附帶有k個終結(jié)符。每個項目的一般形式是Aab, a1a2ak ，這樣的一個項目稱為一個LR(k)項目。項目中的 a1a2ak 稱為它的向前搜索符串(或展望串)。u 向前搜索符串僅對歸約項目Aa，a1a2ak有意義。對于任何移進或待約項目Aab, a1a2ak, be，搜索符串 a1a2ak 沒有作用。按上述算法構(gòu)造的分析表，若不存在多重定義的入口(即，動作沖突)的情形，則稱它是文法G的一張規(guī)范的LR(1)分析表。使用這種分析表的分析器叫做一個規(guī)范的LR分析器。具有規(guī)范的LR(1)分析表的文法稱為一個LR(1)文法。LR(1)狀態(tài)比SLR多，LR(0)S

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

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

29、一致性檢查 u 相關(guān)名字檢查u 名字的作用域分析 7.1 中間語言u 常用的中間語言：u 后綴式，逆波蘭表示u 圖表示： DAG、抽象語法樹u 三地址代碼u 三元式u 四元式u 間接三元式u 逆波蘭表示法不用括號。只要知道每個算符的目數(shù)，對于后綴式，不論從哪一端進行掃描，都能對它進行唯一分解。u 后綴式的計算u 用一個棧實現(xiàn)。u 一般的計算過程是：自左至右掃描后綴式，每碰到運算量就把它推進棧。每碰到k目運算符就把它作用于棧頂?shù)膋個項，并用運算結(jié)果代替這k個項。7.4 布爾表達式的翻譯u 布爾表達式的兩個基本作用:u 用于邏輯演算,計算邏輯值;u 用于控制語句的條件式.u 產(chǎn)生布爾表達式的文法: EE or E | E andE | E | (E) | i rop i | i第十章 優(yōu)化u 優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能生成更有效的目標代碼。u 等價：指不改變程序的運行結(jié)果。u 有效：指目標代碼運行時間短，占用的存儲空間小。10.1 概述u 優(yōu)化的三