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

    梯形圖是使用最多的圖形編輯語言,，被稱為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 AOV圖及其數(shù)據(jù)結(jié)構(gòu)
    AOV圖是一種用頂點(diǎn)表示活動(dòng)，用弧<i,，j>表示活動(dòng)i必須在活動(dòng)j之前完成的有向圖,，其中i稱為j的前驅(qū)，j稱為i的后繼,。
    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)指針堆棧——“與堆棧”和“或堆棧”,，分別用于保存二叉樹中的“與”和“或”節(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)從“與堆棧”中彈出“與”節(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。
    至此得到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。在“與堆棧”中查找VP：①若未找到,，則新建一個(gè)“與”節(jié)點(diǎn),，將其賦給P3，并將P3和VP壓入“與堆棧”中,。若P2的左子樹為空,，則將P3作為P2的左子樹，否則將P3作為P2的右子樹,。P4作為P3的左子樹,。將P4和NP壓入“或堆棧”中，并將NP的壓棧標(biāo)志stacked置位,，將P2賦給P4,。②若在“與堆棧”中找到VP,，則不新建“與”節(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)從“或堆棧”中彈出圖符頂點(diǎn)對(duì)象賦給P1,，再?gòu)棾龆鏄涔?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í)例。
參考文獻(xiàn)
[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.