施昊言 王庭有

（昆明理工大學(xué)機(jī)電工程學(xué)院）

PLC是具有完善控制功能和數(shù)據(jù)處理功能的工業(yè)控制計(jì)算機(jī)， 其結(jié)構(gòu)緊湊且抗干擾能力強(qiáng)，在自控領(lǐng)域應(yīng)用廣泛，利用PLC可以快速、可靠、經(jīng)濟(jì)地構(gòu)建控制系統(tǒng)。PLC發(fā)展至今，其控制性能越來越穩(wěn)定［1］。為了滿足更加豐富的控制需求，還研發(fā)出嵌入式軟PLC技術(shù)， 利用軟件優(yōu)化了傳統(tǒng)PLC的不足之處，得以更加自由地組建控制系統(tǒng)［2］。指令表和梯形圖是PLC軟件的主要編程語言，二者間的相互轉(zhuǎn)換在編程軟件中是不可缺少的。 梯形圖語言形象直觀， 指令表語言編輯過程較復(fù)雜。 在處理數(shù)據(jù)時(shí)，由于指令表是直接對(duì)堆棧進(jìn)行操作，控制效率較高，并且計(jì)算機(jī)可以較容易地將其轉(zhuǎn)換為可運(yùn)行的機(jī)器語言， 因此大部分PLC編程系統(tǒng)都采用先將梯形圖轉(zhuǎn)換為指令表，再對(duì)指令表編譯執(zhí)行的方式來實(shí)現(xiàn)邏輯控制。

文獻(xiàn)［3，4］提出拓?fù)渑判蛩惴ǎ瑢?shí)現(xiàn)過程簡單，但處理較復(fù)雜的梯形圖時(shí)精度不夠。 文獻(xiàn)［5］將梯形圖抽象為二叉樹， 遍歷樹即可得到指令表；文獻(xiàn)［6］在文獻(xiàn)［5］的基礎(chǔ)上進(jìn)行改進(jìn)，將梯形圖抽象為多叉樹， 算法減少了邏輯結(jié)點(diǎn)的個(gè)數(shù)，較二叉樹法有很大改進(jìn)，但二者在處理復(fù)雜梯形圖時(shí)效率不高。 文獻(xiàn)［7］用雙向鏈表存儲(chǔ)梯形圖。文獻(xiàn)［8，9］用目標(biāo)樹處理邏輯關(guān)系。但以上方法都未解決多線圈輸出問題。 文獻(xiàn)［10］在處理多輸出時(shí)將梯形圖劃分為多個(gè)帶有單個(gè)輸出線圈的子網(wǎng)絡(luò)，但效率不高。 總的來看，目前已有算法主要有以下缺陷：

a. 算法過程主要針對(duì)特定數(shù)據(jù)結(jié)構(gòu)操作，沒有給出將梯形圖保存為該類數(shù)據(jù)結(jié)構(gòu)的方法；

b. 大多算法無邏輯錯(cuò)誤檢測(cè)功能，出現(xiàn)語法問題時(shí)不能發(fā)出警告， 需編程人員自行檢查，增加了人工成本；

c. 基本都是針對(duì)單輸出繼電器梯形圖的轉(zhuǎn)換，很少能處理多輸出情況下的轉(zhuǎn)換。

筆者就以上技術(shù)難點(diǎn)和已有算法的不足，提出一種新的轉(zhuǎn)換算法，不但能在多輸出情況下進(jìn)行語言轉(zhuǎn)換，也能實(shí)現(xiàn)自動(dòng)檢測(cè)邏輯錯(cuò)誤。

1 轉(zhuǎn)換算法的基本思想

1.1 梯形圖的存儲(chǔ)

目前的PLC編程環(huán)境基本采用網(wǎng)格實(shí)現(xiàn)圖元的添加和刪除，這種方法在編輯梯形圖時(shí)交互性較好［11］，但缺點(diǎn)也明顯。 由于網(wǎng)格大小固定，所以編輯較長的元件就需要占用多個(gè)網(wǎng)格，增加了元件存儲(chǔ)難度；而且在掃描梯形圖轉(zhuǎn)換為有向圖的過程中，需反復(fù)將元件和豎直連接線壓棧、出棧才能建立頂點(diǎn)連接生成AOV圖，過程復(fù)雜。

為提高轉(zhuǎn)換效率，將梯形圖中的元件和連接線都當(dāng)作對(duì)象存儲(chǔ)：為每個(gè)對(duì)象分配ID，其左右端口再分別分配端口號(hào)，左端口為L，右端口為R；再存儲(chǔ)該元件的類型以及與之左右端口相連的元件ID，以及相連元件的端口［12］。 梯形圖的存儲(chǔ)過程如圖1所示，掃描梯形圖時(shí)，沿著連接線進(jìn)行搜索即可。

圖1 梯形圖的存儲(chǔ)

1.2 AOV圖的數(shù)據(jù)結(jié)構(gòu)

元件以類對(duì)象的形式存于內(nèi)存中，將每一個(gè)元件對(duì)象轉(zhuǎn)換為圖的頂點(diǎn)結(jié)構(gòu)，頂點(diǎn)信息如下：

再增加兩個(gè)頂點(diǎn)， 分別代表左母線和右母線，頂點(diǎn)編號(hào)為0和n+1。

1.3 AOV圖的存儲(chǔ)

AOV圖的存儲(chǔ)結(jié)構(gòu)有鄰接表、 十字鏈表等。鄰接表容易得到每個(gè)頂點(diǎn)的出度，但要得到入度須遍歷整個(gè)圖［13］。 在筆者提出的轉(zhuǎn)換算法中，頂點(diǎn)出度、入度的使用頻率很高，采用十字鏈表結(jié)構(gòu)可以簡單地求出頂點(diǎn)的出度和入度，故采用十字鏈表存儲(chǔ)有向圖更能滿足需求，就不再需要為每個(gè)結(jié)點(diǎn)添加輔助結(jié)點(diǎn)，從而提升轉(zhuǎn)換效率。 十字鏈表的數(shù)據(jù)結(jié)構(gòu)如圖2所示， 其中，data存儲(chǔ)頂點(diǎn)數(shù)據(jù)，firstin為入邊表頭指針，firstout為出邊表頭指針，tailvex為弧起點(diǎn)編號(hào)，headvex為弧終點(diǎn)編號(hào)，headlink指向終點(diǎn)相同的弧，taillink指向起點(diǎn)相同的?。?4］。

圖2 十字鏈表結(jié)構(gòu)

在1.1節(jié)中已說明了梯形圖的存儲(chǔ)，通過掃描各元件ID和元件端口所存儲(chǔ)的相連元件ID，得到有向圖的頂點(diǎn)，并把這些頂點(diǎn)與代表左、右母線的兩個(gè)頂點(diǎn)相連，就可以將梯形圖（圖3）轉(zhuǎn)換為十字鏈表存儲(chǔ)的有向圖（圖4）。

圖3 梯形圖

圖4 AOV圖

1.4 語法錯(cuò)誤檢測(cè)

梯形圖的語法錯(cuò)誤通常有短路、斷路、電路只有輸出繼電器和電路只有輸入繼電器。

對(duì)于梯形圖語法錯(cuò)誤通常采用兩種方式檢測(cè)， 其中， 短路錯(cuò)誤無法與其他3種錯(cuò)誤一同檢測(cè)，需借助虛結(jié)點(diǎn)，因此將檢測(cè)任務(wù)放在后續(xù)歸并過程中進(jìn)行。 對(duì)斷路、電路只有輸出繼電器和電路只有輸入繼電器這3種錯(cuò)誤的檢測(cè)方法如下：

a. 掃描與左母線直接相連的LINE類型元件右端口，若該端口連接的元件的輸出標(biāo)志位為1，則可判斷發(fā)生了輸出元件直接與左母線相連的錯(cuò)誤；

b. 掃描與右母線直接相連的LINE類型元件左端口，若該端口連接的元件輸出標(biāo)志位為0，則可判斷發(fā)生了無輸出錯(cuò)誤；

c. 掃描元件的端口，若出現(xiàn)有端口未與其他元件連接，則可判斷發(fā)生了斷路錯(cuò)誤。

1.5 轉(zhuǎn)換過程

轉(zhuǎn)換過程可以分為6個(gè)步驟， 即創(chuàng)建輸出總結(jié)點(diǎn)、設(shè)置階級(jí)、插入虛結(jié)點(diǎn)、歸并結(jié)點(diǎn)、迭代生成最簡結(jié)構(gòu)、掃描最簡結(jié)構(gòu)生成指令表。

1.5.1 創(chuàng)建輸出總結(jié)點(diǎn)

在1.3節(jié)已將梯形圖轉(zhuǎn)換為十字鏈表存儲(chǔ)的有向圖。 為解決多線圈輸出問題，需在有向圖中添加輸出總結(jié)點(diǎn)。

輸出總結(jié)點(diǎn)，即距離所有輸出結(jié)點(diǎn)最近的公共結(jié)點(diǎn)，沿著該結(jié)點(diǎn)的出度方向能找到所有輸出結(jié)點(diǎn)，類似二叉樹里的最近公共父結(jié)點(diǎn)。 創(chuàng)建輸出總結(jié)點(diǎn)的方法是，在創(chuàng)建有向圖階段統(tǒng)計(jì)出輸出標(biāo)志位為1的結(jié)點(diǎn)個(gè)數(shù)n，搜索輸出結(jié)點(diǎn)入邊表得到結(jié)點(diǎn)vi（vi是vj的前驅(qū)結(jié)點(diǎn)，vj是vi的后繼節(jié)點(diǎn)），沿著vi出度方向搜索，若能搜索到n個(gè)輸出結(jié)點(diǎn)，則在vi出度方向建立一個(gè)后繼結(jié)點(diǎn)，即為輸出總結(jié)點(diǎn)（為區(qū)別于其他結(jié)點(diǎn)，設(shè)置該結(jié)點(diǎn)的編號(hào)為-1）， 若不能則繼續(xù)搜索vi的入邊表內(nèi)的結(jié)點(diǎn)，重復(fù)此過程，直到找到第1個(gè)滿足要求的結(jié)點(diǎn)，如圖5所示。

圖5 輸出總結(jié)點(diǎn)的確定

1.5.2 設(shè)置階級(jí)

從左往右為每個(gè)結(jié)點(diǎn)設(shè)置階級(jí)， 以保證并聯(lián)歸并時(shí)只在同級(jí)別進(jìn)行，防止并聯(lián)誤判，步驟如下：

a. 初始化結(jié)點(diǎn)階級(jí)，令所有結(jié)點(diǎn)階級(jí)都為0，然后搜索編號(hào)為0的結(jié)點(diǎn)即左母線結(jié)點(diǎn)， 該結(jié)點(diǎn)的階級(jí)li=0，將它放入隊(duì)列中。

b. 彈出隊(duì)頭元素結(jié)點(diǎn)vi， 掃描結(jié)點(diǎn)vi出邊表，得到結(jié)點(diǎn)vj，若該結(jié)點(diǎn)非右母線（編號(hào)n+1），將vj插入隊(duì)尾，如果vj的階級(jí)lj

圖6 設(shè)置階級(jí)

1.5.3 插入虛結(jié)點(diǎn)

對(duì)各元件設(shè)置階級(jí)后，相連元件間可能出現(xiàn)跳級(jí)情況，即vi結(jié)點(diǎn)的級(jí)別為5，與之相連的后繼結(jié)點(diǎn)vj級(jí)別為7，中間缺失一級(jí)。 為保證同級(jí)并聯(lián)，同時(shí)在并聯(lián)過程中檢測(cè)短路問題， 需插入虛結(jié)點(diǎn)。 在并聯(lián)歸并時(shí)如果出現(xiàn)虛結(jié)點(diǎn)與其他結(jié)點(diǎn)并聯(lián)的情況則產(chǎn)生短路錯(cuò)誤。 為區(qū)別其他結(jié)點(diǎn)，設(shè)置虛結(jié)點(diǎn)編號(hào)為小于-1的負(fù)整數(shù)，這里的虛結(jié)點(diǎn)為-2和-3（圖7）。

圖7 插入虛結(jié)點(diǎn)

插入方法如下：

a. 將左母線結(jié)點(diǎn)放入隊(duì)列。

b. 彈出隊(duì)頭結(jié)點(diǎn)vi，掃描結(jié)點(diǎn)出邊表，得到結(jié)點(diǎn)vj，如果不是右母線則將vj插入隊(duì)尾，如果lj-li=n>1，則插入虛結(jié)點(diǎn)vv，并設(shè)置vv的階級(jí)為li+1。直到隊(duì)列為空。

1.5.4 歸并結(jié)點(diǎn)

根據(jù)各結(jié)點(diǎn)的出度、入度和元件類型進(jìn)行串并聯(lián)歸并，并聯(lián)歸并步驟如下：

a. 確定掃描最大階級(jí)數(shù)lmax和最小階數(shù)lmin，其中l(wèi)min=0，lmax為右母線結(jié)點(diǎn)階級(jí)數(shù)。

b. 掃描階級(jí)為li（lmin≤li

圖8 并聯(lián)歸并

c. 搜索所有得到的復(fù)合結(jié)點(diǎn)，若復(fù)合結(jié)點(diǎn)中出現(xiàn)小于-1的指令數(shù)，說明有短路問題。

由于虛結(jié)點(diǎn)是額外添加的，其本質(zhì)還是一條連接線，所以當(dāng)出現(xiàn)一個(gè)結(jié)點(diǎn)與虛結(jié)點(diǎn)發(fā)生并聯(lián)歸并時(shí)，即表示圖中有一條連接線與元件發(fā)生并聯(lián)，判斷發(fā)生了短路錯(cuò)誤。 并聯(lián)歸并結(jié)束后，進(jìn)行串聯(lián)歸并，步驟如下：

a. 確定最大階級(jí)數(shù)lmax、最小階級(jí)數(shù)lmin和輸出總結(jié)點(diǎn)的階級(jí)lh，其中，lmin=0。 由于是多線圈輸出，最終轉(zhuǎn)換生成指令表時(shí)要使用輸出總結(jié)點(diǎn)，不能將輸出總結(jié)點(diǎn)與任何結(jié)點(diǎn)發(fā)生串聯(lián)歸并。 故掃描結(jié)點(diǎn)時(shí)，不能掃描輸出總結(jié)點(diǎn)以及比輸出總結(jié)點(diǎn)級(jí)別低1級(jí)的結(jié)點(diǎn)，因此掃描階級(jí)li的范圍為（lmin

b. 掃描階級(jí)li的結(jié)點(diǎn)vli，若vli的出度為1，vli+1結(jié)點(diǎn)入度也為1，則串聯(lián)vli和vli+1生成復(fù)合結(jié)點(diǎn)。 串聯(lián)歸并得到的復(fù)合結(jié)點(diǎn)階級(jí)取li（圖9）。 若出現(xiàn)復(fù)合結(jié)點(diǎn)串聯(lián)歸并，需增加ANB關(guān)系。與虛結(jié)點(diǎn)的串聯(lián)，同樣是將虛結(jié)點(diǎn)看作連接線，串聯(lián)時(shí)只需刪除虛結(jié)點(diǎn)即可。1.5.5 迭代生成最簡結(jié)構(gòu)迭代上述過程直到剩下6部分（圖10）：左母線結(jié)點(diǎn)（階級(jí)為0）、左母線與輸出總結(jié)點(diǎn)間的一個(gè)復(fù)合結(jié)點(diǎn)（階級(jí)為1）、輸出總結(jié)點(diǎn)（階級(jí)為2）、輸出總結(jié)點(diǎn)與輸出結(jié)點(diǎn)間的復(fù)合結(jié)點(diǎn)（階級(jí)為3）、各輸出結(jié)點(diǎn)（階級(jí)為4）、右母線結(jié)點(diǎn)（階級(jí)為5）。

圖9 串聯(lián)歸并

圖10 最簡結(jié)構(gòu)

1.5.6 生成指令表

輸出總結(jié)點(diǎn)前的指令表通過掃描級(jí)別為1的復(fù)合結(jié)點(diǎn)得到，當(dāng)輸出線圈數(shù)量n大于1，需要在輸出復(fù)合結(jié)點(diǎn)的指令后添加MPS入棧指令， 然后掃描輸出總結(jié)點(diǎn)的任意一個(gè)后繼結(jié)點(diǎn)輸出指令表，當(dāng)輸出標(biāo)志位為1的元件被輸出，返回輸出總結(jié)點(diǎn)，繼續(xù)掃描輸出總結(jié)點(diǎn)的剩余后繼結(jié)點(diǎn)輸出指令表。 當(dāng)已經(jīng)輸出n-1個(gè)輸出線圈指令后，需添加MPP出棧指令， 再掃描最后一個(gè)輸出總結(jié)點(diǎn)的后繼結(jié)點(diǎn)， 直到所有后繼結(jié)點(diǎn)都被掃描完畢，生成的指令表如圖11，算法的總流程如圖12所示。

圖11 指令表

圖12 算法流程

2 算法驗(yàn)證

為驗(yàn)證算法的可行性，根據(jù)算法開發(fā)的編程軟件如圖13、14所示。 該軟件基于圖形用戶界面研發(fā)軟件Qt開發(fā)，主要由梯形圖編輯界面和指令表編輯界面構(gòu)成，根據(jù)菜單欄的“梯形圖”按鈕和“指令表”按鈕切換界面。

根據(jù)圖3梯形圖進(jìn)行算法驗(yàn)證， 在梯形圖編輯界面完成梯形圖的程序編輯（圖13），點(diǎn)擊“指令表”按鈕完成界面切換與算法轉(zhuǎn)換，得到轉(zhuǎn)換后的指令表結(jié)果如圖14所示，轉(zhuǎn)換結(jié)果和理論預(yù)期結(jié)果一致。

圖13 軟件編輯梯形圖

圖14 轉(zhuǎn)換算法的軟件測(cè)試結(jié)果

3 時(shí)間復(fù)雜度分析

首先設(shè)AOV圖有V個(gè)頂點(diǎn)和E條弧，在創(chuàng)建輸出總結(jié)點(diǎn)階段， 最好情況是輸出結(jié)點(diǎn)前的第1個(gè)結(jié)點(diǎn)即為總結(jié)點(diǎn)，復(fù)雜度為O（1），在最壞的特殊情況下為O（V+E）。 在設(shè)置階級(jí)和插入虛結(jié)點(diǎn)時(shí)，分別都需要搜索一次，均為O（V+E）。

有向圖中存在直接后繼結(jié)點(diǎn)數(shù)最多的結(jié)點(diǎn)，如果其出度為A， 并聯(lián)階段最好情況是只有1個(gè)，復(fù)雜度為O（A），如果全部結(jié)點(diǎn)都滿足，則并聯(lián)時(shí)復(fù)雜度為O（A2）；在串聯(lián)階段，符合串聯(lián)關(guān)系的結(jié)點(diǎn)有B對(duì)，得到串聯(lián)的復(fù)雜度為O（B）。

若串并聯(lián)的關(guān)系較為清晰， 并聯(lián)結(jié)點(diǎn)少，層次淺，總時(shí)間復(fù)雜度最好情況為O（1+2V+2E+A+B），其中A+B+1遠(yuǎn)小于V+E，故時(shí)間復(fù)雜度趨近于O（V+E）。 當(dāng)并聯(lián)結(jié)點(diǎn)很多，串并聯(lián)混合程度很高，這時(shí)復(fù)雜度為O（3E+3V+A2+B），A與V數(shù)量級(jí)相同，為O（V2）。

相較于傳統(tǒng)算法，最好的情況下，時(shí)間復(fù)雜度趨近相同，在轉(zhuǎn)換復(fù)雜邏輯關(guān)系圖時(shí)，傳統(tǒng)算法復(fù)雜度會(huì)優(yōu)于本算法。 但傳統(tǒng)方法在處理復(fù)雜結(jié)構(gòu)圖時(shí)，由于算法缺陷，容易產(chǎn)生轉(zhuǎn)換錯(cuò)誤，如在處理多個(gè)元件并聯(lián)時(shí)，會(huì)無法正確判斷元件的串并聯(lián)關(guān)系，也無法檢測(cè)短路的邏輯錯(cuò)誤，不能對(duì)多輸出結(jié)構(gòu)進(jìn)行轉(zhuǎn)換等［15］。

在實(shí)際生產(chǎn)環(huán)境中，絕大部分梯形圖的邏輯關(guān)系并不復(fù)雜，該算法在復(fù)雜度上與傳統(tǒng)算法基本相同。 若有特殊需求，遇到非常復(fù)雜的圖，需要優(yōu)先保證轉(zhuǎn)換的正確性，傳統(tǒng)算法在處理時(shí)不能滿足要求，本算法能彌補(bǔ)缺陷，它既能保證轉(zhuǎn)換的正確性，又克服了多線圈的輸出問題，能夠較好地處理各種情況的轉(zhuǎn)換。

4 結(jié)束語

為解決復(fù)雜多輸出結(jié)構(gòu)下的轉(zhuǎn)換問題，筆者提出新的轉(zhuǎn)換算法，用十字鏈表存儲(chǔ)圖，不必再添加輔助結(jié)點(diǎn)。 插入輸出總結(jié)點(diǎn)解決了多線圈輸出問題， 設(shè)置階級(jí)保證并聯(lián)只能發(fā)生在同階級(jí)，插入虛結(jié)點(diǎn)用于短路錯(cuò)誤檢測(cè)，最后歸并結(jié)點(diǎn)生成復(fù)合結(jié)點(diǎn)簡化圖，生成元件邏輯關(guān)系，掃描最簡圖即可輸出指令表。 筆者提出的算法適用于各種PLC編程系統(tǒng)的開發(fā)，具有廣闊的應(yīng)用前景。