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

關鍵詞：源程序代碼;流程圖;標準流程圖定義;流程圖標準化方法

DOI：10. 11907/rjdk. 182612

中圖分類號：TP301文獻標識碼：A文章編號：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 引言

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

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

1 相關工作

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

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

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

2 標準轉(zhuǎn)化方法

2.1 標準流程圖定義

根據(jù)ISO 5807：1985標準[15]，流程圖一般由平面圖節(jié)點、邊和文字標號構(gòu)成。本文對流程圖元素進行綜合分析，從節(jié)點類型、邊類型和結(jié)構(gòu)類型3方面進行標準流程圖元素定義。

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

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

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

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

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

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

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

2.2 特定語言流程圖轉(zhuǎn)換為標準流程圖的方法

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

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

有時將程序代碼轉(zhuǎn)換成流程圖的工作無需體現(xiàn)具體的代碼語句，因此需要將節(jié)點和邊一一映射轉(zhuǎn)換為標準流程圖中的節(jié)點和邊。將程序代碼轉(zhuǎn)換成對應的流程圖，邊根據(jù)類型定義相應轉(zhuǎn)換成數(shù)據(jù)依賴邊和控制依賴邊。

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

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

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

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

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

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

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

4 結(jié)語

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

下一步將從以下3個方面進行深入研究：

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

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

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

參考文獻：

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

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

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

[4] GB/T 1526—1989.信息處理數(shù)據(jù)流程圖、程序流程圖、系統(tǒng)流程圖、程序網(wǎng)絡圖和系統(tǒng)資源圖的文件編制符號及約定[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.信息技術[S].

[7] 童天添. 科技期刊信息處理類流程圖的編輯加工[J]. 編輯學報， 2017，29（1）：33-36.

[8] 譚浩強. C程序設計[M]. 第4 版. 北京：清華大學出版社，2010：19-28.

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

[10] 胡正軍. 程序代碼相似度檢測方法研究及應用[D]. 長沙：中南大學，2012.

[11] 李沐東. 教學設計流程圖符號的標準化問題[J]. 教育傳播與技術，2006（1）：52-54.

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

[13] 楊超培. 程序化一種重要的標準化方法[J]. 信息技術與標準化， 1999（1）：25-25.

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

[15] 波爾. 結(jié)構(gòu)化與面向?qū)ο蟪绦蛟O計[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]. 計算機學報，2001，24（9）：985-990.

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

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

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