表达式求值及符号推导

英昌盛

(吉林师范大学 计算机学院，吉林 四平 136000)

0 引言

表达式的分析、求值等运算是编译程序中的一个关键部分。研究翻译程序的工作原理和工作流程，对于教师的教学和研究，对于学生理论联系实际都具有较为实用的意义和价值。

1 系统设计及概要设计

1.1 运算符和数据类型的支持

系统支持算术运算、关系运算和逻辑运算。算术运算符有包括:()、+、-、*、/、^(乘方)，其中^为新增运算符。逻辑运算符包括:!、＆(逻辑与为化简运算符)、|(逻辑或为化简运算符)。关系运算符包括:＞、＞=、==、_(负号)。

系统支持整数及浮点数。在进行算术运算、关系运算、逻辑运算时运算规则和结合性基本同C语言中相应的规则一致。

1.2 数据结构

用户输入的数据是随机的，同时程序处理数据时用栈这种结构实现较好，所以系统采用两个链栈［1］来保存运算量和运算符。因输入的变量个数无法确定，系统采用动态生成链表［2］来存储。

2 系统实现

2.1 算符优先级及数据结构

系统使用结构体数组charindex［］和OPTable［］保存运算符及其对应的优先级。charindex［］用来存放运算符和该运算符的栈外、内优先级在OPTable［］中的下标。charindex［］结构体数组的op域用来保存第i个运算符，index域用来存放第i个运算符在OPTable［］结构体数组相应元素中的下标，如表1［3］所示。

表1 运算符及其栈内、外优先级

OPTable［］的opri域和ipri域分别表示charindex［］数组中第i个运算符对应的栈外、栈内优先级。为方便运算和节省栈的域，OPTable［］的元素个数较charindex［］的元素个数多三项。系统只用一个整数表示一个运算符，而＞=，==，＜=等运算符都是两个……