軟件工程第4章

第4章形式化說明技術(shù)4.1概述4.2有窮狀態(tài)機(jī)4.3Petri網(wǎng)4.4Z語言4.5小結(jié)習(xí)題按照形式式化的程程度，可可以把軟軟件工程程使用的的方法劃劃分成非非形式化化、半形形式化和和形式化化3類:用自然語語言描述述需求規(guī)規(guī)格說明明，是典典型的非非形式化化方法。。用數(shù)據(jù)流流圖或?qū)崒?shí)體-聯(lián)系圖建建立模型型，是典典型的半半形式化化方法。。所謂形式式化方法法，是描描述系統(tǒng)統(tǒng)性質(zhì)的的基于數(shù)數(shù)學(xué)的技技術(shù)，也也就是說說，如果果一種方方法有堅(jiān)堅(jiān)實(shí)的數(shù)數(shù)學(xué)基礎(chǔ)礎(chǔ)，那么么它就是是形式化化的。用自然語語言書寫寫的系統(tǒng)統(tǒng)規(guī)格說說明書，，可能存存在矛盾盾、二義義性、含含糊性、、不完整整性及抽抽象層次次混亂等等問題。。4.1概述4.1..1非形式化化方法的的缺點(diǎn)為了克服服非形式式化方法法的缺點(diǎn)點(diǎn)，人們們把數(shù)學(xué)學(xué)引入軟軟件開發(fā)發(fā)過程，，創(chuàng)造了了基于數(shù)數(shù)學(xué)的形形式化方方法。數(shù)學(xué)最有有用的一一個(gè)性質(zhì)質(zhì)是，它它能夠簡簡潔準(zhǔn)確確地描述述物理現(xiàn)現(xiàn)象、對(duì)對(duì)象或動(dòng)動(dòng)作的結(jié)結(jié)果，因因此是理理想的建建模工具具。數(shù)學(xué)學(xué)特別適適合于表表示狀態(tài)態(tài)，也就就是表示示“做什什么”。。需求規(guī)格格說明書書主要描描述應(yīng)用用系統(tǒng)在在運(yùn)行前前和運(yùn)行行后的狀狀態(tài)，因因此，數(shù)數(shù)學(xué)比自自然語言言更適于于描述詳詳細(xì)的需需求。4.1..2形式化方方法的優(yōu)優(yōu)點(diǎn)應(yīng)該選用用適當(dāng)?shù)牡谋硎痉椒椒ā?2)應(yīng)該形式式化，但但不要過過分形式式化。(3)應(yīng)該估算算成本。。(4)應(yīng)該有形形式化方方法顧問問隨時(shí)提提供咨詢?cè)儭?5)不應(yīng)該放放棄傳統(tǒng)統(tǒng)的開發(fā)發(fā)方法。。(6)應(yīng)該建立立詳盡的的文檔。。(7)不應(yīng)該放放棄質(zhì)量量標(biāo)準(zhǔn)。。(8)不應(yīng)該盲盲目依賴賴形式化化方法。。(9)應(yīng)該測(cè)試試、測(cè)試試再測(cè)試試。(10))應(yīng)該重用用。4.1..3應(yīng)用形式式化方法法的準(zhǔn)則則簡單例子子介紹有有窮狀態(tài)態(tài)機(jī)的基基本概念念。一個(gè)保險(xiǎn)險(xiǎn)箱上裝裝了一個(gè)個(gè)復(fù)合鎖鎖，鎖有有三個(gè)位位置，分分別標(biāo)記記為1、2、3，轉(zhuǎn)盤可可向左(L)或向右(R)轉(zhuǎn)動(dòng)。保險(xiǎn)箱的的組合密密碼是1L、3R、2L，轉(zhuǎn)盤的的任何其其他運(yùn)動(dòng)動(dòng)都將引引起報(bào)警警。4.2有窮狀態(tài)態(tài)機(jī)4.2..1概念圖4.1保險(xiǎn)箱的的狀態(tài)轉(zhuǎn)轉(zhuǎn)換圖從上面這這個(gè)簡單單例子可可以看出出，一個(gè)個(gè)有窮狀狀態(tài)機(jī)包包括下述述5個(gè)部分：：狀態(tài)集J:｛保險(xiǎn)箱箱鎖定，，A，B，保險(xiǎn)箱箱解鎖，，報(bào)警｝｝。輸入集K：｛1L，1R，2L，2R，3L，3R｝。轉(zhuǎn)換函數(shù)數(shù)T：由當(dāng)前前狀態(tài)和和當(dāng)前輸輸入確定定下一個(gè)個(gè)狀態(tài)(次態(tài)),如表4.1所示。初始態(tài)S：保險(xiǎn)箱箱鎖定。。終態(tài)集F：｛保險(xiǎn)險(xiǎn)箱解鎖鎖，報(bào)警警｝。如果使用用更形式式化的術(shù)術(shù)語，一一個(gè)有窮窮狀態(tài)機(jī)機(jī)可以表表示為一一個(gè)5元組(J，K，T，S，F(xiàn))，其中：：J是一個(gè)有有窮的非非空狀態(tài)態(tài)集；K是一個(gè)有有窮的非非空輸入入集；T是一個(gè)從從(J-F)×K到J的轉(zhuǎn)換函函數(shù)；S∈J，是一個(gè)個(gè)初始狀狀態(tài)；FJ，是終態(tài)態(tài)集。用自然語語言描述述的對(duì)電電梯系統(tǒng)統(tǒng)的需求求：在一幢m層的大廈廈中需要要一套控控制n部電梯的的產(chǎn)品，，要求這這n部電梯按按照約束束條件C1，C2和C3在樓層間間移動(dòng)。。C1：每部電電梯內(nèi)有有m個(gè)按鈕，，當(dāng)按下下一個(gè)按按鈕時(shí),電梯駛向向相應(yīng)的的樓層。。C2：每層樓樓都有兩兩個(gè)按鈕鈕分別請(qǐng)請(qǐng)求電梯梯上行和和下行。。電梯向向要求的的方向移移動(dòng)。C3：當(dāng)對(duì)電電梯沒有有請(qǐng)求時(shí)時(shí)，它關(guān)關(guān)門并停停在當(dāng)前前樓層。。4.2..2例子有窮狀態(tài)態(tài)機(jī)對(duì)本本產(chǎn)品進(jìn)進(jìn)行規(guī)格格說明:這個(gè)問題題中有兩兩個(gè)按鈕鈕集。n部電梯中中的每一一部都有有m個(gè)按鈕，，一個(gè)按按鈕對(duì)應(yīng)應(yīng)一個(gè)樓樓層。因因?yàn)檫@m×n個(gè)按鈕都都在電梯梯中，所所以稱它它們?yōu)殡婋娞莅粹o鈕。每層樓有有兩個(gè)按按鈕，一一個(gè)請(qǐng)求求向上，，另一個(gè)個(gè)請(qǐng)求向向下，這這些按鈕鈕稱為樓樓層按鈕鈕。圖4.2電梯按鈕鈕的狀態(tài)態(tài)轉(zhuǎn)換圖圖圖4.3樓層按鈕鈕的狀態(tài)態(tài)轉(zhuǎn)換圖圖圖4.4電梯的狀狀態(tài)轉(zhuǎn)換換圖給出電梯梯的狀態(tài)態(tài)轉(zhuǎn)換規(guī)規(guī)則:S(U,,e,f)+DC(e,f))M((U,e,f++1)S(D,,e,f)+DC(e,f))M((D,e,f--1)S(N,,e,f)+DC(e,f))W((e,f)第一條規(guī)規(guī)則表明明，如果果電梯e停在f層準(zhǔn)備向向上移動(dòng)動(dòng)，且門門已經(jīng)關(guān)關(guān)閉，則則電梯將將向上一一樓層移移動(dòng)。第二條和和第三條條規(guī)則，，分別對(duì)對(duì)應(yīng)于電電梯即將將下降或或者沒有有待處理理的請(qǐng)求求的情況況。有窮狀態(tài)態(tài)機(jī)方法法采用了了一種簡簡單的格格式來描描述規(guī)格格說明：：當(dāng)前狀態(tài)態(tài)+事件+謂詞下下個(gè)狀態(tài)態(tài)這種形式式的規(guī)格格說明易易于書寫寫、易于于驗(yàn)證，，而且可可以比較較容易地地把它轉(zhuǎn)轉(zhuǎn)變成設(shè)設(shè)計(jì)或程程序代碼碼。有窮狀態(tài)態(tài)機(jī)方法法比數(shù)據(jù)據(jù)流圖技技術(shù)更精精確4.2..3評(píng)價(jià)并發(fā)系統(tǒng)統(tǒng)中遇到到的一個(gè)個(gè)主要問問題是定定時(shí)問題題。用于確定定系統(tǒng)中中隱含的的定時(shí)問問題的一一種有效效技術(shù)是是Petri網(wǎng)，Petri網(wǎng)是由CarlAdamPetri發(fā)明的。。在性能評(píng)評(píng)價(jià)、操操作系統(tǒng)統(tǒng)和軟件件工程等等領(lǐng)域，，Petri網(wǎng)應(yīng)用得得都比較較廣泛。。Petri網(wǎng)包含4種元素：：一組位位置P、一組轉(zhuǎn)轉(zhuǎn)換T、輸入函函數(shù)I以及輸出出函數(shù)O。4.3Petri網(wǎng)4.3..1概念圖4.5Petri網(wǎng)的組成成圖4.6帶標(biāo)記的的Petri網(wǎng)圖4.7圖4.6的Petri網(wǎng)在轉(zhuǎn)換換t1被激發(fā)后后的情況況圖4.8圖4.7的Petri網(wǎng)在轉(zhuǎn)換換t2被激發(fā)后后的情況況現(xiàn)在把Petri網(wǎng)應(yīng)用于于電梯問問題。當(dāng)用Petri網(wǎng)表示電電梯系統(tǒng)統(tǒng)的規(guī)格格說明時(shí)時(shí)，每個(gè)個(gè)樓層用用一個(gè)位位置Ff代表(1≤f≤m))，在Petri網(wǎng)中電梯梯是用一一個(gè)權(quán)標(biāo)標(biāo)代表的的。在位置Ff上有權(quán)標(biāo)標(biāo)，表示示在樓層層f上有電梯梯。4.3..2例子圖4.10Petri網(wǎng)表示的的電梯按按鈕圖4.11Petri網(wǎng)表示樓樓層按鈕鈕用Z語言描述述的、最最簡單的的形式化化規(guī)格說說明含有有下述4個(gè)部分：：給定的集集合、數(shù)數(shù)據(jù)類型型及常數(shù)數(shù)。狀態(tài)定義義。初始狀態(tài)態(tài)。操作。4.4Z語言4.4..1簡介1.給定的集集合對(duì)于電梯梯問題，，給定的的初始化化集合稱稱為Button，即所有有按鈕的的集合，，因此，，Z規(guī)格說明明開始于于：〔Button〕2.狀態(tài)定義義一個(gè)Z規(guī)格說明明由若干干個(gè)“格格(schema)”組成，每每個(gè)格含含有變量量說明和和限定變變量取值值范圍的的謂詞。。例如，，格S的格式如如圖4.12所示。圖4.12Z格S的格式3.初始狀態(tài)態(tài)對(duì)于電梯梯問題來來說，抽抽象的初初始狀態(tài)態(tài)為：Button__Init〔〔Button_State｜pushed==Φ〕上式表示示，當(dāng)系系統(tǒng)首次次開啟時(shí)時(shí)pushed集為空，，即所有有按鈕都都處于關(guān)關(guān)閉狀態(tài)態(tài)。4.操作如果一個(gè)個(gè)原來處處于關(guān)閉閉狀態(tài)的的按鈕被被按下，，則該按按鈕開啟啟，這個(gè)個(gè)按鈕就就被添加加到pushed集中。圖4.13Z格Button__State圖4.14操作Push_Button的Z規(guī)格說明明圖4.15操作Floor_Arrival的Z規(guī)格說明明目前，Z也許是應(yīng)應(yīng)用得最最廣泛的的形式化化語言，，尤其是是在大型型項(xiàng)目中中Z語言的優(yōu)優(yōu)勢(shì)更加加明顯。。使用形式式化規(guī)格格說明是是全球的的總趨勢(shì)勢(shì)，過去去，主要要是歐洲洲習(xí)慣于于使用形形式化規(guī)規(guī)格說明明技術(shù)，，現(xiàn)在越越來越多多的美國國公司也也開始使使用形式式化規(guī)格格說明技技術(shù)。4.4..2評(píng)價(jià)基于數(shù)學(xué)學(xué)的形式式化規(guī)格格說明技技術(shù)，目目前還沒沒有在軟軟件產(chǎn)業(yè)業(yè)界廣泛泛應(yīng)用。。形式化方方法比欠欠形式化化方法更更難學(xué)習(xí)習(xí)，不僅僅在培訓(xùn)訓(xùn)階段要要花大量量的投資資，而且且對(duì)某些些軟件工工程師來來說，它它代表了了一種““文化沖沖擊”。。把形式化化方法和和欠形式式化方法法有機(jī)地地結(jié)合起起來，使使它們?nèi)∪￠L補(bǔ)短短，應(yīng)該該能獲得得更理想想的效果果。4.5小結(jié)4-1舉例對(duì)比比形式化化方法和和欠形式式化方法法的優(yōu)缺缺點(diǎn)。4-2在在什么么情況下下應(yīng)該使使用形式式化說明明技術(shù)??使用形形式化說說明技術(shù)術(shù)時(shí)應(yīng)遵遵守哪些些準(zhǔn)則??4-3一個(gè)浮點(diǎn)點(diǎn)二進(jìn)制制數(shù)的構(gòu)構(gòu)成是：：一個(gè)可可選的符符號(hào)(+或-)，后跟一一個(gè)或多多個(gè)二進(jìn)進(jìn)制位，，再跟上上一個(gè)字字符E，再加上上另一個(gè)個(gè)可選符符號(hào)(+或-)及一個(gè)或或多個(gè)二二進(jìn)制位位。例如如，下列列的字符符串都是是浮點(diǎn)二二進(jìn)制數(shù)數(shù)：習(xí)題110101E-101-100111E11101+1E0更形式化化地，浮浮點(diǎn)二進(jìn)進(jìn)制數(shù)定定義如下下：〈floatingpointbinary〉∷==［〈sign〉］〈bitstring〉E［〈sign〉］〈bitstring〉〈sign〉∷∷=+｜-〈bitstring〉∷==〈bit〉［〈bitstring〉］〈bit〉∷==0｜1其中，符號(hào)∷=表示定義義為；符號(hào)［...］表示可可選項(xiàng)；；符號(hào)a｜b表示a或b。假設(shè)有這這樣一個(gè)個(gè)有窮狀狀態(tài)機(jī)：：以一串串字符為為輸入，，判斷字字符串中中是否含含有合法法的浮點(diǎn)點(diǎn)二進(jìn)制制數(shù)。試試對(duì)這個(gè)個(gè)有窮狀狀態(tài)機(jī)進(jìn)進(jìn)行規(guī)格格說明。。4-4考慮下述述的自動(dòng)動(dòng)化圖書書館流通通系統(tǒng)：：每本書書都有一一個(gè)條形形碼，每每個(gè)借閱閱人都有有一個(gè)帶帶有條形形碼的卡卡片。當(dāng)當(dāng)一個(gè)借借閱人想想借一本本書時(shí)，，圖書管管理員掃掃描書上上的條形形碼和借借閱人卡卡片上的的條形碼碼，然后后在計(jì)算算機(jī)終端端上輸入入C；當(dāng)歸還還一本書書時(shí)，圖圖書管理理員將再再做一次次掃描，，并輸入入R。圖書管管理員可可以把一一些書加加到(+)圖書集合合中，也也可以刪刪除(-)它們。借閱人可可以在終終端上查查找到某某個(gè)作者者所有的的書(輸入“A=”和作者名名字)，或具有有指定標(biāo)標(biāo)題的所所有書籍籍(輸入“T=”和標(biāo)題)，或?qū)儆谟谔囟ㄖ髦黝}范圍圍內(nèi)的所所有圖書書(輸入“S=”加主題范范圍)。