摘要： 提出了利用串并联归并算法以实现PLC梯形图到指令表的转换方法。该算法将梯形图转化为有向无环图，对图中的串并联关系进行分类归并，将串并联结构按层次存储在广义表中，根据广义表生成指令表。该算法克服了传统拓扑排序算法在梯形图结构复杂时产生误判的缺陷，增加了检查逻辑错误的功能。在最佳情况下，该算法的时间复杂度为O(n)，最差情况下为O(n2)，与拓扑排序算法基本一致，有时略优于拓扑排序算法。

关键词: 可编程控制器, 梯形图, 指令表

Abstract: To realize the transformation from ladder diagram to instruction list, a new algorithm is introduced. It translates the ladder diagram into directed acyclic graph, sorts and unites the serial and parallel relationship of the graph, and stores the serial-parallel structure in lists, generates the instruction list based on the lists. Traditional topological sort algorithm applied in the transformation does not always provide the correct instruction list when the structure of the ladder diagram is complex, while the new algorithm overcomes the flaw. The new algorithm provides the function of checking the logical faults in the ladder diagram. The time complexity of the new algorithm is O(n) in the best situation, O(n2) in the worst situation, which is basically the same with the topological sort algorithm. In normal condition, it is a little better than the topological sort algorithm.

Key words: programmable logic controller(PLC), ladder diagram, instruction lists

中图分类号: 

• TP301.6