摘 要： 提出一種直接以AOV(Activity On Vertex)圖存儲PLC(Programmable Logic Controller)梯形圖的方法。編輯梯形圖的同時，修改AOV圖，然后根據AOV圖的拓撲結構更新梯形圖圖符坐標，最后進行繪制顯示。該方法無需進行梯形圖向AOV圖的轉換，通過操作規則的約束來替代語法的檢查，使梯形圖的編輯更加便捷和規范。詳細介紹了AOV圖的編輯過程和坐標的更新算法。對AOV圖向二叉樹的轉換算法進行修改，使其能適應于所有AOV圖，并給出了相應的實例。
關鍵詞： 可編程邏輯控制器；梯形圖；AOV圖；指令表
梯形圖是使用最多的圖形編輯語言，被稱為PLC的第一編程語言。梯形圖以圖符的形式直觀地再現了各邏輯控件的電器連接關系, 并用串、并聯等拓撲關系組織圖符的順序位置來表述邏輯。梯形圖形象直觀，但對于PLC來說是不可執行代碼，無法直接運行，需事先轉換成指令表。指令表是一系列符合IEC61131-3標準的指令的集合。對嵌入式PLC系統來說, 研究梯形圖向語句表的轉換算法及其實現技術是必要的。PLC梯形圖轉換為指令表通常包括5個步驟[1]。參考文獻[1-3]對梯形圖存儲結構、語法檢查的規則做了詳細介紹。但對梯形圖的編輯沒有限制，可任意繪制，從而導致處理復雜、語法檢查規則繁瑣。因此本文提出了直接以AOV圖對梯形圖進行存儲的方法，編輯梯形圖的同時，進行相應的規則約束，動態生成AOV圖。該過程將梯形圖編輯、語法檢查和AOV圖的生成同時完成，使常用的5個步驟縮短為3個，如圖1所示。該方法與常用方法相比更為簡便、快捷。
1 AOV圖及其數據結構
AOV圖是一種用頂點表示活動，用弧<i，j>表示活動i必須在活動j之前完成的有向圖，其中i稱為j的前驅，j稱為i的后繼。
PLC的梯形圖程序由若干圖符按一定的規則鏈接而成，其自上而下、自左向右的執行方式本質上就是一種AOV圖，因此本文直接將梯形圖中的圖符以AOV圖的結構進行存儲，其中橫線不存儲，豎線存儲為虛節點。如圖2中上圖為梯形圖，下圖為梯形圖在內存中實際的存儲結構。AOV圖中普通圖符有行和列兩個坐標值，如X8(2，4)表示X8在梯形圖中第2列第4行。虛節點有3個坐標值，分別表示虛節點的列坐標、行起始坐標和行結束坐標，如V3(2，1，3)表示該虛節點在第2列，起始位置為第1行，結束位置為第3行，文中規定虛節點列坐標的取值為其左邊相鄰位置的列坐標。
所有頂點使用一個鏈表進行存儲，訪問時對該鏈表進行遍歷。
2 坐標的更新
按照以上的對應關系，對梯形圖進行修改時，其實也就是對AOV圖進行修改。對梯形圖的修改操作有很多：插入串聯節點、插入并聯節點、刪除串聯節點、刪除并聯節點、插入并聯分支、插入輸出分支等，如果對各種操作進行分析，根據插入、刪除的各種不同情況更新AOV各個頂點的坐標，處理復雜、繁瑣。因此本文提出一種直接通過AOV圖拓撲結構生成AOV圖各個頂點坐標的算法。該算法只需對修改后的AOV圖重新進行坐標的生成，而無需理會具體的操作。算法的具體流程如下：
(1)申請一個存放AOV頂點的指針堆棧、當前列坐標CurrentX、當前行坐標CurrentY、臨時變量x1、y1、x2、y2，AOV頂點指針為P1、P2、P3，并將P1指向AOV圖中入度為0的頂點。CurrentX初始化為0，CurrentY初始化為1；
(2)循環直到P1指向的節點的第一個后繼節點的列坐標為11(文中描述的系統只提供11列的標記，最后一列固定為輸出節點或功能塊)，循環過程中P1指向的節點如果為虛節點，則虛節點的列坐標設置為CurrentX，更新標記置位，若虛節點出度大于1，則將虛節點指針壓入堆棧中，P1指向虛節點的第一個出度；若P1指向的節點為圖符節點，則CurrentX加1，將該節點的列坐標設置為CurrentX，行坐標設置為CurrentY，更新標記置位，P1指向圖符節點的后繼節點。
(3)從堆棧中取出棧頂指針賦給P1，循環直至堆棧為空。循環過程中進行如下操作：①初始化變量：CurrentX設為P1指向虛節點的列坐標，P2、P3取為P1所指向的虛節點的第一個坐標未更新的后繼節點，若該虛節點除了P2指向的節點外仍有未更新的后繼節點，則將該虛節點的指針再次壓入堆棧。②獲取CurrentY的值：x1設為P1指向虛節點的列坐標，y1設為P1指向虛節點的最后一個已更新過坐標的后繼節點的行坐標。如圖3中，若P1指向V1，P2指向X8，則x1=0，y1=1。做如下循環操作：循環直至P2指向的節點為虛節點，且虛節點的第一個后繼的行坐標小于等于y1時停止；循環中P2賦值為其指向節點的第一個后繼節點。循環結束后，將x2設為P2指向虛節點的列坐標。仍以X8為例，最后P2指向V5時停止，x2=5。至此獲得(x1，x2)組成的區間。遍歷該區間內已更新過坐標的節點，并獲取這些節點中行坐標的最大值，并將CurrentY設為該最大值加1。③更新該行直至P2指向虛節點之間的節點坐標：此時P3指向P1所指向的虛節點的第一個坐標未更新的后繼節點，循環直至P3指向的節點為P2指向的虛節點。循環過程中分以下幾種情況進行處理：①若P3指向節點為圖符節點且其后繼也為圖符節點，則CurrentX+1，將該節點的列坐標設置為CurrentX，行坐標設置為CurrentY，更新標記置位，P3指向圖符節點的后繼節點；②若P3指向節點為圖符節點，且其后繼為與P3指向節點列坐標相同的虛節點，說明已更新好坐標的節點中需要插入一個新節點，某些坐標需要向右移動一個位置。此時需遍歷AOV圖的存儲鏈表，尋找列坐標大于等于P3指向節點列坐標的所有虛節點，將其列坐標加1，并依次尋找這些虛節點的后繼節點，沿著這些后繼節點向右遍歷，直至虛節點停止，將找到的后繼節點列坐標加1；③若P3指向節點為虛節點，則虛節點的列坐標設置為CurrentX，更新標記置位，若虛節點出度大于1，則將虛節點指針壓入堆棧中，P3指向虛節點的第一個出度。
3 AOV圖的編輯
不是所有的操作對AOV圖都是有效和正確的，因此首先對AOV圖的編輯進行相應的規則約束，以保證AOV圖擁有正確的拓撲結構，使最后生成的梯形圖符合標準，無語法錯誤。
對梯形圖進行一些全局約束：梯形圖中只提供11列元件編輯位置，最后一列固定為輸出線圈或功能塊。每個網絡建立之后默認生成一個輸出線圈，參數待用戶修改。因為每個網絡都必須有一個輸出，其輸出為輸出線圈或功能塊。
對AOV圖（或稱梯形圖）的編輯只提供以下操作：添加串聯開關、添加并聯開關、添加輸出分支、刪除節點，能基本滿足編輯的需要。
4 指令表的生成
在完成了對AOV圖的編輯后，需要將AOV圖轉換成二叉樹，再對二叉樹進行后續遍歷即可獲得指令表。參考文獻[4-6]提出的各種基于二叉樹的AOV圖轉換為指令表算法都無法適用于本文中的AOV圖，參考文獻[7]給出的方法無法適應于虛節點出度或入度大于2的情況。本文對參考文獻[7]提出的算法進行了修改，使其能適用于各種AOV圖向二叉樹的轉換。修改后的算法流程如圖4所示。
(1)創建兩個二叉樹節點指針堆棧——“與堆棧”和“或堆棧”，分別用于保存二叉樹中的“與”和“或”節點指針，并初始化兩個堆棧為空。二叉樹初始時為一個根節點Root，無左右子樹。申請圖符頂點指針P1和二叉樹頂點指針P2，并將P1指向AOV圖中入度為0的頂點，P2指向Root。
(2)從“與堆棧”中彈出“與”節點指針，并賦給P2。
(3)創建一個“與”節點，并賦給P3，如果P2的左子樹為空，則將P3指向節點作為P2的左子樹，否則將P3指向的節點作為P2的右子樹。P1所指向的節點作為P3的左子樹。P2新指向P3。
新建一個臨時AOV圖頂點指針堆棧stack，申請一個臨時頂點指針tp，從P1所指頂點的第二個后繼開始，做如下操作，直至最后一個后繼： 設當前為第OutNum個后繼，將tp指向該后繼。tp沿其第一個后繼尋找起始行坐標小于等于P2的第OutNum-1個后繼行坐標的虛節點，找到后停止。找到時如果stack為空，則將P1的第OutNum個后繼和tp壓入stack；當stack不為空時，如果tp指向的虛節點列坐標大于等于stack的堆頂的指針所指向的虛節點的列坐標，則將P1的第OutNum個出度和tp壓入stack。
至此得到P1指向虛節點后繼的執行順序，越靠近stack堆頂的頂點越后執行。根據該stack建立“與”和“或”節點：從stack彈出一個圖符頂點和一個虛節點，分別賦給NP和VP。新建一個“或”節點，將其賦給P4。在“與堆棧”中查找VP：①若未找到，則新建一個“與”節點，將其賦給P3，并將P3和VP壓入“與堆棧”中。若P2的左子樹為空，則將P3作為P2的左子樹，否則將P3作為P2的右子樹。P4作為P3的左子樹。將P4和NP壓入“或堆棧”中，并將NP的壓棧標志stacked置位，將P2賦給P4。②若在“與堆棧”中找到VP，則不新建“與”節點，若P2的左子樹為空，則將P4作為P2的左子樹，否則將P4作為P2的右子樹，并將P4和NP壓入“或堆棧”中，將NP的壓棧標志stacked置位，將P2賦給P4。
循環以上操作，直至stack為空。再將P1新指向當前P1所指頂點的第一個出度。
(4)從“或堆棧”中彈出圖符頂點對象賦給P1，再彈出二叉樹節點對象賦給P2；查找沿P1的支路上未建立“與”、“或”節點的后繼，并為其建立“與”、“或”節點。
將P1的前驅賦給VP，計算P1在VP后繼中的序號，記為OutNum。接下來的過程與步驟(3)類似，只是操作從VP的第OutNum+1個后繼開始，直至第一個已入棧的后繼結束，且P1也不指向頂點的第一個出度。這里不再詳述。
(5)創建一個“與”節點，并將該節點賦給P3；若P2節點的左子樹為空，則將P3指向的節點作為P2的左子樹，否則將P3指向的節點作為P2的右子樹；然后將P1指向的節點作為P3的左子樹，并使P2指向P3對應的節點，P1新指向當前P1所指頂點的后繼。因為出度小于2，所以只有一個或沒有后繼。
圖5給出了該算法的具體實例。圖5(a)為顯示時所看到的梯形圖程序，圖5(b)為內存中實際的存儲結構，圖5(c)為按上述算法生成的二叉樹。將圖5(c)中二叉樹的輸出節點及其父節點去除，再去除二叉樹中多余的與節點和虛節點則得到圖5(d)中的二叉樹，對其進行后序遍歷即可得到圖5(e)中的指令表。
本文提出了一種直接編輯AOV圖的方法來編輯PLC梯形圖，以AOV圖的數據結構直接存儲PLC梯形圖，省去了PLC向AOV圖的轉換過程，且使PLC繪制過程更加便捷、規范。文中提出的AOV圖坐標更新算法簡化了AOV圖的各種編輯情況，使其只需考慮AOV圖的結構變化，而無需對節點坐標的變化進行瑣碎的處理。最后文中對AOV圖生成二叉樹的算法進行了修改，使其可適用于各種AOV圖向二叉樹的轉換，并給出了具體的轉換實例。
參考文獻
[1] 俞鋒達.PLC編程軟件的設計與下位機的仿真與實現[D]. 南京：東南大學，2008.
[2] 保慧.PLC圖形化編程系統的研究與實現[D].南京：東南大學，2008.
[3] 葛芬.水電自動化監控系統中PLC編程工具軟件的設計與實現[D]．南京：南京航空航天大學，2006.
[4] 崔小樂，周卓岑.可編程控制器的梯形圖語言與語句表語言的互換算法[J].微電子學與計算機，2000，16(l)：26-30.
[5] 譚錦潔，程良鴻.嵌入式PLC中梯形圖到AOV圖的映射[J].計算機測量與控制，2004，12(10)：993-995.
[6] 傅亮，胡飛虎，劉樂，等.基于串并聯歸并的PLC梯形圖向指令表轉換算法[J].計算機工程與應用，2009，45(27)：72-118.
[7] 葛芬，吳寧.基于AOV圖及二叉樹的梯形圖與指令表互換算法[J].南京航空航天大學學報，2006，38(6)：754-758.