算法：一种可扩展的表达式解析及计算方法

算法：一种可扩展的表达式解析及计算方法2013-11-14 ibm 王建光,钱韬概述

在应用软件开发领域，对表达式计算的应用有非常广泛的应用。例如，在报表开发中，经常为用户提供公式输入功能，从而实现更灵活的报表汇总；工作流应用软件中，经常利用逻辑条件进行动态配置，从而提供更加灵活的流程配置；另外，在某些 UI 开发中，需要通过某个属性的表达式计算结果来动态控制 UI 组件的显示。所有这些应用都可以归结为一个通用模型，即表达式的解析以及计算。本文旨在提供一种可扩展的表达式解析及其计算方法。

表达式解析的一般条件及因素

本文所讲的表达式是一种以一定的运算规则组合所表达的字符串；另外，通过解析表达式字符串并以其代表的运算规则可以得到一个结果。表达式解析一般需要满足下列条件：

支持的操作符集合

操作符的优先级

操作符所代表的操作规则集合

支持的分隔符集合以及分隔符所代表的意义

支持的数据类型集合

语法约束，如命名规则、分割符所代表的语法规则等

表达式解析除了以上必须满足的条件之外，在有些表达式环境中，可能还支持函数、变量。结合本文所要解决的问题，如下列出可选的条件：

支持的内部函数集合

支持的内部全局变量

支持函数定制

支持自定义变量

支持函数以及操作符重载

以上最后三个可选条件，是一个表达式解析引擎的可扩展支持需要满足的条件。

再谈编译原理

一般的编译过程主要包括词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，如下图所示。其中，词法分析主要任务是输入源程序，对构成源程序的程序进行扫描和分解，识别出一个一个的单词。单词是语言中具有独立意义的最基本结构。一般这些单词包括程序语言所支持的保留字、数据类型、操作符、分隔符以及程序定义的标识符、常量等。

语法分析的主要任务是在词法分析的基础上，根据语言的语法规则把单词序列组合成各类语法单位（一般表示成语法树）。

语义分析的主要任务是进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等语义约束规则。

图 1. 编译一般过程

上述只是非常简要的介绍了一般的编译原理知识，详细知识需要参考编译原理相关的书籍和文档。对于本文所讲的表达式解析，笔者认为其与程序编译具有本质上的相似，只是在问题的复杂性上会简单的很多。表达式解析同样需要首先把输入的表达式字符串分解成一个一个的单词，然后把单词序列组合成语法单位，最后依据表达式的语言环境所定义的语义约束对这些语法单位进行分析计算。因此，我们可以程序编译的基本方法有选择的运用到表达式解析上。