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指向起点相同的弧［14］。

图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编程系统的开发，具有广阔的应用前景。