可编程逻辑控制器(programmable logic controller, PLC)是实现自动化制造的重要工具之一。随着计算机技术的快速发展，利用软件来代替传统硬件PLC，即软PLC技术，由于其功能更强大，具有更高的开放性和通用性，越来越受到关注^[1-2]。IEC 61131-3标准规范了PLC编程语法，并将指令表(instruction list, IL)、梯形图(ladder diagram, LD)、结构化文本(structured text, ST)和功能块图(function block diagram, FBD)定义为PLC的编程语言^[3-4]。其中，梯形图与继电器控制电路相似，直观且容易编程，因此是自动化行业中应用最为广泛的语言。

由于梯形图并不能被控制器直接执行，一般将梯形图转换为指令表。控制器能够相对容易地将类似汇编语言的指令表转化为可以被执行的机器指令。Welch^[5-6]将梯形图转换为完全分解的Boole形式的运算，并采用AND-OR树形式来表征运算逻辑。Xie等^[7]则先将梯形图抽象为AOV图，然后遍历AOV图对应的AND-OR树以产生Boole表达式。Kim等^[8]提出了梯形图的数学表示方法，进而设计了高效的梯形图逐列求解算法。韩兵兵^[9]则提出块递归划分的算法，将每个复杂串并联块无限分割成简单的逻辑块。文[10-11]则提出了另一种转换算法，即先将梯形图抽象为AOV图，再将AOV图转换为二叉树形式，进而后序遍历二叉树以获得对应的指令表。Yan等^[12]首次提出了两终端串并联(two terminal series parallel, TTSP)拓扑结构，将基于二叉树形式的转换算法进一步扩展以支持多线圈输出。

将梯形图转换成指令表形式的另一种常见方法是运用有向图的拓扑排序。Yi等^[13]提出一种分形串并联有向图，相比二叉树，可以更直观和简洁地表达梯形图的Boole逻辑。朱兆斌^[14]利用队列和栈，循环输出无前驱的顶点及删除该顶点和对应的弧，最后获得指令表。Moonga等^[15]提出了一种基于双栈深度优先搜索(two stack depth first search, TSDFS)的梯形图遍历算法，算法不需要将AOV图转换成树结构，而是利用虚节点对分支合并或分割，最终生成指令表。有向图的拓扑排序算法依赖于节点的处理顺序，需要增加Boole判断变量以确保生成正确的语义，鲁棒性较差。此外，无论是基于二叉树或者拓扑排序的方法，都需要查找和插入额外的虚节点，对大量虚节点的处理会降低转换效率，且都难以检查出复杂梯形图的短路和断路的错误。因此，Lin等^[16]将梯形图抽象为层次清晰的广义表，无需增加虚节点即可转换为对应的指令表形式，具有算法实现简单、效率较高、易检查梯形图中存在的逻辑错误的特点，但并没有解决多线圈输出的转换问题。

本文提出了改进的基于AOV图和广义表的转换算法，以将梯形图转换成符合IEC 61131-3标准规范的指令表形式。通过串并联归并，抽象地将梯形图的拓扑结构存储在广义表中，同时标志位记录多输出线圈。最后采用深度优先搜索算法，遍历带有输出标志位的广义表。重点解决了多线圈输出的问题，可以生成正确的指令表。

1 梯形图抽象为AOV图

基于梯形逻辑的梯形图是广泛使用的PLC编程语言，采用从左往右流动的有向图，清晰地表达了各个图形单元之间的逻辑关系，每个图形单元代表着开关控制系统中的线圈、触点或功能块等。大的梯形图可以被细分为若干个子网络。指令表是另一种PLC编程语言，一般由指令和操作数构成，如图 1所示。指令表描述了由指令和操作数构成的节点信号的顺序逻辑关系。PLC指令包括基本指令和功能指令。基本指令是对触点和内部继电器等信号进行基本逻辑运算，如“与”“或”，从而产生线圈控制信号^[14]。基本指令包括IN、OUT、AND、OR、AND-ST和OR-ST等，其中OR-ST和AND-ST用于连接2个串联或并联的电路块。功能指令一般用于复杂控制任务，包括定时指令TIM、传送指令MOV、计数指令CNT、旋转指令ROT等。

由于指令表和梯形图在表达上的差别巨大，二者之间的直接转换并不现实。考虑到梯形图具有的2个显著特点：1)梯形图中每个图形单元都是独立的，互不影响的；2)梯形图中相邻图形单元之间有确定的逻辑先后关系，可构成一个有向无环图。

因此，考虑使用AOV图来描述PLC梯形图中每个图形单元之间的关系，如图 2所示。用AOV图中的每个顶点来表征梯形图中的一个图形单元，顶点之间的有向弧则代表图形单元之间的逻辑先后关系。AOV图可以被数学形式化的表达为：

$\operatorname{Graph}=(V, R), $

$V=\{x | x \in \text { DataObject }\} \quad R=\{\mathrm{VR}\}, $

$\mathrm{VR}=\{\langle x, y\rangle | x, y \in V\}. $

其中: V是图顶点的集合，R是顶点关系集，VR则是顶点弧的集合。〈x, y〉代表一条由顶点X指向Y的有向弧，X为弧尾，Y为弧头。顶点V的入度di(V)是指以顶点V为弧头的弧数量，类比可以定义顶点的出度do(V)。

十字链表适用于存储有向图的信息^[17]，其数据结构如图 3所示。data存储顶点的数据，包括入度、出度和编号。firstin和firstout分别代表以该顶点为弧头或者弧尾的弧链表。tailvex和headvex存储弧顶点编号，taillink和headlink分别存储弧尾或弧头一致的弧链表。

按照以下算法步骤，将梯形图抽象为AOV图。

步骤1  按先左后右的行优先顺序，为每个PLC元件，包括触点、线圈和功能函数块等，登记一个对应的AOV图顶点。

步骤2  增加2个顶点，分别代表左侧起始线和右侧终止线，顶点编号为0和N+1。

步骤3  利用深度优先算法创建十字链表。通过对每个图顶点，以深度优先的方式，沿着连接线，向右上、向右边、向右下搜索，找到所有的后继顶点或者直到碰到终止线，并创建图顶点之间的弧。

在搜索整个AOV图建立十字链表时，左侧起始线向下的连接线总是存在的。这样，经过上述算法步骤，将梯形图最终抽象为AOV图。

2 AOV图的广义表转化

广义表通常被记为

$L_{s}=\left(a_{1}, a_{2}, \cdots, a_{i}, \cdots, a_{n}\right). $

其中：n代表是广义表的长度；a_i代表广义表的元素，它可以是一个广义表原子或者子表。如图 4所示，P代表一个并联子表头，S代表串联子表头，方框中的编号对应各个AOV图顶点。

梯形图中存在的短路和断路错误增加了转换的难度。如图 5a所示，顶点D被短路，而在图 5b中，顶点E被断路。在转换之前，需要给出数学形式化的描述短路和断路的判断条件。

不妨设AOV图的顶点集合为V，左侧起始线和右侧终止线分别用V₀和V_n+1表示(在图 5中分别用A和Z代表)。

1) 若V_i∈V，V_i的入度或出度为0，且V_i≠V₀ or V_n+1，则有结论：顶点V_i被断路。

2) 若V_i∈V，后继顶点为V_i1, V_i2, …, V_ik，其后继顶点集合分别为S₁, S₂, …, S_k。令集合U₁={V_i1, V_i2, …, V_ik}，U₂={S₁∪S₂∪…∪S_k}，U₃=U₁∩U₂。若U₃≠∅，则∀V_j∈U₃，则有结论：顶点V_j被短路。

通过以上的数学形式化描述，容易判断顶点是否被断路或者短路。

基于文[16]的串并联归并方法，将AOV图转换为带有输出标志位的广义表的改进算法步骤如下：

步骤1  对AOV图进行短路和断路的检错，然后初始化广义表，将每个图顶点登记为一个广义表原子，对于代表输出线圈的原子设置输出标志位为1。

步骤2  串联归并。搜索十字链表中所有顶点，假设一顶点为V_j，其前驱顶点为V_i，当di(V_j)=1且do(V_i)=1，则V_i和V_j是串联关系，对两个顶点串联归并：将V_j的后继链接到V_i的后继指针, 修改V_i顶点的出度；从十字链表中移除顶点V_j；移除弧〈V_i, V_j〉，如图 6所示。

将广义表信息记录在V_i，继承输出标记，删除广义表V_j，这里需要分情况处理。

(1) 当V_i记录的是串联关系的子表时，对V_i和V_j的输出标志位求或。如果V_j是子表，则将V_j子表的头元素链接到V_i子表的尾指针上。如果V_j是广义表原子，则将V_j链接到V_i子表的尾指针上。

(2) 当V_i记录的是广义表原子或者并联关系的子表时，则开辟一个新的广义表元素地址。设置为串联关系子表，子表的输出标志位设置为V_i和V_j的标志位求或所得值。V_i为新建子表的头元素。若V_j是串联子表，将新建子表的尾指针指向V_j的头元素，否则将V_j直接链接到新建子表中。

步骤3  并联归并。

搜索十字链表中所有顶点，寻找出度大于1的顶点V_i，设出度为do(V_i)=m。设V_i直接后继顶点分别为V₁, V₂, …, V_m。将V₁, V₂, …, V_m归入集合S₁, S₂, …, S_k中，要求在同一个集合S_i内的顶点在AOV图中有一样的前驱顶点和一样的后继顶点，则同一集合内的顶点是并联关系。

对属于同一个集合S_i内的顶点V_i1, V_i2, …，V_ik进行并联归并。

(1) 删除十字链表中除了集合里第一个顶点V_i1以外的所有并联顶点以及对应的弧，重新组织弧链，并修改这些顶点的前驱顶点的出度和后继顶点的入度。目的在于，在AOV图中，仅仅保留并联集合中的第一个顶点及其入弧出弧，即可表征同一集合里所有并联顶点的逻辑关系。

(2) 开辟一个新的广义表元素地址，设置为并联关系子表，子表的输出标志位设置为同集合内所有广义表元素的标志位求或所得的值。逐个将集合内所有的广义表元素归并到新建的并联子表下，需要分2种情况处理：若当前处理的广义表元素是并联子表，则去掉子表头，仅将子表下的广义表元素合并到新建的并联子表下；若当前处理的广义表元素是串联子表或原子，则直接将其链接到新建的并联子表下。

步骤4  重复步骤2—3，直到所有的广义表元素都被归并到一个子表下。若有其他顶点不能归并，则说明梯形图中存在逻辑问题。当广义表充分归并成功后，删除多余的代表左侧起始线和右侧起始线的图顶点0和N+1。

将AOV图转化为广义表的方法如图 6所示，相比Lin等^[16]所提的归并方法，主要增加了对多线圈输出问题的转化考虑。经过算法步骤1—4，充分归并后的广义表满足以下2个结论：

(1) 并联子表P下面只有原子、串联子表S。当并联子表P的输出标志位为1时，并联子表P下面只有输出标志位为1的原子、串联子表S。

(2) 串联子表S下面只有原子、并联子表P。当串联子表S的输出标志位为1时，串联子表S下若有标志位为1的子表P，则有且仅有一个子表P。

以上结论为下一步将广义表转化为符合PLC编程标准的指令表的深度优先搜索算法提供了理论指导。

3 深度优先搜索算法

将带有输出标志位的广义表转化为指令表的深度优先搜索算法(depth first search, DFS)如图 7所示。

在本文的算法中，仅仅增加一个输出标志位，在串并联归并时仅做或运算，最后即可通过深度优先搜索处理得到包含多输出的指令表。其他算法如Yan等^[12]采用的是分治方法来解决多线圈输出的难题，即将整个梯形图网络划分为多个子网络，每个子网络只有一个线圈，然后得到各子网的IL值，再级联各子网以获得整个网络。这种分治方法虽然理论上具有可行性，但额外的分治处理无疑会降低转换算法的效率。

4 实验测试

基于本文所提出的算法开发的PLC编程原型系统如图 8所示。原型系统是在Linux下基于Qt软件开发的，界面右侧是梯形图，左侧为转换后的指令表，错误等信息在信息输出窗口中。

图 8的实例中，包含了多线圈输出、功能函数块输出等复杂梯形图，所提算法仍能够有效地完成转换。在配备Intel i5-2450M 2.5 GHz CPU的电脑上，所提算法的运算时间为0.68 ms(重复计算1 000次取平均运算时间)。探讨所提算法的时间复杂度。假定AOV有e条弧，n个顶点。本文算法将梯形图转换为AOV时间复杂度为O(e)，当梯形图的串并联耦合程度高时，串并联归并的最坏时间复杂度为O(n²)，当串并联耦合程度低，复杂度趋于O(n)。DFS生成指令表的时间复杂度也取决于梯形图的复杂程度，但即使每个顶点都属于一个独立的子表，DFS的时间复杂度也仅为O(2n)。因此，本文算法最坏情况的时间复杂度为O(n²)，这与Lin等^[16]的时间复杂度分析结果一致，原因在于该算法仅仅增加了输出标志位来应对多线圈输出，在核心耗时的串并联归并过程中，仅仅需要做位或运算，这并不会增加算法的时间复杂度。对比拓扑排序算法，其时间复杂度为O(n+e)。当边稀疏时，算法复杂度趋近于O(n)；当边密集时，算法复杂度趋近于O(n²)^{[14, 16]}。因此该算法与拓扑排序算法时间复杂度基本一致，但该算法不依赖节点的处理顺序，且能有效地检查出梯形图存在的短路和断路错误。

5 结论

本文提出了改进的基于AOV图和广义表的梯形图转指令表的转换算法。通过串并联归并，抽象地将梯形图的拓扑结构存储在广义表中，同时标志位记录输出线圈。最后采用深度优先搜索算法，遍历带有输出标志位的广义表。重点解决了多线圈输出的问题，以生成正确的指令表。实验测试结果表明：该算法能够有效生成符合标准规范的指令表格式。