一種從源程序代碼到標(biāo)準(zhǔn)流程圖的轉(zhuǎn)化方法

摘 要：流程圖可清晰、直觀地表示算法執(zhí)行流程和程序結(jié)構(gòu)，將程序源碼直接轉(zhuǎn)化成流程圖的方法多樣。流程圖結(jié)構(gòu)與程序源碼緊密相關(guān)，但目前缺乏將流程圖標(biāo)準(zhǔn)化的統(tǒng)一方法。因此提出一種將程序源代碼轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖的方法。首先參照ISO 5807：1985標(biāo)準(zhǔn)，定義標(biāo)準(zhǔn)化流程圖節(jié)點(diǎn)、邊類(lèi)型及其結(jié)構(gòu);然后提出將基于特定程序語(yǔ)言的流程圖轉(zhuǎn)換為標(biāo)準(zhǔn)化流程圖定義的方法;最后通過(guò)實(shí)例具體說(shuō)明該方法標(biāo)準(zhǔn)化規(guī)則。實(shí)驗(yàn)結(jié)果表明，該方法將源代碼轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖的操作行之有效。

關(guān)鍵詞：源程序代碼;流程圖;標(biāo)準(zhǔn)流程圖定義;流程圖標(biāo)準(zhǔn)化方法

DOI：10. 11907/rjdk. 182612

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）001-0065-04

Abstract： A flow chart clearly and intuitively represents the execution flow and program structure of the corresponding algorithm. Many methods and tools can directly convert the program source code into a flowchart， but the structure of the obtained flowchart is closely related to the program source code， and there is still no unified method to further standardize the flowchart. This paper presents a method for converting program source code into a standard flowchart. Firstly， by referring to the ISO 5807：1985 standard， the nodes， edge types and their structures of the standardized flowchart are defined. Then， the method of converting the flow chart based on the specific programming language into the standardized flowchart definition is given. Finally， the standardization rules of the method are specifically illustrated by examples. The results show that the method is effective to convert source code to standard flowchart.

0 引言

在軟件項(xiàng)目開(kāi)發(fā)過(guò)程中，程序流程圖是軟件開(kāi)發(fā)人員必不可少的工具。流程圖一般由平面圖節(jié)點(diǎn)、邊和文字標(biāo)號(hào)構(gòu)成，可以清晰地表示算法執(zhí)行流程和程序整體結(jié)構(gòu)。在很多復(fù)雜的程序設(shè)計(jì)過(guò)程中，通常先用流程圖描述算法整體思路，再依據(jù)流程圖編寫(xiě)出對(duì)應(yīng)的程序代碼。此外，在代碼分析中，流程圖可清晰地展示程序整體結(jié)構(gòu)，用它分析程序結(jié)構(gòu)遠(yuǎn)方便于直接分析源程序代碼本身[1]?，F(xiàn)有許多方法和工具可把程序源碼直接轉(zhuǎn)化成流程圖[2-5]。但是在實(shí)際工作中，利用現(xiàn)有工具得到的流程圖與源代碼緊密相關(guān)，有時(shí)將程序代碼轉(zhuǎn)換成流程圖的工作并不需要體現(xiàn)具體的代碼語(yǔ)句，為將流程圖進(jìn)一步標(biāo)準(zhǔn)化，也不僅局限于源程序代碼的具體內(nèi)容，目前還沒(méi)有一個(gè)統(tǒng)一的方法。

針對(duì)上述問(wèn)題，本文提出一種從源程序代碼到其流程圖的標(biāo)準(zhǔn)轉(zhuǎn)化方法，分別定義流程圖節(jié)點(diǎn)類(lèi)型和邊類(lèi)型，將節(jié)點(diǎn)、邊及結(jié)構(gòu)標(biāo)準(zhǔn)化后生成對(duì)應(yīng)的標(biāo)準(zhǔn)流程圖，并通過(guò)實(shí)例具體說(shuō)明該方法的轉(zhuǎn)化規(guī)則。

1 相關(guān)工作

理解一個(gè)源程序的首要任務(wù)是弄清其邏輯結(jié)構(gòu)，包括控制依賴結(jié)構(gòu)和數(shù)據(jù)依賴結(jié)構(gòu)。其中，程序控制依賴結(jié)構(gòu)包括程序整體結(jié)構(gòu)與控制流程結(jié)構(gòu)。程序整體結(jié)構(gòu)描述程序單位 （如過(guò)程、函數(shù)或子程序）間的調(diào)用關(guān)系及聯(lián)系信息，并以程序結(jié)構(gòu)樹(shù)的形式（即程序調(diào)用結(jié)構(gòu)圖或程序模塊圖）簡(jiǎn)單明確地刻畫(huà)其結(jié)構(gòu);控制流程結(jié)構(gòu)描述程序控制結(jié)構(gòu)傳遞和流向，并以程序流程圖的方式詳細(xì)刻畫(huà)程序單位結(jié)構(gòu)[6]。

流程圖用具有各種確定含義的符號(hào)、簡(jiǎn)潔的說(shuō)明文字和各種連線描述某一個(gè)問(wèn)題（或某一項(xiàng)工作）的定義、分析或解決方法，圖中各種符號(hào)表示操作、數(shù)據(jù)、流向等，被廣泛用于描繪各種類(lèi)型的信息處理問(wèn)題[7-10]。隨著計(jì)算機(jī)學(xué)科的迅速發(fā)展，流程圖在諸多領(lǐng)域得到廣泛應(yīng)用。

美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)（American National Standards Institute）規(guī)定了一些常用流程圖符號(hào)[11-14]，已被世界各國(guó)程序人員使用。文獻(xiàn)[8]介紹了通過(guò)流程圖表示一種算法執(zhí)行流程和程序整體結(jié)構(gòu)的方法。1973 年美國(guó)學(xué)者Nassi& Shneiderman提出一種不允許破壞結(jié)構(gòu)化構(gòu)造的工具，并以他們二人的名字命名，稱(chēng)為N-S結(jié)構(gòu)化流程圖，該圖去掉帶箭頭流程線，將全部算法寫(xiě)在一個(gè)矩形框內(nèi)，其基本元素也是一個(gè)框，可以包含其它從屬性元素。

2 標(biāo)準(zhǔn)轉(zhuǎn)化方法

2.1 標(biāo)準(zhǔn)流程圖定義

根據(jù)ISO 5807：1985標(biāo)準(zhǔn)[15]，流程圖一般由平面圖節(jié)點(diǎn)、邊和文字標(biāo)號(hào)構(gòu)成。本文對(duì)流程圖元素進(jìn)行綜合分析，從節(jié)點(diǎn)類(lèi)型、邊類(lèi)型和結(jié)構(gòu)類(lèi)型3方面進(jìn)行標(biāo)準(zhǔn)流程圖元素定義。

（1）節(jié)點(diǎn)類(lèi)型。程序流程圖表示程序操作順序[16]，程序代碼經(jīng)過(guò)轉(zhuǎn)換成為流程圖的節(jié)點(diǎn)和邊，一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一種類(lèi)型。本文在標(biāo)準(zhǔn)化流程圖節(jié)點(diǎn)、邊的基礎(chǔ)上，結(jié)合流程圖結(jié)構(gòu)，給出標(biāo)準(zhǔn)流程圖節(jié)點(diǎn)類(lèi)型，見(jiàn)表1。

（2）邊類(lèi)型。用戶可通過(guò)流程圖邊的走向了解工作具體流程，而邊是由控制依賴關(guān)系決定的，因此制定標(biāo)準(zhǔn)化流程圖時(shí)將邊分為兩種類(lèi)型：數(shù)據(jù)依賴邊（Data Dependency Edge，DDE）和控制依賴邊（Control Dependency Edge，CDE），見(jiàn)表2。針對(duì)兩種邊的性質(zhì)，本文給出如下定義：

定義1數(shù)據(jù)依賴邊：如果存在變量Var，則從程序節(jié)點(diǎn)V 1到V2存在數(shù)據(jù)依賴邊滿足：①可以通過(guò)指針直接或間接地將V1賦值給VAR;②V2可直接或間接通過(guò)指針使用VAR中的值;③程序中存在執(zhí)行路徑，從對(duì)應(yīng)于V1節(jié)點(diǎn)的代碼到對(duì)應(yīng)于V2節(jié)點(diǎn)的代碼，沿著該路徑?jīng)]有給變量Var任何賦值。

定義2控制依賴邊：如果條件的取值控制下一節(jié)點(diǎn)的執(zhí)行，則存在從control或loop節(jié)點(diǎn)到下一節(jié)點(diǎn)的控制依賴邊。

[邊類(lèi)型＼&邊描述＼&邊圖符＼&DDE＼&數(shù)據(jù)依賴邊＼&＼&CDE＼&控制依賴邊＼&＼&]

（3）結(jié)構(gòu)類(lèi)型。程序中循環(huán)結(jié)構(gòu)，如for循環(huán)、while循環(huán)、do-while循環(huán)等，在一定程度上均可實(shí)現(xiàn)相同功能，但是利用現(xiàn)有工具和方法生成的流程圖樣式卻不相同，表3列出了各種循環(huán)結(jié)構(gòu)利用現(xiàn)有工具生成的流程圖樣式和標(biāo)準(zhǔn)化后的結(jié)構(gòu)樣式。

由表3可以看出，3種不同循環(huán)結(jié)構(gòu)利用現(xiàn)有工具生成的流程圖樣式不同，在進(jìn)行標(biāo)準(zhǔn)化時(shí)，以for循環(huán)為參照，while和do-while循環(huán)統(tǒng)一轉(zhuǎn)化成與for循環(huán)結(jié)構(gòu)一樣的形式。

2.2 特定語(yǔ)言流程圖轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖的方法

將基于特定程序語(yǔ)言生成的流程圖轉(zhuǎn)換成標(biāo)準(zhǔn)流程圖時(shí)，需將基于特定程序語(yǔ)言的流程圖中的節(jié)點(diǎn)、邊和結(jié)構(gòu)對(duì)照標(biāo)準(zhǔn)流程圖定義進(jìn)行轉(zhuǎn)換，再合并相鄰?fù)N節(jié)點(diǎn)類(lèi)型無(wú)邏輯關(guān)系的節(jié)點(diǎn);為應(yīng)對(duì)代碼抄襲中的常用混淆手段，如多余的變量聲明、添加冗余代碼等，還需根據(jù)標(biāo)準(zhǔn)化流程圖進(jìn)一步生成主流程圖[17-20]。整個(gè)流程包括4個(gè)步驟：

（1）節(jié)點(diǎn)與邊標(biāo)準(zhǔn)化——映射。定義（映射）兩個(gè)非空集合A與B間存在對(duì)應(yīng)關(guān)系f，而且對(duì)于A中的每一個(gè)元素x，B中總有唯一元素y與之對(duì)應(yīng)，將這種對(duì)應(yīng)為從A到B的映射，記作f：A→B。

有時(shí)將程序代碼轉(zhuǎn)換成流程圖的工作無(wú)需體現(xiàn)具體的代碼語(yǔ)句，因此需要將節(jié)點(diǎn)和邊一一映射轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖中的節(jié)點(diǎn)和邊。將程序代碼轉(zhuǎn)換成對(duì)應(yīng)的流程圖，邊根據(jù)類(lèi)型定義相應(yīng)轉(zhuǎn)換成數(shù)據(jù)依賴邊和控制依賴邊。

（2）結(jié)構(gòu)標(biāo)準(zhǔn)化。如果兩段代碼使用不同類(lèi)型的循環(huán)結(jié)構(gòu)或相同循環(huán)結(jié)構(gòu)的不同形式，則流程圖中循環(huán)結(jié)構(gòu)也可能不同。如在圖3中，有的循環(huán)結(jié)構(gòu)在生成的流程圖中只體現(xiàn)判斷條件語(yǔ)句的節(jié)點(diǎn)，初始化語(yǔ)句和控制條件語(yǔ)句自動(dòng)省略，而有的循環(huán)一句對(duì)應(yīng)生成一個(gè)節(jié)點(diǎn)，不便于用戶利用流程圖理解程序的循環(huán)結(jié)構(gòu)。此時(shí)標(biāo)準(zhǔn)流程圖代表判斷條件語(yǔ)句的節(jié)點(diǎn)統(tǒng)一變?yōu)閘oop類(lèi)型，按照結(jié)構(gòu)標(biāo)準(zhǔn)化轉(zhuǎn)化規(guī)則，將按照程序源碼生成的流程圖中代表初始化語(yǔ)句和控制條件語(yǔ)句的兩個(gè)節(jié)點(diǎn)刪除。邊集e根據(jù)類(lèi)型定義相應(yīng)轉(zhuǎn)換成數(shù)據(jù)依賴邊和控制依賴邊。

（3）無(wú)邏輯關(guān)系節(jié)點(diǎn)合并。兩個(gè)節(jié)點(diǎn)一一映射轉(zhuǎn)換成對(duì)應(yīng)的節(jié)點(diǎn)類(lèi)型，若兩個(gè)相鄰節(jié)點(diǎn)是同一類(lèi)型，判斷兩個(gè)節(jié)點(diǎn)之間是否有邏輯關(guān)系，即數(shù)據(jù)依賴關(guān)系和控制依賴關(guān)系。若無(wú)邏輯關(guān)系，則將兩個(gè)相鄰的同種類(lèi)型節(jié)點(diǎn)合并在一起。如圖1所示，a=1和b=1兩個(gè)相鄰節(jié)點(diǎn)一一映射成同一種節(jié)點(diǎn)類(lèi)型，而且兩者無(wú)任何邏輯關(guān)系，因此可以合并成一個(gè)"assign"節(jié)點(diǎn);同樣將兩個(gè)節(jié)點(diǎn)的順序交換，也可以合并成一個(gè)。

（4）主數(shù)據(jù)流圖生成。結(jié)合傳統(tǒng)的程序依賴圖（Program Dependency Graph， PDG），把輸出程序結(jié)果的語(yǔ)句轉(zhuǎn)換成流程圖節(jié)點(diǎn)輸出標(biāo)記，在程序流程圖生成后，從流程圖輸出節(jié)點(diǎn)開(kāi)始圖的深度遍歷，進(jìn)而得到一個(gè)最大連通圖，刪除不在最大連通圖中的節(jié)點(diǎn)，最終得到的程序流程圖被稱(chēng)為主流程圖。

對(duì)于利用解析程序生成的流程圖，如果抄襲者添加一些無(wú)用代碼，會(huì)導(dǎo)致產(chǎn)生多余圖節(jié)點(diǎn)，無(wú)用代碼對(duì)程序運(yùn)行結(jié)果不產(chǎn)生影響，因此可去除冗余節(jié)點(diǎn)。從該角度分析可知，凡是與輸出結(jié)果無(wú)關(guān)的圖節(jié)點(diǎn)都應(yīng)刪除，該過(guò)程即為主數(shù)據(jù)流圖的生成過(guò)程[10]。

3 轉(zhuǎn)化實(shí)現(xiàn)

本部分通過(guò)一個(gè)實(shí)例說(shuō)明特定語(yǔ)言流程圖轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖的方法。為利用Java實(shí)現(xiàn)求n的階乘，分別運(yùn)用while和for循環(huán)結(jié)構(gòu)，利用現(xiàn)有工具生成的流程圖樣式分別見(jiàn)圖3和圖4。

從兩者生成的流程圖中可以看出，for循環(huán)中5節(jié)點(diǎn)的控制語(yǔ)句只體現(xiàn)了i<=n這一句，i=1和i++被自動(dòng)省略，而在while循環(huán)中由于這3句是分開(kāi)寫(xiě)的，所以均被體現(xiàn)出來(lái)，且一句代表一個(gè)節(jié)點(diǎn)。因此結(jié)構(gòu)標(biāo)準(zhǔn)化時(shí)，刪除while循環(huán)結(jié)構(gòu)流程圖代表i=1和i++兩個(gè)語(yǔ)句的節(jié)點(diǎn)，邊集e根據(jù)刪除的兩個(gè)節(jié)點(diǎn)和依賴關(guān)系進(jìn)行相應(yīng)改變，實(shí)現(xiàn)流程圖結(jié)構(gòu)標(biāo)準(zhǔn)化。

4 結(jié)語(yǔ)

本文提出了一種從源程序代碼到其流程圖的標(biāo)準(zhǔn)轉(zhuǎn)化方法，定義了流程圖節(jié)點(diǎn)類(lèi)型和邊類(lèi)型、節(jié)點(diǎn)、邊以及結(jié)構(gòu)標(biāo)準(zhǔn)化后生成對(duì)應(yīng)的標(biāo)準(zhǔn)流程圖，并通過(guò)實(shí)例具體說(shuō)明該方法的轉(zhuǎn)化規(guī)則。

下一步將從以下3個(gè)方面進(jìn)行深入研究：

（1）由于標(biāo)準(zhǔn)化后的流程圖節(jié)點(diǎn)不受具體代碼語(yǔ)句或編程語(yǔ)言約束，因此可考慮繼續(xù)深入研究基于流程圖的跨程序語(yǔ)言代碼相似度檢測(cè)。

（2）本文方法對(duì)于檢測(cè)控制結(jié)構(gòu)級(jí)的代碼冗余和錯(cuò)誤還有上升空間，可繼續(xù)優(yōu)化流程圖標(biāo)準(zhǔn)轉(zhuǎn)換。

（3）對(duì)于將程序源代碼轉(zhuǎn)化成流程圖的工作，有的實(shí)驗(yàn)系統(tǒng)現(xiàn)在僅提供對(duì)應(yīng)接口，用于集成到其它系統(tǒng)中，后續(xù)工作可將系統(tǒng)實(shí)現(xiàn)為一個(gè)用戶界面友好的工具，既可單獨(dú)使用也可服務(wù)于其它軟件以供集成使用。

參考文獻(xiàn)：

[1] 朱云， 曾曉勤， 朱寧，等. 基于圖文法的程序流程圖與源代碼自動(dòng)轉(zhuǎn)換[J]. 計(jì)算機(jī)工程與科學(xué)， 2015， 37（5）：937-945.

[2] 天涯海角路.幾款代碼轉(zhuǎn)流程圖軟件[EB/OL]. https：//www.cnblogs.com/aademeng/articles/6905245.html.

[3] 丁忠俊. 從源程序到流程圖的轉(zhuǎn)換方法及實(shí)現(xiàn)[J]. 計(jì)算機(jī)科學(xué)與探索，1993（5）：34-39.

[4] GB/T 1526—1989.信息處理數(shù)據(jù)流程圖、程序流程圖、系統(tǒng)流程圖、程序網(wǎng)絡(luò)圖和系統(tǒng)資源圖的文件編制符號(hào)及約定[S].

[5] ANNOMIT Y. Information processing： documentation symbols and conventions for data， program and system flowcharts， program network charts and system resources charts： ISO 5807：1985[S/OL].http：//www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm？csnumber=11955.

[6] GB/T 5271.1—2000.信息技術(shù)[S].

[7] 童天添. 科技期刊信息處理類(lèi)流程圖的編輯加工[J]. 編輯學(xué)報(bào)， 2017，29（1）：33-36.

[8] 譚浩強(qiáng). C程序設(shè)計(jì)[M]. 第4 版. 北京：清華大學(xué)出版社，2010：19-28.

[9] 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言[M]. 北京：清華大學(xué)出版社，2011：13.

[10] 胡正軍. 程序代碼相似度檢測(cè)方法研究及應(yīng)用[D]. 長(zhǎng)沙：中南大學(xué)，2012.

[11] 李沐東. 教學(xué)設(shè)計(jì)流程圖符號(hào)的標(biāo)準(zhǔn)化問(wèn)題[J]. 教育傳播與技術(shù)，2006（1）：52-54.

[12] 孫林，岳麗華，賈文舉. 一種從源程序代碼到其流程圖的自動(dòng)轉(zhuǎn)換算法[J]. 網(wǎng)絡(luò)新媒體技術(shù)，2001，22（3）：181-186.

[13] 楊超培. 程序化一種重要的標(biāo)準(zhǔn)化方法[J]. 信息技術(shù)與標(biāo)準(zhǔn)化， 1999（1）：25-25.

[14] 劉大為. 一種經(jīng)改進(jìn)的流程圖[J]. 質(zhì)量指南， 1995（3）：12-13.

[15] 波爾. 結(jié)構(gòu)化與面向?qū)ο蟪绦蛟O(shè)計(jì)[M]. 第7版.北京：電子工業(yè)出版社，2008.

[16] SHIBUTANI T，ONOGUCHI M，YAMADA T，et al. Optimization of the filter parameters in （99m）Tc myocardial perfusion SPECT studies： the formulation of flowchart[J]. Australasian Physical & Engineering Sciences in Medicine，2016，39（2）：571-581.

[17] 廖湖聲. 基于程序流程圖的數(shù)據(jù)例化與程序例化[J]. 計(jì)算機(jī)學(xué)報(bào)，2001，24（9）：985-990.

[18] 馮曉寧，李麒星，王卓. 一種基于BPMN的業(yè)務(wù)流程圖到BPEL的映射方法[J]. 計(jì)算機(jī)研究與發(fā)展，2013，50（s1）：44-52.

[19] 汪文勇，王學(xué)東，向渝，等. 匯編嵌入式軟件程序流程圖自動(dòng)生成的研究[J]. 計(jì)算機(jī)科學(xué)，2005，32（2）：173-175.

[20] 黃煙波，趙旭華，劉中宇. 基于.NET的流程圖繪制程序的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（5）：231-233.