梯形图是IEC 61131-3标准定义的4种可编程逻辑控制器（programmable logic controller，PLC）编程语言之一，但因为梯形图无法被处理器直接执行，所以大多数商用PLC编程系统都会将梯形图转换为类似汇编语言的指令表，便于生成机器指令。该文提出一种基于AOV（activity on vertex）图和广义表的转换算法，相比基于广义表的现有算法，重点解决了多线圈输出问题。此外，该文提出了遍历带有输出标志位的广义表的深度优先搜索算法，以生成对应的指令表。算法时间复杂度最佳情况为O（n），最差为O（n2）。
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(n2).
[1] WU H F, YAN Y, SUN D F, et al. A customized real-time compilation for motion control in embedded PLCs[J]. IEEE Transactions on Industrial Informatics, 2019, 15(2):812-821.
[2] JIANG Y, ZHANG H H, SONG X Y, et al. Bayesian-network-based reliability analysis of PLC systems[J]. IEEE Transactions on Industrial Electronics, 2013, 60(11):5325-5336.
[3] IEC. IEC 61131-3 Standard-programmable controllers-Part 3:Programming languages[S]. Geneva:International Electrical Commission, 2003.
[4] JOHN K H, TIEGELKAMP M. IEC 61131-3:Programming industrial automation systems[M]. 2rd ed. New York:Springer-Verlage, 1995.
[5] WELCH J T. Translating relay ladder logic for CCM solving[J]. IEEE Transactions on Robotics and Automation, 1997, 13(1):148-153.
[6] WELCH J T. An event chaining relay ladder logic solver[J]. Computers in Industry, 1995, 27(1):65-74.
[7] XIE H X, ZHUANG Z Y. An algorithm for generating Boolean expressions in VHDL based on ladder diagrams[J]. Mathematical Problems in Engineering, 2015, 2015:530586.
[8] KIM J I, PARK J, KWON W H. Architecture of a ladder solving processor for programmable controllers[J]. Microprocessors and Microsystems, 1992, 16(7):369-379.
[9] 韩兵兵. PLC梯形图编程系统研究与实现[D]. 广州:华南理工大学, 2013 HAN B B. Research and implementation of PLC ladder programming system[D]. Guangzhou:South China University of Technology, 2013. (in Chinese)
[10] KIM H S, KWON W H, CHANG N. A translation method for ladder diagram with application to a manufacturing process[C]//Proceedings of 1999 IEEE International Conference on Robotics and Automation. Detroit, USA:IEEE, 1999:793-798.
[11] 葛芬, 吴宁. 基于AOV图及二叉树的梯形图与指令表互换算法[J]. 南京航空航天大学学报, 2006, 38(6):754-758. GE F, WU N. Transformation algorithm between ladder diagram and instruction list based on AOV diagraph and binary tree[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2006, 38(6):754-758. (in Chinese)
[12] YAN Y, ZHANG H P. Compiling ladder diagram into instruction list to comply with IEC 61131-3[J]. Computers in Industry, 2010, 61(5):448-462.
[13] YAN Y, ZHANG H P. A new translation algorithm from ladder diagrams to instruction lists[J]. IFAC Proceedings Volumes, 2008, 41(2):14804-14809.
[14] 朱兆斌. 嵌入式数控系统软PLC模块的研究与实现[D]. 南京:南京航空航天大学, 2009. ZHU Z B. Research and implementation of SoftPLC of embedded NC machine[D]. Nanjing:Nanjing University of Aeronautics and Astronautics, 2009. (in Chinese)
[15] MOONGA K H, YOU L R, LIU S J. Algorithm for compiling unrestricted ladder diagram to IEC 61131-3 compliant instruction list[C]//Proceedings of the World Congress on Engineering. London, UK:WCE, 2011.
[16] 林懋恺, 王晓芳, 林亨. PLC梯形图的广义表转换[J]. 计算机工程, 2007, 33(13):75-77, 95.LIN M K, WANG X F, LIN H. Transformation from PLC ladder diagram to Lists[J]. Computer Engineering, 2007, 33(13):75-77, 95. (in Chinese)
[17] REINHARD D. Graph theory[M]. New York:Springer-Verlag, 1997.
