基于AOV和广义表的梯形图转指令表的转换算法  

Transformation algorithm from a ladder diagram to an instruction list based on AOV and Lists

作　　者：王炜新 周凯[1] 毛飞龙 WANG Weixin;ZHOU Kai;MAO Feilong(Department of Mechanical Engineering,Tsinghua University,Beijing 100084,China)

机构地区：[1]清华大学机械工程系

出　　处：《清华大学学报（自然科学版）》2019年第12期1039-1044,共6页Journal of Tsinghua University(Science and Technology)

摘　　要：梯形图是IEC 61131-3标准定义的4种可编程逻辑控制器(programmable logic controller,PLC)编程语言之一,但因为梯形图无法被处理器直接执行,所以大多数商用PLC编程系统都会将梯形图转换为类似汇编语言的指令表,便于生成机器指令。该文提出一种基于AOV(activity on vertex)图和广义表的转换算法,相比基于广义表的现有算法,重点解决了多线圈输出问题。此外,该文提出了遍历带有输出标志位的广义表的深度优先搜索算法,以生成对应的指令表。算法时间复杂度最佳情况为O(n),最差为O(n^2)。The ladder diagram is one of the four programmable logic controller(PLC)programming languages defined by the IEC 61131-3 standard.However,since the ladder diagram cannot be directly executed by processors,most commercial PLC programming systems convert the ladder diagram into an instruction list similar to assembly language that is convenient for generating machine instructions.This paper presents a transformation algorithm based on AOV(activity on vertex)and Lists.Unlike in existing List algorithms,this algorithm solves the multi-coil output problem.In addition,a depth-first search algorithm is used to traverse the generated Lists with output flag bits to generate a correct instruction list.The optimal time complexity of the algorithm is O(n),and the worst is O(n^2).

关 键 词：可编程逻辑控制器 梯形图 指令表 AOV图 广义表 

分 类 号：TP273.5[自动化与计算机技术—检测技术与自动化装置]