軟考軟件設(shè)計(jì)師專題講義：程序語(yǔ)言部分

　　2.4代碼優(yōu)化

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

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

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

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

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

　　最后給出了另一個(gè)�？键c(diǎn)：?jiǎn)棠匪够�的方法分類�?/P>

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

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

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

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

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

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

　　n 給出某語(yǔ)言的上下文無(wú)法方法，要求證明該文法是否二義;

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

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

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

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

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

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

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

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

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

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

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

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

　　a.題目給定一正規(guī)式，要求給出其N(xiāo)FA，DFA或最簡(jiǎn)DFA形式。

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

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

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

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

　　這些考點(diǎn)，綜合起來(lái)看，是在正規(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)換是正確的。