2012年軟考系統(tǒng)分析師經(jīng)典教程：重點(diǎn)與難點(diǎn)

　　第4頁：

　　2.5.4 代碼優(yōu)化

　　優(yōu)化是對程序進(jìn)行等價(jià)(指不改變程序的運(yùn)行結(jié)果)變換，經(jīng)變換后的程序能生成更有效(運(yùn)行時(shí)間更短、占用空間更小)的目標(biāo)代碼。

　　根據(jù)優(yōu)化所涉及的程序范圍，可分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個(gè)不同的級別

　　編譯原理重點(diǎn)難點(diǎn)歸納：

　　了解編譯程序工作的大致過程，要清楚編譯程序是如何生成的。請大家記憶并理解以下概念：編譯程序，解釋程序，翻譯程序，掃描器，分析器，編譯前端與后端，符號表。

　　要掌握的幾個(gè)重量級概念：上下文無關(guān)文法，語法分析樹和二義性，同時(shí)也引出了與此緊密聯(lián)系的其它概念：推導(dǎo)，句型，句子，最左推導(dǎo)，最右推導(dǎo)等。

　　最后給出了另一個(gè)常考點(diǎn)：喬姆斯基的方法分類。

　　1.上下文無關(guān)文法的定義，判斷和轉(zhuǎn)化，以及與上下文無關(guān)文法密切相關(guān)的概念。

　　首先，應(yīng)該掌握上下文無關(guān)文法的四個(gè)構(gòu)成要素;

　　其次，應(yīng)該清楚對于上下文無關(guān)文法，其每個(gè)產(chǎn)生式的左部和右部必須滿足的條件。

　　在有關(guān)上下文無關(guān)文法的考點(diǎn)中，有這樣幾種考查方式：

　　◆ 給出某語言的自然語言描述方式，要求寫該語言的上下文無關(guān)文法表述形式;

　　◆ 給出某語言的上下文無關(guān)文法，要求用自然語言描述該語言;

　　◆ 給出某語言的上下文無法方法，要求證明該文法是否二義;

　　◆ 給出某語言的上下文無關(guān)文法，要求給出指定句子的最左或最右推導(dǎo);

　　◆ 給出某語言的上下文無關(guān)文法，要求給出指定句子的語法分析樹;

　　◆ 給出一個(gè)具有二義性的上下文無關(guān)文法，要求將其轉(zhuǎn)換成非二義性的。

　　2.喬姆斯基的文法分類：

　　首先，應(yīng)該非常清楚喬姆斯基對于四種文法分類的定義，并能理解其含義。幾種文法中，最基本的是0型文法，讀者可以將它理解為其它所有文法的基礎(chǔ)，它是可以表示任何語言的文法。后面的1，2,3三種文法，是分別對于0型文法產(chǎn)生式的兩邊作了不同的限制之后，形成了新的文法。比如：規(guī)定0型文法的每個(gè)產(chǎn)生式中，其左邊字符集長度小于右邊字符集長度并且同時(shí)規(guī)定開始符號只可出現(xiàn)于產(chǎn)生式的左邊，不能出現(xiàn)在任何產(chǎn)生式的右邊，這樣，就成為了1型文法(即上下文有關(guān)文法)。其它與此類似，在1型文法的基礎(chǔ)上，進(jìn)一步規(guī)定該文法的任意產(chǎn)生式，其左部只允許有一個(gè)字符且必須為非終結(jié)符，這樣就構(gòu)成了上下文無關(guān)文法;再在上下文無關(guān)文法的基礎(chǔ)上進(jìn)行限制：規(guī)定除了左部有且只有一個(gè)非終結(jié)符外，還特別規(guī)定右部最多只允許有兩個(gè)字符，當(dāng)為兩上字符時(shí)必須一個(gè)為非終結(jié)符，另一個(gè)為終結(jié)符，而當(dāng)只有一個(gè)字符時(shí)，必須為終結(jié)符，這樣的文法就成了正規(guī)文法。這樣一層套一層的限制，就形成了從0型到3型文法的定義體制，每一層都是在前一層基礎(chǔ)上進(jìn)行定義的，所以說前一層一定比該層表示的范圍要廣，因?yàn)槠涫艿南拗埔�少�?/P>

　　那么，我們在判斷一個(gè)文法時(shí)應(yīng)該以什么規(guī)則來判斷呢?這個(gè)規(guī)則當(dāng)然是：3->2->1->0.也就是說，我們判斷是從高到低來判斷的，比如：一旦判斷其屬于正規(guī)文法之后就沒必要再判斷其是否屬于上下文無關(guān)的了(因?yàn)樗�必定屬于上下文無關(guān)，我們應(yīng)該以最高規(guī)則來判定其屬于的文法類型)，其它情況與此類推。只有當(dāng)我們判斷不屬于3型文法時(shí)，我們才向下判斷，其是不是屬于2型的，若不屬于2型的，則依此類推再向下判斷。最終的結(jié)果如果不屬于3，2和1三種類型，那就只有屬于0型了。

　　“給定一個(gè)文法，要求判斷其屬于何種文法”是一個(gè)重要考點(diǎn)，其出題形式可能是填空，選擇等多種題型。

　　正規(guī)式和有限自動機(jī)，對于詞法分析一章的考點(diǎn)，可以說80%到90%以上集中在這一節(jié)的內(nèi)容上。針對于這一節(jié)的知識點(diǎn)介紹和考點(diǎn)分析：

　　1)詞法分析器的功能：輸入的是源程序，輸出的是分析完成的單詞符號;

　　2)狀態(tài)轉(zhuǎn)換圖：是一張有向圖，用于標(biāo)識在特定的輸入下詞法分析器應(yīng)該選擇的分析方向。

　　對于考點(diǎn)1)，作為選擇進(jìn)行考查，而對于考點(diǎn)2)，多數(shù)是與有限自動機(jī)一些考查，要求給出以“狀態(tài)圖”表示的確定有限自動機(jī)，或者是要求直接給出針對于某正規(guī)式的狀態(tài)轉(zhuǎn)換圖，大家記住一句話：狀態(tài)轉(zhuǎn)換圖，就是一張當(dāng)輸入不同的內(nèi)容時(shí)，選擇不同分析路徑的有向圖。

　　下面，我們重點(diǎn)看一下有關(guān)“正規(guī)式與有限自動機(jī)”這一考點(diǎn)的各種可能考查形式：

　　a.題目給定一正規(guī)式，要求給出其NFA，DFA或最簡DFA形式。

　　b.題目給定一用狀態(tài)圖表示的NFA，要求給出其對應(yīng)的DFA或最簡DFA形式。

　　c.題目給定一NFA，DFA或最簡DFA，要求給出其對應(yīng)的正規(guī)式。

　　d.題目給定一正規(guī)集，要求給出其相應(yīng)的DFA。

　　e.題目給定一用自然語言描述的正規(guī)集，要求給出其相應(yīng)的正規(guī)式表示形式。

　　這些考點(diǎn)，綜合起來看，是在正規(guī)式，正規(guī)集，NFA和DFA之間作各種可能的轉(zhuǎn)換，當(dāng)然這種轉(zhuǎn)換正確與否的判斷標(biāo)準(zhǔn)就是轉(zhuǎn)換之后的內(nèi)容是不是與轉(zhuǎn)換之前的內(nèi)容等價(jià)，如果等價(jià)，我們就認(rèn)為轉(zhuǎn)換是正確的。

　　在考點(diǎn)e這類的轉(zhuǎn)換題目中，有一些是需要另外規(guī)納出來的，他們在某一方面具有共同的特征，如果掌握了其中一題，將可舉一反三解出其它題。

　　比如有以下的幾種題目就可以作以總結(jié)：

　　1.求偶(奇)數(shù)個(gè)a與偶(奇)數(shù)個(gè)b構(gòu)成的語言的正規(guī)式;

　　2.求能被3(4、5、或其它任意給定的n)整除的正規(guī)式的DFA;

　　3.求不以(或以)n(n從0到9)開頭的XXXX(符號某種條件的)奇(偶數(shù))數(shù)的正規(guī)式。

　　以上三種類型的考題，在每一種類型中，都是有規(guī)律可循的，也都有簡便的方法可以幫助我們快速求解其正規(guī)式，進(jìn)而快速確定DFA及最簡DFA。針對于這三種類型的解題思路分析，我會在另外的文章中給出。

　　當(dāng)詞法分析器對源程序進(jìn)行了詞法分析，獲得了一個(gè)個(gè)獨(dú)立的單詞符號后，編譯程序總控模塊就會調(diào)用語法分析子程序?qū)�這些單詞符號集進(jìn)行語法分析，也就是：利用該文法的產(chǎn)生式來判斷這些單詞符號是否足以構(gòu)成一個(gè)在語法上正確的程序。如果可以構(gòu)成一個(gè)在語法上正確的程序，則接著作編譯下面的工作，比如：語法制導(dǎo)翻譯，中間代碼生成、代碼優(yōu)化等工作;而如果不能構(gòu)成一個(gè)在語法上正確的程序，則給出相應(yīng)的錯誤提示并將錯誤信息記入對應(yīng)的數(shù)據(jù)記錄中。

　　語法分析的規(guī)則主要基于兩種：自上而下分析和自下而上分析。自上而下分析的大致思路是：根據(jù)產(chǎn)生式規(guī)則，從產(chǎn)生式的開始符號進(jìn)行推導(dǎo)，一直推導(dǎo)到可以產(chǎn)生當(dāng)前要判斷的這個(gè)句子為止。如果推導(dǎo)了所有可能情況，但沒有推出這樣的句子，那么這個(gè)句子就是不符合該語言的語法規(guī)則的(產(chǎn)生式即定義了語言的語法規(guī)則)。

　　一種自上而下的分析方法：LL(1)分析法，下面，我介紹一下本章的主要常考知識點(diǎn)及考查角度：

　　1.給定一文法，要求將其改造成可以進(jìn)行自上而下分析的形式。

　　這里面涉及到兩方面的知識點(diǎn)：

　　左遞歸的去除及公因子的提取。所謂的左遞歸是指產(chǎn)生式是形如：P->Pab…的形式，即：產(chǎn)生式右邊的第一個(gè)字符就是該產(chǎn)生式左邊的那個(gè)非終結(jié)符。當(dāng)一個(gè)文法中有左遞歸的產(chǎn)生式時(shí)，是無法進(jìn)行自上而下推導(dǎo)的，因?yàn)橹灰�這個(gè)產(chǎn)生式被推導(dǎo)，就勢必會使這種推導(dǎo)過程陷入一種遞歸循環(huán)無休止推導(dǎo)的情形。去除左遞歸的方法是比較簡單的，其基本思路是將左遞歸通過轉(zhuǎn)化變成與之等價(jià)的右遞歸。即將形如：P->Pa|b 形式的左遞歸變成如下形式：P->bP',P'->aP'|e(注：e表示空)。提取公因子的目的是為了避免推導(dǎo)過程中的回溯，也就是使每一次的向下推導(dǎo)是唯一的，而不是有多個(gè)選擇，因?yàn)橛卸鄠�(gè)選擇的話就可能出現(xiàn)回溯。

　　2.給定一文法，要求判斷其是否為LL(1)文法。判斷一個(gè)文法是否為LL(1)文法主要有兩種方法：一種是判斷文法是否二義，如果二義，則文法必定不為LL(1)(注意：此命題的否合命題不真);二是根據(jù)關(guān)于LL(1)文法成立的三個(gè)條件。顯然，第一種判斷方法效率是比較高的，但是，其只能判斷文法“不為”LL(1)的，并不能判定文法“是”LL(1)的，要判斷文法“是”LL(1)的，就得用第二種方法，但在考題中，如果要求你判斷某文法是否為LL(1)的，則該文法多半不是LL(1)的，而且此點(diǎn)可以很容易地用二義性來證明，這是一種�？夹问�。

　　3.給定一文法，要求構(gòu)造LL(1)分析表。LL(1)分析的重點(diǎn)和難點(diǎn)內(nèi)容都在其分析表的構(gòu)造上，后面要講的LR分析也是，它的難點(diǎn)也在于其分析表的構(gòu)造。構(gòu)造LL(1)分析表是一個(gè)常考點(diǎn)，也是大分值題的可能出題點(diǎn)，對于普通學(xué)校而言，相比于LR分析，他們更喜歡考LL(1)。LL(1)分析表構(gòu)造前，需要先弄清FIRST集和FOLLOW集的構(gòu)造方法，簡單地說，F(xiàn)IRST集是用于求非終結(jié)符推出的產(chǎn)生式中的第一個(gè)終結(jié)符的，而FOLLOW集是用于求與該非終結(jié)符后緊鄰的那個(gè)終結(jié)符的。FIRST集的構(gòu)造方法見編譯原理的教材，在構(gòu)造的三個(gè)規(guī)則中，前兩個(gè)規(guī)則都是比較容易理解的，第三個(gè)規(guī)則看上去就有點(diǎn)復(fù)雜了，我們簡單地來看第三條規(guī)則，就是：當(dāng)由X推出的產(chǎn)生式中前面若干個(gè)非終結(jié)符，其FIRST集均含有空時(shí)，就取這若干個(gè)非結(jié)符的后一個(gè)字符的FIRST集，當(dāng)然，這“后一個(gè)字符”可能是終結(jié)符，也可能是非終結(jié)符，只要其FIRST集不為空就行;而當(dāng)X推出的右邊全是非終結(jié)符，且這些非終結(jié)符的FIRST集全含有空時(shí)，就把空加到FIRST(X)中。FOLLOW集的構(gòu)造方法很簡單，不作詳細(xì)講解了。LL(1)分析表的構(gòu)造方法見教材，構(gòu)造規(guī)則主要有3條。說到這里，大家應(yīng)該明確分析表中的各個(gè)單元到底代表什么含義，我作一下簡單的介紹：分析表中的最頂一行，是產(chǎn)生式中所有的終結(jié)符;分析表中的最左一列，是產(chǎn)生式中所有的非終結(jié)符;而產(chǎn)生式中間的諸多單元格則可以存放該文法的產(chǎn)生式或特殊標(biāo)志(比如成功和錯誤標(biāo)志)。這樣的二維表格構(gòu)成的單元格的含義是：當(dāng)左邊的非終結(jié)符遇到最上一行中的某個(gè)終結(jié)符時(shí)應(yīng)該選擇哪個(gè)產(chǎn)生式進(jìn)行向下的推導(dǎo)，這個(gè)產(chǎn)生式就是放在對應(yīng)二維坐標(biāo)處的產(chǎn)生式。

　　4.給定一文法，先要求求解其LL(1)分析表，然后要求給出針對于某一個(gè)句子的具體分析過程。這個(gè)考點(diǎn)的第二問主要就是考查考生對預(yù)測分析程序的工作過程的理解了，預(yù)測分析程序完全是按照分析表機(jī)械工作的，針對于考生而言，要明確何時(shí)出棧，何時(shí)入棧，以及如何入棧，這些細(xì)節(jié)信息都是要通過作題掌握的，只理解而不會熟練解答是沒有用的。

　　5.給定一文法，要求給出其遞歸下降分析程序。遞歸下降分析的條件也是無左遞歸及不帶回溯，其構(gòu)造的過程比較簡單，就是將每個(gè)非終結(jié)符處理成可以互相遞歸調(diào)用的過程體。詳細(xì)過程參照P74到P75的例子，你可以試著寫一下P76頁教材上未列出的F過程的實(shí)現(xiàn)。

　　相關(guān)推薦：

　　2012年軟考系統(tǒng)分析師考試60天完美復(fù)習(xí)計(jì)劃

　　2012年軟件水平考試網(wǎng)絡(luò)工程師章節(jié)筆記講義匯總

　　2012年上半年軟件水平考試成績查詢匯總