基于N 叉樹的PLC 功能塊向指令表的轉換算法研究*

周 偉，張得禮

(南京航空航天大學 機電學院，江蘇 南京 210016)

0 引言

所謂軟PLC 就是使用PC 機作為硬件支持平臺，使用軟件來實現傳統PLC 的基本功能，PLC 控制函數封裝在軟件中，運行于PC 環境中?；赑C 的自動控制系統具有成本低、開放性好、易于使用等優點，使它成為一個新的發展方向。根據PLC 的傳統結構，軟PLC 系統分為兩部分，程序開發系統和運行系統，其中運行系統是軟PLC 技術的核心。

在IEC61131-3 標準中提供了5 種編程語言［1］，其中功能塊圖(FBD)是一種圖形化編程語言，相比于梯形圖語言，FBD 語言能夠更好地描述各個輸入觸點間的邏輯關系。使用功能塊圖編程語言不僅可以提高系統的可靠性，利于結構化程序設計，且還能有效地實現程序代碼的復用，加速應用程序的開發。

結合軟PLC 的設計思想，依據IEC61131-3 標準，本研究設計的Soft PLC 軟件平臺提供了功能塊圖(FBD)和指令語言(IL)兩種編程語言。編譯器則負責對編輯器中的功能塊圖和指令語言程序進行編譯，實現從圖形語言到文字語言的轉化，最終生成二進制目標代碼。其中編譯轉化過程是程序開發中的關鍵。

文獻［2］介紹了嵌入式的軟PLC 控制系統，運行控制模塊是以ARM920T 處理器為核心，編輯軟件生成代碼指令列表(IL)代碼，然后PLC 系統通過解釋執行IL 代碼來實現具體的控制。無論是基于PC 或是嵌入式的軟PLC 系統，編譯轉化模塊都是至關重要的環節，直接關系到后面的運行控制模塊對程序解析執行的對錯。

文獻［3-4］介紹了由AOV 圖建立二叉樹，并對其進行后序遍歷實現梯形圖與指令表程序轉換的算法，適用于串、并聯復雜的梯形圖，存在的不足是只能應用單輸出的梯形圖網絡。文獻［5-6］將梯形圖轉化為AOV 圖，并利用AOV 圖建立因果圖，然后遍歷因果圖的節點生成PLC 所能識別的語句表，對于復雜的多輸出的梯形圖網絡也并不適用。

文獻［7］介紹了PLC 功能塊圖向指令表的轉換算法，采用樹結構中的孩子兄弟表示法(又稱二叉鏈表表示法)來存儲每一個功能塊的數據和邏輯關系等信息，每一個功能塊圖都可以表示成一棵樹，對樹進行一次遍歷，就得出了用戶程序對應的IL 程序。但這并不通用，且不適用于串、并聯邏輯關系復雜和多重輸出的FBD 程序。

本研究針對軟PLC 多重輸出的問題，提出將FBD圖映射到N 叉樹型數據結構，對N 叉樹進行后序遍歷依次訪問各個節點，得到相應IL 程序的算法。該算法適用于復雜的多輸出FBD 程序，采用分解重組的方式，將生成的復雜樹結構分解成N個有序的樹結構組合，然后對每個N個樹結構進行有序遍歷，生成IL 程序。該算法具有通用性，能提高PLC 解釋執行的效率。

1 N 叉樹結構及其遍歷方式

1.1 N 叉樹結構

樹是n(n≥0)個有限數據元素的集合T，任一非空樹(n ＞0)滿足下面兩個條件:

(1)且僅有一個稱為根(root)的結點，根結點沒有前驅結點;

(2)當n ＞1 時，除根結點以外的其余數據元素被分成m(0 ＜m≤n)個互不相交的集合T1，T2，……，Tm，其中每一個集合Ti(1≤i≤m)本身又是一棵樹。樹T1，T2，……，Tm稱為這個根結點的子樹。當樹中的每個結點最多只有兩棵子樹時，稱為二叉樹［8］，多于兩棵子樹時稱為多叉樹。

1.2 N 叉樹的存儲表示

如果采用二叉樹的表示方法，則每個節點內設置多少個指針子節點不好確定。若以整個樹中子節點最多的節點為準給各節點設置指針，則大量指針為空，將浪費存儲空間;若每個節點按其實際的子節點數設置指針，則各子節點數不相等，形式也不統一，這將給管理和操作帶來不便。因為N 叉樹每個節點的子節點數沒有限制，其更為適合用來存儲復雜FBD 程序。

每一個CPTreeNode 節點之間的連接規律是:pNode_Parent 指針指向父節點的指針，pNode_FirstChild 指針指向第一個孩子節點的指針，pNode_Next-Brother 指針指向下一個兄弟節點的指針，m_TreeType保存節點本身的基本信息。

2 基于N 叉樹PLC 功能塊向指令表轉化算法

遍歷是對樹的一種最基本的運算，所謂遍歷N 叉樹，就是按一定的規則和順序走遍N 叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。二叉樹的遍歷主要有中序遍歷(LDR)、先序遍歷(DLR)和后序遍歷(LRD)3 種，對于N 叉樹而言，無所謂中根次序，而只有先根，后根次序遍歷的方式［9］。

轉化前的N 叉樹結構如圖1 所示。其中節點19為根節點，根節點第一子樹集合{8，1，2，3，4，5，6，7};第二子樹集合{9，10，11，12};第三子樹結合{13，14，15，16，17，18}［10］。

后根次序遍歷結果:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19。

圖1 轉化前的N 叉樹結構

先根次序遍歷結果:19 8 1 3 2 7 4 5 6 12 11 9 10 18 13 17 16 14 15。

無論是后根次序遍歷還是先根次序遍歷對于該樹結構的所有子樹遍歷方式都是必須是相同的，當出現要求所有子樹遍歷方式不盡相同的時候，傳統的單一遍歷算法就顯得力不從心。

對于N 叉樹T，定義一種新的遍歷方式:樹T 的子樹T1{}集合采用后根次序的遍歷方式，其余的子樹T2{}集合采用先根次序的遍歷方式。若是還采用傳統單一的遍歷算法，勢必會造成程序量上面的冗雜堆積，浪費不必要的內存空間。研究者可以采用分解重組的方式，將整個N 叉樹結構進行分解，將需要進行后根次序遍歷的子樹T1{}保持不變，將需要進行先根次序遍歷的子樹T2{}各個節點改變父節點、孩子節點等參數連接指向，根節點19 因此派生出多個虛根節點，如圖4 中白色的19'，19″節點，節點19'為根節點19 的第一虛根節點，19″為第二虛根節點，派生出的虛根節點依次作為T2{}集合成員的子節點。

圖2 轉化后的N 叉樹結構

圖1 中N 叉樹進過分解重組轉化后生成的由多個N 叉樹組成的集合如圖2 所示。重組后的樹結構被分解成3個較為簡單的樹，這樣就可以采用唯一的遍歷方式來訪問各個節點。

在同等運行環境中，采用多次執行取均值的方式，未采用分解算法的平均執行時間為0.099 52 ms，采用分割組合后的平均執行時間為0.099 62 ms，在程序執行快慢方面大相近庭，但是前者在遍歷過程中使用了96 B的臨時變量空間，而采用分割組合后的算法只使用了60 B的臨時變量空間，因為在遍歷過程中，前者需要兩種方式的遍歷，而進行分割重組后的樹結構只需要一種方式就可以達到遍歷的要求，減少了程序代碼量上面的冗雜堆積。由此可見，當節點數增多時，采用本研究算法可以簡化程序，節省更多的空間。

3 FBD 向IL 語句轉化算法設計

經過多年的研究與發展，國內外的PLC 產品及其編程平臺已相當成熟，大多集成開發環境都包含了梯形圖與指令表程序互換的功能，相對較少涉及FBD 向指令表轉換算法。本研究采用樹結構中的孩子兄弟表示法來存儲每一個功能塊的數據和邏輯關系等信息，每一個功能塊圖都可以表示成樹結構的一個節點，通過依次查找的方式找到每個節點的父節點、兄弟節點，再對樹進行一次遍歷，就得出了用戶程序對應的IL程序。

本研究設計的算法適用于串、并聯邏輯關系復雜、且具有多重輸出的FBD 程序，FBD 程序轉化實例如圖3 所示，筆者以如圖3 所示的FBD 程序為例驗證本研究算法的正確性。

圖3 FBD 程序轉化實例

3.1 基于N 叉樹結構的FBD 模塊表達

PLC 多重輸出指令又被稱為堆棧指令，LPS(進棧指令)、LRD(讀棧指令)、LPP(出棧指令)為一組指令，主要用在當多重輸出且邏輯條件不同的情況下，將連接點的結果存儲起來，以便連接點后面的電路編程。

為滿足PLC 的多重輸出指令的要求，本研究設計CVerLine 類為應對多重輸出的PLC 程序。在處理CVerLine 類型節點過程中，CVerLine 類對象轉化方式如圖4 所示，圖4 中為3 重輸出分支，一個實例化CVerLine 的類對象產生一個L_Ver 樹形節點，并且派生出3個R_Ver 虛節點，R_Ver1、R_Ver2、R_Ver3 為節點L_Ver 的有序派生虛節點，依次為第一、第二、第三派生虛節點。第一步先遍歷以L_Ver 為根節點的樹結構，第二步再按順序依次遍歷以R_Ver1、R_Ver2、R_Ver3 為子節點的樹結構，在第二步過程中遍歷到R_Ver1、R_Ver2、R_Ver3 等虛節點，不做任何處理，就可以達到“使每一個結點都被訪問一次，而且只被訪問一次”的遍歷效果。

圖4 CVerLine 類對象轉化方式

本研究在設計N 叉樹型數據結構時采用上述的方式保存節點，圖3 中FBD 程序經過轉換映射、分解重組產生的樹結構如圖5 所示。

圖5 經過分解重組后的N 叉樹結構

3.2 N 叉樹結構的簡化

邏輯樹建好之后，對其進行后序遍歷便可生成功能塊圖所對應的指令表程序。為簡化后序遍歷過程，需對邏輯樹進行化簡，化簡方法是:遍歷樹結構中的所有邏輯節點，判斷邏輯節點的類型是否與其父節點類型相同，若相同，則刪除該節點，并將其所有的子節點直接追加為其父節點的子節點。

N 叉樹結構的簡化實例如圖6 所示。圖6 中存在一個AND 節點與其父節點類型相同，其表達的邏輯關系是完全正確的，但在向IL 指令表轉化中，為了簡化N 叉樹結構，將其自己的所有孩子節點全部賦給自己的父節點，并消除自身節點。

圖6 N 叉樹結構的簡化實例

化簡結果如圖7 所示。

圖7 樹結構簡化后的結果

3.3 轉換算法實現

經過分解重組的樹結構可以很方便地按照后根次序的遍歷訪問各個節點，算法流程圖和最后編譯轉化結果如圖8、圖9 所示。

圖8 轉換算法流程圖

從編譯結果可以看出，該算法能較好地實現PLC功能塊圖到指令表的轉換，對每個節點進行一次掃描的原則，保證每個節點不重復掃描;編譯輸出的指令程序與西門子STEP-7 軟件編譯的一致，即可達到功能塊圖編譯的效果。與以往基于AOV 圖及二叉樹結構的算法相比，該算法給出了另外一種嶄新的思路，加快了編譯速度，節省了內存空間。實驗證明該算法是正確可行的，可以應對串并聯邏輯關系復雜、且有多重輸出的FBD 程序。

圖9 轉化后對應的指令表程序

目前，本研究在PC 機上已對16個基本邏輯指令(LD、LDN、O、ON、A、AN、S、R、N、P、=、NOT、LPS、LRD、LPP、END)、定時器(T)、計數器(C)、4個浮點數計算指令(ADD_R、SUB_R、MUL_R、DIV_R)和8個整數計算指令(ADD_I、SUB_I、MUL_I、DIV_I、ADD_DI、SUB_DI、MUL_DI、DIV_DI)進行了編譯。

4 結束語

本研究提出了將PLC 功能圖向N 叉樹型數據結構的轉化算法，即通過分解重組的方式生成IL 指令表語言，實驗結果驗證了算法的正確性，能夠將具有多重輸出的復雜控制邏輯功能塊圖轉換成指令表語句，提高了PLC 功能塊圖編譯轉換的效率。

本研究軟PLC 的開發系統帶有編譯和仿真運行的功能，用戶在編輯器中完成FBD 程序的編寫。相比之前文獻中的梯形圖向指令表轉化算法，本研究提出的一種基于分解重組的轉換思路，實現了FBD 功能塊向指令表的轉換，在面對具有復雜邏輯關系的FBD 程序時，本研究算法簡化了轉化的過程、節省更多的空間、提高了編譯的效率和準確性，也為后續研究軟PLC運行系統打下了良好的基礎。

［1］IEC61131-3 Programmable controller-part3［Z］.programming languages，International Electrotechnieal Commission，1993.

［2］Zhou QingguoYang，Xuhui Han，Genliang Yang，et al.An Embedded Control System Designed Based on Soft PLC［J］.Multimedia and Ubiquitous Engineering，2014，308:115-120.

［3］葛 芬，吳 寧.基于AOV 圖及二叉樹的梯形圖與指令表互換算法［J］.南京航空航天大學學報，2006，38(6):754-758.

［4］傅 亮，胡飛虎，劉 樂，等.基于串并聯歸并的PLC 梯形圖向指令表轉換算法［J］.計算機工程與應用，2009，45(27):72-74，118.

［5］潘庭龍，沈學芹，紀志成.基于AOV 圖及因果圖的梯形圖與語句表互換算法［J］.測控技術，2008，11:64-66.

［6］朱兆斌，趙東標.軟PLC 中梯形圖向指令表轉化的實現［J］.機械與電子，2008，12:61-64.

［7］張愛民，蔣 剛，張連原，等.軟PLC 的設計思想在0 繼電保護裝置中的應用［J］.高壓電器，2007(6):444-447.

［8］Nishant Doshi，Tarun Sureja，Bhavesh Akbari，et al.Width of a Binary Tree［J］.International ournal of Computer Applications，2010，9(2):41-43.

［9］林桂伍.多叉樹結構及其實現［J］.福州大學學報:自然科學版，1995，23(1):15-19.

［10］S.Olariu，M.Overstreet，Z.F.Wen.Reconstructing a Binary Tree from Its Traversals in Doubly Logarithmic CREW Time［J］.Journal of Parallel and Distributed Computing，1995，27(1):100-105.