張惠杰，林偉敏

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

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

圖1 PLC指令表生成過程

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

AOV圖是一種用頂點表示活動，用弧

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

所有頂點使用一個鏈表進行存儲，訪問時對該鏈表進行遍歷。

2 坐標的更新

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

(1)申請一個存放AOV頂點的指針堆棧、當前列坐標 CurrentX、當前行坐標 CurrentY、臨時變量 x1、y1、x2、y2，AOV頂點指針為 P1、P2、P3， 并將 P1指向 AOV圖中入度為0的頂點。CurrentX初始化為0，CurrentY初始化為1；

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

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

3 AOV圖的編輯

不是所有的操作對AOV圖都是有效和正確的，因此首先對AOV圖的編輯進行相應(yīng)的規(guī)則約束，以保證AOV圖擁有正確的拓撲結(jié)構(gòu)，使最后生成的梯形圖符合標準，無語法錯誤。

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

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

4 指令表的生成

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

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

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

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

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

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

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

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

(4)從“或堆棧”中彈出圖符頂點對象賦給 P1，再彈出二叉樹節(jié)點對象賦給P2；查找沿P1的支路上未建立“與”、“或”節(jié)點的后繼，并為其建立“與”、“或”節(jié)點。

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

(5)創(chuàng)建一個“與”節(jié)點，并將該節(jié)點賦給 P3；若 P2節(jié)點的左子樹為空，則將P3指向的節(jié)點作為P2的左子樹，否則將P3指向的節(jié)點作為P2的右子樹；然后將P1指向的節(jié)點作為P3的左子樹，并使P2指向P3對應(yīng)的節(jié)點，P1新指向當前P1所指頂點的后繼。因為出度小于2，所以只有一個或沒有后繼。

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

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

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

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

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

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

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

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

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