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

宋倩 張峰

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

1 引言

在軟件項(xiàng)目的開發(fā)過程中，程序流程圖（簡稱為流程圖，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)。由于使用的編程語言或代碼功能的實(shí)現(xiàn)方式不同，相同流程的代碼得到的流程圖結(jié)構(gòu)也會(huì)不同，這樣不便于用戶的理解和使用。

針對上述問題，本文提出了一種程序源代碼的標(biāo)準(zhǔn)化流程圖轉(zhuǎn)化方法，參照ISO 5807：1985標(biāo)準(zhǔn)，對流程圖的節(jié)點(diǎn)類型和邊類型進(jìn)行了定義，給出了程序流程的三種基本結(jié)構(gòu)：順序、循環(huán)和分支的標(biāo)準(zhǔn)結(jié)構(gòu)；給出了基于特定語言代碼的流程圖轉(zhuǎn)換為標(biāo)準(zhǔn)化流程圖的方法，節(jié)點(diǎn)以及結(jié)構(gòu)標(biāo)準(zhǔn)化后生成對應(yīng)的標(biāo)準(zhǔn)流程圖；在轉(zhuǎn)換過程中，為了應(yīng)對代碼冗余等問題，將相鄰的無邏輯關(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］主要用于對已有的程序進(jìn)行分析，并為制作項(xiàng)目文檔做準(zhǔn)備。它生成的流程圖支持展開或合攏，縮放和移動(dòng)，并且可以預(yù)設(shè)流程圖的長寬和縱向橫向間距?？梢詫⒘鞒虉D導(dǎo)出到WORD文檔或BMP圖像文件中。它支持C，C++，VC++（Visual C++.NET），Delphi（Object Pascal）等語言。

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

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

Visustin［4］，一個(gè)支持 42 種編程語言的流程圖制作軟件。Visustin支持的語言有ABAP，Action?Script，Ada，ASP，assembler，BASIC，Batch files，C，C++，C#，Java，Python等。生成的流程圖詳細(xì)，功能很全面，可以對圖進(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)邏輯功能的正確性，檢測錯(cuò)誤。導(dǎo)出的流程圖為BMP或者JPG格式文件以及用于VISIO的XML文件。它提供代碼和注釋的自動(dòng)格式化功能，為功能調(diào)用定制相應(yīng)的形狀。利用它可以把自己或別人寫的代碼格式化，并可以生成直觀的流程圖、交叉調(diào)用圖、直觀的注釋等。

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

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

本文提出的程序源代碼的標(biāo)準(zhǔn)化流程圖轉(zhuǎn)化方法，在應(yīng)對由于編程語言或?qū)崿F(xiàn)方式的不同而導(dǎo)致流程圖結(jié)構(gòu)不同的問題方面，對節(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)將基于特定語言的流程圖轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖的方法。在標(biāo)準(zhǔn)化過程中，為了應(yīng)對代碼冗余的問題，將相鄰的無邏輯關(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)。為了使冗余的代碼不對整個(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)

對于無邏輯關(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（控制依賴邊）對于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)格按照語句出現(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)對應(yīng)的control標(biāo)準(zhǔn)化結(jié)構(gòu)。

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

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

將基于特定程序語言生成的流程圖轉(zhuǎn)換成標(biāo)準(zhǔn)流程圖時(shí)，需要將基于特定程序語言的流程圖中的節(jié)點(diǎn)、邊和結(jié)構(gòu)對照標(biāo)準(zhǔn)流程圖定義進(jìn)行轉(zhuǎn)換。

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

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

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

將程序代碼轉(zhuǎn)換成流程圖并不需要體現(xiàn)具體的代碼語句，因此需要將節(jié)點(diǎn)和邊一一映射轉(zhuǎn)換為標(biāo)準(zhǔn)流程圖中的節(jié)點(diǎn)和邊。將程序代碼轉(zhuǎn)換成對應(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)化

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

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

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

圖9 最終的主流程圖

3.3 實(shí)例

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

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

在兩者生成的流程圖中可以看出，for循環(huán)中5節(jié)點(diǎn)的控制語句只體現(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è)語句的節(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é)語

本文提出了一種從源程序代碼到其流程圖的標(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)不受具體代碼語句或使用的編程語言的約束，因此可以考慮繼續(xù)深入研究基于流程圖的跨程序語言代碼相似度的檢測。

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

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