軟件工程第4章

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