第4章 程序語言的設(shè)計(jì)

1、WQJWQJ第4章 程序語言的設(shè)計(jì) 基礎(chǔ)：控制結(jié)構(gòu)和數(shù)據(jù)類型分別描述了程序的算法和數(shù)據(jù)結(jié)構(gòu)。 這一章中將給出最簡單的語言設(shè)計(jì)方法，使讀者在科研和軟件開發(fā)中需要設(shè)計(jì)一個(gè)語言時(shí)，知道如何入手。這里僅僅給出一些使讀者成為語言設(shè)計(jì)者的入門知識(shí)，要設(shè)計(jì)一個(gè)通用語言或功能強(qiáng)大的語言需要許多語言理論、技術(shù)和方法等知識(shí)，讀者尚需查閱相關(guān)的文獻(xiàn)。WQJWQJ4.1 語言的定義程序設(shè)計(jì)語言用來描述計(jì)算機(jī)處理數(shù)據(jù)時(shí)所執(zhí)行算法的形式表示，它主要由兩部分組成，即語法(規(guī)則)和語義(規(guī)則)。1.語法是一組規(guī)則的集合，用以構(gòu)造程序及其成分。常用方法有兩種：1)生成的觀點(diǎn)，即通過一組有限的規(guī)則(產(chǎn)生式)把有效的句子生成出來；

2、2)識(shí)別的觀點(diǎn)，即通過一組轉(zhuǎn)換圖(識(shí)別圖)來識(shí)別合法的句子。WQJWQJ4.1 語言的定義2.語義也是一組規(guī)則的集合，用以規(guī)定語法正確的單詞符號(hào)和各種語法單位的含義。常用的描述語義的方法是，通過映射每一語言結(jié)構(gòu)到已知其含義的論域(Domain)來表示其語義。語義的形式描述是計(jì)算機(jī)學(xué)科的一個(gè)重要研究領(lǐng)域。1）指稱語義學(xué)(Denotational Semantics)2）操作語義學(xué)(operational Semantics)3）代數(shù)語義學(xué)(Algebraic Semantics)4）公理語義學(xué)(Axiomatic Semantics)WQJWQJ4.1.1語法字母表是該語言允許使用的所有字符(C

3、haracter)的集合。字符是字母表中的元素(Element)。符號(hào)是由字母表(Alphabet)上的字符串(String)構(gòu)成的，符號(hào)是由字符組成的有限串。詞法規(guī)則(LexicalRules)規(guī)定什么樣的字符串可以構(gòu)成語言的有效符號(hào)。詞法規(guī)則定義(單詞)符號(hào)，它是最簡單的語法規(guī)則。 WQJWQJ 語法和語義是緊密相關(guān)的。 語法從結(jié)構(gòu)方面來進(jìn)行討論，而不管其意義和解釋。（雖然結(jié)構(gòu)的定義總是考慮從屬于更高的目的-語義） 語法包括詞法規(guī)則和各個(gè)語法單位(即程序及其成分)的形成規(guī)則。 語法可以使用文法或語法圖進(jìn)行描述。WQJWQJ1用文法描述語法規(guī)則文法的產(chǎn)生式實(shí)際上就表達(dá)了形成規(guī)則，如C語言算術(shù)

4、表達(dá)式的定義： EE+TE-TT T T*FT/FTFF F (E) I I L I L I D L a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z D 0|1|2|3|4|5|6|7|8|9|其中：I代表標(biāo)識(shí)符。WQJWQJ2用識(shí)別圖或稱語法圖來描述形成規(guī)則任何以產(chǎn)生式給定的文法，均可以構(gòu)造一個(gè)等效的語法圖，用來識(shí)別該文法所生成的合法句子(從識(shí)別的觀點(diǎn)來考慮語言的定義)，即用所謂識(shí)別圖RecognitionGraph)，或稱語法圖(Syntax Graph)來定義給定的語言。WQJWQJ非終結(jié)符：代表語法單位，本書通常用大寫英文字母表示

5、；終結(jié)符：代表符號(hào)，本書通常用小寫英文字母或其它符號(hào)表示；語法圖構(gòu)造規(guī)則如下： 每一非終結(jié)符N連同其相應(yīng)的各個(gè)產(chǎn)生式 N 12n映射到一個(gè)語法圖N，其結(jié)構(gòu)由產(chǎn)生式右邊按下面的規(guī)則決定，上述產(chǎn)生式中的i (i1，2，n)是終結(jié)符和或非終結(jié)符的序列。 i中每出現(xiàn)一個(gè)終結(jié)符x，以圓框中的x來標(biāo)記，如P112圖4-1所示。 i中每出現(xiàn)一個(gè)非終結(jié)符N，以方框中的N來標(biāo)記，如P112圖4-2所示。 形如N 12n的產(chǎn)生式映射到圖4-3。其中，每個(gè)帶方框的i 是把構(gòu)造規(guī)則應(yīng)用到i 得到的WQJWQJ形如N 12n的產(chǎn)生式映射到圖4-4。其中，每個(gè)帶方框的i是把構(gòu)造規(guī)則應(yīng)用到i得到的，每個(gè)i或者是終結(jié)符，或者

6、是非終結(jié)符。 形如N N|的產(chǎn)生式映射到圖4-5。其中， 和 是終結(jié)符和或非終結(jié)符序列。 P112利用構(gòu)造規(guī)則，上述標(biāo)識(shí)符文法的語法圖如圖4-6所示，運(yùn)算符文法的語法圖如圖4-7所示，表達(dá)式文法的語法圖如圖4-8所示。WQJWQJ將上述三圖歸并得到表達(dá)式進(jìn)一步的語法圖，如圖4-9WQJWQJ 在語法圖中，終結(jié)符用圓框標(biāo)記，非終結(jié)符用方框標(biāo)記。 任何一個(gè)非終結(jié)符均可由僅有的一個(gè)入口邊和一個(gè)出口邊的語法圖來定義。P113若一個(gè)終結(jié)符序列是合法的，那么必須從語法圖的入口邊通過語法圖而到達(dá)出口邊，且在通過的過程中，恰恰能識(shí)別該終結(jié)符序列。在通過標(biāo)識(shí)終結(jié)符的圓框時(shí)，標(biāo)記的終結(jié)符與被識(shí)別的終結(jié)符正好符合，

7、則該終結(jié)符被識(shí)別；若通過標(biāo)記為非終結(jié)符的方框，那么由通過該非終結(jié)符的語法圖來識(shí)別；若遇到分支，可以經(jīng)由任一邊來識(shí)別，若經(jīng)由這個(gè)邊識(shí)別不成功，則返回再選另一邊來識(shí)別，這種情況稱為回溯(Back track)，直到所有分支的邊都識(shí)別不成功，則該終結(jié)符序列是不合法的，不屬于該語法圖定義的語言。該語法圖能識(shí)別的所有終結(jié)符序列的集合即為該語法圖定義的語言。WQJWQJ語法描述的發(fā)展：自然語言 BNF 語法圖。 BNF和語法圖是語言文法的等價(jià)表示。語言的語法描述用于產(chǎn)生和識(shí)別一個(gè)正確的程序,對語言的設(shè)計(jì)者、實(shí)現(xiàn)者和使用者都是非常有用的。 表達(dá)語言設(shè)計(jì)者的意圖和設(shè)計(jì)目標(biāo)。 指導(dǎo)語言的使用者如何寫出一個(gè)正確的

8、程序。例如，當(dāng)你對ifthenelse語句的嵌套沒有把握時(shí)，查看一下相應(yīng)的BNF或語法圖就可以確定。 指導(dǎo)語言的實(shí)現(xiàn)者(編譯程序設(shè)計(jì)者)如何編寫一個(gè)語法檢查程序來識(shí)別所有合法的程序。(LEX和YACC是著名的詞法分析程序和語法分析程序的自動(dòng)生成器)WQJWQJ1.2 語義語言的語義規(guī)則定義語言合法句子的含義。例如，C語言的語義幫助理解語句 if (ab) maxa else maxb；必須先計(jì)算關(guān)系表達(dá)式ab的值，然后按照所得值決定計(jì)算maxa或maxb。*語法規(guī)則告訴我們?nèi)绾涡纬蛇@個(gè)語句，語義規(guī)則告訴我們這個(gè)語句的作用和意義是什么。WQJWQJ操作語義學(xué)的方法以一個(gè)抽象機(jī)(Abstract

9、Machine)的行為來描述語言的各個(gè)結(jié)構(gòu)的作用和含義。 抽象機(jī)不是實(shí)際機(jī)器,它能簡單地表示程序設(shè)計(jì)語言運(yùn)行時(shí)的需要，并非要實(shí)際有效地執(zhí)行。實(shí)際上，在實(shí)際機(jī)器上實(shí)現(xiàn)時(shí)，僅需實(shí)現(xiàn)與抽象機(jī)同樣的作用，但必須給出實(shí)際機(jī)器的具體限制和結(jié)構(gòu)，因此，應(yīng)當(dāng)將語言的語義問題和實(shí)現(xiàn)問題分開。WQJWQJGAM的抽象機(jī)的簡單結(jié)構(gòu)，用它來定義和理解語言結(jié)構(gòu)的語義。 WQJWQJ GAM一旦啟動(dòng)，由專門的裝入程序(Loader)將一個(gè)要運(yùn)行的程序裝入代碼存儲(chǔ)器中，并置中指向該程序的第一條指令。然后依次完成下述工作： (1)執(zhí)行ip所指向的指令。 (2)修改ip的內(nèi)容。 若所執(zhí)行的指令已修改過ip，則不再修改ip(顯然

10、剛執(zhí)行的指令是一條轉(zhuǎn)移指令)。執(zhí)行的指令未修改ip，那么修改ip使之指向下一條指令，即ip:=ip+4。 (3)若ip指向特殊的STOP指令，則終止執(zhí)行，否則轉(zhuǎn)回執(zhí)行(1)。WQJWQJ以GAM的操作來定義語言的語義時(shí)，是基于我們已經(jīng)“知道”和“理解”了GAM的語義。假設(shè)GAM對各種程序設(shè)計(jì)語言所常用的運(yùn)算符(如+，-，*，等)都有相應(yīng)的指令與之對應(yīng)。只要知道GAM操作的語義，也就知道了語言結(jié)構(gòu)的語義。*為了成功地應(yīng)用這種方法，GAM自身的語義應(yīng)盡可能地簡單，以使我們能夠把問題集中到語言的語義上，而不是抽象機(jī)自身的復(fù)雜性上。因此，GAM必須是一個(gè)簡單的模型工具。WQJWQJ4.2 文法語言由語

11、法和語義定義。語法定義可有三種方法:自然語言(如FORTRAN);BNF(如ALGOL 60);轉(zhuǎn)換圖(語法圖，如Pascal)。 語法的形式描述(BNF)稱為文法，用于語言的設(shè)計(jì)和語言的實(shí)現(xiàn)(編譯)。WQJWQJ4.2.1 文法的定義文法G定義成一個(gè)四元式 G(Vt，Vn，S，P)其中，Vt為終結(jié)符的非空有限集；Vn為非終結(jié)符的非空有限集；S是文法的開始符，SVn；P為產(chǎn)生式的非空有限集，產(chǎn)生式是一個(gè)有序偶對(，)，通常寫成 :=或 讀作定義為。且有(VtVn)*Vn (VtVn)*和 (VtVn)*WQJWQJ通常約定以英文大寫字母表示某個(gè)非終結(jié)符，以英文小寫字母表示某個(gè)終結(jié)符，以希臘小寫

12、字母表示由終結(jié)符和或非終結(jié)符組成的某個(gè)符號(hào)串。例如，用I表示標(biāo)識(shí)符，L表示字母，D表示數(shù)字，則標(biāo)識(shí)符的文法可以寫成 G0(a，b，z，0，9，I ，L，D， I ，P)其中， I為文法的開始符號(hào)，P為I L 規(guī)則1I I D 規(guī)則2I I L 規(guī)則3D 0 規(guī)則4D 1 規(guī)則5D 9 規(guī)則13L a 規(guī)則14L b 規(guī)則15L z 規(guī)則39注意，在文法中使用了省略號(hào)，在正式定義語言時(shí)，應(yīng)將每個(gè)符號(hào)寫出來，以免產(chǎn)生歧義。WQJWQJ 在上述文法G0的定義中可以看出，有許多規(guī)則的左部是完全相同的，因此采用一種縮寫的方法。若有一組產(chǎn)生式 1 2 n則簡記為 1|2|n其中，每個(gè)i(1in)稱為候選式

13、(Candidate form)。WQJWQJ每個(gè)候選式代表?xiàng)l完整的規(guī)則。這樣，G0中的規(guī)則可以簡寫成I L I L I D D 0|1|9|La|b|z注意，在正式定義語言時(shí)，不要使用省略號(hào)，應(yīng)將每個(gè)符號(hào)寫出來。WQJWQJ例：按照上述方法，令E代表表達(dá)式，A表示運(yùn)算符，i表示變量或常量(終結(jié)符)，一個(gè)只有+和*的表達(dá)式文法G1可簡寫成 E EAE(E)iA +*顯然，通過上述文法可以知道，對于文法G1：有Vt=+,*,i，Vn=E,A，開始符為E。WQJWQJ4.2.2 文法的分類喬姆斯基將文法分成4類：0型、l型、2型和3型。這幾類文法的差別在于對產(chǎn)生式施加不同的限制。 (1)0型文法上

14、一小節(jié)定義的文法即是0型文法。在它的產(chǎn)生式 中， (VtVn)*Vn (VtVn)*和(VtVn)* ，此外無別的限制。0型文法生成的語言稱為0型語言，0型文法又稱為短語文法(PhraseGrammar)，簡記為PSG。0型文法的能力相當(dāng)于圖靈(Turing)機(jī)，或者說任何0型語言都是遞歸可枚舉(Recursively Enumerable)的；反之，任何遞歸可枚舉集(Recursively Enumerable Set)必定是一個(gè)0型語言。WQJWQJ (2)1型文法文法G的任何產(chǎn)生式 均滿足 ，僅僅S例外，但S不得出現(xiàn)在任何產(chǎn)生式的右部。其中 表示符號(hào)串的符號(hào)個(gè)數(shù)，即 的長度； 表示沒有任

15、何符號(hào)的符號(hào)串，即空符號(hào)串，0。1型文法也稱為上下文有關(guān)文法或前后文有關(guān)文法(Context-sensitive Grammar，簡記為CSG)。1型文法生成的語言稱為1型語言，又稱為上下文有關(guān)語言(Context-sensitive Language)，它是遞歸集(Recursive Set)的子集，也就是說，1型文法生成的語言一定是遞歸集，但遞歸集不一定是1型語言。WQJWQJ (3)2型文法 文法G的任何產(chǎn)生式均為A 形式，其中， AVn, (VtVn)* ，稱G為2型文法。2型文法的產(chǎn)生式左邊僅有一個(gè)非終結(jié)符，它不受上下文限制，因此也稱為上下文無關(guān)文法(Context-free Gra

16、mmar，簡記為CFG)。2型文法生成的語言稱為2型語言，也稱為上下文無關(guān)語言(Context-free Language，簡記為CFI)。WQJWQJ (4)3型文法文法G的任何產(chǎn)生式均為A B或A 的形式，其中， A ，B Vn, Vt* ， 稱G為3型文法，也稱正則文法(Regular Grammar)或右線性文法(Right Linear Grammar)。3型文法也可以定義成A B 或A 形式，稱G為左線性文法(Left Linear Grammar)，可以證明，每個(gè)左線性文法均可找到一個(gè)等價(jià)的右線性文法。3型文法生成的語言稱為3型語言，它是2型語言的一個(gè)子集，特別稱為正則集(Reg

17、ular Set)。通常強(qiáng)制式語言屬于2型語言，該語言的單詞(符號(hào))屬于正則集。因此，描述一個(gè)強(qiáng)制式語言通常使用上下文無關(guān)文法和正則文法就足夠了。WQJWQJ4.2.3 文法產(chǎn)生的語言1. 推導(dǎo)與歸約 直接推導(dǎo): 若 ，則 即由產(chǎn)生式右邊替換產(chǎn)生式左邊 推導(dǎo)序列:1 2 n歸約:推導(dǎo)的逆過程WQJWQJ舉例: 已知G(E) EE+EE*E(E)i i+i*i的推導(dǎo)過程 E E+E E+E*E E+E*i E+i*i i+i*i E E+E i+E i+E*E i+i*E i+i*i E E*E E*i E+E*i E+i*i i+i*iWQJWQJ練習(xí) 已知G1(E) ： EE+EE*E(E)

18、i (i+i)*i的最左推導(dǎo)過程和i+(i*i)的最右推導(dǎo)過程 E E*E(E)*E (E+E)*E (i+E)*E (i+i)*E (i+i)*i E E+E E+ (E) E+(E*E) E+(E*i) E+(i*i) i+(i*i) WQJWQJ2.句型設(shè)文法G=(VT,VN,S,P), 若S , V*, 則稱為文法G的一個(gè) (SententialForm)。從上述定義可以看出，從文法的開始符推導(dǎo)出的任意符號(hào)串均是該文法的句型，開始符自身也是一個(gè)句型，它由0步推導(dǎo)出。*WQJWQJ 3.句子和語言1）若句型中 VT*，則稱是一個(gè)句子，即只含終結(jié)符的句型是一個(gè)。例如，文法G1有一個(gè)推導(dǎo)S

19、E+E E+E* E E+i* E E+i*i i+i*i顯然i+i*i是G1的一個(gè)句子。WQJWQJ2)語言:文法G=(VT,VN,S,P)的句子的全體, 稱為由文法G產(chǎn)生的語言, 記為L(G), 即 L(G)=S VT*一個(gè)文法定義的語言可以是有限集合(如在4.1節(jié)定義的只產(chǎn)生4個(gè)英語句子的文法);也可以是無限集合(如定義標(biāo)識(shí)符的文法和定義表達(dá)式的文法)。 +WQJWQJ如果在一個(gè)文法中包含有遞歸定義的產(chǎn)生式，那么該文法定義的語言是無限集合。 例1：設(shè)文法G的產(chǎn)生式為S aSb這是一個(gè)右線性文法，不難看出L(G)anbn0WQJWQJ例2：設(shè)文法G2(S)的產(chǎn)生式為： SaSaP PbPb

20、Q QcQc則有L(G2)=aibjcki,j,k1上述文法生成的語言是所有i個(gè)a后跟j個(gè)b再跟k個(gè)c的符號(hào)串的集合，符號(hào)串中a，b和c至少都要有一個(gè)。 WQJWQJ例3：設(shè)文法G3(S)的產(chǎn)生式為: SaSPQabQ QPPQ bPbb bQbc cQcc則有L(G3)= aibicii 1符號(hào)串中a，b和c的個(gè)數(shù)相等且所有的a在前面，所有的c在后面，所有的b在中間。WQJWQJ4.2.4推導(dǎo)樹 以圖的方式表示推導(dǎo)過程對一個(gè)句子或一個(gè)句型的推導(dǎo)過程不止一種，可以用一棵樹來表示多種不同的推導(dǎo)，這種樹稱為推導(dǎo)樹(Derivation Tree)，或稱語法樹(Syntactic Tree)，也可稱

21、為分析樹(Parse Tree)。WQJWQJ推導(dǎo)樹是一棵有序的標(biāo)記樹 每個(gè)結(jié)點(diǎn)的標(biāo)記是文法G的非終結(jié)符或終結(jié)符； 標(biāo)記為A的內(nèi)部結(jié)點(diǎn)從左到右有子結(jié)點(diǎn)X1，X2，,Xn,則AX1Xn是一個(gè)產(chǎn)生式; 如果有結(jié)點(diǎn)標(biāo)記為，則它必是葉結(jié)點(diǎn)，且它是該父結(jié)點(diǎn)的唯一子結(jié)點(diǎn)。推導(dǎo)樹的：一棵推導(dǎo)樹所有葉結(jié)點(diǎn)的從左到右的連接。WQJWQJ推導(dǎo)樹的構(gòu)造 例（i+i*i）E（E）EE*EE+iiiE（E）EE+EEiii*WQJWQJ文法的二義性：一個(gè)有兩棵不同的推導(dǎo)樹。WQJWQJ限定條件構(gòu)造無二義文法例：考慮運(yùn)算符+和*的運(yùn)算優(yōu)先關(guān)系和結(jié)合規(guī)則，例如*的優(yōu)先性高于+，且它們都服從左結(jié)合律，那么可以構(gòu)造一個(gè)文法G，

22、它的規(guī)則如下E TE+TT FT*FF (E)i這里G就是一個(gè)無二義文法 。*試用此文法構(gòu)造（i+i*i）的推導(dǎo)樹。WQJWQJ4.3 語言的設(shè)計(jì)1.語言必須描述算法和數(shù)據(jù)結(jié)構(gòu)。2.所設(shè)計(jì)的語言的復(fù)雜程度依賴于設(shè)計(jì)目標(biāo)，即語言面向的問題和面向的機(jī)器。本節(jié)給出的是設(shè)計(jì)一個(gè)強(qiáng)制式語言的入門知識(shí)和方法。3.語言的設(shè)計(jì)首先需要定義語言的字母表和語言的詞法規(guī)則。語言的單詞符號(hào)一般包括：關(guān)鍵字、標(biāo)識(shí)符、常量、運(yùn)算符、界符。然后再定義其他的語法規(guī)則和語義規(guī)則。字母表和詞法規(guī)則定義相對簡單，略。WQJWQJ4.3.1 表達(dá)式的設(shè)計(jì) 強(qiáng)制式語言對數(shù)據(jù)的處理(運(yùn)算)主要在表達(dá)式中進(jìn)行，所以設(shè)計(jì)表達(dá)式至關(guān)重要。 表

23、達(dá)式分為邏輯表達(dá)式(Logic Expression)、關(guān)系表達(dá)式(Relational Expression)和算術(shù)表達(dá)式(ArithmeticExpression) 。 |WQJWQJ1.邏輯表達(dá)式邏輯表達(dá)式的運(yùn)算對象通常為布爾常量、布爾變量、關(guān)系表達(dá)式和邏輯表達(dá)式(遞歸)。運(yùn)算符有非()、與()和或()，其中為一元運(yùn)算符，它們有運(yùn)算的優(yōu)先順序，且服從左結(jié)合律。下面用BNF形式定義邏輯表達(dá)式：邏輯表達(dá)式邏輯表達(dá)式 布爾常量布爾變量關(guān)系表達(dá)式布爾常量布爾變量關(guān)系表達(dá)式 邏輯表達(dá)式邏輯表達(dá)式邏輯表達(dá)式邏輯表達(dá)式V邏輯表達(dá)式邏輯表達(dá)式邏輯表達(dá)式邏輯表達(dá)式邏輯表達(dá)式邏輯表達(dá)式布爾常量布爾常量 tr

24、ue false布爾變量布爾變量標(biāo)識(shí)符標(biāo)識(shí)符WQJWQJ2.關(guān)系表達(dá)式關(guān)系表達(dá)式通常用來判斷某個(gè)條件成立或不成立，它的運(yùn)算對象通常為算術(shù)表達(dá)式符通常有6種。關(guān)系表達(dá)式關(guān)系表達(dá)式 關(guān)系運(yùn)算符關(guān)系運(yùn)算符 WQJWQJ3算術(shù)表達(dá)式算術(shù)表達(dá)式是語言中對數(shù)據(jù)進(jìn)行運(yùn)算的最重要的表達(dá)式，其運(yùn)算符根據(jù)語言面向的問題有很多種，并采用了重載。通常算術(shù)表達(dá)式處理的原始數(shù)據(jù)和中間數(shù)據(jù)有整數(shù)和實(shí)數(shù)，如果面向的問題要求數(shù)據(jù)的精確度很高，還有雙精度數(shù)據(jù)。實(shí)數(shù)的描述比較煩瑣，它分為正負(fù)號(hào)部分、整數(shù)部分、小數(shù)部分和指數(shù)部分。指數(shù)部分又分為正負(fù)號(hào)部分和整數(shù)部分等。算術(shù)表達(dá)式的運(yùn)算符之間有優(yōu)先順序，且服從左結(jié)合律。WQJWQJ定義

25、算術(shù)表達(dá)式通常是把“先乘除，后加減”的運(yùn)算優(yōu)先順序和服從左結(jié)合律的規(guī)則考慮到文法中，以避免二義性。算術(shù)表達(dá)式算術(shù)表達(dá)式算術(shù)表達(dá)式算術(shù)表達(dá)式+項(xiàng)算術(shù)表達(dá)式項(xiàng)算術(shù)表達(dá)式-項(xiàng)項(xiàng)項(xiàng)項(xiàng)項(xiàng)項(xiàng)項(xiàng)項(xiàng)*因子項(xiàng)因子因子因子項(xiàng)因子因子因子因子 (算術(shù)表達(dá)式算術(shù)表達(dá)式)常量變量常量變量變量變量 標(biāo)識(shí)符標(biāo)識(shí)符常量常量整型常量實(shí)型常量整型常量實(shí)型常量WQJWQJ4.3.2語句的設(shè)計(jì)強(qiáng)制式語言是面向語句的語言，通過語句描述問題的求解過程，因此設(shè)計(jì)強(qiáng)制式語言的語句非常重要。語句主要分為兩類，一類是說明語句(Declaration Statement)，另一類是執(zhí)行語句(Execute Statement)。說明語句不需要由編

26、譯程序生成目標(biāo)代碼，它用來告訴編譯程序一些實(shí)體的屬性，編譯程序獲得這些屬性信息后，將它存放在相應(yīng)的描述符中，以供編譯程序在生成目標(biāo)代碼時(shí)使用。執(zhí)行語句要由編譯程序生成目標(biāo)代碼來實(shí)現(xiàn)它的語義。WQJWQJ1說明語句說明語句主要包括變量說明和類型說明。內(nèi)部類型不需要說明，用戶定義類型需要通過類型說明語句來說明。WQJWQJ說明語句常量說明變量說明類型說明常量說明const 標(biāo)識(shí)符常量變量說明 var 變量表:類型變量表變量|變量表;變量變量標(biāo)識(shí)符類型 integer | real | char | boolean | 類型名類型說明 type 類型名 用戶定義類型類型名標(biāo)識(shí)符用戶定義類型 (從略)

27、WQJWQJ2執(zhí)行語句執(zhí)行語句主要有數(shù)據(jù)處理語句(賦值語句)和語句執(zhí)行順序控制語句(控制語句)執(zhí)行語句讀語句|寫語句賦值語句控制語句復(fù)合語句讀語句 read(變量)寫語句 write(變量)賦值語句 :=控制語句 順序、選擇、重復(fù) 語句結(jié)束符復(fù)合語句 begin end語句表；WQJWQJ 4.3.3程序單元的設(shè)計(jì) 程序單元需要建立它的局部環(huán)境，因此必須有說明語句，這是它與復(fù)合語句不同的地方。一個(gè)程序單元必須標(biāo)識(shí)它的頭和尾以供編譯程序進(jìn)行區(qū)分。區(qū)分頭和尾的方法很多，為了讓編譯程序知道程序單元的性質(zhì)或?qū)傩?，通常都要?guī)定相應(yīng)的關(guān)鍵字，例如function(函數(shù))，procedure(過程)。WQJ

28、WQJ程序單元可以命名，也可以不命名。1）函數(shù)和過程通常都要命名，并用調(diào)用語句按名調(diào)用。函數(shù)和過程可以帶參數(shù)，以實(shí)現(xiàn)調(diào)用單元和被調(diào)用單元之間的通信。2）分程序(Block)是不命名的程序單元，它是嵌套結(jié)構(gòu)，也可以并列，按照分程序執(zhí)行順序自然調(diào)用(在哪里定義，就在哪里執(zhí)行)。分程序不帶參數(shù)，單元之間的通信依靠非局部變量來實(shí)現(xiàn)。WQJWQJ 設(shè)計(jì)一個(gè)程序單元，必須設(shè)計(jì)如何調(diào)用它，它的語義說明應(yīng)該包括：參數(shù)如何傳遞，程序單元執(zhí)行后應(yīng)將控制轉(zhuǎn)向哪里，以及其他應(yīng)當(dāng)規(guī)定的屬性。這些僅僅是最基本的要求，要設(shè)計(jì)一個(gè)程序單元，需要考慮的問題很多。WQJWQJBNF來對上述內(nèi)容進(jìn)行歸納。 程序單元 ()； 程序單

29、元關(guān)鍵字 procedurefunctionclass程序單元名標(biāo)識(shí)符 形參表形參形參表，形參 程序單元體 begin說明部分；執(zhí)行部分end說明部分說明語句表說明語句表說明語句說明語句表；說明語句 執(zhí)行部分執(zhí)行語句表執(zhí)行語句表執(zhí)行語句執(zhí)行語句表；執(zhí)行語句WQJWQJ分程序 begin說明部分；執(zhí)行部分end說明部分變量說明表；數(shù)組說明表；過程說明表；分程序表變量說明表變量說明變量說明表；變量說明數(shù)組說明表數(shù)組說明數(shù)組說明表；數(shù)組說明過程說明表過程說明過程說明表；過程說明分程序表分程序分程序表；分程序WQJWQJ4.3.4 程序的設(shè)計(jì)語言是用來描述程序的工具，因此，它必須定義程序的語法結(jié)構(gòu)。程

30、序必須有一個(gè)頭，首先應(yīng)當(dāng)有一個(gè)關(guān)鍵字，然后跟一個(gè)標(biāo)識(shí)符作為程序名，其后還可以跟參數(shù)(Pascal程序頭就帶參數(shù))。程序頭后面是程序體。定義非常簡單，形式如下：程序關(guān)鍵字程序名(參數(shù)) 程序體WQJWQJ4.4語言設(shè)計(jì)實(shí)例這一節(jié)首先設(shè)計(jì)一個(gè)極小的語言，它面向的問題是求解n的階乘，面向的機(jī)器就是一般的PC；然后用設(shè)計(jì)的語言編寫出計(jì)算n!的程序。由于n一定是正整數(shù)，因此，數(shù)據(jù)類型可以僅僅是整數(shù)，甚至是無符號(hào)整數(shù)。考慮到計(jì)算n!最簡便的算法為 if n0 then F:=1 else F:=n*F(n1)根據(jù)這個(gè)算法，需要考慮關(guān)系表達(dá)式、賦值語句、if語句和函數(shù)等，且函數(shù)需要遞歸調(diào)用。另外，輸入和輸出語句總是需要的。程序可選擇分程序，這樣就可以方便地設(shè)計(jì)出一個(gè)計(jì)算n!的語言。 WQJWQJbegin ； end ；integer 第三節(jié) 語言的設(shè)計(jì)WQJWQJ abcdefghijklmno pq rstuvwxyz0123456789integer function （）；第三節(jié) 語言的設(shè)計(jì)WQJWQJbegin ； end；read()write()第三節(jié) 語言的設(shè)計(jì)WQJWQJ:=-*第三節(jié) 語言的設(shè)計(jì)WQJWQJifthenelse =第三節(jié) 語言的設(shè)計(jì)WQJWQJ求n!的程序：begin integer k; integer function F(n); begin i