UML活動圖模型中錯誤的定位工具說明書

1、單位代碼 10006 學(xué) 號 分 類 號 TP311 畢業(yè)設(shè)計(論文)UML活動圖模型中錯誤的定位工具院（系）名稱計算機(jī)學(xué)院專業(yè)名稱計算機(jī)科學(xué)與技術(shù)學(xué)生姓名指導(dǎo)教師2013年6月UML活動圖模型中錯誤的定位工具 北京航空航天大學(xué)本科畢業(yè)設(shè)計（論文）任務(wù)書、畢業(yè)設(shè)計（論文）題目：UML活動圖模型中錯誤的定位工具、畢業(yè)設(shè)計（論文）使用的原始資料（數(shù)據(jù)）及設(shè)計技術(shù)要求：1、課題來源：課題來源于實驗室在軟件的自動化調(diào)試方面的科學(xué)研究2、技術(shù)要求： (1)使用C+語言來完成錯誤定位工具的相關(guān)操作部分。 (2)通過讀入外部的活動圖文件，結(jié)合相關(guān)錯誤定位算法實現(xiàn)活動圖的錯誤定位工作。 (3)用戶界面部分可以

2、使用C#編程，使其具有良好的人機(jī)交互。、畢業(yè)設(shè)計（論文）工作內(nèi)容：（1）實現(xiàn)對外部UML活動圖文件的讀取和解析。（2）完成錯誤定位算法在UML活動圖模型上的應(yīng)用。（3）完成良好的用戶界面，在活動圖上能夠明顯的顯示錯誤的位置。、主要參考資料：1 李未, 李寧. A formal semantics for program debuggingJ. SCIENCE CHINA Information Sciences, 2012: 133-148.2 李寧. 基于UML的模型錯誤檢測研究D. 北京: 北京航空航天大學(xué), 2011.3 Roger S.Pressman. Software Engine

3、ering A Practitioners ApproachM. China Machine Press, 2007.4 Booch. UML用戶指南M. 人民郵電出版社, 2006. 計算機(jī)學(xué)院（系）計算機(jī)科學(xué)與技術(shù)專業(yè)類 班學(xué)生劉艾杉畢業(yè)設(shè)計（論文）時間： 2013年3月4日至 2013年6月11日答辯時間： 2013年6月 18日成績：指導(dǎo)教師：李未兼職教師或答疑教師（并指出所負(fù)責(zé)部分）： 系（教研室） 主任（簽字）： 本人聲明我聲明，本論文及其研究工作是由本人在導(dǎo)師指導(dǎo)下獨(dú)立完成的，在完成論文時所利用的一切資料均已在參考文獻(xiàn)中列出。作者：簽字：時間：2013年6月UML活動圖模型中錯誤

4、的定位工具學(xué) 生： 指導(dǎo)教師：摘要目前，隨著各種系統(tǒng)和軟件的規(guī)模與復(fù)雜度的增加，模型驅(qū)動技術(shù)被廣泛的應(yīng)用于系統(tǒng)的構(gòu)建、靜態(tài)和動態(tài)行為刻畫與分析等方面。這其中，以面向?qū)ο蠼橹鲗?dǎo)思想的統(tǒng)一建模語言（UML）得到了廣泛的應(yīng)用。研究成果表明，軟件開發(fā)中70%的錯誤是在軟件工程生命周期中的早期被引入（即在模型設(shè)計階段中引入）；而錯誤中的80%只有到了系統(tǒng)開發(fā)后期的測試階段之后才被發(fā)現(xiàn)，而錯誤的修改成本大大增加1。因此，在模型階段進(jìn)行錯誤的定位，能夠大量的減少后期發(fā)現(xiàn)錯誤改正錯誤所花費(fèi)的精力。本文主要工作和技術(shù)內(nèi)容如下：1、將基于C-Kernal語言的函數(shù)內(nèi)調(diào)試的形式化錯誤定位算法應(yīng)用到了UML模型上

5、。 2、提出了一種分析UML活動圖的方式，即通過解析UML標(biāo)準(zhǔn)的導(dǎo)出的XMI格式文件。在XMI格式的文件中，定義了很有規(guī)律的標(biāo)簽，它們有規(guī)律的記錄了該活動圖的結(jié)構(gòu)等信息。通過使用高級程序語言對XMI文件的解析達(dá)到解析UML活動圖結(jié)構(gòu)的目的。同時，對于UML圖形化部分，通過解析UML格式文件來實現(xiàn)。其中記錄了UML活動圖中各個元素的大小、顏色、位置等圖形化的相關(guān)信息，可以利用來構(gòu)造一個對應(yīng)的活動圖。3、本文以一種新的方式來看待UML活動圖，不僅僅將它看作是一個描述業(yè)務(wù)和活動的工作流程圖，還將它看作是一個順序執(zhí)行的程序。通過在程序中將它抽象成數(shù)據(jù)結(jié)構(gòu)中的圖，并解析成為抽象語法樹，利用函數(shù)內(nèi)調(diào)試的形

6、式化算法，實現(xiàn)了錯誤的定位。關(guān)鍵詞：UML活動圖，錯誤定位，XMI解析，XML Bug Locating Tool for UML Activity Diagram ModelsAuthor：Tutor：AbstractThese days, with the size and complexity of a variety of systems and software increasing rapidly, the model-driven technology is widely used in the construction of the system, the static and

7、 dynamic behavior characterization and analysis and other aspects. Among these, the Unified Modeling Language (UML), which use the object-oriented modeling as the dominant ideology, has been widely used. So it would benefit a lot, when you can locate bugs in the period of modeling. With computer sof

8、tware being applied in various fields as well as the expansion of software scale, the thought of software engineering has been further used in the software development process. Research shows that, 70% of software development errors in the software engineering life cycle are introduced in the early

9、period (ie, errors were introduced into the system in period of the design of the model); while nearly 80% of errors in the system were located in the last period of the software developing process. So, as we can see, it would cost more time and money to fix these bugs.The work and technical content

10、 of this paper are as follows:1. Applying Intral-function automatic debugging error localization algorithm, which is based on the C-Kernal language, to the UML model. 2. Presenting a new method to analyze the UML activity diagram, namely by parsing the UML standard export file called XMI. In XMI for

11、mat file, there are a lot of regular labels which are already defined. These labels regularly record the structure and other information of the activity diagram. By using advanced programming language, we can parse the XMI file in order to achieve the aim of analyzing UML activity diagram structure.

12、 Meanwhile, as for the UML graphical part, we can solve the problem in order to analyzing the UML format files. UML format file, which is similar to the XMI format file, using the Extensible Markup Language (XML), but it also records the various elements of UML activity, such as diagram size, color,

13、 position, and other graphical information which can be used to construct a corresponding activity diagram.3. In this paper, we use a new way to treat the UML activity diagrams, not only will it be seen as a description of the operations and activities of the work flow, but also will it be seen as a

14、 sequential process. In the program, it will be abstracted into a map in data and structure, also resolve it to a code segment, locating the bugs.Key words：UML activity diagrams, fault location, XMI parsing, XML目 錄1 緒論11.1 課題來源11.2 研究背景與意義11.3 國內(nèi)外研究現(xiàn)狀21.3.1 UML模型的一致性檢查21.3.2 模型檢查21.3.3 UML測試調(diào)試工具31.3

15、.4 小結(jié)31.4 研究內(nèi)容與解決方案31.4.1 UML活動圖的處理31.4.2 錯誤定位算法31.4.3 解決方案41.5 論文組織架構(gòu)42 相關(guān)技術(shù)和算法62.1 UML活動圖的解析62.1.1 XMI格式文件的解析62.1.2 UML格式文件的解析62.2 C+和C#混合開發(fā)相關(guān)技術(shù)72.2.1 C+編寫外部文件讀取以及活動圖解析的部分72.2.2 C#編寫界面72.2.3 多項目混合開發(fā)的解決方案82.3 錯誤定位算法83 錯誤定位工具的設(shè)計與實現(xiàn)103.1 系統(tǒng)開發(fā)環(huán)境103.2 系統(tǒng)整體設(shè)計103.3 讀取解析XMI格式和UML格式文件113.3.1 讀取解析XMI格式文件123

16、.3.2 讀取解析UML格式文件153.4 活動圖的解析163.4.1 循環(huán)的檢查判定193.4.2 詞法分析203.4.3 語法分析203.4.4 生成中間結(jié)構(gòu)243.5 錯誤定位253.6 GUI設(shè)計264 錯誤定位工具運(yùn)行結(jié)果展示274.1 系統(tǒng)運(yùn)行環(huán)境274.2 系統(tǒng)運(yùn)行結(jié)果27總結(jié)與展望35總結(jié)35展望35致謝37參考文獻(xiàn)391 緒論1.1 課題來源本課課題來源于實驗室在軟件的自動化調(diào)試方面的科學(xué)研究。1.2 研究背景與意義軟件工程是研究和應(yīng)用如何以系統(tǒng)性的、規(guī)范化的、可定量的過程化方法去開發(fā)和維護(hù)軟件，以及如何把經(jīng)過時間考驗而證明正確的管理技術(shù)和當(dāng)前能夠得到的最好的技術(shù)方法結(jié)合起來

17、1。眾所周知，軟件工程主要包括了需求獲取、項目策劃、建模分析設(shè)計、編碼、測試以及部署交付等過程。研究成果表明，70%的錯誤是在軟件工程生命周期中的早期被引入（即在模型設(shè)計階段中引入）；而錯誤中的80%只有到了系統(tǒng)開發(fā)后期的測試階段之后才被發(fā)現(xiàn)2，因此錯誤的修改成本大大增加?；萜?、IBM、以及其他組織的研究人員發(fā)現(xiàn)，在構(gòu)建軟件模型階段清除一個錯誤，其成本僅僅是在開發(fā)過程的最后階段做同樣事情的十分之一到百分之一34。因此針對于設(shè)計模型的錯誤檢查研究，有著非常重要的意義，可以大大降低錯誤檢查的成本，有效保障軟件質(zhì)量5。目前，隨著各種系統(tǒng)和軟件的規(guī)模與復(fù)雜度增加，模型驅(qū)動技術(shù)被廣泛的應(yīng)用于系統(tǒng)的構(gòu)建、

18、靜態(tài)和動態(tài)行為刻畫與分析等方面，模型作為對系統(tǒng)行為的刻畫發(fā)揮著越來越重要的作用。統(tǒng)一建模語言（UML）是一種面向?qū)ο蟮慕ＵZ言，它是運(yùn)用統(tǒng)一的、標(biāo)準(zhǔn)化的標(biāo)記和定義實現(xiàn)對軟件系統(tǒng)進(jìn)行面向?qū)ο蟮拿枋龊徒?。它作為一種描述能力強(qiáng)大、涵義直觀且被工業(yè)界廣泛使用的可視化建模語言，提供了多種圖形元素，從靜態(tài)結(jié)構(gòu)和動態(tài)行為等多角度及不同層次刻畫系統(tǒng)特征和運(yùn)行環(huán)境6。統(tǒng)一建模語言（UML），它的目標(biāo)是用面向?qū)ο蟮乃枷雭砻枋鱿到y(tǒng)，因此它具有很廣的應(yīng)用領(lǐng)域。在建立軟件系統(tǒng)的模型這一環(huán)節(jié)，它得到了很多的應(yīng)用，同時UML也可以用于描述各種非軟件領(lǐng)域的系統(tǒng)，如：企業(yè)機(jī)構(gòu)、機(jī)械系統(tǒng)以及業(yè)務(wù)過程等等。此外，對于處理復(fù)雜數(shù)據(jù)

19、的信息系統(tǒng)、對于實時要求很高的工業(yè)系統(tǒng)，都有很好的應(yīng)用。所以，UML是一個通用的建模標(biāo)準(zhǔn)，可以對任何具有靜態(tài)結(jié)構(gòu)和動態(tài)行為的系統(tǒng)進(jìn)行建模。活動圖是UML2.0中動態(tài)行為建模中的重要模型之一，可以對系統(tǒng)功能過程實現(xiàn)進(jìn)行刻畫，是一種流程刻畫的圖形建模語言，它結(jié)合了Jim Odell的事件圖、SDL(規(guī)約和描述語言)狀態(tài)建模技術(shù)、工作流建模以及Petri網(wǎng)等?；顒訄D的應(yīng)用領(lǐng)域廣泛，且可以對于不同層次的過程模型進(jìn)行刻畫，包括對于工作流建模、執(zhí)行算法建模以及代碼層次模型等4。隨著活動圖在系統(tǒng)建模中的應(yīng)用越來越多，活動圖模型的正確性檢測與錯誤定位也為復(fù)雜系統(tǒng)的錯誤檢查和定位提供了一種方式，即利用活動圖作為

20、系統(tǒng)功能的過程模型，結(jié)合實際觀測或者需求期望來判定該模型是否存在錯誤。選題具有一定的意義。如果能在建模階段就自動化的查找包括語法和語義的錯誤（bug），那么我們就可以大量的減少在后期編程階段或者測試階段再次發(fā)現(xiàn)錯誤所需要的工作量并減輕修改這些錯誤所需要的精力財力和物力。1.3 國內(nèi)外研究現(xiàn)狀統(tǒng)一建模語言（UML）作為一種描述能力強(qiáng)大、涵義直觀且被工業(yè)界廣泛使用的可視化建模語言，提供了多種圖形元素，從靜態(tài)結(jié)構(gòu)和動態(tài)行為等多角度及不同層次刻畫系統(tǒng)特征和運(yùn)行環(huán)境。當(dāng)前針對于UML錯誤檢查的相關(guān)研究主要集中在UML一致性研究、基于模型檢查技術(shù)的UML 模型錯誤檢查以及UML測試調(diào)試工具。1.3.1 U

21、ML模型的一致性檢查UML模型的一致性檢查是最常見的錯誤檢查，它包含了語法檢查和語義檢查等，對于語法檢查是將模型看作一組相互關(guān)聯(lián)的元素，通過把元素之間的關(guān)系限定到一定模式，防止模型中產(chǎn)生某些類型的矛盾，這類方法的基本特征是以模型的語法結(jié)構(gòu)為基礎(chǔ)，定義元素之間的一致性約束。通常利用模型間語法結(jié)構(gòu)等建立一致性約束，進(jìn)一步執(zhí)行模型檢查。語義檢查則通過形式化語義模型，包括進(jìn)程代數(shù)、Petri網(wǎng)、R-演算等理論，實現(xiàn)語義層面一致性的判定78。1.3.2 模型檢查針對于UML的模型檢查，通常的方式是將UML模型轉(zhuǎn)化為常用的模型檢查工具輸入模型，并建立屬性檢查期望。模型檢查是針對于UML模型錯誤檢查中最常見

22、、也是應(yīng)用最廣泛的，通常將UML模型轉(zhuǎn)化為SMV9、SPIN等主流的模型檢查工具所支持的中間語言10，然后利用模型檢查工具，來判定UML模型是否滿足指定的性質(zhì)。模型檢查主要用于檢查功能屬性，例如無死鎖性、活性、安全性等，缺點(diǎn)除了狀態(tài)空間爆炸問題外，對于檢查過程的推理過程缺乏直觀的刻畫，對于度量模型不統(tǒng)一的檢驗無法有效處理。1.3.3 UML測試調(diào)試工具UML能夠允許開發(fā)者在一個較高的抽象層次，利用活動圖、狀態(tài)機(jī)和順序圖等來對系統(tǒng)行為進(jìn)行描述。為了進(jìn)一步便于模型驅(qū)動開發(fā)，開發(fā)者需要增加對于UML模型的調(diào)試和測試。UML測試調(diào)試工具則是在UML建模環(huán)境中，實現(xiàn)針對于模型的虛擬執(zhí)行環(huán)境，加入測試和調(diào)

23、試的功能, 常見的工具如IBM在以色列的Haifa研究室提供的Model debugger，基于Eclipse的代碼調(diào)試器，提供了相似的視圖：調(diào)試、變量和斷點(diǎn)1112。1.3.4 小結(jié)通過以上的總結(jié)，我們可以發(fā)現(xiàn)，目前主流的幾種UML錯誤檢查的方法都各自存在優(yōu)缺點(diǎn)。UML模型的一致性檢查多用于進(jìn)行語法的檢測；而模型檢查主要用于檢查功能屬性，對于檢查過程的推理過程缺乏直觀的刻畫，對于度量模型不統(tǒng)一的檢驗無法有效處理；UML測試調(diào)試工具則主要是針對于人工的手動調(diào)試13。選題則是主要針對于語義錯誤的自動化檢測和定位，通過對實際運(yùn)行狀態(tài)和期望狀態(tài)的比較來進(jìn)行進(jìn)一步的相對精確的錯誤定位。1.4 研究內(nèi)容

24、與解決方案1.4.1 UML活動圖的處理UML活動圖中有許多的元素和對象包括了：活動、狀態(tài)、轉(zhuǎn)移（動作流）、分支與合并、分叉與匯合以及泳道等等。在這里我們主要討論的是比較簡單的活動圖（只含有活動、狀態(tài)、轉(zhuǎn)移、分支與合并）以及怎樣讀入一個UML文件，并怎么樣對這個文件進(jìn)行操作，讀取出其中的元素和對象，供下一步的使用。1.4.2 錯誤定位算法如果要在一個UML活動圖中進(jìn)行錯誤的定位，那么就必須要有一個高效的錯誤定位算法。目前我們已經(jīng)有了一個形式化錯誤定位算法，但是這個算法的提出是針對于所C-kernel語言，它是C語言的一個子集，這一語言所有變量和常量都是整型的1415。而我們的研究的對象是UML

25、活動圖，這其中有很多不同之處，面向的對象從一個程序段變成了一個圖形化的活動圖。那么我們就需要對讀取出來的UML活動圖元素對象以及錯誤定位算法進(jìn)行進(jìn)一步的修改和轉(zhuǎn)化，從而能夠使我們的研究對象適應(yīng)這個成型的算法。1.4.3 解決方案首先，對于UML活動圖的讀取，我們可以使用starUML的export功能將活動圖導(dǎo)出成XMI格式或者使用可以直接操作UML的庫。然而XMI的優(yōu)點(diǎn)是使用擴(kuò)展標(biāo)記語言（XML），因為其中包含了豐富而有規(guī)律的標(biāo)簽，因此XML語言為程序員提供了一種數(shù)據(jù)信息交換的標(biāo)準(zhǔn)方法。XMI的目的在于幫助使用UML以及不同語言和開發(fā)工具的程序員彼此交換數(shù)據(jù)模型。正如我們都知道的，XML格式

26、的文件中，定義了很有規(guī)律的標(biāo)簽，我們可以用高級程序語言（如C+）對XML文件進(jìn)行操作，從而得到了系統(tǒng)的活動圖的結(jié)構(gòu)，從而進(jìn)行下一步的基于XML結(jié)構(gòu)化的形式化的文件的操作16。接著，我們將對象元素使用高級程序語言轉(zhuǎn)換成錯誤定位算法所需要的格式從而進(jìn)行下一步的操作。這其中，從UML活動圖中讀取的結(jié)構(gòu)可以對應(yīng)到編程語言中的某些結(jié)構(gòu)，比如：UML活動圖中的活動就可以看成普通的順序執(zhí)行的操作語句；UML活動圖中的分支與合并就可以轉(zhuǎn)換成編程語言中的判定、循環(huán)等等。最后，對于語義錯誤的檢測和定位，我們將使用課題組提出的函數(shù)內(nèi)調(diào)試的形式化錯誤定位算法。這個算法的提出是針對于C-kernel語言，它是C語言的一

27、個子集，這一語言所有變量和常量都是整型的而且沒有復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。所以我們需要將活動圖轉(zhuǎn)換成的XMI中的元素的格式更改并對算法進(jìn)行適當(dāng)?shù)恼{(diào)整，使雙方能夠進(jìn)行匹配，從而能夠使用這個成型的定位算法完成錯誤的定位。1.5 論文組織架構(gòu)本文的核心在于研究、設(shè)計及實現(xiàn)UML活動圖模型中錯誤的定位工具。首先，分析國內(nèi)外研究和相關(guān)技術(shù)的優(yōu)缺點(diǎn)。接著，設(shè)計系統(tǒng)整體框架并詳細(xì)討論系統(tǒng)中每一模塊的關(guān)鍵技術(shù)和核心功能的設(shè)計方案與具體實施。最后，展示系統(tǒng)運(yùn)行成果并致謝。論文組織結(jié)構(gòu)如下：第一章，介紹課題的研究背景及意義，明確本文的研究目標(biāo)和主要工作內(nèi)容，并對目前的研究現(xiàn)狀進(jìn)行介紹。第二章，分析系統(tǒng)中所用到的幾項主要技術(shù)

28、和相關(guān)算法。首先介紹使用高級程序設(shè)計語言解析UML活動圖的技術(shù)，隨后簡要介紹一下C+和C#編程的知識，最后介紹錯誤定位的算法。第三章，根據(jù)課題研究目標(biāo)，提出系統(tǒng)的設(shè)計原則，并設(shè)計系統(tǒng)的整體框架結(jié)構(gòu)。對于每一個部分，詳細(xì)說明具體的設(shè)計思路、數(shù)據(jù)結(jié)構(gòu)以及實現(xiàn)細(xì)節(jié)，并介紹每一部分的關(guān)鍵技術(shù)。第四章，在各個部分都完成的基礎(chǔ)上，展示系統(tǒng)在相應(yīng)環(huán)境下的運(yùn)行情況。第五章，總結(jié)論文的主要工作。2 相關(guān)技術(shù)和算法本文的主要研究內(nèi)容是設(shè)計并實現(xiàn)UML活動圖模型中錯誤的定位工具。本章中將分別針對系統(tǒng)設(shè)計和系統(tǒng)實現(xiàn)過程中的相關(guān)技術(shù)、算法和概念展開介紹。22.1 UML活動圖的解析UML活動圖是UML建模中行為圖中的一

29、種，它主要描述系統(tǒng)的動態(tài)模型和組成對象間的交互關(guān)系，它對于系統(tǒng)的功能建模特別重要，強(qiáng)調(diào)對象間的控制流程。2.1.1 XMI格式文件的解析通過使用軟件starUML的export功能，可以將UML活動圖導(dǎo)出成XMI格式。XMI格式的文件是UML的標(biāo)準(zhǔn)導(dǎo)出和操作文件。同時，XMI使用了擴(kuò)展標(biāo)記語言（XML），為程序員和其它用戶提供元數(shù)據(jù)信息交換的標(biāo)準(zhǔn)方法。因此，我們可以使用高級程序語言（如C+和JAVA等）對于XMI格式的文件進(jìn)行操作。同時，通過分析導(dǎo)出的XMI文件，可以發(fā)現(xiàn)它定義了關(guān)于一張UML活動圖整體結(jié)構(gòu)的信息，包括了所有元素的個數(shù)、每個元素的類型（活動、轉(zhuǎn)移、選擇、開始節(jié)點(diǎn)、結(jié)束節(jié)點(diǎn)等等）

30、、每個轉(zhuǎn)移的條件以及各個元素之間的關(guān)系，比如：活動A和哪個轉(zhuǎn)移相連；轉(zhuǎn)移B從哪個活動指向哪個活動等等。這些就是我們分析一張UML活動圖的重要信息，通過對這些信息的提取，可以將一個抽象的活動圖整理成一個順序執(zhí)行的程序段，從而進(jìn)行錯誤的定位。2.1.2 UML格式文件的解析UML格式的文件也是我們進(jìn)行錯誤定位要處理的一個文件。與XMI文件相似，UML格式的文件也是使用擴(kuò)展標(biāo)記語言（XML）編寫的，這就可以通過高級程序語言進(jìn)行分析了。與XMI文件有所不同的是，UML格式的文件其中記錄的信息不是活動圖的整體結(jié)構(gòu)，而是關(guān)于一張活動圖的圖形化的信息。其中記錄了關(guān)于活動圖中每一個元素的位置（基于左上角的橫縱

31、坐標(biāo)像素值）、每一個轉(zhuǎn)移流的直線或折線的位置信息以及每個元素的大小顏色等等。這些信息都是有助于我們后期在圖形界面上進(jìn)行錯誤定位的操作。對于XMI格式和UML格式的文件中元素的解析和讀取，我們選擇了TinyXML這個基于C+的XML解析器。TinyXML是一個開源的解析XML的解析庫，能夠在Windows或Linux中編譯。它簡單易用且小巧玲瓏，非常適合存儲簡單數(shù)據(jù)，并且支持對XML的讀取和修改。這個解析庫的模型通過解析XML文件，然后在內(nèi)存中生成DOM模型，從而讓用戶很方便的遍歷整棵XML樹。DOM模型即文檔對象模型，是將整個文檔分成多個元素（如書、章、節(jié)、段等），并利用樹型結(jié)構(gòu)表示這些元素之

32、間的順序關(guān)系以及嵌套包含關(guān)系。從開源中國社區(qū)上下載得到TinyXML的項目，配置時只需要通過將tinystr.cpp，tinyxml.cpp，tinyxmlerror.cpp，tinyxmlparser.cpp，tinyxml.h，tinystr.h這六個文件導(dǎo)入到我們的項目中，就可以調(diào)用其中的API來對XML文件進(jìn)行讀取解析。2.2 C+和C#混合開發(fā)相關(guān)技術(shù)本項目采用C+和C#混合開發(fā)。主要因為C+語言十分靈活方便，而且是面向?qū)ο笳Z言，而C#在GUI開發(fā)方面擁有很強(qiáng)的便利性。使用C#編寫系統(tǒng)的圖形界面非常方便，它的封裝性非常優(yōu)秀，既可用代碼來編寫界面也可以直接通過C#提供的拖拽控件的功能直

33、接編寫界面。我們的整體的思路是使用C+來編寫對于XML文件和UML文件的讀取和活動圖元素的解析部分的程序，而使用C#來編寫程序的界面相關(guān)部分的程序，界面部分調(diào)用解析部分的函數(shù)來完成系統(tǒng)的實現(xiàn)。2.2.1 C+編寫外部文件讀取以及活動圖解析的部分在對于外部文件的操作部分，使用C+語言來編寫相關(guān)的操作和處理程序。主要包括了：使用TinyXML對XMI文件和UML文件的讀取，將一個活動圖解析成一個順序執(zhí)行的程序段并轉(zhuǎn)換為抽象語法樹結(jié)構(gòu)等等。這些部分主要是使用C+語言來寫的，利用了它的面向?qū)ο筇匦?，可以寫出很多封裝的很好的自定義類來幫助完成。2.2.2 C#編寫界面在GUI部分，使用C#語言來完成界面

34、的繪制。這一部分主要是使用C#的設(shè)計界面，利用它的控件拖拽功能來完成繪制。其中利用到了其中的許多小的設(shè)計好的控件，比如：Form，Panel，DataGridView，TreeView，ToolTip等等。它們都是C#中已經(jīng)封裝好的十分便于使用的小組件，可以讓編程人員方便的實現(xiàn)自己的目的。2.2.3 多項目混合開發(fā)的解決方案在Visual Studio2012中，我們把整個系統(tǒng)稱為是一個解決方案，而這一個解決方案則可能含有多個小的項目，它們要互相調(diào)用內(nèi)部的函數(shù)和數(shù)據(jù)結(jié)構(gòu)，而且這些小的項目可能并不是一種編程語言寫成的（如：我們的解決方案中就是C+和C#）。因為這些項目之間存在著相互調(diào)用的關(guān)系，這

35、樣就需要在屬性中設(shè)置項目依賴項、啟動項目以及包含目錄等等，來確認(rèn)互相之間的調(diào)用關(guān)系，這樣在整個系統(tǒng)啟動的時候編譯器才能找到互相之間的調(diào)用關(guān)系一步步來編譯，才不至于報錯。其次，因為C#和C+并不是同一種語言，因此在C#編寫的界面中調(diào)用到C+編寫的函數(shù)的時候就要使用動態(tài)鏈接庫（Dynamic Link Library，簡寫為dll）。將C#中將要調(diào)用到的C+中的函數(shù)，用一系列語句和規(guī)定封裝成動態(tài)鏈接庫，在C#項目中通過使用DllImport語句來引入這些函數(shù)，從而實現(xiàn)混合項目之間函數(shù)的調(diào)用。這其中最重要的就是，這些函數(shù)的返回值和參數(shù)目前只允許是簡單的數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的（比如：int ，char，

36、char*，bool）否則就會報錯。2.3 錯誤定位算法選題的錯誤定位算法選擇函數(shù)內(nèi)調(diào)試的形式化錯誤定位算法1011，它在UML活動圖中應(yīng)用的基本思路是：當(dāng)活動圖測試出現(xiàn)了一個失敗的測試用例時，根據(jù)用戶預(yù)期的程序輸入和輸出，從活動圖中找出與用戶預(yù)期矛盾的極小片段，比如：幾個活動和轉(zhuǎn)移流組成的一個片段。若此片段仍然較大，則通過不斷的與用戶交互，讓用戶標(biāo)記其中正確的活動、轉(zhuǎn)移，或者讓用戶進(jìn)一步給出片段中變量在某些狀態(tài)下的預(yù)期值，利用這些新的信息縮小片段的范圍，直到最終定位到活動圖中的一個錯誤。在用戶將此錯誤修復(fù)之后，還需要在修改后的程序上重新運(yùn)行測試用例，進(jìn)行回歸測試。如果不存在失敗的測試用例，表

37、明程序通過了測試，之前的錯誤已經(jīng)修復(fù)；否則，則說明程序中還存在其他的錯誤，需要重復(fù)整個錯誤定位過程，一次一個的找到并修復(fù)錯誤。算法執(zhí)行的活動圖如下：圖2.1 錯誤定位算法的活動圖3 錯誤定位工具的設(shè)計與實現(xiàn)33.1 系統(tǒng)開發(fā)環(huán)境硬件配置：（1） 主機(jī)CPU： Intel(R) Core(TM)i5-2430M CPU 2.40GHz（2） 內(nèi)存：4.00GB 軟件配置：（1） 操作系統(tǒng)：Windows 7 旗艦版（2） 編譯器：Visual Studio 20123.2 系統(tǒng)整體設(shè)計圖3.1 錯誤定位工具的系統(tǒng)圖讀取解析XML文件：這一個模塊主要是負(fù)責(zé)是解析UML格式和XMI格式的文件。因為這

38、兩種格式的文件內(nèi)部都是使用擴(kuò)展標(biāo)記語言（XML）來編寫的，所以在這一模塊我們就使用TinyXML這個基于C+的XML解析器來對這兩個格式的文件進(jìn)行解析，并將整個活動圖抽象成一張圖，保存在一個類似于圖的鄰接矩陣的復(fù)雜二維數(shù)組中。這個鄰接矩陣則作為下一個模塊解析活動圖元素的輸入。解析活動圖元素：這一個模塊的輸入是基于上一個模塊的輸出，即讀取解析XML模塊的操作結(jié)果（一個圖的鄰接矩陣）。這一部分的操作類似于編譯的過程，有詞法分析、語法分析、語義分析（最后不需要生成目標(biāo)機(jī)代碼）。在最后，該模塊并不會生成對應(yīng)的目標(biāo)機(jī)代碼，而是生成一個抽象語法樹。這個抽象語法樹就是講整個活動圖解析后得到的中間結(jié)果，下一步

39、它將作為下一個模塊的輸入。定位錯誤：這一模塊就是實現(xiàn)了函數(shù)內(nèi)調(diào)試的形式化方法這個錯誤定位算法。具體思路是：當(dāng)活動圖測試出現(xiàn)了一個失敗的測試用例時，根據(jù)用戶預(yù)期的程序輸入和輸出，從活動圖中找出與用戶預(yù)期矛盾的極小片段，比如：幾個活動和轉(zhuǎn)移流組成的一個片段。若此片段仍然較大，則通過不斷的與用戶交互，讓用戶標(biāo)記其中正確的活動、轉(zhuǎn)移，或者讓用戶進(jìn)一步給出片段中變量在某些狀態(tài)下的預(yù)期值，利用這些新的信息縮小片段的范圍，直到最終定位到活動圖中的一個錯誤。3.3 讀取解析XMI格式和UML格式文件在我們的系統(tǒng)中，我們把一張UML活動圖看成是一個抽象的圖，主要的操作都集中在這張圖的鄰接矩陣當(dāng)中。這個二維數(shù)組鄰

40、接矩陣（Graph）中的每一個節(jié)點(diǎn)都是一個GraphPoint。這個鄰接矩陣與傳統(tǒng)的一張圖的鄰接矩陣并不完全相同，對于傳統(tǒng)的鄰接矩陣，它只是為了表示一張圖的節(jié)點(diǎn)與節(jié)點(diǎn)之間的連接關(guān)系，簡單化為一個二維整型數(shù)組，在數(shù)組中每一個位置（i , j）都代表了圖中節(jié)點(diǎn)i到節(jié)點(diǎn)j是否存在一條轉(zhuǎn)移的邊。而在我們這里，我們的鄰接矩陣復(fù)雜了不少，二維數(shù)組的每一個位置不僅僅代表圖中的節(jié)點(diǎn)i到節(jié)點(diǎn)j是否存在一條轉(zhuǎn)移，而且其中每一個節(jié)點(diǎn)都包含了很多屬性，涉及到節(jié)點(diǎn)i到節(jié)點(diǎn)j的轉(zhuǎn)移流的條件，以及該節(jié)點(diǎn)在活動圖中的位置等等。下面是關(guān)于GraphPoint類的詳細(xì)屬性介紹：表3.1 GraphPoint類的介紹屬性類型說明I

41、dString節(jié)點(diǎn)的唯一標(biāo)記符IDnameString節(jié)點(diǎn)在活動圖中顯示出的名字guidString節(jié)點(diǎn)在UML格式文件中的標(biāo)記符outInt節(jié)點(diǎn)i到節(jié)點(diǎn)j是否有一條邊即是否有轉(zhuǎn)移流leftInt關(guān)于該節(jié)點(diǎn)的在圖形化界面上對于界面左側(cè)的像素值topInt關(guān)于該節(jié)點(diǎn)的在圖形化界面上對于界面上方的像素值pointsString對于一個轉(zhuǎn)移流，它在圖形化界面上所有點(diǎn)的集合actionString節(jié)點(diǎn)中的“操作”typeGraphType 當(dāng)前節(jié)點(diǎn)的類型，包括了：START，ACTIVITY，CHOOSE，END這四個類型，分別代表開始節(jié)點(diǎn)，活動節(jié)點(diǎn)，選擇節(jié)點(diǎn)，結(jié)束節(jié)點(diǎn)guardString轉(zhuǎn)移流的條

42、件transitionIdString當(dāng)前轉(zhuǎn)移流的ID3.3.1 讀取解析XMI格式文件對于UML活動圖的讀取，我們可以使用starUML的export功能將活動圖導(dǎo)出成XMI格式。XMI格式的文件的優(yōu)點(diǎn)是使用擴(kuò)展標(biāo)記語言（XML）。正如我們所知的，XML格式的文件中，定義了很有規(guī)律的標(biāo)簽，我們可以用高級程序語言（如C+）對XML文件進(jìn)行操作。對于活動圖中的活動：name屬性表示該活動的名稱。outgoing和incoming屬性表示從這個活動出去的“轉(zhuǎn)移”的id和進(jìn)入這個活動的“轉(zhuǎn)移”的id。此外，可以在活動中加入操作，它是活動中執(zhí)行的更小的更詳細(xì)的步驟。分別在以下時刻可以產(chǎn)生操作，為某些變

43、量進(jìn)行賦值：在進(jìn)入活動時發(fā)生的操作：entry；在活動進(jìn)行時發(fā)生的操作：do；在離開活動時發(fā)生的操作：exit；這幾個標(biāo)簽嵌套于該ActionState標(biāo)簽之中：進(jìn)入活動時發(fā)生的操作：在離開活動時發(fā)生的操作：在活動進(jìn)行時發(fā)生的操作： name屬性表示該操作的行為，由用戶定義。對于活動圖中的轉(zhuǎn)移：name屬性表示轉(zhuǎn)移的名字。source和target屬性分別表示源動作和目的動作。這其中還可以嵌套一個子標(biāo)簽，用來表示該轉(zhuǎn)移所需要的條件。對于活動圖中的分支與合并，它們的排列組合就類似于高級程序語言的條件選擇語句和各種循環(huán)語句：這其中屬性的意義同上，kind屬性為“branch”表示是分支合并。這一部

44、分的工作我們主要是使用了網(wǎng)絡(luò)上開源的基于C+語言的XML文件解析器tinyXML。調(diào)用其中的API，完成了XMI文件的解析，然后將讀取出來的數(shù)據(jù)存入我們自定義的數(shù)據(jù)結(jié)構(gòu)Graph之中。雖然整個UML活動圖是一個順序執(zhí)行的過程，但是我們把它抽象成一個圖，我們利用這個圖的鄰接矩陣來對它進(jìn)行解析，判斷是否存在環(huán)路也就是while循環(huán)等等，并為下一步對它進(jìn)行解析生成一棵抽象語法樹做準(zhǔn)備工作。在程序中，所有的操作封裝在函數(shù)SolveXMI(string filePath)之中，通過讀入XMI文件的路徑，從而獲取這個文件。它的解析過程大概是：首先通過語句TiXmlDocument doc(filePath

45、.c_str()函數(shù)和doc.LoadFile()函數(shù)得到操作XML文件的句柄，然后獲取第一個element節(jié)點(diǎn)，循環(huán)調(diào)用FirstChildElement()函數(shù)來獲得子節(jié)點(diǎn)并循環(huán)調(diào)用NextSiblingElement()函數(shù)獲得同一級的下一個標(biāo)簽。當(dāng)找到對應(yīng)的標(biāo)簽項的時候，我們調(diào)用Attribute()來獲取屬性的值，接著保存到我們的自定義結(jié)構(gòu)當(dāng)中。這其中，首先取得標(biāo)簽的名字來判斷節(jié)點(diǎn)的類型，并保存在節(jié)點(diǎn)的type屬性中；接著取得xmi.id的屬性值，保存在Id中；取得name的屬性值，保存在name中。下面來保存轉(zhuǎn)移的屬性，與上面稍有不同的是，在取得到了source和target屬性值

46、之后，要在鄰接矩陣中遍歷，找到對應(yīng)的節(jié)點(diǎn)，然后取得body屬性值，保存在轉(zhuǎn)移的guard中；取得xmi.id的屬性值，保存在transitionId中；最后把對應(yīng)節(jié)點(diǎn)的out值賦值為1，代表從節(jié)點(diǎn)i到節(jié)點(diǎn)j有一條轉(zhuǎn)移流。在鄰接矩陣當(dāng)中，我們只把關(guān)于節(jié)點(diǎn)本身的屬性值（如Id，name等）保存在每行的第一個節(jié)點(diǎn)中，而關(guān)于轉(zhuǎn)移的屬性（如guard，points，out等）就保存在對應(yīng)的第i行第j列的對應(yīng)節(jié)點(diǎn)中。我們解析XMI文件的順序如下：圖3.2 XMI文件解析順序3.3.2 讀取解析UML格式文件為了使得界面美觀簡潔，我們需要從UML格式的文件中提取一些信息，在制作界面的時候使用。從UML格式的

47、文件中，我們可以提取到每一個元素（活動，狀態(tài)，選擇以及轉(zhuǎn)移流）的位置信息、大小信息等等，用于我們在界面上重新繪制出一張UML活動圖。所有的相關(guān)操作都封裝在函數(shù)SolveUML(string filePath)之中。與SolveXMI(string filePath)類似，filePath也保存了對應(yīng)的UML文件的路徑，這樣就可以直接讀取到文件。在后期的操作中，我們選擇將UML格式的文件和對應(yīng)的XMI格式的文件放在同一個文件夾下，名字也相同，這樣我們只用選中一個文件另一個就通過操作來取得。大體來講，獲得XML文件句柄、取得根節(jié)點(diǎn)以及循環(huán)遍歷的過程與對于XMI的操作類似。不同的是，取得guid的屬

48、性值，保存在對應(yīng)節(jié)點(diǎn)的guid之中；取得top屬性值，保存在對應(yīng)節(jié)點(diǎn)的top之中；取得left屬性值，保存在對應(yīng)節(jié)點(diǎn)的left之中；對于轉(zhuǎn)移流，我們需要取得它的head屬性值和tail屬性值，在鄰接矩陣當(dāng)中遍歷一遍，找到對應(yīng)位置的節(jié)點(diǎn)，然后保存相關(guān)信息比如取得points的屬性值，保存在points之中。通過上一步和這一步的解析，我們充分的利用了UML文件和XMI文件中的信息，填好了圖的鄰接矩陣二維數(shù)組，這對我們下一步進(jìn)行整個圖的解析和結(jié)構(gòu)轉(zhuǎn)換是非常重要的。我們解析UML格式文件的順序如下：圖3.3 UML文件的解析順序3.4 活動圖的解析一張UML活動圖類似于一個順序執(zhí)行的程序，其中也有各種

49、的聲明語句、賦值語句等等，這些語句都包含在每個活動或者選擇的“操作”之中。同時，活動圖中的各種結(jié)構(gòu)也可以理解為高級程序設(shè)計語言程序中的if語句和while語句。因為其中包含了循環(huán)語句，因此我把它理解為一張圖，對這個圖的近似的鄰接矩陣進(jìn)行操作，從而解析出其中存在的各種結(jié)構(gòu)。圖中的每一個節(jié)點(diǎn)使用我們定義的類GraphPoint，其中包含了當(dāng)前節(jié)點(diǎn)的名字、操作、種類、ID等等，它的一個二維數(shù)組Graph就是我們操作對象。我們用Graphij的out屬性來判斷當(dāng)前i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)是否有邊，也就是是否可以從i節(jié)點(diǎn)執(zhí)行到j(luò)節(jié)點(diǎn)。每個節(jié)點(diǎn)的屬性type就是用來表示當(dāng)前的節(jié)點(diǎn)的種類，它包括了：活動、選擇、轉(zhuǎn)移、

50、起始節(jié)點(diǎn)、終結(jié)節(jié)點(diǎn)，方便我們的操作。表3.2 AstNode類的介紹屬性類型說明atAstType代表了這個葉節(jié)點(diǎn)的類型，包括了：ASTINT，ASTVAR，ASTBO，ASTUO。分別代表了：整型常數(shù)，變量，雙目操作符以及彈幕操作符。AstNode類是一個父類，它代表了所有抽象語法樹葉節(jié)點(diǎn)。由于它的屬性at代表了不同葉節(jié)點(diǎn)的類型。因此，我們還設(shè)立了對應(yīng)的子類：AstInteger，AstVariable，AstBinaryOperator以及AstUnaryOperator。這些子類都繼承于父類AstNode，各自都擁有各自的不同的屬性，在后面的抽象語法樹中它們構(gòu)成了葉子節(jié)點(diǎn)。在進(jìn)行活動圖解

51、析和生成中間鏈表結(jié)構(gòu)的過程中，我們需要生成一個類似的抽象語法樹，那么每一個語句中變量、常量、表達(dá)式等等都可以需要生成一個對應(yīng)的抽象語法樹節(jié)點(diǎn)。而在程序中，我們會對應(yīng)的生成一個AstNode類型的數(shù)組，更加方便進(jìn)行插入操作和前后的遍歷查找操作等。表3.3 FlowNode類的介紹屬性類型說明lineNoInt該抽象語法樹節(jié)點(diǎn)所對應(yīng)的活動圖中的活動或者選擇在Graph中所在的行號pointNumInt該抽象語法樹節(jié)點(diǎn)所對應(yīng)的活動圖中的活動或者選擇在Graph中所在的行號typeFlowType它的類型，包括了：F_ASSIGN， F_IF， F_WHILE， F_COMP，F(xiàn)_DECLARE。它們

52、分別代表了賦值語句、if-else語句、while循環(huán)語句、block程序塊以及聲明語句astTreeAstNode指針?biāo)砹艘粋€FlowNode節(jié)點(diǎn)下面所包含的一顆抽象語法樹nextFlowNode指針FlowNode類型的指針，代表了本節(jié)點(diǎn)之后的節(jié)點(diǎn)lastFlowNode指針FlowNode類型的指針，代表了本節(jié)點(diǎn)之前的接待你IdString該抽象語法樹節(jié)點(diǎn)所對應(yīng)的活動圖中的活動或者選擇的唯一標(biāo)示符同AstNode類相似，F(xiàn)lowNode類也是一個父類，它代表了抽象語法樹中上層的一些結(jié)構(gòu)體，如：if-else語句、while語句、賦值語句等等。因為屬性type代表了不同的FlowNod

53、e類型，因此還包含了很多子類：FlowAssign，F(xiàn)lowIF，F(xiàn)lowWhile，F(xiàn)lowCompound以及FlowDeclare。在進(jìn)行活動圖解析和生成中間鏈表結(jié)構(gòu)的過程中，我們需要生成一個類似的抽象語法樹，每一個語句，包括：定義語句、賦值語句、if語句、while語句等等都要生成成這種結(jié)構(gòu)的抽象語法樹節(jié)點(diǎn)。在程序中，對應(yīng)的我們會生成一個FlowNode類型的數(shù)組，更加方便進(jìn)行插入操作和前后的遍歷查找操作等。3.4.1 循環(huán)的檢查判定在一張UML活動圖當(dāng)中，一個選擇可能是一個if-else語句的開端，也可能是一個do-while語句，如果不是直接從圖上看是很難區(qū)分的。現(xiàn)在，將活動圖保存

54、在一張圖中，問題就轉(zhuǎn)化成了判斷一張圖中是否存在循環(huán)。在程序中，使用深度優(yōu)先搜索（Depth First Search簡稱DFS）來對整個圖進(jìn)行遍歷查找是否存在循環(huán)。我們把所有的操作封裝在findCircle()這個函數(shù)之中，它對于每一個節(jié)點(diǎn)都調(diào)用函數(shù)DFS(int start,int now,int count）來進(jìn)行遞歸的深度優(yōu)先搜索來發(fā)現(xiàn)循環(huán)。這其中，我們使用了整型數(shù)組occupied來判斷每個節(jié)點(diǎn)是否已經(jīng)被遍歷過，如果被遍歷過則置1，初始為0。從一個節(jié)點(diǎn)開始，開始對與這個節(jié)點(diǎn)之間存在轉(zhuǎn)移流的節(jié)點(diǎn)進(jìn)行遍歷，直到遍歷到和該節(jié)點(diǎn)相同的節(jié)點(diǎn)，表示找到了一個循環(huán)，記錄在circle數(shù)組中，否則不存在循環(huán)。其中，我們加入了幾個剪枝函數(shù)，來減少搜索無用的路徑。包括：如果下一個節(jié)點(diǎn)已經(jīng)被遍歷過，就不遍歷它。最后，當(dāng)所有的節(jié)點(diǎn)都找尋了