一个微型表达式求值器

• 下载源代码 - 78.28 KB

引言

@TinyExe 代表“一个微型表达式求值器”。它是一个小型命令行实用程序，允许您输入简单和更复杂的数学公式，这些公式将被即时求值和计算。尽管 CodeProject 和其他地方已经有许多表达式求值器，但这个项目主要用于演示 @TinyPG 的功能。 @TinyPG 是一个用于创建各种类型语言的解析器生成器，并在 CodeProject 的另一篇 文章中进行了介绍。

因此，这个表达式求值器基于典型的解析器/词法分析器编译理论。语义的实现是纯 C# 代码后台完成的。由于 @TinyPG 也生成纯净且易于阅读的 C# 代码，因此这个表达式求值器是一整套完全独立的 C# 源代码，无需任何外部依赖。因此，您可以轻松地在您自己的项目中使用它。本项目还包含用于生成扫描器和解析器的语法文件，因此您可以随时根据自己的需要修改语法。

在本文中，我将主要解释

• 此表达式求值器当前支持的一些功能
• 如何将此求值引擎集成到您自己的项目中
• 如何扩展此求值器的功能以适应您的特定需求

背景

由于缺乏好的示例语法和演示如何使用 @TinyPG，我决定构建一个演示项目，展示 @TinyPG 如何用于更高级的语法，例如表达式求值器。那么，为什么还要创建一个表达式求值器作为演示呢？因为，运行时表达式求值器很酷！以 Excel 为例，它是当今使用最广泛的运行时表达式求值器。在您自己的应用程序中释放一些 Excel 的强大功能，岂不是一件很棒的事情？

所以，因为运行时表达式求值器可能会派上用场，我认为这将是一个很好的演示项目。请注意，这不仅仅是一个演示。这个表达式求值器功能齐全，随时可以执行！

尽管 @TinyPG 提供了一个简单的教程，教您如何编写一个简单的表达式求值器，但我决定展示 @TinyPG 可以用于生成强大的 LL(1) 语法。本项目还清晰地展示了如何将语法和句法与语义干净地分离。计算规则与解析器和扫描器是分开实现的。

使用工具

该工具的功能基于 Excel 中使用的实现。目前，表达式求值器支持以下功能

• 它可以解析数学表达式，包括对最常用函数的支持，例如
  • 4*(24/2-5)+14
  • cos(Pi/4)*sin(Pi/6)^2
  • 1-1/E^(0.5^2)
  • min(5;2;9;10;42;35)
• 支持以下函数：
  • 关于 Abs Acos And Asin Atan Atan2 Avg Ceiling Clear Cos Cosh Exp Fact Floor Format Help Hex If Floor Left Len Ln Log Lower Max Min Mid Min Not Or Pow Right Round Sign Sin Sinh Sqr Sqrt StDev Trunc Upper Val Var
• 基本的字符串函数
  • "Hello " & "world"
  • "Pi = " & Pi
  • Len("hello world")
• 布尔运算符
  • true != false
  • 5 > 6 ? "hello" : "world"
  • If(5 > 6;"hello";"world")
• 函数和变量声明
  • x := 42
  • f(x) := x^2
  • f(x) := sin(x) / cos(x)    // 使用内置函数声明新的动态函数
  • Pi
  • E
• 递归和作用域
  • fac(n) := (n = 0) ? 1 : fac(n-1)*n     // fac 以不同参数调用自身
  • f(x) = x*Y       // x 在函数作用域内，Y 在全局作用域内
• 辅助函数
  • Help() - 列出所有内置函数
  • About() - 显示有关实用程序的说明
  • Clear() - 清除显示

基本上，在启动工具时，只需在命令行上直接输入要计算的表达式。使用向上和向下按钮可自动完成以前输入的表达式和公式。这难道比使用 Windows 计算器方便得多吗？总之，目前只支持 5 种数据类型：double、hexidecimal、int、string 和 boolean。请注意，整数（以及十六进制数）在默认情况下用于计算时总是转换为双精度浮点数。使用 int() 函数显式转换为整数。

该工具使用以下运算符优先级规则

1.	( ), f(x)	分组，函数
2.	!   ~   -   +	(大多数)一元运算
3.	^	幂运算（Excel 规则：a^b^c -> (a^b)^c
3.	*   /   %	乘法，除法，取模
4.	+   -	加法和减法
4.	&	字符串连接
5.	<   <=   >   >=	比较：小于，等等
6.	=   !=   <>	比较：等于和不等于
7.	&&	逻辑与
8.	||	逻辑或
9.	?:	条件表达式
10	:=	赋值

嵌入求值引擎

如果您想将此微型表达式求值器嵌入到您自己的项目中，只需几个简单的步骤。

1. 将 Evaluator 文件夹（包括其中的所有类）复制到您自己的 C# 项目中。简而言之，我们有以下类
   1. Context - context 保存所有可用的已声明函数和变量以及作用域堆栈。
   2. Expression - 包装类，用于保存和求值表达式。
   3. Function - 定义函数的原型。函数必须具有名称、指向实际函数实现的指针（委托）以及设置的最小和最大允许参数数量。
   4. Functions - 此类定义默认可用函数的列表。随时可以添加您自己的函数。
   5. Parser - 表达式的解析器。此代码由 TinyPG 生成。
   6. ParseTree - 解析表达式后的结果解析树。此代码由 TinyPG 生成。
   7. ParseTreeEvaluator - 这是 ParseTree 的子类，实现了运算符的核心语义。代码应该很容易理解，因为类的所有方法都直接对应于定义的语法（参见TinyExe.tpg）。
   8. Scanner - 这是解析器用于匹配表达式中终结符的扫描器。此代码也由 TinyPG 生成。
   9. Variables - 目前实现为一个（区分大小写的）字典。变量只是一个 <name, value> 对。
2. 将命名空间（在本例中为 TinyExe，但您可以随时更改）添加到您的类中。
3. 然后，插入以下代码来执行求值

   string expr = "1*3/4"; // define the expression as a string
   ...
   // create the Expression object providing the string
   Expression exp = new Expression(expr);
   
   // check for parse errors
    if (exp.Errors.Count > 0)
    {
        Console.WriteLine(exp.Errors[0].Message);
        return;
    }
    
    // No parse error, go ahead and evaluate the expression
    // Note that Eval() always returns an object that can be of various types
    // you will need to check for the type yourself
    object val = exp.Eval();
    
    // check for interpretation errors (e.g. is the function defined?)
    if (exp.Errors.Count > 0)
    {
        Console.WriteLine(exp.Errors[0].Message);
        return;
    }
    // nothing returned, nothing to evaluate or some kind of error occured?
    if (val == null)
        return;
        
    //print the result to output as a string
    Console.WriteLine(string.Format(CultureInfo.InvariantCulture, "{0}", val));

上面的代码会优雅地处理任何表达式。但为了绝对确保，您可能需要使用 try...catch 语句捕获任何异常。

扩展求值引擎

基本上，有两种扩展方式

1. 在求值器允许的语法范围内添加您自己的内置函数
2. 增强或更改语法，从而改变语法

添加静态函数

添加新函数的最简单方法是打开 Functions 类，并在 InitDefaults() 方法中添加您的实现。如果您更喜欢将函数外部化，那么您应该将函数添加到 Context.Default.Functions。

例如

Context.Default.Functions.Add("myfunc", new StaticFunction("MyFunc", MyFunc, 2, 3));

其中 MyFunc 函数声明为

private static object MyFunc(object[] parameters) { ... }

参数作为对象列表传递。对象的数量将始终与声明中指定的数量相同，在此情况下，最少 2 个参数，最多 3 个。函数需要检查参数数量并检查传递的类型是否正确。

在更高级的设置中，例如，如果您需要访问 Context 对象，或者项目中的其他类，您可以实现自己的 Function 类版本。您需要创建一个派生自 Function 类的子类并实现 Eval() 方法。此外，您还需要负责参数的初始化、Parametersettings 并处理作用域。例如，可以查看 ClearFunction 类。

更改语法

为了更改语法并为表达式语言添加新功能，例如添加对额外数据类型（即 Date/Time、Money）的支持，或者允许自定义数据类型（即 structs），或者甚至更奇特的：允许评估 JavaScript，您需要对解析器和编译器理论有基本的了解。请参阅 @TinyPG 解析器生成器文章，它解释了如何为您的语言创建解析器的基础知识。

仅仅更改语法是不够的。更改用于解析输入的语法非常简单，但语义（代码后台）也需要相应地更新。幸运的是，生成的 ParseTree 使用起来相当简单。例如，如果我们想支持一个新规则，例如 IF-THEN-ELSE 语句。我们可以在语法文件中添加一个新语句（请参阅随附的TinyExe.tpg）

IfThenElseStatement	-> IF RelationalExpression THEN Expression (ELSE Expression)?;

使用 @TinyPG 为 Scanner、Parser 和 ParseTree 生成代码时，通常 ParseTree 会包含一个名为

protected virtual object EvalIfThenElseStatement
		(ParseTree tree, params object[] paramlist)

如您所见，该方法声明为 virtual，这意味着您可以在子类中重写此方法。这正是我在 TinyExe 中所做的。ParseTreeEvaluator 是 ParseTree 的子类，并包含所有必需的重写。将其放入子类中的主要原因是，我现在可以一遍又一遍地更改解析器的语法并生成新的 ParseTree，而不会覆盖子类。

因此，您需要做的是在 ParseTreeEvaluator 类中重写该函数。您需要理解，该方法是在评估解析树时即时调用的。在解析输入的某个点，Parser 创建了一个新的 ParseNode 类型为 IfThenElseStatement。在评估此节点期间，将调用相应的 EvalIfThenElseStatement（您重写的方法！）。

在此方法入口点，您需要理解当前 ParseNode （类型为 IfThenElseStatement）实际上是 this。因为该语句包含 6 个部分（其中 ELSE 部分的最后 2 个是可选的），this 将包含 4 个或 6 个节点

1. this.Nodes[0] 对应于 ParseNode 类型为 IF
2. this.Nodes[1] 对应于 RelationalExpression
3. this.Nodes[2] 对应于 ParseNode 类型为 THEN
4. this.Nodes[3] 对应于 Expression 节点
5. 如果 this.Nodes[4] 存在，它将对应于 ELSE 节点
6. 如果 this.Nodes[5] 存在，它将对应于 Expression 节点。

因此，我希望再次清楚，ParseTree 的结构非常简单，并且可以快速追溯到原始语法。

现在，真正有趣的节点当然是节点 1、3 和 5。所以，我们首先评估 Nodes[1]。因为 Nodes[1] 是一个非终结符，这意味着它可能包含一个完整的子树。这个子树需要被求值。为了更方便，您可以使用辅助函数 this.GetValue().

object result = this.GetValue(tree, TokenType.RelationalExpression, 0);

请注意，我们期望求值结果是布尔值（true 或 false），但我们无法确定。因此，请务必先检查返回值类型。如果结果不是布尔值，则引发错误。

如果结果为 true，那么我们可以重复此过程，评估 Nodes[3] 并返回此值。否则，我们评估 Nodes[5]（如果存在）并返回它。

这基本上是支持扩展的两种方式。如果您有其他问题，请随时给我写信。

关注点

除了编写一个功能齐全、易于使用、功能全面、功能强大的微型公式计算实用程序，它远远优于默认的 Windows 计算器之外，我希望本项目还能很好地展示 @TinyPG 如何在实际场景中应用。

当然，总有可以添加的新功能，但就目前而言，我认为这个演示很好地展示了如何通过掌握一些基本的语法、解析器和当然还有一些 C# 知识来创建相当强大的语言。

就这样。如果您有任何关于新功能、评论或意见的想法，请留言！

历史历史

@TinyExe v1.0

Tiny Expression Evaluator Version 1.0 于 2011 年 8 月 16 日发布。此版本包含以下功能

• 数学函数和表达式的求值
• 默认内置函数
• 运行时函数和变量声明
• 函数作用域和全局变量
• 递归函数调用
• 多数据类型支持（double、int、hex、bool 和 string）
• 递归函数调用
• 预定义常量 Pi 和 E
• 布尔运算符和赋值