PLC 多線圈梯形圖向指令表的轉換算法

施昊言 王庭有

（昆明理工大學機電工程學院）

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

文獻［3，4］提出拓撲排序算法，實現過程簡單，但處理較復雜的梯形圖時精度不夠。 文獻［5］將梯形圖抽象為二叉樹， 遍歷樹即可得到指令表；文獻［6］在文獻［5］的基礎上進行改進，將梯形圖抽象為多叉樹， 算法減少了邏輯結點的個數，較二叉樹法有很大改進，但二者在處理復雜梯形圖時效率不高。 文獻［7］用雙向鏈表存儲梯形圖。文獻［8，9］用目標樹處理邏輯關系。但以上方法都未解決多線圈輸出問題。 文獻［10］在處理多輸出時將梯形圖劃分為多個帶有單個輸出線圈的子網絡，但效率不高。 總的來看，目前已有算法主要有以下缺陷：

a. 算法過程主要針對特定數據結構操作，沒有給出將梯形圖保存為該類數據結構的方法；

b. 大多算法無邏輯錯誤檢測功能，出現語法問題時不能發出警告， 需編程人員自行檢查，增加了人工成本；

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

筆者就以上技術難點和已有算法的不足，提出一種新的轉換算法，不但能在多輸出情況下進行語言轉換，也能實現自動檢測邏輯錯誤。

1 轉換算法的基本思想

1.1 梯形圖的存儲

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

為提高轉換效率，將梯形圖中的元件和連接線都當作對象存儲：為每個對象分配ID，其左右端口再分別分配端口號，左端口為L，右端口為R；再存儲該元件的類型以及與之左右端口相連的元件ID，以及相連元件的端口［12］。 梯形圖的存儲過程如圖1所示，掃描梯形圖時，沿著連接線進行搜索即可。

圖1 梯形圖的存儲

1.2 AOV圖的數據結構

元件以類對象的形式存于內存中，將每一個元件對象轉換為圖的頂點結構，頂點信息如下：

再增加兩個頂點， 分別代表左母線和右母線，頂點編號為0和n+1。

1.3 AOV圖的存儲

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

圖2 十字鏈表結構

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

圖3 梯形圖

圖4 AOV圖

1.4 語法錯誤檢測

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

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

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

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

c. 掃描元件的端口，若出現有端口未與其他元件連接，則可判斷發生了斷路錯誤。

1.5 轉換過程

轉換過程可以分為6個步驟， 即創建輸出總結點、設置階級、插入虛結點、歸并結點、迭代生成最簡結構、掃描最簡結構生成指令表。

1.5.1 創建輸出總結點

在1.3節已將梯形圖轉換為十字鏈表存儲的有向圖。 為解決多線圈輸出問題，需在有向圖中添加輸出總結點。

輸出總結點，即距離所有輸出結點最近的公共結點，沿著該結點的出度方向能找到所有輸出結點，類似二叉樹里的最近公共父結點。 創建輸出總結點的方法是，在創建有向圖階段統計出輸出標志位為1的結點個數n，搜索輸出結點入邊表得到結點vi（vi是vj的前驅結點，vj是vi的后繼節點），沿著vi出度方向搜索，若能搜索到n個輸出結點，則在vi出度方向建立一個后繼結點，即為輸出總結點（為區別于其他結點，設置該結點的編號為-1）， 若不能則繼續搜索vi的入邊表內的結點，重復此過程，直到找到第1個滿足要求的結點，如圖5所示。

圖5 輸出總結點的確定

1.5.2 設置階級

從左往右為每個結點設置階級， 以保證并聯歸并時只在同級別進行，防止并聯誤判，步驟如下：

a. 初始化結點階級，令所有結點階級都為0，然后搜索編號為0的結點即左母線結點， 該結點的階級li=0，將它放入隊列中。

b. 彈出隊頭元素結點vi， 掃描結點vi出邊表，得到結點vj，若該結點非右母線（編號n+1），將vj插入隊尾，如果vj的階級lj

圖6 設置階級

1.5.3 插入虛結點

對各元件設置階級后，相連元件間可能出現跳級情況，即vi結點的級別為5，與之相連的后繼結點vj級別為7，中間缺失一級。 為保證同級并聯，同時在并聯過程中檢測短路問題， 需插入虛結點。 在并聯歸并時如果出現虛結點與其他結點并聯的情況則產生短路錯誤。 為區別其他結點，設置虛結點編號為小于-1的負整數，這里的虛結點為-2和-3（圖7）。

圖7 插入虛結點

插入方法如下：

a. 將左母線結點放入隊列。

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

1.5.4 歸并結點

根據各結點的出度、入度和元件類型進行串并聯歸并，并聯歸并步驟如下：

a. 確定掃描最大階級數lmax和最小階數lmin，其中lmin=0，lmax為右母線結點階級數。

b. 掃描階級為li（lmin≤li

圖8 并聯歸并

c. 搜索所有得到的復合結點，若復合結點中出現小于-1的指令數，說明有短路問題。

由于虛結點是額外添加的，其本質還是一條連接線，所以當出現一個結點與虛結點發生并聯歸并時，即表示圖中有一條連接線與元件發生并聯，判斷發生了短路錯誤。 并聯歸并結束后，進行串聯歸并，步驟如下：

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

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

圖9 串聯歸并

圖10 最簡結構

1.5.6 生成指令表

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

圖11 指令表

圖12 算法流程

2 算法驗證

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

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

圖13 軟件編輯梯形圖

圖14 轉換算法的軟件測試結果

3 時間復雜度分析

首先設AOV圖有V個頂點和E條弧，在創建輸出總結點階段， 最好情況是輸出結點前的第1個結點即為總結點，復雜度為O（1），在最壞的特殊情況下為O（V+E）。 在設置階級和插入虛結點時，分別都需要搜索一次，均為O（V+E）。

有向圖中存在直接后繼結點數最多的結點，如果其出度為A， 并聯階段最好情況是只有1個，復雜度為O（A），如果全部結點都滿足，則并聯時復雜度為O（A2）；在串聯階段，符合串聯關系的結點有B對，得到串聯的復雜度為O（B）。

若串并聯的關系較為清晰， 并聯結點少，層次淺，總時間復雜度最好情況為O（1+2V+2E+A+B），其中A+B+1遠小于V+E，故時間復雜度趨近于O（V+E）。 當并聯結點很多，串并聯混合程度很高，這時復雜度為O（3E+3V+A2+B），A與V數量級相同，為O（V2）。

相較于傳統算法，最好的情況下，時間復雜度趨近相同，在轉換復雜邏輯關系圖時，傳統算法復雜度會優于本算法。 但傳統方法在處理復雜結構圖時，由于算法缺陷，容易產生轉換錯誤，如在處理多個元件并聯時，會無法正確判斷元件的串并聯關系，也無法檢測短路的邏輯錯誤，不能對多輸出結構進行轉換等［15］。

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

4 結束語

為解決復雜多輸出結構下的轉換問題，筆者提出新的轉換算法，用十字鏈表存儲圖，不必再添加輔助結點。 插入輸出總結點解決了多線圈輸出問題， 設置階級保證并聯只能發生在同階級，插入虛結點用于短路錯誤檢測，最后歸并結點生成復合結點簡化圖，生成元件邏輯關系，掃描最簡圖即可輸出指令表。 筆者提出的算法適用于各種PLC編程系統的開發，具有廣闊的應用前景。