Flee - 快速轻量级表达式求值器

• 下载演示应用程序 - 62.8 KB
• 下载编译库 - 121 KB
• 下载源代码 - 134 KB
• 从 CodePlex 下载最新版本

引言

Flee 是一个 .NET 库，允许您解析和评估任意表达式。它与其他表达式求值器的主要区别在于，它使用自定义编译器将表达式转换为 IL，然后使用轻量级代码生成 (Lightweight CodeGen) 在运行时将 IL 发射到动态方法中。这意味着表达式求值比使用解释性表达式求值器快几个数量级。事实上，库和表达式语言的整个设计都旨在使求值尽可能快。

特点

以下是主要功能列表

• 快速高效的表达式求值
• 使用自定义编译器将表达式编译为 IL
• 小巧轻量级的库
• 为表达式生成的代码可以进行垃圾回收
• 不创建任何停留在内存中的动态程序集
• 支持所有算术运算，包括幂 (^) 运算符
• 支持字符串、字符、布尔和浮点文字
• 支持 32/64 位、有符号/无符号和十六进制整数文字
• 具有真正的条件运算符
• 发出短路逻辑运算
• 允许自定义表达式编译

关于轻量级代码生成 (Lightweight CodeGen)

轻量级代码生成 (LCG) 是 .NET 2.0 中引入的一项功能，用于实现高效的运行时代码生成。使用其 DynamicMethod 类，您可以在运行时创建方法，设置方法体的代码，最后调用创建的方法。它的主要优点是生成的方法及其代码在不再被引用时可以进行垃圾回收，并且它不会生成任何停留在内存中的动态程序集。它的一个缺点是创建方法体的唯一方法是发出 IL。由于 IL 基本上是一种汇编语言形式，因此即使执行简单的任务也需要大量的指令并了解 CLR 的低级工作原理。例如，这是评估表达式 DateTime.Now.ToString() 所需的 IL

L_0001: call valuetype [mscorlib]System.DateTime [mscorlib]System.DateTime::get_Now()
L_0006: stloc.0 
L_0007: ldloca.s dt
L_0009: constrained [mscorlib]System.DateTime
L_000f: callvirt instance string [mscorlib]System.Object::ToString()

自动化表达式到 IL 的转换是这个库的用武之地。本质上，它与 C# 编译器做同样的事情，只是它在运行时编译，将 IL 发射到内存而不是程序集，并且旨在处理表达式（它们是完整编程语言的子集）。

演练：创建和评估表达式

在此演练中，我们将使用表达式 sqrt(a^2 + b^2) 计算边长为 a 和 b 的三角形的斜边。首先，我们需要添加对 ciloci.Flee.dll 的引用并导入 ciloci.Flee 命名空间。首先，我们需要声明我们的表达式所有者。这是一个类，表达式生成的动态方法将附加到该类。一旦附加，动态方法将作为该类的静态函数运行，并可以访问其所有成员（甚至是非公共成员）。我们将声明一个类并为其提供两个字段来表示三角形的 a 和 b 边

public class ExpressionOwner
{
   public int a;
   public int b;
}

为了在表达式中使用 sqrt 函数，我们必须导入 Math 类。导入决定了除了所有者上的成员之外，哪些成员对表达式可见。默认情况下，不导入任何类型，并且不允许使用完全限定名引用类型。这是一个安全功能：由于表达式在运行时编译和评估，并且可能由用户输入，因此允许他们调用加载到程序中的任何类型上的任意方法不是一个好主意。一旦我们导入 Math 类，我们就可以在表达式中使用它的所有常量和方法。我们将使用 sqrt 函数，但我们不需要 pow 函数，因为幂运算符内置于表达式语言中。我们需要创建 ExpressionOptions 类的一个实例，并使用其 Imports 属性进行实际导入

ExpressionOptions options = new ExpressionOptions();
options.Imports.AddType(typeof(System.Math));

接下来，我们创建表达式所有者的实例并初始化 a 和 b 字段

ExpressionOwner owner = new ExpressionOwner();
owner.a = 4;
owner.b = 5;

现在，我们创建表达式，将所有者和选项传递给它

try
{
    Expression e = new Expression("sqrt(a^2 + b^2)", owner, options);
}
catch (ExpressionCompileException e)
{
    // This exception will be thrown
    // if for any reason the expression cannot be compiled            
}

现在内存中有一个包含表达式代码的方法。表达式有一个 Evaluator 属性，它公开了一个指向此方法的委托。该委托将始终是 ExpressionEvaluator 的一个实例，这是一个在库中定义的通用委托。要评估我们的表达式，我们需要检索委托并将其转换为具有正确返回类型的 ExpressionEvaluator。尽管这看起来比仅仅返回一个对象更麻烦，但它确保了对于评估为值类型的表达式不会发生装箱。应用上述内容，我们现在可以评估我们的表达式

ExpressionEvaluator<double> evaluator = (ExpressionEvaluator<double>)e.Evaluator;
double result = evaluator();

就是这样！您现在可以更新所有者上的字段，然后再次评估表达式以获取更新后的结果。如果您好奇表达式生成了什么 IL，可以使用其 EmitToAssembly() 方法将其 IL 转储到磁盘上的程序集中。然后您可以使用 ILDasm（或者更好的是 Reflector）来检查它。这是我们斜边表达式的 IL

L_0000: ldarg.0 
L_0001: ldfld int32 [ConsoleTester]ConsoleTester.ExpressionOwner::a
L_0006: conv.r8 
L_0007: ldc.i4.2 
L_0008: conv.r8 
L_0009: call float64 [mscorlib]System.Math::Pow(float64, float64)
L_000e: ldarg.0 
L_000f: ldfld int32 [ConsoleTester]ConsoleTester.ExpressionOwner::b
L_0014: conv.r8 
L_0015: ldc.i4.2 
L_0016: conv.r8 
L_0017: call float64 [mscorlib]System.Math::Pow(float64, float64)
L_001c: add 
L_001d: call float64 [mscorlib]System.Math::Sqrt(float64)
L_0022: ret

请注意，作为整数的 a 和 b 字段是如何隐式转换为 double 以用于 ^ 运算符的，以及 ^ 运算符是如何转换为对 Pow 函数的调用的。上面的 IL 流只有 35 字节长，并将 JIT 编译为本机处理器指令。将其与解释性求值器进行比较，后者必须通过多次函数（可能还有反射）调用和 if 语句来评估相同的表达式。

演示应用程序

还有一个演示应用程序，展示了该库的实际用法。这个概念的灵感来自于 Pascal Ganaye 的 演示，用于他的表达式求值器。本质上，该演示通过评估红色、绿色和蓝色分量的表达式来生成图像，其中表达式可以引用当前像素的 x 和 y 坐标。这基本上是绘制函数图的彩色版本。使用该演示将让您很好地了解表达式的评估速度。即使在我家里过时的电脑上，我仍然能够每秒进行超过一百万次评估。这意味着，在现代电脑上，您可以在不到一秒钟的时间内生成一个 800x600 的图像。

表达式语言

该库解析的表达式语言是 C# 和 VB.NET 元素的混合。由于该库的目标是速度，因此该语言是强类型的（与 C# 相同的规则），并且没有后期绑定。与 C# 不同，该语言**不**区分大小写。以下是语言元素的细分

元素	描述	示例
+, -	加法	100 + a
*, /, %	乘法	100 * 2 / (3 % 2)
^	幂	2 ^ 16
-	取反	-6 + 10
+	串联	"abc" + "def"
<<, >>	Shift	0x80 >> 2
=, <>, <, >, <=, >=	比较	2.5 > 100
And, Or, Xor, Not	逻辑	(1 > 10) and (true or not false)
And, Or, Xor, Not	位运算	100 And 44 or (not 255)
If	Conditional	If(a > 100, "greater", "less")
Cast	类型转换	cast(100.25, int)
[]	数组索引	1 + arr[i+1]
.	成员	varA.varB.function("a")
字符串文字		"string!"
字符文字		'c'
布尔文字		true AND false
实数文字	双精度和单精度	100.25 + 100.25f
整数文字	有符号/无符号 32/64 位	100 + 100U + 100L + 100LU
十六进制文字		0xFF + 0xABCDU + 0x80L + 0xC9LU

许可证

该库根据 LGPL 许可。这意味着只要您动态链接（即添加引用）到官方发布中的程序集，您就可以自由地将该库用于任何目的。

实现细节

实现表达式求值器需要两件事：一个将表达式字符串转换为语法树的解析器，以及一个将树转换为 IL 的编译器。

解析器

我选择不自己编写解析器，而是使用了 Grammatica，因为它是由一位专门从事解析和语言理论的人编写的。Grammatica 是一个解析器生成器：一个接受语法（一套语言规则）并输出一个将解析它的类的程序。如果您熟悉递归和正则表达式，为它编写语法并不困难。它具有出色的错误处理功能，并将报告任何无效的语法结构。该库的源代码包包含表达式语言的语法文件，因此您可以了解它的工作原理。如果您想进行比正则表达式提供更强大功能的解析，Grammatica 是一个很棒的工具。不要被它的 alpha 状态所迷惑，它坚如磐石，从未给我带来任何问题。

编写表达式语言的语法后，我让 Grammatica 为我生成了一个解析器。解析器类具有回调方法，我可以挂钩这些方法以了解解析器何时遇到某个语言元素。从那时起，我来决定如何处理该元素。事实证明，表示语言元素的最佳方法是使用树结构。像 1 + 2 这样的表达式将表示为一个 ADD 元素，带有两个表示操作数的子元素。每个元素在设置子元素时都会验证它们，以确保它们对于其特定操作有效，如果无效，则会抛出 ExpressionCompileException。随着不断解析，树会不断构建，直到到达表达式的末尾，您将留下一个代表整个表达式的根节点。此时，我们有一个有效的表达式及其编译表示；我们完成了解析，必须转到代码生成。

编译器

我们现在有一棵由各种运算符和操作数组成的树，我们必须将其转换为 IL。我们树中的每个元素都派生自 ExpressionElement 类，该类要求该元素能够发出 IL。从这里开始，主要的挑战是发出尽可能紧凑且遵循 CLR 类型规则的 IL。这意味着您必须始终注意是在处理值类型还是引用类型。为表达式 mystring.func() 发出的 IL 与为 myint.func() 发出的 IL 不同。为了为我们的方法生成 IL，我们让根元素发出其 IL 以及其所有子元素的 IL。然后，我们在 DynamicMethod 上调用 CreateDelegate 方法，将代码“烧录”到内存中并获得一个指向它的委托。从这里开始，方法的代码已设置且无法更改。

测试

对于这样的项目来说，单元测试至关重要。当您调整表达式的语法时，您必须确保它不会使以前有效的表达式失效，并且评估表达式的结果是正确的。幸运的是，这种类型的项目非常适合单元测试。您所要做的就是创建一个测试，该测试由一个文本文件组成，每行包含一个表达式，以及一个将表达式馈送到求值器的循环。如果您没有收到异常并且结果正确，则测试通过。随着您构建语言并添加新元素，您会不断添加到文本文件中，以便在任何时候，您都可以确定自己没有破坏任何以前的表达式。

结论

这个项目的想法源于我从以前的 项目 中学到的经验。事实证明，人们主要希望能够定义变量并在表达式中对其进行评估。以前的项目允许他们这样做，但由于它与 Excel 兼容，它必须以特定方式评估表达式并支持更动态的类型系统。对于这个项目，我想消除这些限制，并尝试创建一个快速高效的表达式求值器。我还想尝试构建一个编译器，因为这是 每个 程序员都应该做的事情。我期待您的反馈，并计划根据您的反馈积极维护和改进此库。谢谢！

历史

• 2007 年 7 月 26 日：文章首次发布。
• 2007 年 7 月 30 日：修订文章以使其更好。
• 2007 年 8 月 19 日：动态变量和 CalculationEngine 的更新。
• 2007 年 8 月 26 日：添加了关于 ExpressionOptions 的段落。
• 2007 年 10 月 11 日：添加了运算符优先级表。