基于多叉樹(shù)的梯形圖向指令表轉(zhuǎn)換算法

周偉強(qiáng)，何通能，陳德富

(浙江工業(yè)大學(xué) 信息工程學(xué)院，杭州 310023)

基于多叉樹(shù)的梯形圖向指令表轉(zhuǎn)換算法

周偉強(qiáng)，何通能，陳德富

(浙江工業(yè)大學(xué) 信息工程學(xué)院，杭州 310023)

針對(duì)目前可編程邏輯控制器(PLC)編輯軟件中梯形圖向指令表轉(zhuǎn)化算法的缺陷，通過(guò)對(duì)梯形圖語(yǔ)言的分析與研究，并考慮到梯形圖和指令表在實(shí)際應(yīng)用時(shí)的優(yōu)劣點(diǎn)，提出了一種借助多叉樹(shù)來(lái)實(shí)現(xiàn)PLC梯形圖向指令表轉(zhuǎn)換的算法;該算法采取從左至右，從上至下的掃描原則將梯形圖構(gòu)建成多叉樹(shù)，借助多叉樹(shù)來(lái)反應(yīng)圖符間的邏輯關(guān)系，然后通過(guò)后序遍歷多叉樹(shù)來(lái)得到指令表程序;此算法在處理多重串并聯(lián)結(jié)構(gòu)梯形圖時(shí)具有更高的效率，同時(shí)適用于堆棧指令，使得該算法具有更好的通用性。

可編程邏輯控制器;梯形圖;指令表;多叉樹(shù)

0 引言

可編程邏輯控制器即Programmable Logic Controller(以下簡(jiǎn)稱(chēng)PLC)，是一種專(zhuān)門(mén)為在工業(yè)環(huán)境下應(yīng)用而設(shè)計(jì)的現(xiàn)代化自動(dòng)控制設(shè)備[1]，廣泛應(yīng)用于各種類(lèi)型的控制系統(tǒng)中，主要功能包括控制、計(jì)數(shù)、數(shù)據(jù)采集和通信聯(lián)網(wǎng)等。

為了適應(yīng)廣大工程設(shè)計(jì)人員的編程習(xí)慣，國(guó)際電工委員會(huì)設(shè)計(jì)制定了PLC編程語(yǔ)言的標(biāo)準(zhǔn)——IEC 61131-3。該標(biāo)準(zhǔn)規(guī)定了PLC的編程語(yǔ)言包括梯形圖(LD)、指令表(IL)、功能模塊圖(FBD)、順序功能流程圖(SFC)和結(jié)構(gòu)化文本(ST)共五種。其中主要由母線(xiàn)、觸點(diǎn)和線(xiàn)圈等構(gòu)成的梯形圖簡(jiǎn)明易懂，使用梯形圖編寫(xiě)的PLC程序易于理解，從而使梯形圖成為PLC的主要編程語(yǔ)言[2]。但是，梯形圖只是形象得展示了電器元件之間的組合邏輯關(guān)系，無(wú)法被PLC識(shí)別并直接運(yùn)行，而PLC所能識(shí)別運(yùn)行的目標(biāo)代碼一般由指令表轉(zhuǎn)化而來(lái)。因此通過(guò)轉(zhuǎn)換算法將梯形圖轉(zhuǎn)換為指令表，并將其運(yùn)用在PLC上位開(kāi)發(fā)系統(tǒng)中，這樣就省去了人工對(duì)梯形圖的翻譯工作，提高了開(kāi)發(fā)的效率。

通過(guò)對(duì)梯形圖設(shè)計(jì)規(guī)則和指令表編程規(guī)則進(jìn)行的研究分析，并參考了傳統(tǒng)的拓?fù)渑判蚝投鏄?shù)遍歷等一系列算法的不足之后，提出了基于多叉樹(shù)的梯形圖向指令表轉(zhuǎn)換的算法。

1 梯形圖和指令表

梯形圖是以觸點(diǎn)符號(hào)代替?zhèn)鹘y(tǒng)電氣控制回路中的按鈕開(kāi)關(guān)、接觸器、繼電器觸點(diǎn)等部件的一種編程語(yǔ)言，是目前使用最多的一種PLC編程語(yǔ)言。其設(shè)計(jì)與編寫(xiě)梯形圖語(yǔ)言時(shí)應(yīng)注意以下規(guī)則：1)繼電器的觸點(diǎn)應(yīng)畫(huà)在橫線(xiàn)上，不可以畫(huà)在豎線(xiàn)上，繪制梯形圖時(shí)應(yīng)依照從左至右、從上至下的原則；2)沒(méi)有觸點(diǎn)的線(xiàn)路應(yīng)置于垂直方向，不能置于水平方向，這樣有利于分辨觸點(diǎn)的邏輯組合以及邏輯結(jié)果；3)依照左重右輕、上重下輕的原則，即出現(xiàn)若干串聯(lián)模塊并聯(lián)時(shí)應(yīng)將觸點(diǎn)最多的那條線(xiàn)路放在梯形圖的上方，而當(dāng)若干并聯(lián)模塊串聯(lián)時(shí)應(yīng)將觸點(diǎn)最多的那個(gè)并聯(lián)模塊放在梯形圖的左邊；4)線(xiàn)圈放在梯形圖的最右邊，觸點(diǎn)必須放在線(xiàn)圈的左邊[3]。

指令表也稱(chēng)為語(yǔ)句表，是一種助記符表達(dá)式，與匯編語(yǔ)言中的指令類(lèi)似。它將一系列操作指令(助記符)組成的控制流程，通過(guò)編程器存入PLC中[4]。指令表的每條指令是由操作碼和操作數(shù)兩部分組成的，操作碼是指令的助記符，操作數(shù)是功能指令所作用的數(shù)據(jù)，包括繼電器編號(hào)、定時(shí)器/計(jì)數(shù)器配置值和常數(shù)等。雖然梯形圖的優(yōu)點(diǎn)是形象、直觀、實(shí)用，為廣大電氣技術(shù)人員所接受，但是難以將其直接轉(zhuǎn)化為PLC能直接運(yùn)行的代碼，而指令表可以直接編譯為PLC的可執(zhí)行代碼。在PLC軟件的開(kāi)發(fā)過(guò)程中，實(shí)現(xiàn)梯形圖向指令表的轉(zhuǎn)換是必不可少的一部分，使得PLC軟件可以在最后通過(guò)對(duì)指令表的編譯或解釋執(zhí)行來(lái)實(shí)現(xiàn)PLC控制程序的運(yùn)行[5]。

目前已有一些文獻(xiàn)給出了梯形圖向指令表轉(zhuǎn)換的算法，如文獻(xiàn)[6]中先將梯形圖映射為AOV圖運(yùn)用了拓?fù)渑判蛩惴āＴ撍惴ǖ膬?yōu)點(diǎn)是有良好的算法效率，時(shí)間復(fù)雜度為O(n+e)，其中n表示AOV網(wǎng)頂點(diǎn)的個(gè)數(shù)，e表示弧的個(gè)數(shù)，但是該算法過(guò)于依賴(lài)梯形圖本身的圖符含義，當(dāng)梯形圖的串并聯(lián)關(guān)系較為復(fù)雜時(shí)轉(zhuǎn)化不穩(wěn)定，且存在誤判的可能，通用性較差。文獻(xiàn)[7]和文獻(xiàn)[8]提出了基于AOV網(wǎng)及二叉樹(shù)的轉(zhuǎn)換算法，該算法在處理串并聯(lián)結(jié)構(gòu)復(fù)雜的梯形圖時(shí)，借助二叉樹(shù)建立了過(guò)多的邏輯節(jié)點(diǎn)，占用了過(guò)多的空間，使得算法的遍歷效率也因此下降，同時(shí)該算法不適用于存在堆棧指令的梯形圖程序。文獻(xiàn)[9]中雖然借助串并聯(lián)歸并清晰地表示了梯形圖的層次，但并沒(méi)有提高遍歷的效率。

通過(guò)研究傳統(tǒng)轉(zhuǎn)換算法的缺陷與不足，從而提出了一種基于多叉樹(shù)的梯形圖向指令表轉(zhuǎn)換的算法，從左至右，從上至下掃描梯形圖，將梯形圖各元件之間的邏輯關(guān)系轉(zhuǎn)換為多叉樹(shù)數(shù)結(jié)構(gòu)，然后對(duì)多叉樹(shù)進(jìn)行后序遍歷得到指令表。該算法在多重串并聯(lián)梯形圖程序中，與使用二叉樹(shù)結(jié)構(gòu)相比，有效得減少了邏輯節(jié)點(diǎn)的個(gè)數(shù)，從而提升了算法效率，同時(shí)也適用于具有堆棧指令的梯形圖程序，使得該轉(zhuǎn)換算法具有更好的通用性，且不會(huì)出現(xiàn)傳統(tǒng)拓?fù)渑判蛩惴ㄖ写⒙?lián)誤判的情況。

2 多叉樹(shù)

樹(shù)是一些節(jié)點(diǎn)(node)的集合。這個(gè)集合可以是空集；若不是空集，則樹(shù)由稱(chēng)做根(root)的節(jié)點(diǎn)r以及0或多個(gè)非空的(子)樹(shù)T1，T2，…，Tk組成，這些子樹(shù)中每一棵的根都被來(lái)自根r的一條有向的邊(edge)所連接。當(dāng)樹(shù)的每個(gè)節(jié)點(diǎn)最多只有兩棵子樹(shù)時(shí)，稱(chēng)為二叉樹(shù)，而任一節(jié)點(diǎn)的子樹(shù)多于兩棵時(shí)，稱(chēng)為多叉樹(shù)。

實(shí)現(xiàn)樹(shù)的一種方法是在每一個(gè)節(jié)點(diǎn)除數(shù)據(jù)外還要有一些鏈，使得該節(jié)點(diǎn)的每一個(gè)兒子都被一個(gè)鏈所鏈接。然而，由于每個(gè)節(jié)點(diǎn)的兒子樹(shù)可以變化很大并且事先不知道，因此在數(shù)據(jù)結(jié)構(gòu)中建立到各子節(jié)點(diǎn)的直接鏈接是不可行的，因?yàn)檫@樣會(huì)產(chǎn)生太多浪費(fèi)的空間。解決方法為將每個(gè)節(jié)點(diǎn)的所有兒子都放在樹(shù)節(jié)點(diǎn)的鏈表中，一般的多叉樹(shù)數(shù)據(jù)結(jié)構(gòu)如下：

struct TreeNode

{

Int NodeType; //多叉樹(shù)節(jié)點(diǎn)的基本信息

TreeNode *firstChild; //指向兒子的指針

TreeNode *nextSibling; //指向兄弟的指針

}

通過(guò)對(duì)PLC梯形圖程序編寫(xiě)原則的分析可得，用梯形圖編程的過(guò)程實(shí)質(zhì)上就是利用梯形圖圖符來(lái)表示功能元件，借助圖符間的連接方式來(lái)表示功能元件之間的串并聯(lián)結(jié)構(gòu)及邏輯關(guān)系[10]?？紤]到梯形圖的圖符元件代表著指令表中的功能指令，因此將PLC的梯形圖程序轉(zhuǎn)化為指令表程序一定是有規(guī)律可循的。

通過(guò)研究發(fā)現(xiàn)梯形圖中每個(gè)梯級(jí)的圖符之間的串并聯(lián)關(guān)系是一種層次結(jié)構(gòu)，而這種層次結(jié)構(gòu)可以用數(shù)據(jù)結(jié)構(gòu)中的樹(shù)來(lái)表達(dá)，而且借助多叉樹(shù)表達(dá)一個(gè)梯級(jí)中圖符之間的邏輯關(guān)系之后，那么整個(gè)梯形圖就是多個(gè)樹(shù)的集合，也就是森林。而掃描梯形圖，就是一個(gè)構(gòu)建樹(shù)和森林的過(guò)程。樹(shù)由一個(gè)根節(jié)點(diǎn)和若干棵子樹(shù)構(gòu)成，這若干根子樹(shù)中每一棵都有一個(gè)根節(jié)點(diǎn)和它自己的子樹(shù)。這里用樹(shù)的葉節(jié)點(diǎn)代表具體的元件，而用非葉節(jié)點(diǎn)表示其左右子樹(shù)的邏輯結(jié)合方式[11]。

3 由梯形圖建立多叉樹(shù)算法的主要步驟

在梯形圖向指令表轉(zhuǎn)換的過(guò)程中，通過(guò)梯形圖建立多叉樹(shù)是最為關(guān)鍵的一部分[12]。構(gòu)造多叉樹(shù)以先左后右，先上后下為原則對(duì)每一行梯形圖進(jìn)行遍歷，當(dāng)掃描完一個(gè)節(jié)點(diǎn)后若沒(méi)有發(fā)現(xiàn)豎線(xiàn)就一直向右掃描，若掃描到豎線(xiàn)記錄其位置且處理完并聯(lián)節(jié)點(diǎn)后繼續(xù)向右掃描，直到掃描到最后一個(gè)節(jié)點(diǎn)為止。

3.1 算法的主要步驟

S1：自左向右進(jìn)行遍歷，每掃描到一條豎線(xiàn)就記下該豎線(xiàn)的位置以及之前遍歷的節(jié)點(diǎn)，記錄此時(shí)遍歷的節(jié)點(diǎn)數(shù)目，新建一個(gè)“與”節(jié)點(diǎn)(若此前只遍歷了1個(gè)節(jié)點(diǎn)則新建一個(gè)“或”節(jié)點(diǎn))，將之前遍歷的節(jié)點(diǎn)作為該“與”節(jié)點(diǎn)的子節(jié)點(diǎn)，這些子節(jié)點(diǎn)自左向右的排列順序必須與遍歷的順序一致。若該“與”節(jié)點(diǎn)不是所在行最后的節(jié)點(diǎn)，則將該新建的“與”節(jié)點(diǎn)視為后續(xù)節(jié)點(diǎn)的子節(jié)點(diǎn)，從而繼續(xù)構(gòu)造多叉樹(shù)，然后轉(zhuǎn)S2處理豎線(xiàn)；若該“與”節(jié)點(diǎn)是所在行最后的節(jié)點(diǎn)，則判斷是否還有記錄的豎線(xiàn)未處理，若無(wú)則終止算法，若有則說(shuō)明出現(xiàn)了多重輸出的情況，轉(zhuǎn)S8。

S2：當(dāng)掃描到豎線(xiàn)時(shí)，用標(biāo)志位記錄該列豎線(xiàn)的數(shù)量(豎線(xiàn)的數(shù)量即為豎線(xiàn)所占的行數(shù))。根據(jù)豎線(xiàn)位置，以先右后左的原則進(jìn)行遍歷。從豎線(xiàn)的位置(即豎線(xiàn)所在的坐標(biāo))開(kāi)始向左掃描，判斷是否存在節(jié)點(diǎn)，若有則轉(zhuǎn)S3，否則轉(zhuǎn)S6。

S3：新建一個(gè)“或”節(jié)點(diǎn)(該節(jié)點(diǎn)為上一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，即上一行梯形圖所構(gòu)建的子樹(shù)的根節(jié)點(diǎn))并繼續(xù)向左掃描，當(dāng)掃描到豎線(xiàn)時(shí)，判斷該豎線(xiàn)是向上還是向下，若為向上的豎線(xiàn)，則轉(zhuǎn)S4，否則轉(zhuǎn)S5。

S4：根據(jù)該行遍歷的節(jié)點(diǎn)數(shù)目，類(lèi)比步驟S1的方式建立“與”節(jié)點(diǎn)，且該“與”節(jié)點(diǎn)作為之前“或”節(jié)點(diǎn)的子節(jié)點(diǎn)，然后轉(zhuǎn)S1繼續(xù)向右掃描。

S5：記錄該豎線(xiàn)的位置，轉(zhuǎn)S7。

S6：此時(shí)由于豎線(xiàn)的左邊沒(méi)有節(jié)點(diǎn)，表明豎線(xiàn)的右邊存在元件，新建一個(gè)“與”節(jié)點(diǎn)，并將該節(jié)點(diǎn)作為已經(jīng)構(gòu)建完成的多叉樹(shù)的根節(jié)點(diǎn)，記錄該豎線(xiàn)的位置，返回該豎線(xiàn)的上一行轉(zhuǎn)S1開(kāi)始繼續(xù)向右掃描(將已經(jīng)構(gòu)建的多叉樹(shù)的根節(jié)點(diǎn)作為后續(xù)“與”節(jié)點(diǎn)的子節(jié)點(diǎn))。

S7：當(dāng)豎線(xiàn)標(biāo)志位的值(即該列豎線(xiàn)的數(shù)量)大于等于1時(shí)，將該標(biāo)志位減1，并將掃描的初始位置放至下一行，并轉(zhuǎn)S3；若標(biāo)志位的值等于0時(shí)，表明該并聯(lián)塊已經(jīng)處理完畢，根據(jù)記錄的豎線(xiàn)位置，轉(zhuǎn)S1開(kāi)始繼續(xù)向右掃描(將已經(jīng)構(gòu)建的多叉樹(shù)的根節(jié)點(diǎn)作為后續(xù)“與”節(jié)點(diǎn)的子節(jié)點(diǎn))。

S8：判斷該豎線(xiàn)所占的行數(shù)，添加堆棧節(jié)點(diǎn)并逐行掃描轉(zhuǎn)換節(jié)點(diǎn)，直至結(jié)束。

注意：

1) 在構(gòu)建多叉樹(shù)時(shí)，若是從左至右掃描，兄弟節(jié)點(diǎn)則按照掃描的順序從左至右依次排列；若是從右至左掃描，兄弟節(jié)點(diǎn)則是從右至左依次排列。

2) 當(dāng)出現(xiàn)豎線(xiàn)嵌套時(shí)，類(lèi)比堆棧的原則，優(yōu)先處理后掃描到的豎線(xiàn)所在的行，之后處理先掃描到的豎線(xiàn)所在的行。

3) 當(dāng)父節(jié)點(diǎn)與子節(jié)點(diǎn)為同一種邏輯節(jié)點(diǎn)(即“與”節(jié)點(diǎn)和“或”節(jié)點(diǎn))時(shí)，則刪去該邏輯子節(jié)點(diǎn)，并直接將被刪去的邏輯子節(jié)點(diǎn)的相應(yīng)葉節(jié)點(diǎn)作為邏輯父節(jié)點(diǎn)的子節(jié)點(diǎn)。

4)S8中，在第一行豎線(xiàn)起始位置添加進(jìn)棧指令(MPS)，中間行(行數(shù)小于3則不添加讀棧指令)起始位置添加讀棧指令(MPD)，最后一行起始位置設(shè)置出棧指令(MPP)。

通過(guò)以上方法就完成了梯形圖向多叉樹(shù)的結(jié)構(gòu)轉(zhuǎn)換，而構(gòu)建完成的多叉樹(shù)主要反映了梯形圖圖符間的串并聯(lián)關(guān)系，要得到指令表還需進(jìn)一步轉(zhuǎn)化。其中該多叉樹(shù)的葉子節(jié)點(diǎn)必定是圖符元件，而邏輯節(jié)點(diǎn)必定都是非葉節(jié)點(diǎn)。

3.2 多叉樹(shù)轉(zhuǎn)化為指令表

經(jīng)過(guò)掃描和錯(cuò)誤檢查后，對(duì)構(gòu)建完成的多叉樹(shù)進(jìn)行遍歷即可將梯形圖轉(zhuǎn)化為指令表。根據(jù)構(gòu)造多叉樹(shù)時(shí)圖符元件與邏輯節(jié)點(diǎn)之間的位置關(guān)系可以得到，應(yīng)該對(duì)多叉樹(shù)采取后序遍歷的方式。即先遍歷左子樹(shù)，然后依次遍歷右子樹(shù)，最后遍歷根節(jié)點(diǎn)。但是在遍歷完成后需要考慮到堆棧指令的問(wèn)題，即出現(xiàn)多重輸出指令時(shí)，需要自動(dòng)識(shí)別并添加堆棧指令MPS與MPP。

直接對(duì)多叉樹(shù)進(jìn)行后序遍歷得到原始指令表只是表明了圖符間的邏輯結(jié)構(gòu)，但不符合指令表語(yǔ)言的編程規(guī)范，需要在遍歷時(shí)添加判斷條件，從而得到最終可以直接轉(zhuǎn)換為十六進(jìn)制目標(biāo)代碼的指令表程序，具體轉(zhuǎn)換原則見(jiàn)第4章。

4 基于多叉樹(shù)的梯形圖向指令表轉(zhuǎn)換的實(shí)例

如圖1所示為一個(gè)梯形圖程序，該程序中包含了多重串、并聯(lián)的關(guān)系，且由于是多重輸出(即包含了Y0和Y1)，因此需要使用堆棧指令進(jìn)行入棧出棧的操作(傳統(tǒng)借助AOV圖進(jìn)行拓?fù)渑判蚧蛘咿D(zhuǎn)化為二叉樹(shù)的算法不能適用)。

圖1 梯形圖程序

根據(jù)第3章中說(shuō)明的算法，從母線(xiàn)開(kāi)始向右掃描，當(dāng)掃描到常開(kāi)觸點(diǎn)X0右邊的豎線(xiàn)時(shí)，建立一個(gè)“或”節(jié)點(diǎn)，用符號(hào)“+”表示，并將節(jié)點(diǎn)“X0”作為該“或”節(jié)點(diǎn)的左子節(jié)點(diǎn)。由于掃描到的豎線(xiàn)占據(jù)兩行，因此本該新建一個(gè)“或”節(jié)點(diǎn)作為節(jié)點(diǎn)“X0”的兄弟節(jié)點(diǎn)，但由于父節(jié)點(diǎn)也為“或”節(jié)點(diǎn)，因此省略，接著依次掃描X1和X2建立元件節(jié)點(diǎn)并將其作為“或”節(jié)點(diǎn)的子節(jié)點(diǎn)。如圖2所示即為X0、X1和X2所構(gòu)成的第一個(gè)并聯(lián)塊所構(gòu)建的多叉樹(shù)。

圖2 并聯(lián)塊X0X1X2構(gòu)建的多叉樹(shù)

建立完圖2所示多叉樹(shù)后，繼續(xù)回到主線(xiàn)路向右掃描直至常開(kāi)觸點(diǎn)X4右邊的豎線(xiàn)，此時(shí)新建一個(gè)“與”節(jié)點(diǎn)，用“*”表示，將之前由X0、X1和X2構(gòu)建的多叉樹(shù)作為該“與”節(jié)點(diǎn)的左子樹(shù)，之后建立元件節(jié)點(diǎn)“X3”和“X4”并分別將其作為該“與”節(jié)點(diǎn)的子節(jié)點(diǎn)。

然后開(kāi)始處理豎線(xiàn)，先建立一個(gè)“或”節(jié)點(diǎn)，并將之前構(gòu)建好的多叉樹(shù)作為該“或”節(jié)點(diǎn)的左子樹(shù)，然后掃描X5、X6和X7所在的行，當(dāng)掃描到向上的豎線(xiàn)時(shí)，該行的掃描結(jié)束。根據(jù)掃描結(jié)果新建一個(gè)“與”節(jié)點(diǎn)，將其作為處理豎線(xiàn)時(shí)新建的“或”節(jié)點(diǎn)的右子節(jié)點(diǎn)，然后將元件節(jié)點(diǎn)“X5”、“X6”和“X7”依次從左至右作為該“與”節(jié)點(diǎn)的子節(jié)點(diǎn)。如圖3所示即為并聯(lián)塊X0X1X2、串聯(lián)塊X3X4以及串聯(lián)塊X5X6X7共同構(gòu)建的多叉樹(shù)。

圖3 并聯(lián)塊X0X1X2、串聯(lián)塊X3X4和串聯(lián)塊X5X6X7構(gòu)建的多叉樹(shù)

回到主線(xiàn)路繼續(xù)向右掃描，當(dāng)掃描至常開(kāi)觸點(diǎn)X10右邊的豎線(xiàn)時(shí)，新建一個(gè)“與”節(jié)點(diǎn)，將之前構(gòu)建的多叉樹(shù)作為該“與”節(jié)點(diǎn)的左子樹(shù)，同時(shí)將元件節(jié)點(diǎn)“X10”作為該“與”節(jié)點(diǎn)的右子節(jié)點(diǎn)。接著開(kāi)始處理豎線(xiàn)，發(fā)現(xiàn)豎線(xiàn)左邊沒(méi)有元件，記錄該豎線(xiàn)位置后返回主線(xiàn)路繼續(xù)向右掃描直至Y0，此時(shí)發(fā)現(xiàn)Y0的右邊沒(méi)有豎線(xiàn)，表明出現(xiàn)了堆棧指令。因此新建進(jìn)棧指令節(jié)點(diǎn)“MPS”，元件節(jié)點(diǎn)“X11”以及輸出節(jié)點(diǎn)“Y0”，依次從左至右排列作為之前“與”節(jié)點(diǎn)的子節(jié)點(diǎn)。最后處理下一行，即新建出棧指令節(jié)點(diǎn)“MPP”，元件節(jié)點(diǎn)“X12”和輸出節(jié)點(diǎn)“Y1”。最終遍歷圖1梯形圖構(gòu)建的多叉樹(shù)如圖4所示。

圖4 遍歷梯形圖構(gòu)建的多叉樹(shù)

將梯形圖轉(zhuǎn)化為多叉樹(shù)之后，如果直接對(duì)圖4的多叉樹(shù)進(jìn)行后續(xù)遍歷而不加以區(qū)分的話(huà)，則會(huì)得到如下所示的原始指令表程序：

LD X0

LD X1

LD X2

OR

LD X3

LD X4

AND

LD X5

LD X6

LD X7

AND

OR

LD X10

MPS

LD X11

OUT Y0

MPP

LD X12

OUT Y1

AND

該原始指令表程序雖然清晰的反應(yīng)了圖符間的邏輯結(jié)構(gòu)，但是不符合指令表語(yǔ)言的編程規(guī)范，因此在后序遍歷時(shí)加入判斷條件，從而得到符合指令表語(yǔ)言編程規(guī)范的程序。具體的判斷原則的如下所示：

1)若為觸點(diǎn)元件，且為父節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)，則其生成指令的操作碼為L(zhǎng)D(若為常閉觸點(diǎn)則為L(zhǎng)DI)；

2)若為觸點(diǎn)元件，且不為父節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)，則其生成指令的操作碼與父節(jié)點(diǎn)的邏輯類(lèi)型相同，即父節(jié)點(diǎn)為“與”節(jié)點(diǎn)則為AND，父節(jié)點(diǎn)為“或”節(jié)點(diǎn)則為OR(若為常閉觸點(diǎn)則分別為ANI或ORI)；

3)若為邏輯節(jié)點(diǎn)，且為父節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)，則不生成指令(若沒(méi)有父節(jié)點(diǎn)，即為根節(jié)點(diǎn)時(shí)也不生成指令)；

4)若為邏輯節(jié)點(diǎn)，且不為父節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)，則其生成指令的操作碼與父節(jié)點(diǎn)的邏輯類(lèi)型相同，即父節(jié)點(diǎn)為“與”節(jié)點(diǎn)則為ANB，父節(jié)點(diǎn)為“或”節(jié)點(diǎn)則為ORB。

根據(jù)以上原則對(duì)圖4多叉樹(shù)進(jìn)行后序遍歷得到的符合編程規(guī)范的最終指令表如下所示：

LD X0

OR X1

OR X2

AND X3

AND X4

LD X5

AND X6

AND X7

ORB

AND X10

MPS

AND X11

OUT Y0

MPP

AND X12

OUT Y1

5 結(jié)束語(yǔ)

研究分析了梯形圖節(jié)點(diǎn)元件互相之間的邏輯關(guān)系，借助多叉樹(shù)特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)反應(yīng)圖符之間的邏輯關(guān)系并完成梯形圖向指令表的轉(zhuǎn)換。在自主開(kāi)發(fā)的梯形圖編譯軟件上成功應(yīng)用了該梯形圖向指令表轉(zhuǎn)換的算法，表明其能夠正確地將用戶(hù)的梯形圖程序轉(zhuǎn)換為指令表程序。該算法可用于邏輯復(fù)雜梯形圖向指令表的轉(zhuǎn)換，即使出現(xiàn)堆棧指令也能同樣適用，且梯形圖的掃描過(guò)程不重復(fù)、不遺漏。構(gòu)建完多叉樹(shù)之后的遍歷過(guò)程相較遍歷二叉樹(shù)等也更為高效。

[1] 李金城. 三菱FX2NPLC功能指令應(yīng)用詳解[M]. 北京:電子工業(yè)出版社, 2011.

[2] 呂俊白, 施敏芳. PLC梯形圖可視化編輯與語(yǔ)句表的自動(dòng)生成[J]. 自動(dòng)化儀表, 2005, 26(3): 28-30.

[3] 韓雪濤, 韓廣興. 雙色圖解PLC梯形圖及語(yǔ)句表[M]. 北京:人民郵電出版社, 2012.

[4] 陽(yáng)俊將, 黃道平, 劉少君. 關(guān)于PLC梯形圖到指令表轉(zhuǎn)換算法的研究[J]. 信息技術(shù), 2012, (6): 75-78.

[5] 未慶超, 蔡啟仲. 基于ARM的PLC編譯系統(tǒng)設(shè)計(jì)[J]. 計(jì)算機(jī)測(cè)量與控制, 2014, 22(4): 1225-1229.

[6] 崔小樂(lè), 周卓岑. 可編程控制器的梯形圖語(yǔ)言與語(yǔ)句表語(yǔ)言的互換算法[J]. 微電子學(xué)與計(jì)算機(jī), 2000(1): 26-30.

[7] 葛 芬, 吳 寧. 基于AOV圖及二叉樹(shù)的梯形圖與指令表互換算法[J]. 南京航空航天大學(xué)學(xué)報(bào), 2006, 38(6): 754-758.

[8] 黃晶晶, 陳文薌. 基于二叉樹(shù)的PLC梯形圖轉(zhuǎn)化為指令表的算法[J]. 現(xiàn)代電子技術(shù), 2010(4): 125-134.

[9] 傅 亮, 胡飛虎. 基于串并聯(lián)歸并的PLC梯形圖向指令表轉(zhuǎn)換算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2009, 45(27): 72-118.

[10] 莫易敏, 章德平. PLC梯形圖轉(zhuǎn)化為指令表算法及實(shí)現(xiàn)[J]. 控制工程, 2006, 13(6): 573-576.

[11] 石 銳, 周 雷, 楊正益. 軟PLC梯形圖到語(yǔ)句表轉(zhuǎn)換新策略的研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46(18): 244-248.

[12] 譚錦潔, 程良鴻, 殷學(xué)鵬. 嵌入式PLC中梯形圖到AOV圖的映射[J]. 計(jì)算機(jī)測(cè)量與控制, 2004, 12(10): 993-1004.

Transformation Algorithm from Ladder Diagram to Instruction List Based on Multi-tree

Zhou Weiqiang, He Tongneng, Chen Defu

(College of Information and Engineering, Zhejiang University of Technology, Hangzhou 310023, China)

Aiming at the shortcomings of the transformation algorithm from ladder diagram to instruction list in the current programmable logic controller(PLC) editing software, this paper presents an algorithm to realize the transformation from PLC ladder diagram to instruction list based on multi-tree. Through the analysis and research of ladder diagram, shows the advantages and disadvantages of the ladder diagram and instruction list in practical application. The multi-tree data structure is created following the scanning principle that from left to right, from top to bottom. And the multi-tree is used to reflect the logical relationship between the diagrams. Then get the instruction list by post-traversing the multi-tree.This algorithm has higher efficiency when dealing with the ladder diagram which has multiple series-parallel structures. And it is also suitable for the stack instruction, which makes the algorithm more versatile.

programmable logic controller; ladder diagram; instruction list; multi-tree

2017-02-18；

2017-03-05。

周偉強(qiáng)(1990-)，男，浙江海寧人，碩士研究生，主要從事控制科學(xué)嵌入式方向的研究。

1671-4598(2017)08-0191-04

10.16526/j.cnki.11-4762/tp.2017.08.049

TP273

A