計(jì)算機(jī)編譯原理課件4

第4章程序語言的設(shè)計(jì)第2章和第3章分別討論了程序設(shè)計(jì)語言的數(shù)據(jù)類型和控制結(jié)構(gòu)，分別描述程序的數(shù)據(jù)結(jié)構(gòu)和算法。本章介紹語言的設(shè)計(jì)方法。1第4章程序語言的設(shè)計(jì)第2章和第3章分別討論了程序設(shè)計(jì)語言的1語言的定義語言=語法+語義語法：用以構(gòu)造程序及其成分（語法單位）的規(guī)則的集合。語義：用以規(guī)定語法正確的語法單位的含義的規(guī)則的集合。21語言的定義語言=語法+語義21.1語法1.1.1幾個術(shù)語(1)字母表語言允許使用字符的集合，其元素稱為字符(2)符號由字符組成的有限串（字符串）(3)字匯表由符號組成的集合，其元素稱為字31.1語法1.1.1幾個術(shù)語3(4)詞法規(guī)則規(guī)定什么樣的字符序列可以構(gòu)成語言的有效符號（單詞符號）(5)語法規(guī)則確定一個符號序列是否為一個句子，并提供句子的結(jié)構(gòu)（什么樣的符號序列是合法的）4(4)詞法規(guī)則4語言的定義語言的定義可以從生成（文法）和識別（語法圖）的觀點(diǎn)進(jìn)行。5語言的定義語言的定義可以從生成（文法）和識別（語法圖）的觀點(diǎn)1.1.2生成的觀點(diǎn)用文法來定義語言(1)一個簡單英語句子的描述I/Studentsstudy/run61.1.2生成的觀點(diǎn)用文法來定義語言6(2)文法<句子>→<主語><謂語><主語>→I|Students<謂語>→study|run7(2)文法7(3)語言根據(jù)文法規(guī)則生成的所有句子的集合，稱為語言。8(3)語言8標(biāo)識符的文法<標(biāo)識符>→<字母><標(biāo)識符>→<標(biāo)識符><字母><標(biāo)識符>→<標(biāo)識符><數(shù)字><字母>→A|…|Z|a|…|z<數(shù)字>→0|…|99標(biāo)識符的文法<標(biāo)識符>→<字母>9表達(dá)式的文法<表達(dá)式>→<標(biāo)識符><表達(dá)式>→(<表達(dá)式>)<表達(dá)式>→<表達(dá)式><運(yùn)算符><表達(dá)式><運(yùn)算符>→+|-|*|/10表達(dá)式的文法<表達(dá)式>→<標(biāo)識符>101.1.3識別的觀點(diǎn)用語法圖來定義的語言(1)語法圖的構(gòu)造終結(jié)符x對應(yīng)一個語法圖非終結(jié)符N對應(yīng)一個語法圖xN111.1.3識別的觀點(diǎn)用語法圖來定義的語言xN11N→1|2|…|n對應(yīng)一個語法圖2n112N→1|2|…|n對應(yīng)一個語法圖2n112→12…m對應(yīng)一個語法圖b1b2bm13→12…m對應(yīng)一個語法圖b1b2bm13→|對應(yīng)一個語法圖gb14→|對應(yīng)一個語法圖gb14(2)識別原則若一個終結(jié)符序列是合法的，那么，必須從語法圖的入口邊通過語法圖而到達(dá)出口邊，而且在通過的過程中，恰恰能識別該終結(jié)符序列。15(2)識別原則15(3)語言語法圖能識別的所有終結(jié)符序列的集合，稱為語言。16(3)語言16標(biāo)識符的語法圖字母字母數(shù)字17標(biāo)識符的語法圖字母字母數(shù)字17表達(dá)式的語法圖標(biāo)識符表達(dá)式運(yùn)算符()表達(dá)式表達(dá)式18表達(dá)式的語法圖標(biāo)識符表達(dá)式運(yùn)算符()表達(dá)式表達(dá)式18語法描述方法等價文法和語法圖是語言語法的等價表示。文法從產(chǎn)生的觀點(diǎn)來定義語言，更通用、更準(zhǔn)確地給出語言的語法結(jié)構(gòu)。語法圖以識別的觀點(diǎn)定義語言，更直觀、更清晰地給出語言的語法結(jié)構(gòu)。采用生成的方法還是采用識別的方法來定義語言，由語言的設(shè)計(jì)者確定。19語法描述方法等價文法和語法圖是語言語法的等價表示。191.1.4語法描述的用途(1)表達(dá)語言設(shè)計(jì)者的意圖和設(shè)計(jì)目標(biāo)(2)指導(dǎo)語言的使用者編寫正確的程序(3)指導(dǎo)語言的實(shí)現(xiàn)者編寫語法檢查程序來識別所有語法單位201.1.4語法描述的用途(1)表達(dá)語言設(shè)計(jì)者的意圖和設(shè)計(jì)1.2語義語義：定義語言合法句子的含義（即句子的作用和意義）的規(guī)則組合。文法和語法圖已成為語法描述的典型工具，但語義描述至今尚無人們普遍接受的典型描述工具。許多語言仍采用自然語言描述語義。211.2語義語義：定義語言合法句子的含義（即句子的作用和意義本章的語言設(shè)計(jì)，采用自然語言來描述語義。（下篇的）語言實(shí)現(xiàn)涉及到的語義，將以操作語義學(xué)的方法來描述。即以一個抽象機(jī)的行為來描述語言的各個結(jié)構(gòu)的作用和意義。22本章的語言設(shè)計(jì)，采用自然語言來描述語義。22抽象機(jī)GAM的組成由存儲器，控制器，處理器，指令指針ip組成。存儲器分為代碼區(qū)和數(shù)據(jù)區(qū)。23抽象機(jī)GAM的組成由存儲器，控制器，處理器，指令指針ip組成抽象機(jī)GAM的模型ip代碼存儲器（C）數(shù)據(jù)存儲器（D）24抽象機(jī)GAM的模型ip代碼存儲器（C）數(shù)據(jù)存儲器（D）24抽象機(jī)GAM的結(jié)構(gòu)代碼區(qū)（代碼存儲器），存放程序指令，代碼存儲器的內(nèi)容不允許被修改。數(shù)據(jù)區(qū)（數(shù)據(jù)存儲器），存放必要的信息和程序中的數(shù)據(jù)。25抽象機(jī)GAM的結(jié)構(gòu)代碼區(qū)（代碼存儲器），存放程序指令，代碼存ip的內(nèi)容是代碼區(qū)存儲單元的地址，該單元的內(nèi)容是一條指令。C[i]和D[i]表示相應(yīng)存儲區(qū)第i個單元。ip:=ip+4表示指針指向下一條指令，假定每條指令占4個存儲單元（字節(jié)）。26ip的內(nèi)容是代碼區(qū)存儲單元的地址，該單元的內(nèi)容是一條指令。GAM一旦啟動，由專門的裝入程序?qū)⒁粋€要運(yùn)行的程序裝入代碼存儲器，并置ip指向該程序的第一條指令。然后依次完成下述工作：27GAM一旦啟動，由專門的裝入程序?qū)⒁粋€要運(yùn)行的程序裝入代碼存(1)執(zhí)行ip所指向的指令。(2)修改ip的內(nèi)容。若所執(zhí)行的指令未修改ip，則ip+4，使之指向下一條指令。(3)若ip指向特殊的STOP指令，則終止執(zhí)行，否則轉(zhuǎn)回執(zhí)行(1)。28(1)執(zhí)行ip所指向的指令。28假設(shè)GAM對各種程序設(shè)計(jì)語言所常用的運(yùn)算符，如：＋，-，*，/，＞，＜，>=等，都有相應(yīng)的指令與之對應(yīng)。以GAM的操作行為來定義語言的語義，是基于已經(jīng)“理解”GAM的語義。因此，一旦用GAM的操作行為來定義語言結(jié)構(gòu)的作用時，就知道了語言的意義。29假設(shè)GAM對各種程序設(shè)計(jì)語言所常用的運(yùn)算符，如：＋，-，2文法2.1文法的定義文法是描述語言語法結(jié)構(gòu)的形式規(guī)則。通用，準(zhǔn)確，易于理解，描述能力強(qiáng)302文法2.1文法的定義302.1.1文法的形式定義G=(VT，VN，S，P)VT為終結(jié)符的非空有限集；VN為非終結(jié)符的非空有限集；S是文法的開始符號，S∈VN；P為產(chǎn)生式的非空有限集。312.1.1文法的形式定義G=(VT，VN，S，P)產(chǎn)生式是一個有序偶對(，)，記為：→和是由終結(jié)符、非終結(jié)符組成的符號串，但至少應(yīng)含有一個非終結(jié)符。即：

V*VNV*

V*32產(chǎn)生式是一個有序偶對(，)，記為：32產(chǎn)生式的簡化→1→2…

→n簡化為：→1|2|…|n33產(chǎn)生式的簡化→133文法的表示描述文法，直接給出產(chǎn)生式集合即可。例如，算術(shù)表達(dá)式文法G(E)E→E+T|TT→T*F|FF→(E)|i34文法的表示描述文法，直接給出產(chǎn)生式集合即可。342.1.2文法的分類(1)無限制文法（0型文法）產(chǎn)生式為→，V*VNV*,V*(2)上下文有關(guān)文法（1型文法）產(chǎn)生式為A→，AVN，、V*，V+

352.1.2文法的分類(1)無限制文法（0型文法）35(3)上下文無關(guān)文法（2型文法）產(chǎn)生式為A→，AVN，V*(4)正則文法（3型文法）產(chǎn)生式為A→或A→B，VT*，BVN36(3)上下文無關(guān)文法（2型文法）362.2文法產(chǎn)生的語言2.2.1推導(dǎo)與歸約(1)直接推導(dǎo)：wα

wβ

即由產(chǎn)生式右邊替換產(chǎn)生式左邊(2)推導(dǎo)：α1

*αn、α1

+αn

372.2文法產(chǎn)生的語言2.2.1推導(dǎo)與歸約37E→E+E│E*E│(E)│ii+i*i的最左推導(dǎo)過程EE+Ei+Ei+E*Ei+i*Ei+i*i38E→E+E│E*E│(E)│iEE+Ei+E最右推導(dǎo)（規(guī)范推導(dǎo)）EE+EE+E*E

E+E*iE+i*ii+i*i39最右推導(dǎo)（規(guī)范推導(dǎo)）EE+EE+E*E39EE*EE*iE+E*iE+i*ii+i*i40EE*EE*i402.2.2句型和句子文法G=(VT,VN,S,P)S*α若αV*,則α為文法G的一個句型若αVT*,則α是一個句子412.2.2句型和句子文法G=(VT,VN,S,P)41句型與句子的關(guān)系只含終結(jié)符的句型就是一個句子。一個句子是句型。一個句型不一定是句子。42句型與句子的關(guān)系只含終結(jié)符的句型就是一個句子。422.2.3文法產(chǎn)生的語言文法G=(VT,VN,S,P)產(chǎn)生的所有句子的集合,稱為由文法G產(chǎn)生的語言,記為L(G),即L(G)={α│S+α且αVT*

}432.2.3文法產(chǎn)生的語言文法G=(VT,VN,S,P)43文法實(shí)例1文法G1：E→E+T|TT→T*F|FF→(E)|i語言L(G1)表示由符號i、+、*、(、)構(gòu)成的表達(dá)式。44文法實(shí)例1文法G1：44文法實(shí)例2文法G2：S→aS|aPP→bP|bQQ→cQ|c語言L(G2)={aibjck|i，j，k1}45文法實(shí)例2文法G2：45文法實(shí)例3文法G3：S→aSPQ│abQQP→PQbP→bbbQ→bccQ→cc46文法實(shí)例3文法G3：46S…ai-1S(PQ)i-1ai-1abQ(PQ)i-1aibPi-1Qi…aibiQi…aibicQi-1…aibici語言L(G3)={aibici|i1}47S…ai-1S(PQ)i-147說明1)文法的重要特性用有限規(guī)則描述無窮的語言。2)文法的等價對兩個文法G和G’，如果L(G)=L(G’)，則稱文法G和文法G’等價。48說明1)文法的重要特性482.2.4推導(dǎo)樹（語法樹）(1)推導(dǎo)樹是一棵有序的標(biāo)記樹每個結(jié)點(diǎn)的標(biāo)記是文法G的非終結(jié)符或終結(jié)符；標(biāo)記為A的內(nèi)部結(jié)點(diǎn)從左到右有子結(jié)點(diǎn)X1，X2，…,Xn，則A→X1…Xn是一個產(chǎn)生式；492.2.4推導(dǎo)樹（語法樹）(1)推導(dǎo)樹是一棵有序的標(biāo)記樹對于文法E→E+E│E*E│(E)│i句子i+i*i的推導(dǎo)樹為：50對于文法50E（E）EE*EE+iiiE（E）EE+EEiii*51E（E）EE*EE+iiiE（E）EE+EEiii*51(2)推導(dǎo)樹的邊緣推導(dǎo)樹所有葉結(jié)點(diǎn)從左到右的連接。(3)文法的二義性一個句子有兩棵不同的推導(dǎo)樹。52(2)推導(dǎo)樹的邊緣524.3語言的設(shè)計(jì)設(shè)計(jì)的依據(jù)：面向的問題和面向的機(jī)器設(shè)計(jì)內(nèi)容(語法)：表達(dá)式、語句、程序單元、程序描述方式：語法——文法、語義——自然語言534.3語言的設(shè)計(jì)設(shè)計(jì)的依據(jù)：534.3.1表達(dá)式的設(shè)計(jì)邏輯表達(dá)式關(guān)系表達(dá)式算術(shù)表達(dá)式544.3.1表達(dá)式的設(shè)計(jì)邏輯表達(dá)式54(1)邏輯表達(dá)式<邏輯表達(dá)式>→<布爾常量>|<布爾變量>|<關(guān)系表達(dá)式>|<邏輯表達(dá)式>|<邏輯表達(dá)式><邏輯表達(dá)式>|<邏輯表達(dá)式><邏輯表達(dá)式>

55(1)邏輯表達(dá)式<邏輯表達(dá)式>→55<布爾常量>→true|false<布爾變量>→<標(biāo)識符>、、的優(yōu)先順序由低到高56<布爾常量>→true|false56(2)關(guān)系表達(dá)式<關(guān)系表達(dá)式>→<算術(shù)表達(dá)式><關(guān)系運(yùn)算符><算術(shù)表達(dá)式><關(guān)系運(yùn)算符>→<|<=|>|>=|=|<>關(guān)系運(yùn)算符沒有優(yōu)先順序、沒有重載57(2)關(guān)系表達(dá)式<關(guān)系表達(dá)式>→57(3)算術(shù)表達(dá)式<算術(shù)表達(dá)式>→ <常量>|<變量>|(<算術(shù)表達(dá)式>) |<算術(shù)表達(dá)式><算術(shù)運(yùn)算符><算術(shù)表達(dá)式>

58(3)算術(shù)表達(dá)式<算術(shù)表達(dá)式>→58算術(shù)運(yùn)算符有優(yōu)先順序、允許重載算術(shù)運(yùn)算符服從左結(jié)合（上述描述具有二義性）59算術(shù)運(yùn)算符有優(yōu)先順序、允許重載59沒有二義性的描述<算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>+<項(xiàng)>|<算術(shù)表達(dá)式>-<項(xiàng)>|<項(xiàng)><項(xiàng)>→<項(xiàng)>*<因子>|<項(xiàng)>/<因子>|<因子><因子>→(<算術(shù)表達(dá)式>)|<常量>|<變量>60沒有二義性的描述<算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>+<項(xiàng)>6<變量>→<標(biāo)識符><常量>→<各種常量>61<變量>→<標(biāo)識符>614.3.2語句的設(shè)計(jì)說明語句執(zhí)行語句624.3.2語句的設(shè)計(jì)說明語句62(1)說明語句<說明語句>→<常量說明> |<類型說明> |<變量說明>63(1)說明語句<說明語句>→<常量說明>63<常量說明>→const<標(biāo)識符>=<常量><類型說明>→type<類型名>=<用戶定義類型><變量說明>→var<變量表>：<類型><變量表>→<變量>|<變量表>，<變量>64<常量說明>→const<標(biāo)識符>=<常量>64<類型>→int|real|char|boolean|<類型名><變量>→<標(biāo)識符><類型名>→<標(biāo)識符>65<類型>→int|real|char|boo(2)執(zhí)行語句<執(zhí)行語句>→<賦值語句>|<控制語句> |<復(fù)合語句>|<I/O輸出語句><賦值語句>→<變量>:=<表達(dá)式><控制語句>→<順序>|<選擇>|<重復(fù)>針對面向的問題選擇一個方案

66(2)執(zhí)行語句<執(zhí)行語句>→<賦值語句>|<控制語<復(fù)合語句>→begin<語句表>end<語句表>→<執(zhí)行語句>|<執(zhí)行語句表>；<執(zhí)行語句><I/O輸出語句>→read(<變量>)|write(<變量>)67<復(fù)合語句>→begin<語句表>end674.3.3程序單元的設(shè)計(jì)<程序單元>→<程序單元關(guān)鍵字><程序單元名>(<形參表>)；<程序單元體><程序單元關(guān)鍵字>→procedure|function|…<程序單元名>→<標(biāo)識符><形參表>→<形參>|<形參表>；<形參>684.3.3程序單元的設(shè)計(jì)<程序單元>→68形參可以沒有；如果有，可以是變量、數(shù)組、過程等，必須說明類型及與實(shí)參的綁定方式。69形參可以沒有；69<程序單元體>→begin<說明部分>;<執(zhí)行部分>end<說明部分>→<說明語句表><說明語句表>→<說明語句>|<說明語句表>;<說明語句>70<程序單元體>→begin<說明部分>;70<執(zhí)行部分>→<執(zhí)行語句表><執(zhí)行語句表>→<執(zhí)行語句>|<執(zhí)行語句表>;<執(zhí)行語句>71<執(zhí)行部分>→<執(zhí)行語句表>71<分程序>→begin<說明部分>；<執(zhí)行部分>end<說明部分>→<變量說明表>；<數(shù)組說明表>；<過程說明表>；<分程序表>72<分程序>→begin<說明部分>；72<變量說明表>→<變量說明>|<變量說明表>；<變量說明><數(shù)組說明表>→<數(shù)組說明>|<數(shù)組說明表>；<數(shù)組說明>73<變量說明表>→<變量說明>73<過程說明表>→<過程說明>|<過程說明表>；<過程說明><分程序表>→<分程序>|<分程序表>；<分程序>74<過程說明表>→<過程說明>744.3.4程序的設(shè)計(jì)<程序>→<分程序>754.3.4程序的設(shè)計(jì)<程序>→<分程序>754.3.5一些設(shè)計(jì)準(zhǔn)則(1)可寫性語言提供一些機(jī)制來方便地表達(dá)設(shè)計(jì)方法以幫助完成程序設(shè)計(jì)，使得程序員可以把注意力集中在理解問題和求解問題上。764.3.5一些設(shè)計(jì)準(zhǔn)則(1)可寫性76(2)可讀性抽象、注解；影響可修改性和可維護(hù)性。(3)可靠性軟件系統(tǒng)正常工作的能力。數(shù)據(jù)抽象、信息隱蔽、異常處理機(jī)制有利于提高可靠性。77(2)可讀性77第4章程序語言的設(shè)計(jì)第2章和第3章分別討論了程序設(shè)計(jì)語言的數(shù)據(jù)類型和控制結(jié)構(gòu)，分別描述程序的數(shù)據(jù)結(jié)構(gòu)和算法。本章介紹語言的設(shè)計(jì)方法。78第4章程序語言的設(shè)計(jì)第2章和第3章分別討論了程序設(shè)計(jì)語言的1語言的定義語言=語法+語義語法：用以構(gòu)造程序及其成分（語法單位）的規(guī)則的集合。語義：用以規(guī)定語法正確的語法單位的含義的規(guī)則的集合。791語言的定義語言=語法+語義21.1語法1.1.1幾個術(shù)語(1)字母表語言允許使用字符的集合，其元素稱為字符(2)符號由字符組成的有限串（字符串）(3)字匯表由符號組成的集合，其元素稱為字801.1語法1.1.1幾個術(shù)語3(4)詞法規(guī)則規(guī)定什么樣的字符序列可以構(gòu)成語言的有效符號（單詞符號）(5)語法規(guī)則確定一個符號序列是否為一個句子，并提供句子的結(jié)構(gòu)（什么樣的符號序列是合法的）81(4)詞法規(guī)則4語言的定義語言的定義可以從生成（文法）和識別（語法圖）的觀點(diǎn)進(jìn)行。82語言的定義語言的定義可以從生成（文法）和識別（語法圖）的觀點(diǎn)1.1.2生成的觀點(diǎn)用文法來定義語言(1)一個簡單英語句子的描述I/Studentsstudy/run831.1.2生成的觀點(diǎn)用文法來定義語言6(2)文法<句子>→<主語><謂語><主語>→I|Students<謂語>→study|run84(2)文法7(3)語言根據(jù)文法規(guī)則生成的所有句子的集合，稱為語言。85(3)語言8標(biāo)識符的文法<標(biāo)識符>→<字母><標(biāo)識符>→<標(biāo)識符><字母><標(biāo)識符>→<標(biāo)識符><數(shù)字><字母>→A|…|Z|a|…|z<數(shù)字>→0|…|986標(biāo)識符的文法<標(biāo)識符>→<字母>9表達(dá)式的文法<表達(dá)式>→<標(biāo)識符><表達(dá)式>→(<表達(dá)式>)<表達(dá)式>→<表達(dá)式><運(yùn)算符><表達(dá)式><運(yùn)算符>→+|-|*|/87表達(dá)式的文法<表達(dá)式>→<標(biāo)識符>101.1.3識別的觀點(diǎn)用語法圖來定義的語言(1)語法圖的構(gòu)造終結(jié)符x對應(yīng)一個語法圖非終結(jié)符N對應(yīng)一個語法圖xN881.1.3識別的觀點(diǎn)用語法圖來定義的語言xN11N→1|2|…|n對應(yīng)一個語法圖2n189N→1|2|…|n對應(yīng)一個語法圖2n112→12…m對應(yīng)一個語法圖b1b2bm90→12…m對應(yīng)一個語法圖b1b2bm13→|對應(yīng)一個語法圖gb91→|對應(yīng)一個語法圖gb14(2)識別原則若一個終結(jié)符序列是合法的，那么，必須從語法圖的入口邊通過語法圖而到達(dá)出口邊，而且在通過的過程中，恰恰能識別該終結(jié)符序列。92(2)識別原則15(3)語言語法圖能識別的所有終結(jié)符序列的集合，稱為語言。93(3)語言16標(biāo)識符的語法圖字母字母數(shù)字94標(biāo)識符的語法圖字母字母數(shù)字17表達(dá)式的語法圖標(biāo)識符表達(dá)式運(yùn)算符()表達(dá)式表達(dá)式95表達(dá)式的語法圖標(biāo)識符表達(dá)式運(yùn)算符()表達(dá)式表達(dá)式18語法描述方法等價文法和語法圖是語言語法的等價表示。文法從產(chǎn)生的觀點(diǎn)來定義語言，更通用、更準(zhǔn)確地給出語言的語法結(jié)構(gòu)。語法圖以識別的觀點(diǎn)定義語言，更直觀、更清晰地給出語言的語法結(jié)構(gòu)。采用生成的方法還是采用識別的方法來定義語言，由語言的設(shè)計(jì)者確定。96語法描述方法等價文法和語法圖是語言語法的等價表示。191.1.4語法描述的用途(1)表達(dá)語言設(shè)計(jì)者的意圖和設(shè)計(jì)目標(biāo)(2)指導(dǎo)語言的使用者編寫正確的程序(3)指導(dǎo)語言的實(shí)現(xiàn)者編寫語法檢查程序來識別所有語法單位971.1.4語法描述的用途(1)表達(dá)語言設(shè)計(jì)者的意圖和設(shè)計(jì)1.2語義語義：定義語言合法句子的含義（即句子的作用和意義）的規(guī)則組合。文法和語法圖已成為語法描述的典型工具，但語義描述至今尚無人們普遍接受的典型描述工具。許多語言仍采用自然語言描述語義。981.2語義語義：定義語言合法句子的含義（即句子的作用和意義本章的語言設(shè)計(jì)，采用自然語言來描述語義。（下篇的）語言實(shí)現(xiàn)涉及到的語義，將以操作語義學(xué)的方法來描述。即以一個抽象機(jī)的行為來描述語言的各個結(jié)構(gòu)的作用和意義。99本章的語言設(shè)計(jì)，采用自然語言來描述語義。22抽象機(jī)GAM的組成由存儲器，控制器，處理器，指令指針ip組成。存儲器分為代碼區(qū)和數(shù)據(jù)區(qū)。100抽象機(jī)GAM的組成由存儲器，控制器，處理器，指令指針ip組成抽象機(jī)GAM的模型ip代碼存儲器（C）數(shù)據(jù)存儲器（D）101抽象機(jī)GAM的模型ip代碼存儲器（C）數(shù)據(jù)存儲器（D）24抽象機(jī)GAM的結(jié)構(gòu)代碼區(qū)（代碼存儲器），存放程序指令，代碼存儲器的內(nèi)容不允許被修改。數(shù)據(jù)區(qū)（數(shù)據(jù)存儲器），存放必要的信息和程序中的數(shù)據(jù)。102抽象機(jī)GAM的結(jié)構(gòu)代碼區(qū)（代碼存儲器），存放程序指令，代碼存ip的內(nèi)容是代碼區(qū)存儲單元的地址，該單元的內(nèi)容是一條指令。C[i]和D[i]表示相應(yīng)存儲區(qū)第i個單元。ip:=ip+4表示指針指向下一條指令，假定每條指令占4個存儲單元（字節(jié)）。103ip的內(nèi)容是代碼區(qū)存儲單元的地址，該單元的內(nèi)容是一條指令。GAM一旦啟動，由專門的裝入程序?qū)⒁粋€要運(yùn)行的程序裝入代碼存儲器，并置ip指向該程序的第一條指令。然后依次完成下述工作：104GAM一旦啟動，由專門的裝入程序?qū)⒁粋€要運(yùn)行的程序裝入代碼存(1)執(zhí)行ip所指向的指令。(2)修改ip的內(nèi)容。若所執(zhí)行的指令未修改ip，則ip+4，使之指向下一條指令。(3)若ip指向特殊的STOP指令，則終止執(zhí)行，否則轉(zhuǎn)回執(zhí)行(1)。105(1)執(zhí)行ip所指向的指令。28假設(shè)GAM對各種程序設(shè)計(jì)語言所常用的運(yùn)算符，如：＋，-，*，/，＞，＜，>=等，都有相應(yīng)的指令與之對應(yīng)。以GAM的操作行為來定義語言的語義，是基于已經(jīng)“理解”GAM的語義。因此，一旦用GAM的操作行為來定義語言結(jié)構(gòu)的作用時，就知道了語言的意義。106假設(shè)GAM對各種程序設(shè)計(jì)語言所常用的運(yùn)算符，如：＋，-，2文法2.1文法的定義文法是描述語言語法結(jié)構(gòu)的形式規(guī)則。通用，準(zhǔn)確，易于理解，描述能力強(qiáng)1072文法2.1文法的定義302.1.1文法的形式定義G=(VT，VN，S，P)VT為終結(jié)符的非空有限集；VN為非終結(jié)符的非空有限集；S是文法的開始符號，S∈VN；P為產(chǎn)生式的非空有限集。1082.1.1文法的形式定義G=(VT，VN，S，P)產(chǎn)生式是一個有序偶對(，)，記為：→和是由終結(jié)符、非終結(jié)符組成的符號串，但至少應(yīng)含有一個非終結(jié)符。即：

V*VNV*

V*109產(chǎn)生式是一個有序偶對(，)，記為：32產(chǎn)生式的簡化→1→2…

→n簡化為：→1|2|…|n110產(chǎn)生式的簡化→133文法的表示描述文法，直接給出產(chǎn)生式集合即可。例如，算術(shù)表達(dá)式文法G(E)E→E+T|TT→T*F|FF→(E)|i111文法的表示描述文法，直接給出產(chǎn)生式集合即可。342.1.2文法的分類(1)無限制文法（0型文法）產(chǎn)生式為→，V*VNV*,V*(2)上下文有關(guān)文法（1型文法）產(chǎn)生式為A→，AVN，、V*，V+

1122.1.2文法的分類(1)無限制文法（0型文法）35(3)上下文無關(guān)文法（2型文法）產(chǎn)生式為A→，AVN，V*(4)正則文法（3型文法）產(chǎn)生式為A→或A→B，VT*，BVN113(3)上下文無關(guān)文法（2型文法）362.2文法產(chǎn)生的語言2.2.1推導(dǎo)與歸約(1)直接推導(dǎo)：wα

wβ

即由產(chǎn)生式右邊替換產(chǎn)生式左邊(2)推導(dǎo)：α1

*αn、α1

+αn

1142.2文法產(chǎn)生的語言2.2.1推導(dǎo)與歸約37E→E+E│E*E│(E)│ii+i*i的最左推導(dǎo)過程EE+Ei+Ei+E*Ei+i*Ei+i*i115E→E+E│E*E│(E)│iEE+Ei+E最右推導(dǎo)（規(guī)范推導(dǎo)）EE+EE+E*E

E+E*iE+i*ii+i*i116最右推導(dǎo)（規(guī)范推導(dǎo)）EE+EE+E*E39EE*EE*iE+E*iE+i*ii+i*i117EE*EE*i402.2.2句型和句子文法G=(VT,VN,S,P)S*α若αV*,則α為文法G的一個句型若αVT*,則α是一個句子1182.2.2句型和句子文法G=(VT,VN,S,P)41句型與句子的關(guān)系只含終結(jié)符的句型就是一個句子。一個句子是句型。一個句型不一定是句子。119句型與句子的關(guān)系只含終結(jié)符的句型就是一個句子。422.2.3文法產(chǎn)生的語言文法G=(VT,VN,S,P)產(chǎn)生的所有句子的集合,稱為由文法G產(chǎn)生的語言,記為L(G),即L(G)={α│S+α且αVT*

}1202.2.3文法產(chǎn)生的語言文法G=(VT,VN,S,P)43文法實(shí)例1文法G1：E→E+T|TT→T*F|FF→(E)|i語言L(G1)表示由符號i、+、*、(、)構(gòu)成的表達(dá)式。121文法實(shí)例1文法G1：44文法實(shí)例2文法G2：S→aS|aPP→bP|bQQ→cQ|c語言L(G2)={aibjck|i，j，k1}122文法實(shí)例2文法G2：45文法實(shí)例3文法G3：S→aSPQ│abQQP→PQbP→bbbQ→bccQ→cc123文法實(shí)例3文法G3：46S…ai-1S(PQ)i-1ai-1abQ(PQ)i-1aibPi-1Qi…aibiQi…aibicQi-1…aibici語言L(G3)={aibici|i1}124S…ai-1S(PQ)i-147說明1)文法的重要特性用有限規(guī)則描述無窮的語言。2)文法的等價對兩個文法G和G’，如果L(G)=L(G’)，則稱文法G和文法G’等價。125說明1)文法的重要特性482.2.4推導(dǎo)樹（語法樹）(1)推導(dǎo)樹是一棵有序的標(biāo)記樹每個結(jié)點(diǎn)的標(biāo)記是文法G的非終結(jié)符或終結(jié)符；標(biāo)記為A的內(nèi)部結(jié)點(diǎn)從左到右有子結(jié)點(diǎn)X1，X2，…,Xn，則A→X1…Xn是一個產(chǎn)生式；1262.2.4推導(dǎo)樹（語法樹）(1)推導(dǎo)樹是一棵有序的標(biāo)記樹對于文法E→E+E│E*E│(E)│i句子i+i*i的推導(dǎo)樹為：127對于文法50E（E）EE*EE+iiiE（E）EE+EEiii*128E（E）EE*EE+iiiE（E）EE+EEiii*51(2)推導(dǎo)樹的邊緣推導(dǎo)樹所有葉結(jié)點(diǎn)從左到右的連接。(3)文法的二義性一個句子有兩棵不同的推導(dǎo)樹。129(2)推導(dǎo)樹的邊緣524.3語言的設(shè)計(jì)設(shè)計(jì)的依據(jù)：面向的問題和面向的機(jī)器設(shè)計(jì)內(nèi)容(語法)：表達(dá)式、語句、程序單元、程序描述方式：語法——文法、語義——自然語言1304.3語言的設(shè)計(jì)設(shè)計(jì)的依據(jù)：534.3.1表達(dá)式的設(shè)計(jì)邏輯表達(dá)式關(guān)系表達(dá)式算術(shù)表達(dá)式1314.3.1表達(dá)式的設(shè)計(jì)邏輯表達(dá)式54(1)邏輯表達(dá)式<邏輯表達(dá)式>→<布爾常量>|<布爾變量>|<關(guān)系表達(dá)式>|<邏輯表達(dá)式>|<邏輯表達(dá)式><邏輯表達(dá)式>|<邏輯表達(dá)式><邏輯表達(dá)式>

132(1)邏輯表達(dá)式<邏輯表達(dá)式>→55<布爾常量>→true|false<布爾變量>→<標(biāo)識符>、、的優(yōu)先順序由低到高133<布爾常量>→true|false56(2)關(guān)系表達(dá)式<關(guān)系表達(dá)式>→<算術(shù)表達(dá)式><關(guān)系運(yùn)算符><算術(shù)表達(dá)式><關(guān)系運(yùn)算符>→<|<=|>|>=|=|<>關(guān)系運(yùn)算符沒有優(yōu)先順序、沒有重載134(2)關(guān)系表達(dá)式<關(guān)系表達(dá)式>→57(3)算術(shù)表達(dá)式<算術(shù)表達(dá)式>→ <常量>|<變量>|(<算術(shù)表達(dá)式>) |<算術(shù)表達(dá)式><算術(shù)運(yùn)算符><算術(shù)表達(dá)式>

135(3)算術(shù)表達(dá)式<算術(shù)表達(dá)式>→58算術(shù)運(yùn)算符有優(yōu)先順序、允許重載算術(shù)運(yùn)算符服從左結(jié)合（上述描述具有二義性）136算術(shù)運(yùn)算符有優(yōu)先順序、允許重載59沒有二義性的描述<算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>+<項(xiàng)>|<算術(shù)表達(dá)式>-<項(xiàng)>|<項(xiàng)><項(xiàng)>→<項(xiàng)>*<因子>|<項(xiàng)>/<因子>|<因子><因子>→(<算術(shù)表達(dá)式>)|<常量>|<變量>137沒有二義性的描述<算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>+<項(xiàng)>6<變量>→<標(biāo)識符><常量>→<各種常量>138<變量>→<標(biāo)識符>614.3.2語句的設(shè)計(jì)說明語句執(zhí)行語句1394.3.2語句的設(shè)計(jì)說明語句62(1)說明語句<說明語句>→<常量說明> |<類型說明> |<變量說明>140(1)說明語句<說明語句>→<常量說明>63<常量說明>→const<標(biāo)識符>=<常量><類型說明>→type<類型名>=<用戶定義類型><變量說明>→var<變量表>：<類型><變量表>→<變量>|<變量表>，<變量>141<常量說明>→const<標(biāo)識符>=<常量>64<類型>→int|real|char|boolean|<類型名><變量>→<標(biāo)識符><類型名