基于N 叉树的PLC 功能块向指令表的转换算法研究*

周 伟，张得礼

(南京航空航天大学 机电学院，江苏 南京 210016)

0 引言

所谓软PLC 就是使用PC 机作为硬件支持平台，使用软件来实现传统PLC 的基本功能，PLC 控制函数封装在软件中，运行于PC 环境中。基于PC 的自动控制系统具有成本低、开放性好、易于使用等优点，使它成为一个新的发展方向。根据PLC 的传统结构，软PLC 系统分为两部分，程序开发系统和运行系统，其中运行系统是软PLC 技术的核心。

在IEC61131-3 标准中提供了5 种编程语言［1］，其中功能块图(FBD)是一种图形化编程语言，相比于梯形图语言，FBD 语言能够更好地描述各个输入触点间的逻辑关系。使用功能块图编程语言不仅可以提高系统的可靠性，利于结构化程序设计，且还能有效地实现程序代码的复用，加速应用程序的开发。

结合软PLC 的设计思想，依据IEC61131-3 标准，本研究设计的Soft PLC 软件平台提供了功能块图(FBD)和指令语言(IL)两种编程语言。编译器则负责对编辑器中的功能块图和指令语言程序进行编译，实现从图形语言到文字语言的转化，最终生成二进制目标代码。其中编译转化过程是程序开发中的关键。

文献［2］介绍了嵌入式的软PLC 控制系统，运行控制模块是以ARM920T 处理器为核心，编辑软件生成代码指令列表(IL)代码，然后PLC 系统通过解释执行IL 代码来实现具体的控制。无论是基于PC 或是嵌入式的软PLC 系统，编译转化模块都是至关重要的环节，直接关系到后面的运行控制模块对程序解析执行的对错。

文献［3-4］介绍了由AOV 图建立二叉树，并对其进行后序遍历实现梯形图与指令表程序转换的算法，适用于串、并联复杂的梯形图，存在的不足是只能应用单输出的梯形图网络。文献［5-6］将梯形图转化为AOV 图，并利用AOV 图建立因果图，然后遍历因果图的节点生成PLC 所能识别的语句表，对于复杂的多输出的梯形图网络也并不适用。

文献［7］介绍了PLC 功能块图向指令表的转换算法，采用树结构中的孩子兄弟表示法(又称二叉链表表示法)来存储每一个功能块的数据和逻辑关系等信息，每一个功能块图都可以表示成一棵树，对树进行一次遍历，就得出了用户程序对应的IL 程序。但这并不通用，且不适用于串、并联逻辑关系复杂和多重输出的FBD 程序。

本研究针对软PLC 多重输出的问题，提出将FBD图映射到N 叉树型数据结构，对N 叉树进行后序遍历依次访问各个节点，得到相应IL 程序的算法。该算法适用于复杂的多输出FBD 程序，采用分解重组的方式，将生成的复杂树结构分解成N个有序的树结构组合，然后对每个N个树结构进行有序遍历，生成IL 程序。该算法具有通用性，能提高PLC 解释执行的效率。

1 N 叉树结构及其遍历方式

1.1 N 叉树结构

树是n(n≥0)个有限数据元素的集合T，任一非空树(n ＞0)满足下面两个条件:

(1)且仅有一个称为根(root)的结点，根结点没有前驱结点;

(2)当n ＞1 时，除根结点以外的其余数据元素被分成m(0 ＜m≤n)个互不相交的集合T1，T2，……，Tm，其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1，T2，……，Tm称为这个根结点的子树。当树中的每个结点最多只有两棵子树时，称为二叉树［8］，多于两棵子树时称为多叉树。

1.2 N 叉树的存储表示

如果采用二叉树的表示方法，则每个节点内设置多少个指针子节点不好确定。若以整个树中子节点最多的节点为准给各节点设置指针，则大量指针为空，将浪费存储空间;若每个节点按其实际的子节点数设置指针，则各子节点数不相等，形式也不统一，这将给管理和操作带来不便。因为N 叉树每个节点的子节点数没有限制，其更为适合用来存储复杂FBD 程序。

每一个CPTreeNode 节点之间的连接规律是:pNode_Parent 指针指向父节点的指针，pNode_FirstChild 指针指向第一个孩子节点的指针，pNode_Next-Brother 指针指向下一个兄弟节点的指针，m_TreeType保存节点本身的基本信息。

2 基于N 叉树PLC 功能块向指令表转化算法

遍历是对树的一种最基本的运算，所谓遍历N 叉树，就是按一定的规则和顺序走遍N 叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。二叉树的遍历主要有中序遍历(LDR)、先序遍历(DLR)和后序遍历(LRD)3 种，对于N 叉树而言，无所谓中根次序，而只有先根，后根次序遍历的方式［9］。

转化前的N 叉树结构如图1 所示。其中节点19为根节点，根节点第一子树集合{8，1，2，3，4，5，6，7};第二子树集合{9，10，11，12};第三子树结合{13，14，15，16，17，18}［10］。

后根次序遍历结果:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19。

图1 转化前的N 叉树结构

先根次序遍历结果:19 8 1 3 2 7 4 5 6 12 11 9 10 18 13 17 16 14 15。

无论是后根次序遍历还是先根次序遍历对于该树结构的所有子树遍历方式都是必须是相同的，当出现要求所有子树遍历方式不尽相同的时候，传统的单一遍历算法就显得力不从心。

对于N 叉树T，定义一种新的遍历方式:树T 的子树T1{}集合采用后根次序的遍历方式，其余的子树T2{}集合采用先根次序的遍历方式。若是还采用传统单一的遍历算法，势必会造成程序量上面的冗杂堆积，浪费不必要的内存空间。研究者可以采用分解重组的方式，将整个N 叉树结构进行分解，将需要进行后根次序遍历的子树T1{}保持不变，将需要进行先根次序遍历的子树T2{}各个节点改变父节点、孩子节点等参数连接指向，根节点19 因此派生出多个虚根节点，如图4 中白色的19'，19″节点，节点19'为根节点19 的第一虚根节点，19″为第二虚根节点，派生出的虚根节点依次作为T2{}集合成员的子节点。

图2 转化后的N 叉树结构

图1 中N 叉树进过分解重组转化后生成的由多个N 叉树组成的集合如图2 所示。重组后的树结构被分解成3个较为简单的树，这样就可以采用唯一的遍历方式来访问各个节点。

在同等运行环境中，采用多次执行取均值的方式，未采用分解算法的平均执行时间为0.099 52 ms，采用分割组合后的平均执行时间为0.099 62 ms，在程序执行快慢方面大相近庭，但是前者在遍历过程中使用了96 B的临时变量空间，而采用分割组合后的算法只使用了60 B的临时变量空间，因为在遍历过程中，前者需要两种方式的遍历，而进行分割重组后的树结构只需要一种方式就可以达到遍历的要求，减少了程序代码量上面的冗杂堆积。由此可见，当节点数增多时，采用本研究算法可以简化程序，节省更多的空间。

3 FBD 向IL 语句转化算法设计

经过多年的研究与发展，国内外的PLC 产品及其编程平台已相当成熟，大多集成开发环境都包含了梯形图与指令表程序互换的功能，相对较少涉及FBD 向指令表转换算法。本研究采用树结构中的孩子兄弟表示法来存储每一个功能块的数据和逻辑关系等信息，每一个功能块图都可以表示成树结构的一个节点，通过依次查找的方式找到每个节点的父节点、兄弟节点，再对树进行一次遍历，就得出了用户程序对应的IL程序。

本研究设计的算法适用于串、并联逻辑关系复杂、且具有多重输出的FBD 程序，FBD 程序转化实例如图3 所示，笔者以如图3 所示的FBD 程序为例验证本研究算法的正确性。

图3 FBD 程序转化实例

3.1 基于N 叉树结构的FBD 模块表达

PLC 多重输出指令又被称为堆栈指令，LPS(进栈指令)、LRD(读栈指令)、LPP(出栈指令)为一组指令，主要用在当多重输出且逻辑条件不同的情况下，将连接点的结果存储起来，以便连接点后面的电路编程。

为满足PLC 的多重输出指令的要求，本研究设计CVerLine 类为应对多重输出的PLC 程序。在处理CVerLine 类型节点过程中，CVerLine 类对象转化方式如图4 所示，图4 中为3 重输出分支，一个实例化CVerLine 的类对象产生一个L_Ver 树形节点，并且派生出3个R_Ver 虚节点，R_Ver1、R_Ver2、R_Ver3 为节点L_Ver 的有序派生虚节点，依次为第一、第二、第三派生虚节点。第一步先遍历以L_Ver 为根节点的树结构，第二步再按顺序依次遍历以R_Ver1、R_Ver2、R_Ver3 为子节点的树结构，在第二步过程中遍历到R_Ver1、R_Ver2、R_Ver3 等虚节点，不做任何处理，就可以达到“使每一个结点都被访问一次，而且只被访问一次”的遍历效果。

图4 CVerLine 类对象转化方式

本研究在设计N 叉树型数据结构时采用上述的方式保存节点，图3 中FBD 程序经过转换映射、分解重组产生的树结构如图5 所示。

图5 经过分解重组后的N 叉树结构

3.2 N 叉树结构的简化

逻辑树建好之后，对其进行后序遍历便可生成功能块图所对应的指令表程序。为简化后序遍历过程，需对逻辑树进行化简，化简方法是:遍历树结构中的所有逻辑节点，判断逻辑节点的类型是否与其父节点类型相同，若相同，则删除该节点，并将其所有的子节点直接追加为其父节点的子节点。

N 叉树结构的简化实例如图6 所示。图6 中存在一个AND 节点与其父节点类型相同，其表达的逻辑关系是完全正确的，但在向IL 指令表转化中，为了简化N 叉树结构，将其自己的所有孩子节点全部赋给自己的父节点，并消除自身节点。

图6 N 叉树结构的简化实例

化简结果如图7 所示。

图7 树结构简化后的结果

3.3 转换算法实现

经过分解重组的树结构可以很方便地按照后根次序的遍历访问各个节点，算法流程图和最后编译转化结果如图8、图9 所示。

图8 转换算法流程图

从编译结果可以看出，该算法能较好地实现PLC功能块图到指令表的转换，对每个节点进行一次扫描的原则，保证每个节点不重复扫描;编译输出的指令程序与西门子STEP-7 软件编译的一致，即可达到功能块图编译的效果。与以往基于AOV 图及二叉树结构的算法相比，该算法给出了另外一种崭新的思路，加快了编译速度，节省了内存空间。实验证明该算法是正确可行的，可以应对串并联逻辑关系复杂、且有多重输出的FBD 程序。

图9 转化后对应的指令表程序

目前，本研究在PC 机上已对16个基本逻辑指令(LD、LDN、O、ON、A、AN、S、R、N、P、=、NOT、LPS、LRD、LPP、END)、定时器(T)、计数器(C)、4个浮点数计算指令(ADD_R、SUB_R、MUL_R、DIV_R)和8个整数计算指令(ADD_I、SUB_I、MUL_I、DIV_I、ADD_DI、SUB_DI、MUL_DI、DIV_DI)进行了编译。

4 结束语

本研究提出了将PLC 功能图向N 叉树型数据结构的转化算法，即通过分解重组的方式生成IL 指令表语言，实验结果验证了算法的正确性，能够将具有多重输出的复杂控制逻辑功能块图转换成指令表语句，提高了PLC 功能块图编译转换的效率。

本研究软PLC 的开发系统带有编译和仿真运行的功能，用户在编辑器中完成FBD 程序的编写。相比之前文献中的梯形图向指令表转化算法，本研究提出的一种基于分解重组的转换思路，实现了FBD 功能块向指令表的转换，在面对具有复杂逻辑关系的FBD 程序时，本研究算法简化了转化的过程、节省更多的空间、提高了编译的效率和准确性，也为后续研究软PLC运行系统打下了良好的基础。

［1］IEC61131-3 Programmable controller-part3［Z］.programming languages，International Electrotechnieal Commission，1993.

［2］Zhou QingguoYang，Xuhui Han，Genliang Yang，et al.An Embedded Control System Designed Based on Soft PLC［J］.Multimedia and Ubiquitous Engineering，2014，308:115-120.

［3］葛 芬，吴 宁.基于AOV 图及二叉树的梯形图与指令表互换算法［J］.南京航空航天大学学报，2006，38(6):754-758.

［4］傅 亮，胡飞虎，刘 乐，等.基于串并联归并的PLC 梯形图向指令表转换算法［J］.计算机工程与应用，2009，45(27):72-74，118.

［5］潘庭龙，沈学芹，纪志成.基于AOV 图及因果图的梯形图与语句表互换算法［J］.测控技术，2008，11:64-66.

［6］朱兆斌，赵东标.软PLC 中梯形图向指令表转化的实现［J］.机械与电子，2008，12:61-64.

［7］张爱民，蒋 刚，张连原，等.软PLC 的设计思想在0 继电保护装置中的应用［J］.高压电器，2007(6):444-447.

［8］Nishant Doshi，Tarun Sureja，Bhavesh Akbari，et al.Width of a Binary Tree［J］.International ournal of Computer Applications，2010，9(2):41-43.

［9］林桂伍.多叉树结构及其实现［J］.福州大学学报:自然科学版，1995，23(1):15-19.

［10］S.Olariu，M.Overstreet，Z.F.Wen.Reconstructing a Binary Tree from Its Traversals in Doubly Logarithmic CREW Time［J］.Journal of Parallel and Distributed Computing，1995，27(1):100-105.