基于三叉树链表的编译器中间结构的设计方案研究

引言

IEC61131—3组态软件是分布式控制系统中的上位软件，是工程师与系统的接口，可完成控制系统中现场设备运行的逻辑组态，从而实现对系统的控制。随着PLC与DCS系统的应用日趋广泛，IEC6113l一3已经在工业自动化中建立了牢固的国际标准，国内外大部分工业自动化厂商都有提供基于国际标准IEC6113l一3的IEC组态编程系统，IEC组态软件的研发已经成为工业自动化厂商的核心威廉希尔官方网站 。IEC组态软件的实现原理之一是将前端用各种组态语言（ST，LD，FBD，SFC，IL）编写的程序转化成中间结构，再由组态软件编译后端根据不同的硬件平台信息将中间结构编译成在该平台上可执行的目标文件。组态软件编译部分的中间结构是组态软件IEC语言前端与组态软件编译后端的主要接口。好的中间结构可使IEC语言前端做到与目标机器无关，而不依赖于目标机器平台，同时可节省IEC语言前端的翻译工作。现今编译程序使用的中间结构有很多种形式，常见的有逆波兰式、三元式、四元式和树形结构，本文介绍一种基于三叉树链表的中间结构。

1 、总体设计思想

基于树形结构的中间结构是现今大多数编译器中间结构的主流设计方案，比如GCC、LCC、TCC等均使用二叉树或者多又树作为其中间结构。本文介绍的是一种三叉树的设计方案。该方案中，以中间结构表示的高级语言程序单元就是三叉语法树节点组成的多层森林，每一层森林都是一个一维双向链表，链表中的每个“节点”称之为语法树（一棵三叉树），而每棵语法树的节点则称之为树节点。其中，程序单元以POU（程序组织单元）为翻译单位。

每个三叉树节点包括的信息主要有语法树的操作、节点类型、指向三个子树的指针、链表前项与后项指针、关联符号指针等。树节点结构体的数据结构表示如下：

其中，语法操作表示该节点可以完成什么样的“运算”。语法分析树的语法操作符可以分为分别是POU节点操作符、语句操作符和表达式操作符三种类型，这三种类型的语法操作符将在下一节详细介绍，通常可以语法分析树的语法操作来区分不同的语法分析树。

类型是指当前语法分析树所代表的语法操作的类型。

符号指针是指向该节点关联的符号表项，并非所有节点的此项都有内容，具体那些节点中可以关联符号也将在下一节介绍。

图1所示是一个POU程序单元以三叉树链表的中间结构总体表示的总体形式。

采用三叉树森林的方法能够充分的表示正常的高级语言，同时，与其他编译器不同，该方法还引入了POU节点操作符和语句操作符，而省去了前端大量语法翻译的工作，符合IEC工业语言编译器多前端的特征。

2、 中间结构说明

语法分析树的语法操作符可分为POU节点操作符、语句操作符和表达式操作符三种类型。下面来详细介绍这三种语法树节点的各种属性。

2．1 POU节点操作符

POU节点操作符可用于表示POU的开始、结束、作用域和变量定义。各节点属性如表l所列。

其中，语法操作以宏定义的形式声明。符号是该节点关联的符号表项。符号可分为POU符号和变量符号。POU符号包括POU名、参数个数及类型、返回值类型、POU地址等信息；变量符号则包括变量名、类型、作用域和地址等信息。

表l中的唯一节点指整个森林第一层链表中的节点；叶节点指链表中一棵三叉树的叶节点。

2．2 语句操作符

语句操作符分为分支选择操作符、循环操作符、跳出、返回、调用和无条件跳转等。各节点属性如表2所列。

表2中的根节点指森林中一棵三叉树的根节点；中间节点指某三叉树中的中间节点，它既非根节点，也非叶节点。CH00SE的左子节点是条件判定，中子节点是条件为真的内容，右子节点是条件为假的内容。同样，LOOP的左子节点是条件判定，中子节点是循环体，右子节点是循环计数。对于WHILE语句，右子节点可以为空。RETURN的左子节点是返回表达式子树。CALL的左子节点是参数子树，中子节点是调用子树。

2．3 表达式操作符

表达式操作符包括所有的高级语言运算符，如赋值、算术、关系、逻辑运算符等，以赋值、取地址和加法运算符为例，其表达式操作符号主要属性如表3所列。

3 、ST语言代码对应的中间结构表示

本节以一段ST的POU程序为例，将其转化为中间结构，以证明中间结构的可行性。假设此POU中所定义的整型变量为a，b，那么，其POU程序如下：

对应的中间结构如图2所示。其中，EQUAL是等值运算符的宏定义。

4、结束语

本文介绍了一种三叉树的中间结构设计方案。该方案充分考虑了IEC61131—3组态软件的多前端特性，并能够做到不依赖于后端，同时为各语言翻译前端的设计提供了很大的便利。这种中间结构设计在HCC（Hollysys C Compiler）编译器的开发中已经实现，其可行性也得到了验证，并已应用在实际的组态软件开发项目中。

责任编辑：gt