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

周 偉，張得禮

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

0 引言

所謂軟PLC 就是使用PC 機(jī)作為硬件支持平臺，使用軟件來實(shí)現(xiàn)傳統(tǒng)PLC 的基本功能，PLC 控制函數(shù)封裝在軟件中，運(yùn)行于PC 環(huán)境中?；赑C 的自動控制系統(tǒng)具有成本低、開放性好、易于使用等優(yōu)點(diǎn)，使它成為一個(gè)新的發(fā)展方向。根據(jù)PLC 的傳統(tǒng)結(jié)構(gòu)，軟PLC 系統(tǒng)分為兩部分，程序開發(fā)系統(tǒng)和運(yùn)行系統(tǒng)，其中運(yùn)行系統(tǒng)是軟PLC 技術(shù)的核心。

在IEC61131-3 標(biāo)準(zhǔn)中提供了5 種編程語言［1］，其中功能塊圖(FBD)是一種圖形化編程語言，相比于梯形圖語言，F(xiàn)BD 語言能夠更好地描述各個(gè)輸入觸點(diǎn)間的邏輯關(guān)系。使用功能塊圖編程語言不僅可以提高系統(tǒng)的可靠性，利于結(jié)構(gòu)化程序設(shè)計(jì)，且還能有效地實(shí)現(xiàn)程序代碼的復(fù)用，加速應(yīng)用程序的開發(fā)。

結(jié)合軟PLC 的設(shè)計(jì)思想，依據(jù)IEC61131-3 標(biāo)準(zhǔn)，本研究設(shè)計(jì)的Soft PLC 軟件平臺提供了功能塊圖(FBD)和指令語言(IL)兩種編程語言。編譯器則負(fù)責(zé)對編輯器中的功能塊圖和指令語言程序進(jìn)行編譯，實(shí)現(xiàn)從圖形語言到文字語言的轉(zhuǎn)化，最終生成二進(jìn)制目標(biāo)代碼。其中編譯轉(zhuǎn)化過程是程序開發(fā)中的關(guān)鍵。

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

文獻(xiàn)［3-4］介紹了由AOV 圖建立二叉樹，并對其進(jìn)行后序遍歷實(shí)現(xiàn)梯形圖與指令表程序轉(zhuǎn)換的算法，適用于串、并聯(lián)復(fù)雜的梯形圖，存在的不足是只能應(yīng)用單輸出的梯形圖網(wǎng)絡(luò)。文獻(xiàn)［5-6］將梯形圖轉(zhuǎn)化為AOV 圖，并利用AOV 圖建立因果圖，然后遍歷因果圖的節(jié)點(diǎn)生成PLC 所能識別的語句表，對于復(fù)雜的多輸出的梯形圖網(wǎng)絡(luò)也并不適用。

文獻(xiàn)［7］介紹了PLC 功能塊圖向指令表的轉(zhuǎn)換算法，采用樹結(jié)構(gòu)中的孩子兄弟表示法(又稱二叉鏈表表示法)來存儲每一個(gè)功能塊的數(shù)據(jù)和邏輯關(guān)系等信息，每一個(gè)功能塊圖都可以表示成一棵樹，對樹進(jìn)行一次遍歷，就得出了用戶程序?qū)?yīng)的IL 程序。但這并不通用，且不適用于串、并聯(lián)邏輯關(guān)系復(fù)雜和多重輸出的FBD 程序。

本研究針對軟PLC 多重輸出的問題，提出將FBD圖映射到N 叉樹型數(shù)據(jù)結(jié)構(gòu)，對N 叉樹進(jìn)行后序遍歷依次訪問各個(gè)節(jié)點(diǎn)，得到相應(yīng)IL 程序的算法。該算法適用于復(fù)雜的多輸出FBD 程序，采用分解重組的方式，將生成的復(fù)雜樹結(jié)構(gòu)分解成N個(gè)有序的樹結(jié)構(gòu)組合，然后對每個(gè)N個(gè)樹結(jié)構(gòu)進(jìn)行有序遍歷，生成IL 程序。該算法具有通用性，能提高PLC 解釋執(zhí)行的效率。

1 N 叉樹結(jié)構(gòu)及其遍歷方式

1.1 N 叉樹結(jié)構(gòu)

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

(1)且僅有一個(gè)稱為根(root)的結(jié)點(diǎn)，根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn);

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

1.2 N 叉樹的存儲表示

如果采用二叉樹的表示方法，則每個(gè)節(jié)點(diǎn)內(nèi)設(shè)置多少個(gè)指針子節(jié)點(diǎn)不好確定。若以整個(gè)樹中子節(jié)點(diǎn)最多的節(jié)點(diǎn)為準(zhǔn)給各節(jié)點(diǎn)設(shè)置指針，則大量指針為空，將浪費(fèi)存儲空間;若每個(gè)節(jié)點(diǎn)按其實(shí)際的子節(jié)點(diǎn)數(shù)設(shè)置指針，則各子節(jié)點(diǎn)數(shù)不相等，形式也不統(tǒng)一，這將給管理和操作帶來不便。因?yàn)镹 叉樹每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)沒有限制，其更為適合用來存儲復(fù)雜FBD 程序。

每一個(gè)CPTreeNode 節(jié)點(diǎn)之間的連接規(guī)律是:pNode_Parent 指針指向父節(jié)點(diǎn)的指針，pNode_FirstChild 指針指向第一個(gè)孩子節(jié)點(diǎn)的指針，pNode_Next-Brother 指針指向下一個(gè)兄弟節(jié)點(diǎn)的指針，m_TreeType保存節(jié)點(diǎn)本身的基本信息。

2 基于N 叉樹PLC 功能塊向指令表轉(zhuǎn)化算法

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

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

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

圖1 轉(zhuǎn)化前的N 叉樹結(jié)構(gòu)

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

無論是后根次序遍歷還是先根次序遍歷對于該樹結(jié)構(gòu)的所有子樹遍歷方式都是必須是相同的，當(dāng)出現(xiàn)要求所有子樹遍歷方式不盡相同的時(shí)候，傳統(tǒng)的單一遍歷算法就顯得力不從心。

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

圖2 轉(zhuǎn)化后的N 叉樹結(jié)構(gòu)

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

在同等運(yùn)行環(huán)境中，采用多次執(zhí)行取均值的方式，未采用分解算法的平均執(zhí)行時(shí)間為0.099 52 ms，采用分割組合后的平均執(zhí)行時(shí)間為0.099 62 ms，在程序執(zhí)行快慢方面大相近庭，但是前者在遍歷過程中使用了96 B的臨時(shí)變量空間，而采用分割組合后的算法只使用了60 B的臨時(shí)變量空間，因?yàn)樵诒闅v過程中，前者需要兩種方式的遍歷，而進(jìn)行分割重組后的樹結(jié)構(gòu)只需要一種方式就可以達(dá)到遍歷的要求，減少了程序代碼量上面的冗雜堆積。由此可見，當(dāng)節(jié)點(diǎn)數(shù)增多時(shí)，采用本研究算法可以簡化程序，節(jié)省更多的空間。

3 FBD 向IL 語句轉(zhuǎn)化算法設(shè)計(jì)

經(jīng)過多年的研究與發(fā)展，國內(nèi)外的PLC 產(chǎn)品及其編程平臺已相當(dāng)成熟，大多集成開發(fā)環(huán)境都包含了梯形圖與指令表程序互換的功能，相對較少涉及FBD 向指令表轉(zhuǎn)換算法。本研究采用樹結(jié)構(gòu)中的孩子兄弟表示法來存儲每一個(gè)功能塊的數(shù)據(jù)和邏輯關(guān)系等信息，每一個(gè)功能塊圖都可以表示成樹結(jié)構(gòu)的一個(gè)節(jié)點(diǎn)，通過依次查找的方式找到每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)、兄弟節(jié)點(diǎn)，再對樹進(jìn)行一次遍歷，就得出了用戶程序?qū)?yīng)的IL程序。

本研究設(shè)計(jì)的算法適用于串、并聯(lián)邏輯關(guān)系復(fù)雜、且具有多重輸出的FBD 程序，F(xiàn)BD 程序轉(zhuǎn)化實(shí)例如圖3 所示，筆者以如圖3 所示的FBD 程序?yàn)槔?yàn)證本研究算法的正確性。

圖3 FBD 程序轉(zhuǎn)化實(shí)例

3.1 基于N 叉樹結(jié)構(gòu)的FBD 模塊表達(dá)

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

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

圖4 CVerLine 類對象轉(zhuǎn)化方式

本研究在設(shè)計(jì)N 叉樹型數(shù)據(jù)結(jié)構(gòu)時(shí)采用上述的方式保存節(jié)點(diǎn)，圖3 中FBD 程序經(jīng)過轉(zhuǎn)換映射、分解重組產(chǎn)生的樹結(jié)構(gòu)如圖5 所示。

圖5 經(jīng)過分解重組后的N 叉樹結(jié)構(gòu)

3.2 N 叉樹結(jié)構(gòu)的簡化

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

N 叉樹結(jié)構(gòu)的簡化實(shí)例如圖6 所示。圖6 中存在一個(gè)AND 節(jié)點(diǎn)與其父節(jié)點(diǎn)類型相同，其表達(dá)的邏輯關(guān)系是完全正確的，但在向IL 指令表轉(zhuǎn)化中，為了簡化N 叉樹結(jié)構(gòu)，將其自己的所有孩子節(jié)點(diǎn)全部賦給自己的父節(jié)點(diǎn)，并消除自身節(jié)點(diǎn)。

圖6 N 叉樹結(jié)構(gòu)的簡化實(shí)例

化簡結(jié)果如圖7 所示。

圖7 樹結(jié)構(gòu)簡化后的結(jié)果

3.3 轉(zhuǎn)換算法實(shí)現(xiàn)

經(jīng)過分解重組的樹結(jié)構(gòu)可以很方便地按照后根次序的遍歷訪問各個(gè)節(jié)點(diǎn)，算法流程圖和最后編譯轉(zhuǎn)化結(jié)果如圖8、圖9 所示。

圖8 轉(zhuǎn)換算法流程圖

從編譯結(jié)果可以看出，該算法能較好地實(shí)現(xiàn)PLC功能塊圖到指令表的轉(zhuǎn)換，對每個(gè)節(jié)點(diǎn)進(jìn)行一次掃描的原則，保證每個(gè)節(jié)點(diǎn)不重復(fù)掃描;編譯輸出的指令程序與西門子STEP-7 軟件編譯的一致，即可達(dá)到功能塊圖編譯的效果。與以往基于AOV 圖及二叉樹結(jié)構(gòu)的算法相比，該算法給出了另外一種嶄新的思路，加快了編譯速度，節(jié)省了內(nèi)存空間。實(shí)驗(yàn)證明該算法是正確可行的，可以應(yīng)對串并聯(lián)邏輯關(guān)系復(fù)雜、且有多重輸出的FBD 程序。

圖9 轉(zhuǎn)化后對應(yīng)的指令表程序

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

4 結(jié)束語

本研究提出了將PLC 功能圖向N 叉樹型數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)化算法，即通過分解重組的方式生成IL 指令表語言，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的正確性，能夠?qū)⒕哂卸嘀剌敵龅膹?fù)雜控制邏輯功能塊圖轉(zhuǎn)換成指令表語句，提高了PLC 功能塊圖編譯轉(zhuǎn)換的效率。

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

［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］.南京航空航天大學(xué)學(xué)報(bào)，2006，38(6):754-758.

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

［5］潘庭龍，沈?qū)W芹，紀(jì)志成.基于AOV 圖及因果圖的梯形圖與語句表互換算法［J］.測控技術(shù)，2008，11:64-66.

［6］朱兆斌，趙東標(biāo).軟PLC 中梯形圖向指令表轉(zhuǎn)化的實(shí)現(xiàn)［J］.機(jī)械與電子，2008，12:61-64.

［7］張愛民，蔣 剛，張連原，等.軟PLC 的設(shè)計(jì)思想在0 繼電保護(hù)裝置中的應(yīng)用［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］林桂伍.多叉樹結(jié)構(gòu)及其實(shí)現(xiàn)［J］.福州大學(xué)學(xué)報(bào):自然科學(xué)版，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.