張惠杰，林偉敏

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州350000)

梯形圖是使用最多的圖形編輯語言，被稱為PLC的第一編程語言。梯形圖以圖符的形式直觀地再現(xiàn)了各邏輯控件的電器連接關(guān)系,并用串、并聯(lián)等拓?fù)潢P(guān)系組織圖符的順序位置來表述邏輯。梯形圖形象直觀，但對(duì)于PLC來說是不可執(zhí)行代碼，無法直接運(yùn)行，需事先轉(zhuǎn)換成指令表。指令表是一系列符合IEC61131-3標(biāo)準(zhǔn)的指令的集合。對(duì)嵌入式PLC系統(tǒng)來說,研究梯形圖向語句表的轉(zhuǎn)換算法及其實(shí)現(xiàn)技術(shù)是必要的。PLC梯形圖轉(zhuǎn)換為指令表通常包括5個(gè)步驟[1]。參考文獻(xiàn)[1-3]對(duì)梯形圖存儲(chǔ)結(jié)構(gòu)、語法檢查的規(guī)則做了詳細(xì)介紹。但對(duì)梯形圖的編輯沒有限制，可任意繪制，從而導(dǎo)致處理復(fù)雜、語法檢查規(guī)則繁瑣。因此本文提出了直接以AOV圖對(duì)梯形圖進(jìn)行存儲(chǔ)的方法，編輯梯形圖的同時(shí)，進(jìn)行相應(yīng)的規(guī)則約束，動(dòng)態(tài)生成AOV圖。該過程將梯形圖編輯、語法檢查和AOV圖的生成同時(shí)完成，使常用的5個(gè)步驟縮短為3個(gè)，如圖1所示。該方法與常用方法相比更為簡(jiǎn)便、快捷。

圖1 PLC指令表生成過程

1 AOV圖及其數(shù)據(jù)結(jié)構(gòu)

AOV圖是一種用頂點(diǎn)表示活動(dòng)，用弧

PLC的梯形圖程序由若干圖符按一定的規(guī)則鏈接而成，其自上而下、自左向右的執(zhí)行方式本質(zhì)上就是一種AOV圖，因此本文直接將梯形圖中的圖符以AOV圖的結(jié)構(gòu)進(jìn)行存儲(chǔ)，其中橫線不存儲(chǔ)，豎線存儲(chǔ)為虛節(jié)點(diǎn)。如圖2中上圖為梯形圖，下圖為梯形圖在內(nèi)存中實(shí)際的存儲(chǔ)結(jié)構(gòu)。AOV圖中普通圖符有行和列兩個(gè)坐標(biāo)值，如X8(2，4)表示X8在梯形圖中第2列第4行。虛節(jié)點(diǎn)有3個(gè)坐標(biāo)值，分別表示虛節(jié)點(diǎn)的列坐標(biāo)、行起始坐標(biāo)和行結(jié)束坐標(biāo)，如 V3(2，1，3)表示該虛節(jié)點(diǎn)在第 2列，起始位置為第1行，結(jié)束位置為第3行，文中規(guī)定虛節(jié)點(diǎn)列坐標(biāo)的取值為其左邊相鄰位置的列坐標(biāo)。

所有頂點(diǎn)使用一個(gè)鏈表進(jìn)行存儲(chǔ)，訪問時(shí)對(duì)該鏈表進(jìn)行遍歷。

2 坐標(biāo)的更新

按照以上的對(duì)應(yīng)關(guān)系，對(duì)梯形圖進(jìn)行修改時(shí)，其實(shí)也就是對(duì)AOV圖進(jìn)行修改。對(duì)梯形圖的修改操作有很多：插入串聯(lián)節(jié)點(diǎn)、插入并聯(lián)節(jié)點(diǎn)、刪除串聯(lián)節(jié)點(diǎn)、刪除并聯(lián)節(jié)點(diǎn)、插入并聯(lián)分支、插入輸出分支等，如果對(duì)各種操作進(jìn)行分析，根據(jù)插入、刪除的各種不同情況更新AOV各個(gè)頂點(diǎn)的坐標(biāo)，處理復(fù)雜、繁瑣。因此本文提出一種直接通過AOV圖拓?fù)浣Y(jié)構(gòu)生成AOV圖各個(gè)頂點(diǎn)坐標(biāo)的算法。該算法只需對(duì)修改后的AOV圖重新進(jìn)行坐標(biāo)的生成，而無需理會(huì)具體的操作。算法的具體流程如下：

(1)申請(qǐng)一個(gè)存放AOV頂點(diǎn)的指針堆棧、當(dāng)前列坐標(biāo) CurrentX、當(dāng)前行坐標(biāo) CurrentY、臨時(shí)變量 x1、y1、x2、y2，AOV頂點(diǎn)指針為 P1、P2、P3， 并將 P1指向 AOV圖中入度為0的頂點(diǎn)。CurrentX初始化為0，CurrentY初始化為1；

(2)循環(huán)直到P1指向的節(jié)點(diǎn)的第一個(gè)后繼節(jié)點(diǎn)的列坐標(biāo)為11(文中描述的系統(tǒng)只提供11列的標(biāo)記，最后一列固定為輸出節(jié)點(diǎn)或功能塊)，循環(huán)過程中P1指向的節(jié)點(diǎn)如果為虛節(jié)點(diǎn)，則虛節(jié)點(diǎn)的列坐標(biāo)設(shè)置為CurrentX，更新標(biāo)記置位，若虛節(jié)點(diǎn)出度大于1，則將虛節(jié)點(diǎn)指針壓入堆棧中，P1指向虛節(jié)點(diǎn)的第一個(gè)出度；若P1指向的節(jié)點(diǎn)為圖符節(jié)點(diǎn)，則CurrentX加1，將該節(jié)點(diǎn)的列坐標(biāo)設(shè)置為CurrentX，行坐標(biāo)設(shè)置為CurrentY，更新標(biāo)記置位，P1指向圖符節(jié)點(diǎn)的后繼節(jié)點(diǎn)。

(3)從堆棧中取出棧頂指針賦給P1，循環(huán)直至堆棧為空。循環(huán)過程中進(jìn)行如下操作：①初始化變量：CurrentX設(shè)為P1指向虛節(jié)點(diǎn)的列坐標(biāo)，P2、P3取為P1所指向的虛節(jié)點(diǎn)的第一個(gè)坐標(biāo)未更新的后繼節(jié)點(diǎn)，若該虛節(jié)點(diǎn)除了P2指向的節(jié)點(diǎn)外仍有未更新的后繼節(jié)點(diǎn)，則將該虛節(jié)點(diǎn)的指針再次壓入堆棧。②獲取CurrentY的值：x1設(shè)為P1指向虛節(jié)點(diǎn)的列坐標(biāo)，y1設(shè)為P1指向虛節(jié)點(diǎn)的最后一個(gè)已更新過坐標(biāo)的后繼節(jié)點(diǎn)的行坐標(biāo)。如圖3中，若P1指向 V1，P2指向 X8，則 x1=0，y1=1。做如下循環(huán)操作：循環(huán)直至P2指向的節(jié)點(diǎn)為虛節(jié)點(diǎn)，且虛節(jié)點(diǎn)的第一個(gè)后繼的行坐標(biāo)小于等于y1時(shí)停止；循環(huán)中P2賦值為其指向節(jié)點(diǎn)的第一個(gè)后繼節(jié)點(diǎn)。循環(huán)結(jié)束后，將x2設(shè)為P2指向虛節(jié)點(diǎn)的列坐標(biāo)。仍以X8為例，最后P2指向V5時(shí)停止，x2=5。至此獲得(x1，x2)組成的區(qū)間。遍歷該區(qū)間內(nèi)已更新過坐標(biāo)的節(jié)點(diǎn)，并獲取這些節(jié)點(diǎn)中行坐標(biāo)的最大值，并將CurrentY設(shè)為該最大值加1。③更新該行直至P2指向虛節(jié)點(diǎn)之間的節(jié)點(diǎn)坐標(biāo)：此時(shí)P3指向P1所指向的虛節(jié)點(diǎn)的第一個(gè)坐標(biāo)未更新的后繼節(jié)點(diǎn)，循環(huán)直至P3指向的節(jié)點(diǎn)為P2指向的虛節(jié)點(diǎn)。循環(huán)過程中分以下幾種情況進(jìn)行處理：①若P3指向節(jié)點(diǎn)為圖符節(jié)點(diǎn)且其后繼也為圖符節(jié)點(diǎn)，則CurrentX+1，將該節(jié)點(diǎn)的列坐標(biāo)設(shè)置為CurrentX，行坐標(biāo)設(shè)置為 CurrentY，更新標(biāo)記置位，P3指向圖符節(jié)點(diǎn)的后繼節(jié)點(diǎn)；②若P3指向節(jié)點(diǎn)為圖符節(jié)點(diǎn)，且其后繼為與P3指向節(jié)點(diǎn)列坐標(biāo)相同的虛節(jié)點(diǎn)，說明已更新好坐標(biāo)的節(jié)點(diǎn)中需要插入一個(gè)新節(jié)點(diǎn)，某些坐標(biāo)需要向右移動(dòng)一個(gè)位置。此時(shí)需遍歷AOV圖的存儲(chǔ)鏈表，尋找列坐標(biāo)大于等于P3指向節(jié)點(diǎn)列坐標(biāo)的所有虛節(jié)點(diǎn)，將其列坐標(biāo)加1，并依次尋找這些虛節(jié)點(diǎn)的后繼節(jié)點(diǎn)，沿著這些后繼節(jié)點(diǎn)向右遍歷，直至虛節(jié)點(diǎn)停止，將找到的后繼節(jié)點(diǎn)列坐標(biāo)加1；③若P3指向節(jié)點(diǎn)為虛節(jié)點(diǎn)，則虛節(jié)點(diǎn)的列坐標(biāo)設(shè)置為CurrentX，更新標(biāo)記置位，若虛節(jié)點(diǎn)出度大于1，則將虛節(jié)點(diǎn)指針壓入堆棧中，P3指向虛節(jié)點(diǎn)的第一個(gè)出度。

3 AOV圖的編輯

不是所有的操作對(duì)AOV圖都是有效和正確的，因此首先對(duì)AOV圖的編輯進(jìn)行相應(yīng)的規(guī)則約束，以保證AOV圖擁有正確的拓?fù)浣Y(jié)構(gòu)，使最后生成的梯形圖符合標(biāo)準(zhǔn)，無語法錯(cuò)誤。

對(duì)梯形圖進(jìn)行一些全局約束：梯形圖中只提供11列元件編輯位置，最后一列固定為輸出線圈或功能塊。每個(gè)網(wǎng)絡(luò)建立之后默認(rèn)生成一個(gè)輸出線圈，參數(shù)待用戶修改。因?yàn)槊總€(gè)網(wǎng)絡(luò)都必須有一個(gè)輸出，其輸出為輸出線圈或功能塊。

對(duì)AOV圖（或稱梯形圖）的編輯只提供以下操作：添加串聯(lián)開關(guān)、添加并聯(lián)開關(guān)、添加輸出分支、刪除節(jié)點(diǎn)，能基本滿足編輯的需要。

4 指令表的生成

在完成了對(duì)AOV圖的編輯后，需要將AOV圖轉(zhuǎn)換成二叉樹，再對(duì)二叉樹進(jìn)行后續(xù)遍歷即可獲得指令表。參考文獻(xiàn)[4-6]提出的各種基于二叉樹的AOV圖轉(zhuǎn)換為指令表算法都無法適用于本文中的AOV圖，參考文獻(xiàn)[7]給出的方法無法適應(yīng)于虛節(jié)點(diǎn)出度或入度大于2的情況。本文對(duì)參考文獻(xiàn)[7]提出的算法進(jìn)行了修改，使其能適用于各種AOV圖向二叉樹的轉(zhuǎn)換。修改后的算法流程如圖4所示。

(1)創(chuàng)建兩個(gè)二叉樹節(jié)點(diǎn)指針堆?！芭c堆棧”和“或堆?！?，分別用于保存二叉樹中的“與”和“或”節(jié)點(diǎn)指針，并初始化兩個(gè)堆棧為空。二叉樹初始時(shí)為一個(gè)根節(jié)點(diǎn)Root，無左右子樹。申請(qǐng)圖符頂點(diǎn)指針P1和二叉樹頂點(diǎn)指針P2，并將P1指向 AOV圖中入度為0的頂點(diǎn)，P2指向 Root。

(2)從“與堆?！敝袕棾觥芭c”節(jié)點(diǎn)指針，并賦給 P2。

(3)創(chuàng)建一個(gè)“與”節(jié)點(diǎn)，并賦給 P3，如果 P2的左子樹為空，則將 P3指向節(jié)點(diǎn)作為 P2的左子樹，否則將 P3指向的節(jié)點(diǎn)作為P2的右子樹。P1所指向的節(jié)點(diǎn)作為P3的左子樹。P2新指向P3。

新建一個(gè)臨時(shí)AOV圖頂點(diǎn)指針堆棧stack，申請(qǐng)一個(gè)臨時(shí)頂點(diǎn)指針tp，從P1所指頂點(diǎn)的第二個(gè)后繼開始，做如下操作，直至最后一個(gè)后繼：設(shè)當(dāng)前為第OutNum個(gè)后繼，將tp指向該后繼。tp沿其第一個(gè)后繼尋找起始行坐標(biāo)小于等于P2的第OutNum-1個(gè)后繼行坐標(biāo)的虛節(jié)點(diǎn)，找到后停止。找到時(shí)如果stack為空，則將P1的第OutNum個(gè)后繼和 tp壓入 stack；當(dāng) stack不為空時(shí)，如果tp指向的虛節(jié)點(diǎn)列坐標(biāo)大于等于stack的堆頂?shù)闹羔標(biāo)赶虻奶摴?jié)點(diǎn)的列坐標(biāo)，則將P1的第OutNum個(gè)出度和tp壓入 stack。

圖4 AOV圖轉(zhuǎn)換為二叉樹流程圖

至此得到P1指向虛節(jié)點(diǎn)后繼的執(zhí)行順序，越靠近stack堆頂?shù)捻旤c(diǎn)越后執(zhí)行。根據(jù)該stack建立“與”和“或”節(jié)點(diǎn)：從stack彈出一個(gè)圖符頂點(diǎn)和一個(gè)虛節(jié)點(diǎn)，分別賦給NP和VP。新建一個(gè)“或”節(jié)點(diǎn)，將其賦給P4。在“與堆?！敝胁檎襐P：①若未找到，則新建一個(gè)“與”節(jié)點(diǎn)，將其賦給 P3，并將 P3和 VP壓入“與堆?！敝?。若 P2的左子樹為空，則將P3作為 P2的左子樹，否則將 P3作為 P2的右子樹。P4作為P3的左子樹。將P4和NP壓入“或堆?！敝校P的壓棧標(biāo)志stacked置位，將P2賦給P4。②若在“與堆?！敝姓业絍P，則不新建“與”節(jié)點(diǎn)，若 P2的左子樹為空，則將 P4作為 P2的左子樹，否則將 P4作為P2的右子樹，并將 P4和 NP壓入“或堆?！敝校瑢?NP的壓棧標(biāo)志 stacked置位，將 P2賦給 P4。

循環(huán)以上操作，直至stack為空。再將P1新指向當(dāng)前P1所指頂點(diǎn)的第一個(gè)出度。

(4)從“或堆?！敝袕棾鰣D符頂點(diǎn)對(duì)象賦給 P1，再彈出二叉樹節(jié)點(diǎn)對(duì)象賦給P2；查找沿P1的支路上未建立“與”、“或”節(jié)點(diǎn)的后繼，并為其建立“與”、“或”節(jié)點(diǎn)。

將P1的前驅(qū)賦給VP，計(jì)算P1在VP后繼中的序號(hào)，記為OutNum。接下來的過程與步驟(3)類似，只是操作從VP的第OutNum+1個(gè)后繼開始，直至第一個(gè)已入棧的后繼結(jié)束，且P1也不指向頂點(diǎn)的第一個(gè)出度。這里不再詳述。

(5)創(chuàng)建一個(gè)“與”節(jié)點(diǎn)，并將該節(jié)點(diǎn)賦給 P3；若 P2節(jié)點(diǎn)的左子樹為空，則將P3指向的節(jié)點(diǎn)作為P2的左子樹，否則將P3指向的節(jié)點(diǎn)作為P2的右子樹；然后將P1指向的節(jié)點(diǎn)作為P3的左子樹，并使P2指向P3對(duì)應(yīng)的節(jié)點(diǎn)，P1新指向當(dāng)前P1所指頂點(diǎn)的后繼。因?yàn)槌龆刃∮?，所以只有一個(gè)或沒有后繼。

圖5給出了該算法的具體實(shí)例。圖5(a)為顯示時(shí)所看到的梯形圖程序，圖5(b)為內(nèi)存中實(shí)際的存儲(chǔ)結(jié)構(gòu)，圖5(c)為按上述算法生成的二叉樹。將圖5(c)中二叉樹的輸出節(jié)點(diǎn)及其父節(jié)點(diǎn)去除，再去除二叉樹中多余的與節(jié)點(diǎn)和虛節(jié)點(diǎn)則得到圖5(d)中的二叉樹，對(duì)其進(jìn)行后序遍歷即可得到圖5(e)中的指令表。

本文提出了一種直接編輯AOV圖的方法來編輯PLC梯形圖，以AOV圖的數(shù)據(jù)結(jié)構(gòu)直接存儲(chǔ)PLC梯形圖，省去了PLC向AOV圖的轉(zhuǎn)換過程，且使PLC繪制過程更加便捷、規(guī)范。文中提出的AOV圖坐標(biāo)更新算法簡(jiǎn)化了AOV圖的各種編輯情況，使其只需考慮AOV圖的結(jié)構(gòu)變化，而無需對(duì)節(jié)點(diǎn)坐標(biāo)的變化進(jìn)行瑣碎的處理。最后文中對(duì)AOV圖生成二叉樹的算法進(jìn)行了修改，使其可適用于各種AOV圖向二叉樹的轉(zhuǎn)換，并給出了具體的轉(zhuǎn)換實(shí)例。

[1]俞鋒達(dá).PLC編程軟件的設(shè)計(jì)與下位機(jī)的仿真與實(shí)現(xiàn)[D].南京：東南大學(xué)，2008.

[2]保慧.PLC圖形化編程系統(tǒng)的研究與實(shí)現(xiàn)[D].南京：東南大學(xué)，2008.

[3]葛芬.水電自動(dòng)化監(jiān)控系統(tǒng)中PLC編程工具軟件的設(shè)計(jì)與實(shí)現(xiàn)[D].南京：南京航空航天大學(xué)，2006.

[4]崔小樂，周卓岑.可編程控制器的梯形圖語言與語句表語言的互換算法[J].微電子學(xué)與計(jì)算機(jī)，2000，16(l)：26-30.

[5]譚錦潔，程良鴻.嵌入式PLC中梯形圖到AOV圖的映射[J].計(jì)算機(jī)測(cè)量與控制，2004，12(10)：993-995.

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

[7]葛芬，吳寧.基于AOV圖及二叉樹的梯形圖與指令表互換算法[J].南京航空航天大學(xué)學(xué)報(bào)，2006，38(6)：754-758.