宋倩 張峰

（山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 青島 266590）

1 引言

在軟件項(xiàng)目的開發(fā)過程中，程序流程圖（簡(jiǎn)稱為流程圖，F(xiàn)low Process Chart）是軟件開發(fā)過程中不可或缺的工具。在復(fù)雜的程序設(shè)計(jì)過程中，通常需要先通過流程圖來描述算法思路，然后再依據(jù)流程圖編寫出相應(yīng)的程序代碼。此外，在代碼分析中，流程圖可清晰地展示出程序的結(jié)構(gòu)，用它來輔助分析程序結(jié)構(gòu)遠(yuǎn)遠(yuǎn)方便于直接分析源程序本身［1］。因此，為了方便理解，經(jīng)常需要把源碼轉(zhuǎn)換成流程圖?，F(xiàn)有的一些方法和工具可以把程序源碼直接轉(zhuǎn)化成流程圖［2］，但是它們得到的流程圖都跟源代碼緊密相關(guān)。由于使用的編程語(yǔ)言或代碼功能的實(shí)現(xiàn)方式不同，相同流程的代碼得到的流程圖結(jié)構(gòu)也會(huì)不同，這樣不便于用戶的理解和使用。

針對(duì)上述問題，本文提出了一種程序源代碼的標(biāo)準(zhǔn)化流程圖轉(zhuǎn)化方法，參照ISO 5807：1985標(biāo)準(zhǔn)，對(duì)流程圖的節(jié)點(diǎn)類型和邊類型進(jìn)行了定義，給出了程序流程的三種基本結(jié)構(gòu)：順序、循環(huán)和分支的標(biāo)準(zhǔn)結(jié)構(gòu)；給出了基于特定語(yǔ)言代碼的流程圖轉(zhuǎn)換為標(biāo)準(zhǔn)化流程圖的方法，節(jié)點(diǎn)以及結(jié)構(gòu)標(biāo)準(zhǔn)化后生成對(duì)應(yīng)的標(biāo)準(zhǔn)流程圖；在轉(zhuǎn)換過程中，為了應(yīng)對(duì)代碼冗余等問題，將相鄰的無邏輯關(guān)系的節(jié)點(diǎn)合并，根據(jù)標(biāo)準(zhǔn)化的流程圖進(jìn)一步生成主流程圖。最后，通過實(shí)例具體說明該方法的轉(zhuǎn)化規(guī)則。

2 相關(guān)工作

從已有的研究工作來看，現(xiàn)有的將程序源代碼轉(zhuǎn)換為流程圖的工具和方法主要有以下幾種。

1）直接分析源代碼，生成流程圖

AutoFlowchart［3］主要用于對(duì)已有的程序進(jìn)行分析，并為制作項(xiàng)目文檔做準(zhǔn)備。它生成的流程圖支持展開或合攏，縮放和移動(dòng)，并且可以預(yù)設(shè)流程圖的長(zhǎng)寬和縱向橫向間距?？梢詫⒘鞒虉D導(dǎo)出到WORD文檔或BMP圖像文件中。它支持C，C++，VC++（Visual C++.NET），Delphi（Object Pascal）等語(yǔ)言。

Code Visual to Flowchart［3］可以用于迅速地分析源代碼并且在流程圖窗口當(dāng)中顯示當(dāng)前被編輯的代碼的圖形化描述。它是由一個(gè)代碼編輯器和一個(gè)流程圖窗口組成并且支持多種編程語(yǔ)言，諸如C/C++，Java/JavaScript，VB/BASIC/ASP，Delphi/Pas?cal，PHP，Power Builder，Perl以及其它語(yǔ)言。

SourceCode to flowchart［3］，一個(gè)代碼維護(hù)與管理軟件，它能夠快速地分析源代碼，并在流程圖窗口中顯示出目前代碼的圖示。它具有一個(gè)代碼編輯器和一個(gè)流程圖窗口。流程圖的引擎很快，同時(shí)還可以以多種形式輸出流程圖。

Visustin［4］，一個(gè)支持 42 種編程語(yǔ)言的流程圖制作軟件。Visustin支持的語(yǔ)言有ABAP，Action?Script，Ada，ASP，assembler，BASIC，Batch files，C，C++，C#，Java，Python等。生成的流程圖詳細(xì)，功能很全面，可以對(duì)圖進(jìn)行編輯，不足之處是不能向外保存。

2）生成流程圖并拓展其他代碼分析功能

EasyStructure［3］，從 C 來源自動(dòng)地生成流程圖和資源結(jié)構(gòu)樹。EasyStructure從它的分析和結(jié)果字符理解源代碼。樹形瀏覽以一個(gè)可以通過它的結(jié)構(gòu)以及它的原始資源隨意地進(jìn)行瀏覽、組織的形式來顯示資源。可以使用樹節(jié)點(diǎn)來找到包含的各種不同類型的聲明。

Crystal Flow for C［3］，獲得一個(gè)帶有流程圖的清晰代碼，可以用來校驗(yàn)邏輯功能的正確性，檢測(cè)錯(cuò)誤。導(dǎo)出的流程圖為BMP或者JPG格式文件以及用于VISIO的XML文件。它提供代碼和注釋的自動(dòng)格式化功能，為功能調(diào)用定制相應(yīng)的形狀。利用它可以把自己或別人寫的代碼格式化，并可以生成直觀的流程圖、交叉調(diào)用圖、直觀的注釋等。

總的來說，通過分析源代碼生成流程圖的工具和方法，其生成的流程圖都跟程序源碼緊密相關(guān)，即使是相同流程的代碼，換一種編程語(yǔ)言或?qū)崿F(xiàn)方式，對(duì)應(yīng)生成的流程圖結(jié)構(gòu)就會(huì)不同，對(duì)于利用流程圖來理解程序的邏輯結(jié)構(gòu)的用戶來說是不適用的。

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

本文提出的程序源代碼的標(biāo)準(zhǔn)化流程圖轉(zhuǎn)化方法，在應(yīng)對(duì)由于編程語(yǔ)言或?qū)崿F(xiàn)方式的不同而導(dǎo)致流程圖結(jié)構(gòu)不同的問題方面，對(duì)節(jié)點(diǎn)類型和結(jié)構(gòu)類型分別制定了統(tǒng)一的轉(zhuǎn)化標(biāo)準(zhǔn)；在標(biāo)準(zhǔn)流程圖定義的基礎(chǔ)上，給出了標(biāo)準(zhǔn)流程圖的映射方法，實(shí)現(xiàn)將基于特定語(yǔ)言的流程圖轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖的方法。在標(biāo)準(zhǔn)化過程中，為了應(yīng)對(duì)代碼冗余的問題，將相鄰的無邏輯關(guān)系的節(jié)點(diǎn)合并，借鑒傳統(tǒng)的程序依賴圖（Program Dependency Graph，PDG）［5-6］的構(gòu)造思路，生成不包括冗余代碼的程序主流程圖。最后，為了驗(yàn)證效果，通過實(shí)例具體說明該方法的轉(zhuǎn)化規(guī)則。

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

流程圖包括算法流程圖、數(shù)據(jù)流程圖、程序流程圖、系統(tǒng)流程圖等。本文提出的標(biāo)準(zhǔn)流程圖屬于程序流程圖，主要用于表示程序中的操作順序，包括表示實(shí)際處理操作的處理符號(hào)、根據(jù)邏輯條件確定要執(zhí)行路徑的判斷符號(hào)、表示控制流的流線符號(hào)，以及注釋符［7～9］。ISO 5807：1985標(biāo)準(zhǔn)中規(guī)定了25種流程圖符號(hào)，包括基本符號(hào)和特定符號(hào)［10～12］。為了實(shí)現(xiàn)流程圖的標(biāo)準(zhǔn)化，本文從節(jié)點(diǎn)類型、結(jié)構(gòu)類型這兩方面進(jìn)行標(biāo)準(zhǔn)流程圖的定義。

3.1.1 節(jié)點(diǎn)類型

程序代碼經(jīng)過轉(zhuǎn)換，變成流程圖中的節(jié)點(diǎn)和邊。在標(biāo)準(zhǔn)化流程圖的節(jié)點(diǎn)、邊的基礎(chǔ)上，結(jié)合流程圖結(jié)構(gòu)，本文給出的標(biāo)準(zhǔn)流程圖中的節(jié)點(diǎn)類型如表1所示。

表1中給出的節(jié)點(diǎn)類型分為三類：順序節(jié)點(diǎn)、循環(huán)分支節(jié)點(diǎn)和組合節(jié)點(diǎn)。為了使冗余的代碼不對(duì)整個(gè)流程圖結(jié)構(gòu)造成影響，通常會(huì)將相鄰無邏輯關(guān)系的節(jié)點(diǎn)合并，即生成組合節(jié)點(diǎn)（combine節(jié)點(diǎn)），以實(shí)現(xiàn)相同流程但不同源碼的流程圖的標(biāo)準(zhǔn)化。

在根據(jù)代碼得到的程序流程圖中，為了去除冗余的節(jié)點(diǎn)，需要將無邏輯關(guān)系節(jié)點(diǎn)合并?；舅悸肥牵喝绻麅蓚€(gè)節(jié)點(diǎn)是相鄰的，判斷兩個(gè)節(jié)點(diǎn)之間是否有邏輯關(guān)系，即數(shù)據(jù)依賴關(guān)系和控制依賴關(guān)系。若無邏輯關(guān)系，則將兩個(gè)相鄰的節(jié)點(diǎn)合并在一起。例如圖1，a=1和b=1兩個(gè)相鄰節(jié)點(diǎn)一一映射后是同一種節(jié)點(diǎn)類型，而且兩者無任何邏輯關(guān)系，因此可以合并成一個(gè)“assign”節(jié)點(diǎn)；同樣將兩個(gè)節(jié)點(diǎn)的順序交換，也可以合并成一個(gè)。

圖1 合并同種類型無邏輯關(guān)系節(jié)點(diǎn)

對(duì)于無邏輯關(guān)系的不同類型的節(jié)點(diǎn)，如圖2，int b和a=1兩個(gè)相鄰節(jié)點(diǎn)一一映射后是不同的節(jié)點(diǎn)類型，兩者無任何邏輯關(guān)系，因此可以合并成一個(gè)“combine”節(jié)點(diǎn)。

圖2 合并不同類型無邏輯關(guān)系節(jié)點(diǎn)

3.1.2 結(jié)構(gòu)類型

流程圖的基本結(jié)構(gòu)包括：順序結(jié)構(gòu)、循環(huán)結(jié)構(gòu)、分支結(jié)構(gòu)，任何復(fù)雜的邏輯都可以通過這三種基本的程序結(jié)構(gòu)來實(shí)現(xiàn)［13］。因此，為了實(shí)現(xiàn)流程圖的標(biāo)準(zhǔn)化，本文給出了標(biāo)準(zhǔn)化流程圖中的標(biāo)準(zhǔn)結(jié)構(gòu)類型。

順序結(jié)構(gòu)是最常用的流程圖結(jié)構(gòu)［14］。順序結(jié)構(gòu)中連接兩個(gè)節(jié)點(diǎn)的邊稱為順序執(zhí)行邊（Sequen?tial Execution Edge，SEE）。本文給出如下定義。

定義1（順序執(zhí)行邊）如果存在變量var，從節(jié)點(diǎn)v1到v2有邊滿足：變量var在v1處定義、在v2處引用或存在一條從v1到v2的路徑，該路徑表示代碼執(zhí)行的順序。

標(biāo)準(zhǔn)流程圖中定義的順序結(jié)構(gòu)樣式如圖3所示。

圖3 標(biāo)準(zhǔn)化的順序結(jié)構(gòu)

循環(huán)或分支結(jié)構(gòu)中連接loop或control類型的節(jié)點(diǎn)到下一節(jié)點(diǎn)的邊稱為控制依賴邊（Control De?pendency Edge，CDE），給出如下定義。

定義2（控制依賴邊）對(duì)于loop或control類型節(jié)點(diǎn)v1，如果v1條件的取值控制節(jié)點(diǎn)v2的執(zhí)行，則存在從loop或control節(jié)點(diǎn)到下一節(jié)點(diǎn)的邊，稱為控制依賴邊。

程序中的循環(huán)結(jié)構(gòu)，如for循環(huán)、while循環(huán)、do-while循環(huán)，在一定程度上均可實(shí)現(xiàn)相同的功能［15］，但是利用現(xiàn)有的工具和方法生成的流程圖樣式卻不相同，不便于用戶的理解和使用。為此，本文給出了loop的標(biāo)準(zhǔn)化結(jié)構(gòu)，如圖4所示，其中有“yes”和“no”標(biāo)識(shí)的兩條邊是CDE。

圖4 標(biāo)準(zhǔn)化的循環(huán)結(jié)構(gòu)

分支結(jié)構(gòu)的執(zhí)行是依據(jù)一定的條件選擇執(zhí)行路徑，而不是嚴(yán)格按照語(yǔ)句出現(xiàn)的順序。四種基本的分支結(jié)構(gòu)包括：if結(jié)構(gòu)、if...else結(jié)構(gòu)、if...else if結(jié)構(gòu)、switch...case結(jié)構(gòu)［16］。圖5給出了這四種基本結(jié)構(gòu)對(duì)應(yīng)的control標(biāo)準(zhǔn)化結(jié)構(gòu)。

圖5 標(biāo)準(zhǔn)化的分支結(jié)構(gòu)

3.2 特定語(yǔ)言流程圖的標(biāo)準(zhǔn)流程圖轉(zhuǎ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)換。

由于在編程過程中代碼可能存在沒有使用到的變量，這種冗余會(huì)使流程圖的可讀性降低［17～18］。以圖6中的代碼為例，本文給定一段求和代碼，其中包含了部分冗余代碼，圖6是代碼段對(duì)應(yīng)生成的程序依賴關(guān)系圖。為了應(yīng)對(duì)這些代碼冗余的問題，結(jié)合傳統(tǒng)的程序依賴圖［5～6］，需要進(jìn)一步生成主流程圖，從而去除冗余的節(jié)點(diǎn)。

3.2.1 節(jié)點(diǎn)和邊的標(biāo)準(zhǔn)化

定義（映射）兩個(gè)非空集合A與B間存在著對(duì)應(yīng)關(guān)系f，而且對(duì)于A中的每一個(gè)元素x，B中總有唯一的一個(gè)元素y與它對(duì)應(yīng)，這種對(duì)應(yīng)為從A到B的映射，記作 f：A→B［11］。

將程序代碼轉(zhuǎn)換成流程圖并不需要體現(xiàn)具體的代碼語(yǔ)句，因此需要將節(jié)點(diǎn)和邊一一映射轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖中的節(jié)點(diǎn)和邊。將程序代碼轉(zhuǎn)換成對(duì)應(yīng)的流程圖，參照3.1.1每個(gè)節(jié)點(diǎn)內(nèi)的文本給出其節(jié)點(diǎn)類型。邊根據(jù)類型定義3.1.2相應(yīng)轉(zhuǎn)換成順序執(zhí)行邊和控制依賴邊。

3.2.2 結(jié)構(gòu)的標(biāo)準(zhǔn)化

對(duì)于兩段代碼，如果它們使用了不同類型的循環(huán)結(jié)構(gòu)或者相同循環(huán)結(jié)構(gòu)的不同形式，則流程圖中的循環(huán)結(jié)構(gòu)也可能不同［19］。例如有的循環(huán)結(jié)構(gòu)在生成的流程圖中只體現(xiàn)判斷條件語(yǔ)句的節(jié)點(diǎn)，初始化語(yǔ)句和控制條件語(yǔ)句自動(dòng)省略，而有的循環(huán)則一句對(duì)應(yīng)生成一個(gè)節(jié)點(diǎn)，需要將不同類型或相同結(jié)構(gòu)不同形式的循環(huán)結(jié)構(gòu)轉(zhuǎn)變?yōu)闃?biāo)準(zhǔn)結(jié)構(gòu)。這時(shí)標(biāo)準(zhǔn)流程圖代表判斷條件語(yǔ)句的節(jié)點(diǎn)統(tǒng)一映射為loop類型，按照3.1.2循環(huán)結(jié)構(gòu)標(biāo)準(zhǔn)化轉(zhuǎn)化規(guī)則，將按照程序源碼生成的流程圖中代表初始化語(yǔ)句和控制條件語(yǔ)句的兩個(gè)節(jié)點(diǎn)刪除，如圖7。

圖7 循環(huán)結(jié)構(gòu)標(biāo)準(zhǔn)化過程

同樣的，分支結(jié)構(gòu)中if結(jié)構(gòu)、if...else結(jié)構(gòu)、if...else if結(jié)構(gòu)、switch...case結(jié)構(gòu)，無論條件的多少，都統(tǒng)一轉(zhuǎn)換成3.1.2分支結(jié)構(gòu)的標(biāo)準(zhǔn)化形式。

3.2.3 主流程圖的生成

結(jié)合傳統(tǒng)的PDG，把輸出程序結(jié)果的語(yǔ)句轉(zhuǎn)換成流程圖節(jié)點(diǎn)時(shí)進(jìn)行輸出標(biāo)記，在程序流程圖生成以后，從流程圖中的輸出節(jié)點(diǎn)開始深度遍歷圖，進(jìn)而得到一個(gè)最大連通圖，不在最大連通圖的圖節(jié)點(diǎn)將被刪除掉，最終得到的程序流程圖稱為主流程圖。

圖8展示了圖6中求和代碼的程序依賴關(guān)系圖轉(zhuǎn)換成其對(duì)應(yīng)的主數(shù)據(jù)流圖的生成結(jié)果。

圖8 生成的主數(shù)據(jù)流圖

主數(shù)據(jù)流圖對(duì)應(yīng)的代碼段如下，此時(shí)的代碼段去除了冗余代碼，最終生成的主流程圖見圖9。

圖9 最終的主流程圖

3.3 實(shí)例

下面通過一個(gè)實(shí)例說明特定語(yǔ)言流程圖轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖的方法。用Java實(shí)現(xiàn)求n的階乘這一算法，分別用的是while和for循環(huán)結(jié)構(gòu)，源代碼和利用現(xiàn)有工具生成的流程圖樣式見表2。

表2 求n的階乘代碼和對(duì)應(yīng)的流程圖

在兩者生成的流程圖中可以看出，for循環(huán)中5節(jié)點(diǎn)的控制語(yǔ)句只體現(xiàn)了i＜=n這一句，i=1和i++這兩句自動(dòng)省略了，而while循環(huán)中由于這三句是分開寫的，所以都體現(xiàn)了出來，且一句代表一個(gè)節(jié)點(diǎn)。因此循環(huá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)的改變，這就是流程圖的結(jié)構(gòu)標(biāo)準(zhǔn)化。

表3是用標(biāo)準(zhǔn)化后的循環(huán)結(jié)構(gòu)求n的階乘的流程圖和進(jìn)行節(jié)點(diǎn)和邊一一映射后的流程圖樣式。

表3 原流程圖和映射后流程圖

4 結(jié)語(yǔ)

本文提出了一種從源程序代碼到其流程圖的標(biāo)準(zhǔn)轉(zhuǎn)化方法，在標(biāo)準(zhǔn)流程圖定義的基礎(chǔ)上，給出了標(biāo)準(zhǔn)流程圖的映射方法，并通過實(shí)例具體說明該方法的轉(zhuǎn)化規(guī)則。

本文研究的方法還有后續(xù)可以繼續(xù)完善的地方，下一步將從以下幾個(gè)方面進(jìn)行深入研究。

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

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

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