UML活動(dòng)圖模型中錯(cuò)誤的定位工具說(shuō)明書

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

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

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

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

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

6、式化算法，實(shí)現(xiàn)了錯(cuò)誤的定位。關(guān)鍵詞：UML活動(dòng)圖，錯(cuò)誤定位，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 課題來(lái)源11.2 研究背景與意義11.3 國(guó)內(nèi)外研究現(xiàn)狀21.3.1 UML模型的一致性檢查21.3.2 模型檢查21.3.3 UML測(cè)試調(diào)試工具31.3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、明程序通過(guò)了測(cè)試，之前的錯(cuò)誤已經(jīng)修復(fù)；否則，則說(shuō)明程序中還存在其他的錯(cuò)誤，需要重復(fù)整個(gè)錯(cuò)誤定位過(guò)程，一次一個(gè)的找到并修復(fù)錯(cuò)誤。算法執(zhí)行的活動(dòng)圖如下：圖2.1 錯(cuò)誤定位算法的活動(dòng)圖3 錯(cuò)誤定位工具的設(shè)計(jì)與實(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è)計(jì)圖3.1 錯(cuò)誤定位工具的系統(tǒng)圖讀取解析XML文件：這一個(gè)模塊主要是負(fù)責(zé)是解析UML格式和XMI格式的文件。因?yàn)檫@

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

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

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

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

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

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

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

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

46、之后，要在鄰接矩陣中遍歷，找到對(duì)應(yīng)的節(jié)點(diǎn)，然后取得body屬性值，保存在轉(zhuǎn)移的guard中；取得xmi.id的屬性值，保存在transitionId中；最后把對(duì)應(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等）保存在每行的第一個(gè)節(jié)點(diǎn)中，而關(guān)于轉(zhuǎn)移的屬性（如guard，points，out等）就保存在對(duì)應(yīng)的第i行第j列的對(duì)應(yīng)節(jié)點(diǎn)中。我們解析XMI文件的順序如下：圖3.2 XMI文件解析順序3.3.2 讀取解析UML格式文件為了使得界面美觀簡(jiǎn)潔，我們需要從UML格式的文件中提取一些信息，在制作界面的時(shí)候使用。從UML格式的

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

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

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

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

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

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

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

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