摘  要： 提出一種直接以AOV(Activity On Vertex)圖存儲PLC(Programmable Logic Controller)梯形圖的方法。編輯梯形圖的同時，修改AOV圖，然后根據(jù)AOV圖的拓?fù)浣Y(jié)構(gòu)更新梯形圖圖符坐標(biāo)，最后進行繪制顯示。該方法無需進行梯形圖向AOV圖的轉(zhuǎn)換，通過操作規(guī)則的約束來替代語法的檢查，使梯形圖的編輯更加便捷和規(guī)范。詳細(xì)介紹了AOV圖的編輯過程和坐標(biāo)的更新算法。對AOV圖向二叉樹的轉(zhuǎn)換算法進行修改，使其能適應(yīng)于所有AOV圖，并給出了相應(yīng)的實例。
關(guān)鍵詞： 可編程邏輯控制器；梯形圖；AOV圖；指令表

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

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

    所有頂點使用一個鏈表進行存儲，訪問時對該鏈表進行遍歷。
2 坐標(biāo)的更新
    按照以上的對應(yīng)關(guān)系，對梯形圖進行修改時，其實也就是對AOV圖進行修改。對梯形圖的修改操作有很多：插入串聯(lián)節(jié)點、插入并聯(lián)節(jié)點、刪除串聯(lián)節(jié)點、刪除并聯(lián)節(jié)點、插入并聯(lián)分支、插入輸出分支等，如果對各種操作進行分析，根據(jù)插入、刪除的各種不同情況更新AOV各個頂點的坐標(biāo)，處理復(fù)雜、繁瑣。因此本文提出一種直接通過AOV圖拓?fù)浣Y(jié)構(gòu)生成AOV圖各個頂點坐標(biāo)的算法。該算法只需對修改后的AOV圖重新進行坐標(biāo)的生成，而無需理會具體的操作。算法的具體流程如下：
    (1)申請一個存放AOV頂點的指針堆棧、當(dāng)前列坐標(biāo)CurrentX、當(dāng)前行坐標(biāo)CurrentY、臨時變量x1、y1、x2、y2，AOV頂點指針為P1、P2、P3，并將P1指向AOV圖中入度為0的頂點。CurrentX初始化為0，CurrentY初始化為1；
    (2)循環(huán)直到P1指向的節(jié)點的第一個后繼節(jié)點的列坐標(biāo)為11(文中描述的系統(tǒng)只提供11列的標(biāo)記，最后一列固定為輸出節(jié)點或功能塊)，循環(huán)過程中P1指向的節(jié)點如果為虛節(jié)點，則虛節(jié)點的列坐標(biāo)設(shè)置為CurrentX，更新標(biāo)記置位，若虛節(jié)點出度大于1，則將虛節(jié)點指針壓入堆棧中，P1指向虛節(jié)點的第一個出度；若P1指向的節(jié)點為圖符節(jié)點，則CurrentX加1，將該節(jié)點的列坐標(biāo)設(shè)置為CurrentX，行坐標(biāo)設(shè)置為CurrentY，更新標(biāo)記置位，P1指向圖符節(jié)點的后繼節(jié)點。
    (3)從堆棧中取出棧頂指針賦給P1，循環(huán)直至堆棧為空。循環(huán)過程中進行如下操作：①初始化變量：CurrentX設(shè)為P1指向虛節(jié)點的列坐標(biāo)，P2、P3取為P1所指向的虛節(jié)點的第一個坐標(biāo)未更新的后繼節(jié)點，若該虛節(jié)點除了P2指向的節(jié)點外仍有未更新的后繼節(jié)點，則將該虛節(jié)點的指針再次壓入堆棧。②獲取CurrentY的值：x1設(shè)為P1指向虛節(jié)點的列坐標(biāo)，y1設(shè)為P1指向虛節(jié)點的最后一個已更新過坐標(biāo)的后繼節(jié)點的行坐標(biāo)。如圖3中，若P1指向V1，P2指向X8，則x1=0，y1=1。做如下循環(huán)操作：循環(huán)直至P2指向的節(jié)點為虛節(jié)點，且虛節(jié)點的第一個后繼的行坐標(biāo)小于等于y1時停止；循環(huán)中P2賦值為其指向節(jié)點的第一個后繼節(jié)點。循環(huán)結(jié)束后，將x2設(shè)為P2指向虛節(jié)點的列坐標(biāo)。仍以X8為例，最后P2指向V5時停止，x2=5。至此獲得(x1，x2)組成的區(qū)間。遍歷該區(qū)間內(nèi)已更新過坐標(biāo)的節(jié)點，并獲取這些節(jié)點中行坐標(biāo)的最大值，并將CurrentY設(shè)為該最大值加1。③更新該行直至P2指向虛節(jié)點之間的節(jié)點坐標(biāo)：此時P3指向P1所指向的虛節(jié)點的第一個坐標(biāo)未更新的后繼節(jié)點，循環(huán)直至P3指向的節(jié)點為P2指向的虛節(jié)點。循環(huán)過程中分以下幾種情況進行處理：①若P3指向節(jié)點為圖符節(jié)點且其后繼也為圖符節(jié)點，則CurrentX+1，將該節(jié)點的列坐標(biāo)設(shè)置為CurrentX，行坐標(biāo)設(shè)置為CurrentY，更新標(biāo)記置位，P3指向圖符節(jié)點的后繼節(jié)點；②若P3指向節(jié)點為圖符節(jié)點，且其后繼為與P3指向節(jié)點列坐標(biāo)相同的虛節(jié)點，說明已更新好坐標(biāo)的節(jié)點中需要插入一個新節(jié)點，某些坐標(biāo)需要向右移動一個位置。此時需遍歷AOV圖的存儲鏈表，尋找列坐標(biāo)大于等于P3指向節(jié)點列坐標(biāo)的所有虛節(jié)點，將其列坐標(biāo)加1，并依次尋找這些虛節(jié)點的后繼節(jié)點，沿著這些后繼節(jié)點向右遍歷，直至虛節(jié)點停止，將找到的后繼節(jié)點列坐標(biāo)加1；③若P3指向節(jié)點為虛節(jié)點，則虛節(jié)點的列坐標(biāo)設(shè)置為CurrentX，更新標(biāo)記置位，若虛節(jié)點出度大于1，則將虛節(jié)點指針壓入堆棧中，P3指向虛節(jié)點的第一個出度。

3 AOV圖的編輯
    不是所有的操作對AOV圖都是有效和正確的，因此首先對AOV圖的編輯進行相應(yīng)的規(guī)則約束，以保證AOV圖擁有正確的拓?fù)浣Y(jié)構(gòu)，使最后生成的梯形圖符合標(biāo)準(zhǔn)，無語法錯誤。
    對梯形圖進行一些全局約束：梯形圖中只提供11列元件編輯位置，最后一列固定為輸出線圈或功能塊。每個網(wǎng)絡(luò)建立之后默認(rèn)生成一個輸出線圈，參數(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é)點指針堆棧——“與堆棧”和“或堆棧”，分別用于保存二叉樹中的“與”和“或”節(jié)點指針，并初始化兩個堆棧為空。二叉樹初始時為一個根節(jié)點Root，無左右子樹。申請圖符頂點指針P1和二叉樹頂點指針P2，并將P1指向AOV圖中入度為0的頂點，P2指向Root。
    (2)從“與堆棧”中彈出“與”節(jié)點指針，并賦給P2。
    (3)創(chuàng)建一個“與”節(jié)點，并賦給P3，如果P2的左子樹為空，則將P3指向節(jié)點作為P2的左子樹，否則將P3指向的節(jié)點作為P2的右子樹。P1所指向的節(jié)點作為P3的左子樹。P2新指向P3。
    新建一個臨時AOV圖頂點指針堆棧stack，申請一個臨時頂點指針tp，從P1所指頂點的第二個后繼開始，做如下操作，直至最后一個后繼： 設(shè)當(dāng)前為第OutNum個后繼，將tp指向該后繼。tp沿其第一個后繼尋找起始行坐標(biāo)小于等于P2的第OutNum-1個后繼行坐標(biāo)的虛節(jié)點，找到后停止。找到時如果stack為空，則將P1的第OutNum個后繼和tp壓入stack；當(dāng)stack不為空時，如果tp指向的虛節(jié)點列坐標(biāo)大于等于stack的堆頂?shù)闹羔標(biāo)赶虻奶摴?jié)點的列坐標(biāo)，則將P1的第OutNum個出度和tp壓入stack。
    至此得到P1指向虛節(jié)點后繼的執(zhí)行順序，越靠近stack堆頂?shù)捻旤c越后執(zhí)行。根據(jù)該stack建立“與”和“或”節(jié)點：從stack彈出一個圖符頂點和一個虛節(jié)點，分別賦給NP和VP。新建一個“或”節(jié)點，將其賦給P4。在“與堆棧”中查找VP：①若未找到，則新建一個“與”節(jié)點，將其賦給P3，并將P3和VP壓入“與堆棧”中。若P2的左子樹為空，則將P3作為P2的左子樹，否則將P3作為P2的右子樹。P4作為P3的左子樹。將P4和NP壓入“或堆棧”中，并將NP的壓棧標(biāo)志stacked置位，將P2賦給P4。②若在“與堆棧”中找到VP，則不新建“與”節(jié)點，若P2的左子樹為空，則將P4作為P2的左子樹，否則將P4作為P2的右子樹，并將P4和NP壓入“或堆棧”中，將NP的壓棧標(biāo)志stacked置位，將P2賦給P4。
    循環(huán)以上操作，直至stack為空。再將P1新指向當(dāng)前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新指向當(dāng)前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圖坐標(biāo)更新算法簡化了AOV圖的各種編輯情況，使其只需考慮AOV圖的結(jié)構(gòu)變化，而無需對節(jié)點坐標(biāo)的變化進行瑣碎的處理。最后文中對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.