第四章程序語(yǔ)言的性質(zhì)模型ppt課件

1、第四章 程序文語(yǔ)的性質(zhì)言語(yǔ)的方式化模型BNF為描畫程序設(shè)計(jì)言語(yǔ)的屬性提供了一種很好的手段，但并不是充分的手段。BNF回答了程序看起來(lái)象什么，但沒有回答程序是做什么的。方式化模型采用準(zhǔn)確的數(shù)學(xué)模型來(lái)描寫研討對(duì)象，為研討、分析和支配研討對(duì)象提供嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)工具和手段。本章將引見以下方式化模型：方式文法：?jiǎn)棠匪够姆ǚ旨?jí)言語(yǔ)的語(yǔ)義：屬性文法、指稱語(yǔ)義程序的驗(yàn)證4.1 言語(yǔ)的方式化性質(zhì)喬姆斯基分級(jí)文法言語(yǔ)的才干喬姆斯基分級(jí)文法文法由非終結(jié)符、終結(jié)符、開場(chǎng)非終結(jié)符、及產(chǎn)生式構(gòu)成文法的類別3型文法：正那么文法，定義詞法的模型2型文法：BNF文法，上下文無(wú)關(guān)文法1型文法：上下文有關(guān)文法0型文法：3型文法：正那

2、么文法為詞法分析器提供模型。這類文法的大多數(shù)性質(zhì)都是可斷定的如，能產(chǎn)生什么樣的串、給定串能否屬于文法規(guī)定的言語(yǔ)、言語(yǔ)中的串能否有限等正那么文法可以產(chǎn)生形如an的串，其中a為有限字符序列正那么文法只能計(jì)數(shù)有限數(shù)常用于關(guān)鍵字或單詞掃描2型文法上下文無(wú)關(guān)文法產(chǎn)生式的方式為：X , 其中可以是終結(jié)符和非終結(jié)符的恣意序列同樣，這類文法的大多數(shù)性質(zhì)都是可斷定的如，能產(chǎn)生什么樣的串、給定串能否屬于文法規(guī)定的言語(yǔ)、言語(yǔ)能否為空等可用來(lái)計(jì)數(shù)和比較兩個(gè)項(xiàng)，產(chǎn)生形如ancbn的串可以用堆棧來(lái)實(shí)現(xiàn)可用來(lái)自動(dòng)產(chǎn)生程序的語(yǔ)法分析樹2型和3型文法的相關(guān)問題都已根本上得到處理1型文法上下文有關(guān)文法產(chǎn)生式的方式為： , 其中恣

3、意非終結(jié)符串， 是終結(jié)符和非終結(jié)符的恣意序列，但中的符號(hào)個(gè)數(shù)應(yīng)不多于的符號(hào)個(gè)數(shù)從開場(chǎng)符開場(chǎng)導(dǎo)出的串的長(zhǎng)度是遞增的在生成串時(shí)，需求運(yùn)用固定數(shù)量的存儲(chǔ)空間，例如識(shí)別上下文無(wú)關(guān)文法無(wú)法識(shí)別的串a(chǎn)ncnbn上下文有關(guān)文法太復(fù)雜，很難用于程序設(shè)計(jì)言語(yǔ)人們對(duì)上下文有關(guān)文法的很多特征還不太清楚0型文法非限定型文法對(duì)產(chǎn)生式的方式 沒有任何限制可用來(lái)識(shí)別恣意可計(jì)算的函數(shù)其大多數(shù)性質(zhì)都是不可斷定的前往不可斷定性不同類型的文法越來(lái)越復(fù)雜，產(chǎn)生的言語(yǔ)也越來(lái)越復(fù)雜，但能否闡明計(jì)算機(jī)處理問題的才干可以越來(lái)越強(qiáng)，沒有限制？例如：能否編寫一個(gè)C言語(yǔ)程序來(lái)判別另一個(gè)C言語(yǔ)程序能否終了？但這根本上是不能夠的，這不是編程人員的問題

4、，而是由于計(jì)算機(jī)所基于的數(shù)學(xué)模型本身的局限性而導(dǎo)致的。圖靈機(jī)普通來(lái)說，用一種言語(yǔ)編寫的程序也可以用其他另一種言語(yǔ)來(lái)實(shí)現(xiàn)。那么能否存在某個(gè)程序，只能用某種言語(yǔ)來(lái)實(shí)現(xiàn)，而用其他言語(yǔ)就無(wú)法實(shí)現(xiàn)？假設(shè)沒有，那么有哪些程序是其它程序設(shè)計(jì)言語(yǔ)無(wú)法表示的，為什么還需求那么多種不同的言語(yǔ)？假設(shè)我們將可以表示一切計(jì)算的言語(yǔ)都稱為通用言語(yǔ)，那么是不是一切言語(yǔ)都是通用言語(yǔ)？假設(shè)是，能否存在更簡(jiǎn)單的通用言語(yǔ)？圖靈機(jī)的構(gòu)造圖靈機(jī)是一種用來(lái)定義可計(jì)算函數(shù)的籠統(tǒng)計(jì)算機(jī)圖靈機(jī)只需一個(gè)單一的數(shù)據(jù)構(gòu)造，即一個(gè)稱為“帶子的可變長(zhǎng)線性數(shù)組帶子被分為很多格，每格上只包含一個(gè)字符圖靈機(jī)還有一個(gè)指針變量，稱為“讀出頭，它總是指向帶子上的某

5、個(gè)格。圖靈機(jī)的操作圖靈機(jī)只提供幾個(gè)簡(jiǎn)單的操作：讀出頭所指定位置的字符可以被讀出或被修正。程序可以根據(jù)讀出的值進(jìn)展轉(zhuǎn)移。讀出頭可以左右挪動(dòng)。假設(shè)讀出頭挪動(dòng)到帶子的最末端，那么自動(dòng)在帶子上加上一格，并賦予一個(gè)空字符作為初始值。圖靈機(jī)的運(yùn)轉(zhuǎn)圖靈機(jī)開場(chǎng)運(yùn)轉(zhuǎn)時(shí)，帶子上存放輸入數(shù)據(jù)，讀出頭指向輸入數(shù)據(jù)的最左端的字符；圖靈機(jī)根據(jù)預(yù)先編好的操作序列讀寫帶子上的數(shù)據(jù)、或挪動(dòng)讀出頭；假設(shè)最終可以停機(jī)，那么帶子上的內(nèi)容就是最后的輸出結(jié)果。圖靈機(jī)的才干恣意可計(jì)算函數(shù)都可以用圖靈機(jī)計(jì)算出來(lái)Church論題圖靈機(jī)等價(jià)于0型文法確定型圖靈機(jī)等價(jià)于非確定型圖靈機(jī)。停機(jī)問題能否存在某個(gè)通用的算法，它可以斷定恣意給定的圖靈機(jī)在恣

6、意的輸入下能否停機(jī)？停機(jī)問題是不可判別的，即不存在這樣的通用算法。恣意一個(gè)不可判別的問題，都等價(jià)于停機(jī)問題。結(jié)論：任何一種程序設(shè)計(jì)言語(yǔ)都能夠替代其它言語(yǔ)程序設(shè)計(jì)言語(yǔ)不存在質(zhì)的區(qū)別，只需量的區(qū)別，如能否優(yōu)美、易用、高效等任何一種程序設(shè)計(jì)言語(yǔ)都有它存在的理由前往4.2 言語(yǔ)的語(yǔ)義程序設(shè)計(jì)言語(yǔ)根本上都是以上下文無(wú)關(guān)文法(特別是 LR(k) 文法)的中心設(shè)計(jì)的。但語(yǔ)法分析曾經(jīng)不再是人們感興趣的研討問題了。如今的問題是如何確定程序的含義即語(yǔ)義。言語(yǔ)的語(yǔ)義言語(yǔ)的手冊(cè)必需定義言語(yǔ)中每個(gè)構(gòu)造的含義，包括單獨(dú)構(gòu)造的含義以及和其他構(gòu)造組合時(shí)的含義。言語(yǔ)提供了不同構(gòu)造，用戶為了寫正確的程序，預(yù)測(cè)語(yǔ)句的執(zhí)行效果和實(shí)現(xiàn)

7、者正確地實(shí)現(xiàn)言語(yǔ)需求這些構(gòu)造的準(zhǔn)確定義。大多數(shù)言語(yǔ)中，方式文法用于定義語(yǔ)法，一段文字或例子用于定義語(yǔ)義，但定義是不準(zhǔn)確的，有二義性，不同作者能夠有不同了解。語(yǔ)義定義問題還是實(shí)際研討的目的，但至今沒有令人稱心的解答。已有各種方式方法用于語(yǔ)義定義。語(yǔ)義建模1文法模型對(duì)定義言語(yǔ)的BNF文法進(jìn)展擴(kuò)展，給出程序的語(yǔ)法分析樹，從樹中抽取出附加信息。屬性文法便是抽取附加信息的一種方式。語(yǔ)義建模2命令或操作模型定義程序如何在某虛擬機(jī)上執(zhí)行。通常描畫為一自動(dòng)機(jī)，但比語(yǔ)法用的簡(jiǎn)單自動(dòng)機(jī)遠(yuǎn)為復(fù)雜。自動(dòng)機(jī)有內(nèi)部形狀對(duì)應(yīng)程序執(zhí)行時(shí)的內(nèi)部形狀，包括一切變量的值、執(zhí)行程序本身、以及各種系統(tǒng)定義的數(shù)據(jù)構(gòu)造。語(yǔ)義建模2命令或操

8、作模型一組方式定義的操作用于刻劃自動(dòng)機(jī)內(nèi)部形狀如何改動(dòng)。此外還需定義程序文本如何翻譯成自動(dòng)機(jī)的初始形狀。言語(yǔ)的操作定義對(duì)言語(yǔ)如何實(shí)踐執(zhí)行給出了相當(dāng)直接的籠統(tǒng)。也能夠提出一個(gè)更籠統(tǒng)的模型，作為言語(yǔ)的軟件解釋的根底。70年代的VDLVienna Definition Language是一個(gè)操作方法。它擴(kuò)展語(yǔ)法分析樹已包含機(jī)器解釋器。計(jì)算的形狀是程序樹加上描畫機(jī)器中一切數(shù)據(jù)的樹。每條語(yǔ)句的執(zhí)行使樹的形狀發(fā)生變化。語(yǔ)義建模3作用型模型試圖直接構(gòu)造每個(gè)程序的函數(shù)的定義，采用層次式的構(gòu)造方式。程序中每個(gè)根本的或程序員定義的操作代表一個(gè)數(shù)學(xué)函數(shù)。言語(yǔ)的程序控制構(gòu)造用于將這些函數(shù)復(fù)合為更大的序列，代表表達(dá)式和

9、言語(yǔ)。語(yǔ)句序列和條件分叉表示為個(gè)體函數(shù)構(gòu)造而成的函數(shù)。循環(huán)通常表示為遞歸函數(shù)。最終，為整個(gè)程序?qū)С鲆粋€(gè)完好的函數(shù)模型，指稱語(yǔ)義歸于此類。語(yǔ)義建模4公理模型運(yùn)用謂詞演算，每個(gè)語(yǔ)法構(gòu)造的語(yǔ)義被描畫為公理或推導(dǎo)規(guī)那么，用于導(dǎo)出構(gòu)造的執(zhí)行效果。從一個(gè)初始假設(shè)開場(chǎng)，假設(shè)輸入變量滿足一定的約束，在程序語(yǔ)句執(zhí)行后，運(yùn)用公理和推導(dǎo)規(guī)那么來(lái)推導(dǎo)其他變量值需滿足的限制，最終，程序的結(jié)果被證明滿足希望的約束描畫了它們的值和輸入值的關(guān)系。如Hoare的公理語(yǔ)義。 語(yǔ)義建模5規(guī)約模型描畫實(shí)現(xiàn)程序的各個(gè)函數(shù)的關(guān)系，只需我們可以證明一個(gè)實(shí)現(xiàn)符合了一切的函數(shù)間的關(guān)系，那么稱實(shí)現(xiàn)相對(duì)于規(guī)約是正確的。代數(shù)數(shù)據(jù)類型是方式規(guī)約的一種

10、方式。例如：實(shí)現(xiàn)棧的程序，S表示棧，那么有公理，pop(push(S,x)=S任何一個(gè)實(shí)現(xiàn)假設(shè)能堅(jiān)持這種關(guān)系，那么稱是棧的正確實(shí)現(xiàn)。語(yǔ)義模型小結(jié)上述各種方式語(yǔ)義模型各有優(yōu)點(diǎn)，但均不能稱為完全適用的和適用的，各有其適宜范圍。操作語(yǔ)義為言語(yǔ)的實(shí)現(xiàn)提供了一種方式模型，但對(duì)用戶來(lái)說太細(xì)節(jié)公理語(yǔ)義易于了解，但很難用來(lái)定義復(fù)雜的程序設(shè)計(jì)言語(yǔ)，且缺乏對(duì)言語(yǔ)實(shí)現(xiàn)的支持前往語(yǔ)義建模屬性文法這是最早的開發(fā)語(yǔ)義模型的任務(wù)之一。其思想是對(duì)分析樹中的每個(gè)結(jié)點(diǎn)關(guān)聯(lián)一個(gè)函數(shù)，從而給出結(jié)點(diǎn)的語(yǔ)義內(nèi)容。屬性文法的創(chuàng)建過程是為文法中的每一條規(guī)那么都定義相關(guān)的語(yǔ)義函數(shù)。承繼屬性是一個(gè)函數(shù)，它將樹中非終結(jié)符值和樹中更高層的非終結(jié)符值

11、相關(guān)聯(lián)。換言之，任何規(guī)那么右端的非終結(jié)符的函數(shù)值是左端非終結(jié)符的函數(shù)。綜合屬性是一個(gè)函數(shù)，它將左端非終結(jié)符和右端非終結(jié)符的值相關(guān)聯(lián)，這些屬性在樹中向上傳送信息，即從樹中下層信息進(jìn)展“綜合。 屬性文法例：思索算術(shù)表達(dá)式的簡(jiǎn)單文法。ET|E+TTP|TPPI|(E)其語(yǔ)義經(jīng)過文法中非終結(jié)符間的關(guān)系集合定義。如：下面函數(shù)生成該文法生成的恣意表達(dá)式的值：產(chǎn)生式屬性EE+TValue(E1)=V(E2)+V(T)ETV(E)=V(T)TTPV(T1)=V(T2)V(P)TPV(T)=V(P)PIV(P)=數(shù)I的值P(E)VP=VE 屬性文法以下圖是一個(gè)屬性樹，它給出了表達(dá)式2+4(1+2)值 屬性文法屬

12、性文法可用于在語(yǔ)法樹中傳送語(yǔ)義信息。例如，聲明信息可以經(jīng)過言語(yǔ)的聲明產(chǎn)生式搜集。沿樹向下傳的符號(hào)表信息可用于生成表達(dá)式代碼。下面屬性可加到非終結(jié)符和來(lái)創(chuàng)建一個(gè)程序中聲明的名字集合。產(chǎn)生式屬性:= decl_set(declaration1)=declaname(decl) decl_set(declaration2):=decl_set(declaration)=decl-name(decl):=declare xdecl-name(decl)=x(decl):=declare ydecl-name(decl)=y(decl):=declare zdecl-name(decl)=z這是綜合屬性

13、，包含程序中聲明的名字集合。該屬性可以沿樹向下傳送，成為承繼屬性，用于正確地生成數(shù)據(jù)的代碼。屬性文法的運(yùn)用首先創(chuàng)建語(yǔ)法分析樹。屬性文法假設(shè)他曾經(jīng)知道表達(dá)式是如何推導(dǎo)出來(lái)的，它并不關(guān)懷是如何分析推導(dǎo)出來(lái)的。定義屬性的函數(shù)可以是恣意給定的，因此定義屬性的過程完全是手工完成的。假設(shè)只需綜合屬性，并且文法是 LR(k)，那么，屬性文法可以用來(lái)在語(yǔ)法分析時(shí)自動(dòng)產(chǎn)程中間代碼。這就是 YACC 如何任務(wù)的，它利用屬性文法來(lái)計(jì)算一切非終結(jié)符的值。在構(gòu)造分析樹時(shí)，非終結(jié)符的信息逐層向上傳送給分析樹上層的非終結(jié)符。語(yǔ)法分析終了，一切屬性的值將計(jì)算出來(lái)。前往指稱語(yǔ)義指稱語(yǔ)義是一種用來(lái)描畫程序設(shè)計(jì)言語(yǔ)的語(yǔ)義的作用型語(yǔ)

14、義模型指稱語(yǔ)義基于-演算-演算-演算是一種和圖靈機(jī)的計(jì)算才干相當(dāng)?shù)膶?shí)際計(jì)算模型-演算可以作為程序設(shè)計(jì)言語(yǔ)的函數(shù)調(diào)用的模型Algol和Lisp都采用來(lái)-演算的函數(shù)調(diào)用語(yǔ)義指稱語(yǔ)義是對(duì)-演算的擴(kuò)展，它將-演算擴(kuò)展為一種通用的數(shù)據(jù)類型實(shí)際-演算的表達(dá)式-表達(dá)式可以遞歸地定義如下：變量名為-表達(dá)式假設(shè)M為一個(gè)-表達(dá)式，那么x.M也是一個(gè)-表達(dá)式假設(shè)F和A都是-表達(dá)式，那么(F A)也是-表達(dá)式，其中F為操作符，A為操作數(shù)。方式語(yǔ)法：-expr := id | id.-expr | (-expr -expr)x相當(dāng)于聲明參數(shù)變量x，沒有聲明的變量為自在變量，否那么為約束變量。x.M相當(dāng)于函數(shù)聲明，其中x

15、相當(dāng)于M的參數(shù)。例如：x x.x x.(xy) x.y (x.x y.y)-表達(dá)式的操作-表達(dá)式只需一種操作：約簡(jiǎn)(F A)約簡(jiǎn)相當(dāng)于將A作為實(shí)踐參數(shù)，交換F的方式參數(shù)的一切出現(xiàn)(x.M A) M，相當(dāng)于用A交換M中x的一切自在出現(xiàn)。例如：(x.x y) y(x.(xy) x.x) x.x y y留意：約簡(jiǎn)并不一定能簡(jiǎn)化原來(lái)的表達(dá)式(x.(xx) x.(xx) (x.(xx) x.(xx) 指稱語(yǔ)義指稱語(yǔ)義的根本思想是定義一個(gè)語(yǔ)義函數(shù)指稱函數(shù)，把程序的意義映射到某種意義明晰的數(shù)學(xué)對(duì)象就像用中文解釋英文作為被指的數(shù)學(xué)對(duì)象可以根據(jù)需求選擇對(duì)于簡(jiǎn)單的程序文語(yǔ)，一種很自然的選擇是把程序的語(yǔ)義定義為指稱

16、為從形狀到形狀的函數(shù)。定義語(yǔ)義就是定義好每個(gè)程序?qū)?yīng)的函數(shù)。程序的形狀由標(biāo)識(shí)符到值的映射集合構(gòu)成S = id | value, 指稱語(yǔ)義表達(dá)式的語(yǔ)義e S val語(yǔ)句的語(yǔ)義s S S程序的語(yǔ)義m val val指稱語(yǔ)義設(shè)為程序的當(dāng)前形狀表達(dá)式的語(yǔ)義常數(shù)：n = n變量：x = (x)算術(shù)表達(dá)式：e1 + e2 = e1 + e2語(yǔ)句的語(yǔ)義賦值語(yǔ)句：x = e = x | e復(fù)合語(yǔ)句：s1; s2 = s2(s1)條件語(yǔ)句：if b then s1 else s2 = if b then s1 else s2程序的語(yǔ)義m val val前往程序驗(yàn)證在編程時(shí)，人們?cè)絹?lái)越關(guān)懷程序的正確性和可靠性。人

17、們?cè)谠O(shè)計(jì)程序設(shè)計(jì)言語(yǔ)時(shí)，也希望經(jīng)過添加新的特征來(lái)加強(qiáng)程序的正確性和可靠性。我們可以用程序語(yǔ)義，按以下方式來(lái)討論程序的正確性問題：給定程序P，其含義是什么？即，它的規(guī)范描畫S是什么？給定規(guī)范描畫S，開發(fā)實(shí)現(xiàn)了該規(guī)范描畫的程序P規(guī)范描畫S和程序P能否完成了一樣的功能執(zhí)行了一樣的函數(shù)？相當(dāng)于語(yǔ)義建模問題軟件工程的中心問題程序驗(yàn)證的中心問題程序驗(yàn)證測(cè)試不能保證程序的正確性假設(shè)能找到不依賴于測(cè)試的保證程序正確性的方法，產(chǎn)生的程序就能更加可靠：程序計(jì)算了一個(gè)函數(shù)假設(shè)能給出該函數(shù)的規(guī)范描畫，并且可以根據(jù)程序知道它究竟計(jì)算了一個(gè)什么樣的函數(shù)，那么，假設(shè)可以證明程序所計(jì)算的函數(shù)與給定的函數(shù)等價(jià)或一樣，就能證明程

18、序的正確性，而不需再測(cè)試。方式化的規(guī)范描畫任一程序都可以表示成流程圖基調(diào)：函數(shù)名：定義域 值域 fun1: S1 and P1 S3 fun2: S1 and not(P1) S3 fun3: S3 and not(P3) S4 fun4: S3 and P3 S4 S2 and P2 = S4 S2 and not(P2) = S3P1P2P3 Fcn1Fcn4Fcn3Fcn2S1S2S3S4方式化的規(guī)范描畫續(xù)這樣，程序可以看成是一個(gè)定義在其根本成分上的復(fù)雜函數(shù)：C(fun1, fun2, fun3, fun4, p1, p2, p3): S1 S4假設(shè)我們可以方式化地推導(dǎo)出上述關(guān)系，那么我

19、們就可以從數(shù)學(xué)上證明，給定S1, 程序?qū)⒔K止于形狀 S4。但是：證明非常困難。另外，在證明時(shí)，我們總是想證明程序和某個(gè)給定的方式化規(guī)范等價(jià)，但問題是，假設(shè)沒有給出規(guī)范描畫，“程序能否正確？能夠就沒有了意義。公理化驗(yàn)證用謂詞邏輯公式來(lái)描寫程序的語(yǔ)義、用謂詞演算來(lái)驗(yàn)證程序的正確性。 Tony Hoare 在1969年提出的。每個(gè)程序都遵照某種方式化的公理定義。實(shí)證Validation: 經(jīng)過一系列測(cè)試數(shù)據(jù)的測(cè)試，展現(xiàn)程序滿足了其規(guī)范描畫。驗(yàn)證Verification: 根據(jù)程序構(gòu)造，經(jīng)過方式化的討論，展現(xiàn)程序滿足了其規(guī)范描畫。Validation普通以為需求執(zhí)行程序，而 verification不

20、需求。謂詞邏輯公理P1SP2 表示假設(shè) P1 為真，那么在 S 執(zhí)行并終止后，P2 將為真。假設(shè) A 為真，那么 B 也為真。邏輯公理：組合順序1順序2PS1Q,QS2R 組合語(yǔ)句PS1;S2RPSR, RQ 添加后置條件PSQPR, RSQ 添加前置條件 PSQ語(yǔ)句類型的公理?xiàng)l件語(yǔ)句1條件語(yǔ)句2While循環(huán)語(yǔ)句賦值語(yǔ)句PBSQ, Pnot(B)Q Pif B then SQPBS1Q,Pnot(B)S2Q Pif B then S1 else S2QPBSPPwhile B do SP not(B)，其中 P 為不變式P(e)x:=eP(x)，P(x) 為 x 的謂詞。公理化的程序證明給定

21、程序：s1; s2; s3; s4; sn 及其規(guī)約：P 和 QP 為前置條件Q 為后置條件經(jīng)過證明以下的謂詞來(lái)證明 Ps1;snQ：Ps1p1p1s2p2 pn-1snQ反復(fù)運(yùn)用組合公理，產(chǎn)生：Ps1; ; snQ例子B=01X:=B2Y:=03while X0 do4 begin5 Y:= Y+A6 X:= X-17 endY=AB即，給定非負(fù)的 B，證明當(dāng)程序終止時(shí)， Y=A*B.證明過程概要普統(tǒng)統(tǒng)過回溯來(lái)進(jìn)展。首先，找到循環(huán)的不變式：Y 為乘積的一部分，X 為剩下的乘數(shù)因此，Y 和 X*A 必需是所需的乘機(jī)，即不變式Y(jié)+X*A = A*B 就是建議的不變式可以試著用 (Y+X*A=A*

22、B and X=0)作為不變式 證明賦值語(yǔ)句公理(6): (Y+(X-1)A=A*B and X-1=0) X:=X-1 (Y+X*A=A*B and X=0)賦值語(yǔ)句公理(5): (Y+A)+(X-1)A=A*B and X-1=0) Y:=Y+A (Y+(X-1)*A=A*B and X-1=0) 組合公理 (5,6): (Y+A)+(X-1)*A=A*B and X-1=0) Y:=Y+A; X:=X-1 (Y+X*A=A*B and X=0)數(shù)學(xué)定理: Y+X*A=A*B and X0 (Y+A)+(X-1)*A=A*B and X-1=0)順序語(yǔ)句公理: Y+X*A=A*B and

23、X0 Y:=Y+A; X:=X-1 (Y+X*A=A*B and X=0)數(shù)學(xué)定理: (Y+X*A=A*B and X=0) and (X0) Y+X*A=A*B and X0順序語(yǔ)句公理: (Y+X*A=A*B and X=0)and (X0) Y:=Y+A; X:=X-1 (Y+X*A=A*B and X=0) 用 * 來(lái)替代While循環(huán)語(yǔ)句公理: * Y+X*A=A*B and X=0while X0 do Y:=Y+A; X:=X-1 (Y+X*A=A*B and X=0) and not(X0)證明 (續(xù))數(shù)學(xué)定理: (Y+X*A=A*B and X=0) and not(X0)

24、(Y+X*A=A*B and X=0) Y=AB順序語(yǔ)句公理: Y+X*A=A*B and X=0while X0 do Y:=Y+A; X:=X-1 Y+A*B賦值語(yǔ)句公理: 0+X*A=A*B and X=0 Y:=0 Y+X*A=A*B and X=0賦值語(yǔ)句公理: 0+B*A=A*B and B=0 X:=B 0+X*A=A*B and X=0) 組合公理: 0+B*A=A*B and B=0 X:=B; Y:=0 Y+X*A=A*B and X=0)數(shù)學(xué)定理: (B=0) 0+B*A=A*B and B=0順序語(yǔ)句公理: B=0 X:=B; Y:=0Y+X*A=A*B and X=0

25、)組合公理: B=0 program Y=A*B公理化驗(yàn)證小結(jié)需求為言語(yǔ)的一切特征建立公理，能否也為簡(jiǎn)單數(shù)組、過程調(diào)用、參數(shù)等建立公理？即使是要證明小程序也很困難，要證明大型程序就更困難了。還不能很好地處置非數(shù)學(xué)方面的問題，處置起來(lái)極端困難。很難自動(dòng)化，而手工又會(huì)導(dǎo)致大量錯(cuò)誤。但是準(zhǔn)確，可以清楚地域別“程序是什么以及“程序是如何處理問題 它是大多數(shù)其他驗(yàn)證方法的根底，包括半方式化的規(guī)范表示法。對(duì)于關(guān)鍵運(yùn)用，付出的代價(jià)還是值得的。程序驗(yàn)證只需程序正確性的驗(yàn)證過程可以自動(dòng)化，程序驗(yàn)證才有實(shí)踐意義但要證明那些沒有構(gòu)造化的程序、以及那些具有復(fù)雜構(gòu)造的程序的正確性，非常困難，根本上是不能夠的。程序驗(yàn)證任

26、務(wù)的研討成果通常用來(lái)指點(diǎn)程序設(shè)計(jì)言語(yǔ)的設(shè)計(jì)例如，在C+中加斷言等。ML 概述ML (元言語(yǔ)) 是一種函數(shù)式言語(yǔ)，其程序的方式與 C 或 Pascal 類似。 ML 由 Robin Milner 于1970年代中期開發(fā)，是一種機(jī)器輔助方式化證明的機(jī)制。ML 也可以作為一種通用符號(hào)支配言語(yǔ)。1983，該言語(yǔ)中參與了模塊等概念，并經(jīng)過重新設(shè)計(jì)，構(gòu)成了如今的規(guī)范ML。 ML 是一種具有靜態(tài)類型、強(qiáng)類型、和函數(shù)式執(zhí)行的言語(yǔ)，但類型不用由程序員來(lái)指定。ML 程序由假設(shè)干個(gè)函數(shù)定義構(gòu)成。每個(gè)函數(shù)的類型是靜態(tài)的，函數(shù)可以前往恣意類型的值。由于是函數(shù)型的言語(yǔ)，變量的存儲(chǔ)與C或Fortran言語(yǔ)的很不一樣。ML

27、可以經(jīng)過其類型系統(tǒng)支持多態(tài)，還支持?jǐn)?shù)據(jù)籠統(tǒng)。ML 程序例子 1 fun digit(c:string):int = ord(c)-ord(0); 2 (* Store values as a list of characters *) 3 fun SumNext(V) = if V= then (print(n Sum=); 0) 4 else (print(hd(V); 5 SumNext(tl(V)+digit(hd(V); 6 fun SumValues(x:string):int= SumNext(explode(x); 7 fun ProcessData() = 8 (let val infile = open_in(data.sml); 9 val count = digit(input(infile,1) 10 in 11 print(SumValues(input(infile,count) 12 end; 13 print(n);把一個(gè)列表顛倒過來(lái)的函數(shù)datatype list a, b, c, d, ehd(x)：列表的頭，或第一個(gè)元素tl(x)：列表的尾，或除第一個(gè)元素外的元素x:y 表示頭為 x，尾為 y 的列表xy 表示銜接列表 x 和 yfun reverse(L) = if L = nil then nilelse reverse(tl(L) h