? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?一姚糊、概述
1、匯編授舟、編譯救恨、解釋系統(tǒng)的基礎(chǔ)知識(shí)和基本工作原理。
2释树、程序設(shè)計(jì)語(yǔ)言的基本成分:數(shù)據(jù)肠槽、運(yùn)算、控制和傳輸,程序調(diào)用的實(shí)現(xiàn)機(jī)制奢啥。
3秸仙、各類程序設(shè)計(jì)語(yǔ)言的主要特點(diǎn)和適用情況:過程式程序語(yǔ)言、面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言扫尺、函數(shù)式程序設(shè)計(jì)語(yǔ)言筋栋、邏輯程序設(shè)計(jì)語(yǔ)言的基本特點(diǎn)、腳本語(yǔ)言的特點(diǎn)正驻。
? ? ? ? ? ? ? ? ? 二弊攘、匯編、編譯姑曙、解釋系統(tǒng)基礎(chǔ)
1. 解釋與編譯
? ? ?在計(jì)算機(jī)中,使用高級(jí)語(yǔ)言開發(fā)的程序都是不能直接運(yùn)行的襟交。需要經(jīng)過一系列的處理,才能運(yùn)行。這個(gè)過程,根據(jù)其處理方式的不同,可分為:解釋型和編譯型伤靠。
解釋型:接受所輸入的用程序語(yǔ)言編寫的源程序,然后直接解釋執(zhí)行;這類語(yǔ)言中的最典型代表是BASIC.??
編譯型:它是將用某種程序語(yǔ)言編寫的源程序直接翻譯成為另一種語(yǔ)言(目標(biāo)語(yǔ)言程序),而且兩者在邏輯上等價(jià)捣域。如:C語(yǔ)言。
2. 編譯過程
所謂編譯過程,就是使用編譯程序?qū)⒏呒?jí)語(yǔ)言源程序翻譯為等價(jià)的機(jī)器語(yǔ)言程序的過程宴合。一般來說,編譯程序分為以下幾個(gè)部分:詞法分析焕梅、語(yǔ)法分析、語(yǔ)義分析卦洽、中間代碼生成贞言、代碼優(yōu)化、目標(biāo)代碼生成以及貫穿始終的表格管理與出錯(cuò)處理阀蒂。各部分之間的關(guān)系如圖3-2所示该窗。
詞法分析:從左到右逐字符讀入源程序,識(shí)別出一個(gè)個(gè)單詞符號(hào);它是根據(jù)語(yǔ)言的詞法規(guī)則(單詞結(jié)構(gòu)規(guī)則)進(jìn)行的。本節(jié)第4部分對(duì)詞法分析進(jìn)行了詳細(xì)介紹蚤霞。
語(yǔ)法分析:在詞法分析的基礎(chǔ)上將單詞符號(hào)序列分解成各類,諸如"程序"酗失、"語(yǔ)句"、"表達(dá)式"等
語(yǔ)法單位昧绣。
語(yǔ)義分析:審查源程序有無語(yǔ)義錯(cuò)誤,為代碼生成階段收集類型信息规肴。
中間代碼生成:在語(yǔ)法分析過程中,隨著分析的進(jìn)展,一條產(chǎn)生式獲得匹配或用于歸約時(shí),根據(jù)這條產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的方法稱為語(yǔ)法制導(dǎo)翻譯。通過翻譯后,將生成中間代碼。不同的高級(jí)程序語(yǔ)言可能生成同樣的中間代碼奏纪。編譯程序使用的中間代碼通常有逆波蘭鉴嗤、三元式斩启、四元式和樹形四種表示法序调。
代碼優(yōu)化:代碼優(yōu)化是對(duì)程序進(jìn)行等價(jià)變換,使其生成更有效(運(yùn)行時(shí)間更短、占用空間更小)的目標(biāo)代碼兔簇。根據(jù)優(yōu)化所涉及的程序范圍,可以分為局部?jī)?yōu)化发绢、循環(huán)優(yōu)化和全局優(yōu)化三個(gè)不同的級(jí)別。
目標(biāo)代碼生成:目標(biāo)代碼生成是把經(jīng)過語(yǔ)法分析或優(yōu)化后的中間代碼作為輸入,將其轉(zhuǎn)換成特定機(jī)器的機(jī)器語(yǔ)言或匯編語(yǔ)言代碼作為輸出,這樣的轉(zhuǎn)換程序稱為代碼生成器垄琐。
3. 形式語(yǔ)言基本知識(shí)
抽象地說,語(yǔ)言是按照一定規(guī)則排列的符號(hào)和集合边酒。要形式化地描述一個(gè)語(yǔ)言,就需要借助以下一些基本概念。
字母表∑ :非空的有窮集合,例如 ∑ = {a,b}.
字符串:由∑ 的符號(hào)組成的有窮序列叫做字母表∑ 上的字符串狸窘。其中包含的字符數(shù),稱為長(zhǎng)度墩朦。記做|字符串名|.長(zhǎng)度為0的為空串,記做e.要注意的是,e中包括一個(gè)元素!而 ?才是沒有元素的空串。
形式語(yǔ)言: 上的字符串的全體記為∑ *, ∑*的任何子集都稱做字母表?上的形式語(yǔ)言,簡(jiǎn)稱語(yǔ)言翻擒。
前綴氓涣、后綴:設(shè)v是一個(gè)字符串,由v左邊若干連續(xù)符號(hào)組成的字符串稱做v的前綴。由v右邊若
干連續(xù)符號(hào)組成的字符串稱為v的后綴陋气。
連接:設(shè)a=a1a2...an,b=b1b2...bn,則ab表示它們的連接,值為:a1a2...an b1b2...bn.
連續(xù)重復(fù)(方冪):把n個(gè)a的連接記做an.
下面是幾個(gè)常見的字集運(yùn)算(設(shè)A,B?S*,即A劳吠、B是字母表S上的字集):
或操作:AxB={a |axA或a∈B}.
積運(yùn)算:AB={ab |axA且b∈B}.
冪運(yùn)算:An=A·An-1=An-1·A,A0={e}.??
正則閉包:A+=A1∪A2∪A3∪...∪An∪...(也就是所有冪的組合)。?
?閉包:A*=A0∪A+(在正則閉包的基礎(chǔ)上,加上A0)巩趁。
(1)什么是形式文法
文法就是用來描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則痒玩。我們可以從一個(gè)簡(jiǎn)單的例子來理解文法,如下所示:
張三和李四是工程師。
由五個(gè)詞組成:張三 和 李四 是 工程師? 組成一個(gè)句子:由主語(yǔ)议慰、謂語(yǔ)構(gòu)成蠢古。我們知道中文的文法:
<句子>→<主語(yǔ)><謂語(yǔ)>
<主語(yǔ)>→<名詞詞組>
<名詞詞組>→<名詞><連詞><名詞詞組>
<謂語(yǔ)>→<動(dòng)賓詞組>
<動(dòng)賓詞組>→<動(dòng)詞><賓語(yǔ)>
<賓語(yǔ)>→<名詞>
<名詞>→張三|李四|工程師
<連詞>→和
<動(dòng)詞>→是
而在上面的例子中:所有用<>包括起來的都是"非終結(jié)符",而所有直接寫出來的就是"終結(jié)符",以上規(guī)則就是產(chǎn)生式。從上面的例子中,我們通過感性認(rèn)識(shí)理解别凹。
非終結(jié)符:它不是語(yǔ)言的組成部分,而是在推導(dǎo)過程中的占位符,最終要替換成終結(jié)符草讶。? 終結(jié)符:語(yǔ)言是組成部分,是最后的內(nèi)容。
產(chǎn)生式:用終結(jié)符替代非終結(jié)符的規(guī)則番川。? 起始符:能夠用于語(yǔ)言開頭的符號(hào),在本例中的<主語(yǔ)>就是起始符到涂。? 總結(jié)而言,整個(gè)推導(dǎo)的過程為:
<句子> <主語(yǔ)><謂語(yǔ)>
<名詞詞組><謂語(yǔ)> <主語(yǔ)>→<名詞詞組>
<名詞><連詞><名詞詞組><謂語(yǔ)>
<名詞詞組>→<名詞><連詞><名詞詞組>
<名詞><連詞><名詞詞組><動(dòng)賓詞組> <謂語(yǔ)>→<動(dòng)賓詞組>? <名詞><連詞><名詞詞組><動(dòng)詞><名詞>
<動(dòng)賓詞組>→<動(dòng)詞><賓語(yǔ)>
張三和李四是工程師? 我們可以從中發(fā)現(xiàn),它也可以推導(dǎo)出:"張三和工程師是李四",很顯然,它屬于文法正確,但語(yǔ)義是錯(cuò)誤的。
(2)文法的分類
根據(jù)喬姆斯基的分類法,文法可以分成四種類型,如表3-3所示
? ? ? ? ?要根據(jù)這樣的定義來對(duì)文法進(jìn)行判斷,總是讓許多考生無從下手,其實(shí)只要掌握一些規(guī)律,就能夠更好地完成這一任務(wù)颁督。
? ? ? ? 0型文法:就是一般形式的方法,只要符合我們前面的定義,就屬于0型文法践啄。因此也稱為無限制文法、短語(yǔ)文法沉御。由0型文法生成的語(yǔ)言稱為0型語(yǔ)言屿讽。
? ? ? ?1型文法:它的每一個(gè)產(chǎn)生式應(yīng)該滿足以下條件:jAf→jaf;其中:A?V (也就是說,A屬于非終結(jié)符),f,j,a (VxT)* (也就是說,f,j,a是非終結(jié)符或終結(jié)符的組合)。由于這些產(chǎn)生式在替換非終結(jié)符時(shí),需要考慮它的前一個(gè)、后一個(gè)元素(也就是產(chǎn)生式替換的非終結(jié)符的前伐谈、后均有一個(gè)不變的符號(hào)),因此又稱為上下文有關(guān)文法,其產(chǎn)生的就是上下文有關(guān)語(yǔ)言,即1型文法烂完。
? ? ? 2型文法:如果它的所有產(chǎn)生式都形如:A→a;其中:A?V(也就是說,A屬于非終結(jié)符),a ?(V?T)* (也就是說,a是非終結(jié)符和/或終結(jié)符的組合)。那么,它就是一個(gè)2型方法,由于轉(zhuǎn)換與前后元素沒有關(guān)系(也就是產(chǎn)生式的前后都是空的),因此,也稱之為上下文無關(guān)文法诵棵。
3型文法:它也是一個(gè)2型方法抠蚣。??
右線性文法:如果它的所有產(chǎn)生式都形如:A→aB或A→a(也就是除了A→a這種特殊形式外,每個(gè)產(chǎn)生式的右邊都有一個(gè)非終結(jié)符);其中:A,BxV(也就是說,A,B屬于非終結(jié)符),a(VxT)* (也就是說,a是非終結(jié)符和/或終結(jié)符的組合)。??
左線性文法:如果它的所有產(chǎn)生式都形如:A→Ba或A→a(也就是除了A→a這種特殊形式外,每個(gè)產(chǎn)生式的左邊都有一個(gè)非終結(jié)符);其他與上面一樣履澳。?
?右線性嘶窄、左線性都稱做3型文法或正則文法。
4. 詞法分析
? ? ? ? 詞法分析是整個(gè)分析過程的一個(gè)子任務(wù),它把構(gòu)成源程序的字符串轉(zhuǎn)換成語(yǔ)義上關(guān)聯(lián)的單詞符號(hào)(包括關(guān)鍵字距贷、標(biāo)識(shí)符柄冲、常數(shù)、運(yùn)算符和分界符等)的序列忠蝗。詞法分析可以借助于有限自動(dòng)機(jī)的理論與方法進(jìn)行有效的處理现横。
(1)有限自動(dòng)機(jī)
? ? ? ? 有限自動(dòng)機(jī)是一種自動(dòng)識(shí)別裝置,能夠準(zhǔn)確地識(shí)別正規(guī)集。它與3型文法對(duì)應(yīng),可以分為確定的有限自動(dòng)機(jī)和不確定的有限自動(dòng)機(jī)兩種阁最。
?確定的有限自動(dòng)機(jī)(DFA)
M=(S,S, δ,S0,Z)
1)S是一個(gè)有限集,每個(gè)元素為一個(gè)狀態(tài)? 2)S是一個(gè)有窮字母表,每個(gè)元素為一個(gè)輸入字符
3)δ是轉(zhuǎn)換函數(shù):是一個(gè)單值對(duì)照
4)S0,屬于S,是其唯一的初態(tài)
5)Z是一個(gè)終態(tài)集(可空)??
有限狀態(tài)自動(dòng)機(jī)可以形象地用狀態(tài)轉(zhuǎn)換圖表示,設(shè)有限狀態(tài)自動(dòng)機(jī):
DFA = ({S, A, B, C, f}, {1, 0},δ,S, {f}),
其中:
δ(S, 0) = B, δ(S, 1) = A, δ(A, 0) = f, δ(A, 1) = C, δ(B, 0) = C, δ(B, 1) =f,δ(C, 0) = f, δ(C, 1) = f
其對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖3-3所示戒祠。
不確定的有限自動(dòng)機(jī)(NFA)
M=(S,S, δ,S0,Z)
1)S是一個(gè)有限集,每個(gè)元素為一個(gè)狀態(tài)? 2)S是一個(gè)有窮字母表,每個(gè)元素為一個(gè)輸入字符
3)δ是轉(zhuǎn)換函數(shù),是多值對(duì)照
4)S0,屬于S,是非空初態(tài)集
5)Z是一個(gè)終態(tài)集(可空)
? ? ? ? 與確定的有限自動(dòng)機(jī)一樣,不確定有限自動(dòng)機(jī)同樣可以用狀態(tài)轉(zhuǎn)換圖表示,所不同的是,在圖
中一個(gè)狀態(tài)結(jié)點(diǎn)可能有一條以上的邊到達(dá)其它狀態(tài)結(jié)點(diǎn)。
? ? ? ? 從定義的角度來區(qū)分NFA與DFA,我們發(fā)現(xiàn):DFA是單值對(duì)照,NFA是多值對(duì)照(其實(shí)也就對(duì)應(yīng)
著上面所述的"NFA圖中一個(gè)狀態(tài)結(jié)點(diǎn)可能有一條以上的邊到達(dá)其它狀態(tài)結(jié)點(diǎn)")闽撤。
NFA可以轉(zhuǎn)換為等價(jià)的DFA.
(2)正規(guī)式
對(duì)于字母表而言,正規(guī)則式和它所表示的正規(guī)集的遞歸定義是:
空集是正規(guī)表達(dá)式得哆。
任何屬于的a,都是其正規(guī)式。?
?假定U和V都是上的正規(guī)式,那它們的或哟旗、連接贩据、閉包都是正規(guī)式。
? 通常在正規(guī)表達(dá)式中,一元運(yùn)算符"*"具有最高的優(yōu)先級(jí),連接運(yùn)算具有次優(yōu)先級(jí),運(yùn)算符"|"具有最低優(yōu)先級(jí),這三個(gè)運(yùn)算都是左結(jié)合的闸餐。每一個(gè)正規(guī)表達(dá)式R都對(duì)應(yīng)一個(gè)有限自動(dòng)機(jī)M,使M所接受的語(yǔ)言就是正規(guī)表達(dá)式的值饱亮。經(jīng)過以下步驟可以從一個(gè)正規(guī)表達(dá)式R構(gòu)造出相應(yīng)的有限自動(dòng)機(jī)M.
首先定義初始狀態(tài)S和終止?fàn)顟B(tài)f,并且組成有向圖:
然后反復(fù)應(yīng)用以下規(guī)則:
? ? ? 直到所有的邊都以Σ中的字母或ε標(biāo)記為止。由此產(chǎn)生了一個(gè)帶ε–轉(zhuǎn)移的非確定有限自動(dòng)機(jī),然后可以通過上面介紹的方法,把該自動(dòng)機(jī)轉(zhuǎn)換成確定有限狀態(tài)自動(dòng)機(jī)舍沙。
? ? 下面舉一個(gè)例子說明自動(dòng)機(jī)理論在詞法分析程序中的應(yīng)用近上。C語(yǔ)言中對(duì)標(biāo)識(shí)符的規(guī)定為由"_"或以字母開頭的由"_"、字母和數(shù)字組成的字符串,該標(biāo)識(shí)符的定義可以表示為下面的正則表達(dá)式:
? ? ?式中的α代表字母字符{A,...,Z,a,...,z},d代表數(shù)字字符{0,1,...,9}.利用前面的方法構(gòu)造出如圖3-4所示的有限自動(dòng)機(jī)拂铡。
該自動(dòng)機(jī)所接受的語(yǔ)言就是C語(yǔ)言中的標(biāo)識(shí)符壹无。
? ? ?在有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換過程中,需要執(zhí)行相關(guān)的語(yǔ)義動(dòng)作。例如當(dāng)識(shí)別到一個(gè)標(biāo)識(shí)符時(shí),需要在符號(hào)表中添加該標(biāo)識(shí)符,并且向語(yǔ)法分析程序輸送表示該標(biāo)識(shí)符的單詞感帅。
5. 語(yǔ)法分析
? ? ? 語(yǔ)法分析的任務(wù)是識(shí)別由詞法分析給出的單詞符號(hào)序列是否為給定文法的正確句子(程序),語(yǔ)法分析可以分為自底向上分析和自頂向下分析兩大類斗锭。
(1)自底向上分析
? ? ? ?自底向上分析也稱為移進(jìn)--歸約分析法。它的基本思想是:對(duì)輸入符號(hào)串自左向右進(jìn)行掃描,并將輸入符號(hào)逐一移進(jìn)一個(gè)后進(jìn)先出的棧中,邊移進(jìn)邊分析;一旦棧頂符號(hào)串形成某個(gè)句型的可歸約串時(shí),就用某產(chǎn)生式的左部非終結(jié)符來替代(這稱之為歸約)失球。一直重復(fù)這個(gè)過程,直到棧中只剩下文法的開始符號(hào)岖是。
由于"可歸約串"的不同,也就形成了幾種不同的自底向上分析法。
規(guī)范歸約分析法:用"句柄"來刻畫"可歸約串".
?規(guī)范歸約是規(guī)范推導(dǎo)的逆過程。LR分析法是一種規(guī)范歸約分析法,它根據(jù)當(dāng)前分析棧中的符號(hào)串和向右順序查看輸入串的k個(gè)符號(hào),就可以確定分析器的移進(jìn)還是歸約豺撑。
常用的LR分析器有LR(0),SLR(1),LALR(1)和LR(1)四種烈疚。一個(gè)LR分析器由總控程序、分析表聪轿、分析棧三個(gè)部分組成爷肝。
算符優(yōu)先分析法:用"最左素短語(yǔ)"來刻畫"可歸約串".
算符優(yōu)先分析法是定義文法中終結(jié)符之間的優(yōu)先關(guān)系,利用這種關(guān)系定義和操作可歸約串,從而達(dá)到語(yǔ)法分析的目的。
如果文法G中不存在形如P→...QR...的產(chǎn)生式(P,Q,R均為非終結(jié)符),也就是產(chǎn)生式中沒有非終結(jié)符連續(xù)出現(xiàn)的情況,則稱G為算符文法屹电。
對(duì)于一個(gè)不含e產(chǎn)生式的算符文法G,任何一對(duì)終結(jié)符a和b之間具有如下的優(yōu)先關(guān)系,如表3-4所示
(2)自頂向下分析
自頂向下分析法也稱為面向目標(biāo)的分析方法,也就是從文法的開始符號(hào)出發(fā)嘗試推導(dǎo)出與輸入
的單詞串相匹配的句子阶剑。它可以分為確定和不確定兩種,如表3-5所示。
有一類稱為L(zhǎng)L(1)的文法可用遞歸子程序方法或預(yù)測(cè)分析方法來實(shí)現(xiàn)確定的自頂向下的語(yǔ)法分
析危号。要采用自頂向下的分析,必須消除左遞歸、提取公共左因子,然后采用下列方法之一進(jìn)行分
析,如表3-6所示素邪。
