一種程序源代碼的標準化流程圖轉化方法?

宋倩 張峰

（山東科技大學計算機科學與工程學院 青島 266590）

1 引言

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

針對上述問題，本文提出了一種程序源代碼的標準化流程圖轉化方法，參照ISO 5807：1985標準，對流程圖的節點類型和邊類型進行了定義，給出了程序流程的三種基本結構：順序、循環和分支的標準結構；給出了基于特定語言代碼的流程圖轉換為標準化流程圖的方法，節點以及結構標準化后生成對應的標準流程圖；在轉換過程中，為了應對代碼冗余等問題，將相鄰的無邏輯關系的節點合并，根據標準化的流程圖進一步生成主流程圖。最后，通過實例具體說明該方法的轉化規則。

2 相關工作

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

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

AutoFlowchart［3］主要用于對已有的程序進行分析，并為制作項目文檔做準備。它生成的流程圖支持展開或合攏，縮放和移動，并且可以預設流程圖的長寬和縱向橫向間距。可以將流程圖導出到WORD文檔或BMP圖像文件中。它支持C，C++，VC++（Visual C++.NET），Delphi（Object Pascal）等語言。

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

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

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

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

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

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

總的來說，通過分析源代碼生成流程圖的工具和方法，其生成的流程圖都跟程序源碼緊密相關，即使是相同流程的代碼，換一種編程語言或實現方式，對應生成的流程圖結構就會不同，對于利用流程圖來理解程序的邏輯結構的用戶來說是不適用的。

3 程序源代碼的標準化流程圖轉化方法

本文提出的程序源代碼的標準化流程圖轉化方法，在應對由于編程語言或實現方式的不同而導致流程圖結構不同的問題方面，對節點類型和結構類型分別制定了統一的轉化標準；在標準流程圖定義的基礎上，給出了標準流程圖的映射方法，實現將基于特定語言的流程圖轉換為標準流程圖的方法。在標準化過程中，為了應對代碼冗余的問題，將相鄰的無邏輯關系的節點合并，借鑒傳統的程序依賴圖（Program Dependency Graph，PDG）［5-6］的構造思路，生成不包括冗余代碼的程序主流程圖。最后，為了驗證效果，通過實例具體說明該方法的轉化規則。

3.1 標準流程圖定義

流程圖包括算法流程圖、數據流程圖、程序流程圖、系統流程圖等。本文提出的標準流程圖屬于程序流程圖，主要用于表示程序中的操作順序，包括表示實際處理操作的處理符號、根據邏輯條件確定要執行路徑的判斷符號、表示控制流的流線符號，以及注釋符［7～9］。ISO 5807：1985標準中規定了25種流程圖符號，包括基本符號和特定符號［10～12］。為了實現流程圖的標準化，本文從節點類型、結構類型這兩方面進行標準流程圖的定義。

3.1.1 節點類型

程序代碼經過轉換，變成流程圖中的節點和邊。在標準化流程圖的節點、邊的基礎上，結合流程圖結構，本文給出的標準流程圖中的節點類型如表1所示。

表1中給出的節點類型分為三類：順序節點、循環分支節點和組合節點。為了使冗余的代碼不對整個流程圖結構造成影響，通常會將相鄰無邏輯關系的節點合并，即生成組合節點（combine節點），以實現相同流程但不同源碼的流程圖的標準化。

在根據代碼得到的程序流程圖中，為了去除冗余的節點，需要將無邏輯關系節點合并。基本思路是：如果兩個節點是相鄰的，判斷兩個節點之間是否有邏輯關系，即數據依賴關系和控制依賴關系。若無邏輯關系，則將兩個相鄰的節點合并在一起。例如圖1，a=1和b=1兩個相鄰節點一一映射后是同一種節點類型，而且兩者無任何邏輯關系，因此可以合并成一個“assign”節點；同樣將兩個節點的順序交換，也可以合并成一個。

圖1 合并同種類型無邏輯關系節點

對于無邏輯關系的不同類型的節點，如圖2，int b和a=1兩個相鄰節點一一映射后是不同的節點類型，兩者無任何邏輯關系，因此可以合并成一個“combine”節點。

圖2 合并不同類型無邏輯關系節點

3.1.2 結構類型

流程圖的基本結構包括：順序結構、循環結構、分支結構，任何復雜的邏輯都可以通過這三種基本的程序結構來實現［13］。因此，為了實現流程圖的標準化，本文給出了標準化流程圖中的標準結構類型。

順序結構是最常用的流程圖結構［14］。順序結構中連接兩個節點的邊稱為順序執行邊（Sequen?tial Execution Edge，SEE）。本文給出如下定義。

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

標準流程圖中定義的順序結構樣式如圖3所示。

圖3 標準化的順序結構

循環或分支結構中連接loop或control類型的節點到下一節點的邊稱為控制依賴邊（Control De?pendency Edge，CDE），給出如下定義。

定義2（控制依賴邊）對于loop或control類型節點v1，如果v1條件的取值控制節點v2的執行，則存在從loop或control節點到下一節點的邊，稱為控制依賴邊。

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

圖4 標準化的循環結構

分支結構的執行是依據一定的條件選擇執行路徑，而不是嚴格按照語句出現的順序。四種基本的分支結構包括：if結構、if...else結構、if...else if結構、switch...case結構［16］。圖5給出了這四種基本結構對應的control標準化結構。

圖5 標準化的分支結構

3.2 特定語言流程圖的標準流程圖轉換方法

將基于特定程序語言生成的流程圖轉換成標準流程圖時，需要將基于特定程序語言的流程圖中的節點、邊和結構對照標準流程圖定義進行轉換。

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

3.2.1 節點和邊的標準化

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

將程序代碼轉換成流程圖并不需要體現具體的代碼語句，因此需要將節點和邊一一映射轉換為標準流程圖中的節點和邊。將程序代碼轉換成對應的流程圖，參照3.1.1每個節點內的文本給出其節點類型。邊根據類型定義3.1.2相應轉換成順序執行邊和控制依賴邊。

3.2.2 結構的標準化

對于兩段代碼，如果它們使用了不同類型的循環結構或者相同循環結構的不同形式，則流程圖中的循環結構也可能不同［19］。例如有的循環結構在生成的流程圖中只體現判斷條件語句的節點，初始化語句和控制條件語句自動省略，而有的循環則一句對應生成一個節點，需要將不同類型或相同結構不同形式的循環結構轉變為標準結構。這時標準流程圖代表判斷條件語句的節點統一映射為loop類型，按照3.1.2循環結構標準化轉化規則，將按照程序源碼生成的流程圖中代表初始化語句和控制條件語句的兩個節點刪除，如圖7。

圖7 循環結構標準化過程

同樣的，分支結構中if結構、if...else結構、if...else if結構、switch...case結構，無論條件的多少，都統一轉換成3.1.2分支結構的標準化形式。

3.2.3 主流程圖的生成

結合傳統的PDG，把輸出程序結果的語句轉換成流程圖節點時進行輸出標記，在程序流程圖生成以后，從流程圖中的輸出節點開始深度遍歷圖，進而得到一個最大連通圖，不在最大連通圖的圖節點將被刪除掉，最終得到的程序流程圖稱為主流程圖。

圖8展示了圖6中求和代碼的程序依賴關系圖轉換成其對應的主數據流圖的生成結果。

圖8 生成的主數據流圖

主數據流圖對應的代碼段如下，此時的代碼段去除了冗余代碼，最終生成的主流程圖見圖9。

圖9 最終的主流程圖

3.3 實例

下面通過一個實例說明特定語言流程圖轉換為標準流程圖的方法。用Java實現求n的階乘這一算法，分別用的是while和for循環結構，源代碼和利用現有工具生成的流程圖樣式見表2。

表2 求n的階乘代碼和對應的流程圖

在兩者生成的流程圖中可以看出，for循環中5節點的控制語句只體現了i＜=n這一句，i=1和i++這兩句自動省略了，而while循環中由于這三句是分開寫的，所以都體現了出來，且一句代表一個節點。因此循環結構標準化時，將while循環結構的流程圖代表i=1和i++這兩個語句的節點刪除，邊集e根據刪除的兩個節點和依賴關系進行相應的改變，這就是流程圖的結構標準化。

表3是用標準化后的循環結構求n的階乘的流程圖和進行節點和邊一一映射后的流程圖樣式。

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

4 結語

本文提出了一種從源程序代碼到其流程圖的標準轉化方法，在標準流程圖定義的基礎上，給出了標準流程圖的映射方法，并通過實例具體說明該方法的轉化規則。

本文研究的方法還有后續可以繼續完善的地方，下一步將從以下幾個方面進行深入研究。

第一，由于標準化后的流程圖節點不受具體代碼語句或使用的編程語言的約束，因此可以考慮繼續深入研究基于流程圖的跨程序語言代碼相似度的檢測。

第二，方法對于檢測控制結構級的代碼冗余和錯誤還有上升空間，可以繼續優化流程圖的標準轉換。

第三，對于將程序源代碼轉化成流程圖的工作，有的實驗系統現在還只是提供了對應的接口，用于集成到其他系統中，后續工作可以將系統實現為一個有友好用戶界面的工具，既可以單獨使用也可以提供服務集成其他軟件使用［20］。