Sprache.Calc：又一个表达式求值器
4.98/5 (31投票s)
本文演示了使用语法继承来构建 Sprache 解析器的一种技术。
引言
本文演示了使用语法继承来构建解析器的一种技术。继承允许基于现有语法构建新语法，通过添加新规则或覆盖继承的规则来加速新解析器的开发。对基础语法的任何更改都会自动反映在继承的语法中。当解析器需要支持多种语言方言或版本时，此技术尤其有用。
许多解析器工具包（如 ANTLR 或 Nitra）都支持语法继承，并且许多使用面向对象语言作为语法描述语言（如 Sprache 和 Irony）的工具都内置了此功能。
可扩展的表达式求值器库是本文的示例代码。该求值器支持算术运算、自定义函数和参数。它接收表达式的 `string` 表示形式，并将其转换为结构化的 LINQ 表达式实例，该实例可以轻松编译为可执行的委托。与 NCalc 等解释型表达式求值器不同，编译后的表达式的执行速度与原生 C# 方法一样快。以下是现成的求值器库的用法示例：
// using variables
var s = "Sin(y/x)";
var expr = calc.ParseExpression(s, x => 2, y => 3.14);
var func = expr.Compile();
Console.WriteLine("Result = {0}", func());
// custom functions
calc.RegisterFunction("Mul", (a, b, c) => a * b * c);
expr = calc.ParseExpression("2 ^ Mul(PI, a, b)", a => 2, b => 10);
Console.WriteLine("Result = {0}", func.Compile()());
// end-user's functions
calc.RegisterFunction("Add", "a + b", "a", "b");
expr = calc.ParseExpression("Add(353, 181)");
Console.WriteLine("Result = {0}", expr.Compile()());
 |
PM> Install-Package Sprache.Calc |
Sprache 工具包概述
Sprache 工具包是一个轻量级的函数式库，用于直接在 C# 代码中构建解析器。作者声称它介于正则表达式和 ANTLR 等全功能工具集之间，并不打算与“工业级”语言工作台竞争。
我认为 Sprache 是一个出色的工具，非常适合各种与解析相关的任务。对我来说，Sprache 最吸引人的功能是它能够使用 LINQ 查询语法来定义解析器和强类型解析结果。Sprache 鼓励逐步进行语法设计，并提倡解析器的测试驱动开发。当然，解析器组合子并非没有缺点（诊断复杂和错误恢复能力差），但这些细节超出了本文的范围。
Sprache 中的解析器是将输入字符串转换为其他内容的函数。与传统的解析器框架不同，Sprache 不使用代码生成。解析器直接在源代码中定义，并可立即用于解析文本。这允许在编写解析器时并行编写单元测试。以下是一个简单的解析器示例，它会解析一系列 A 字符：
var parseA = Parse.Char('A').AtLeastOnce();
使用 Sprache 内置的扩展方法（如 `Or`、`And`、`Many` 等），通常可以通过 LINQ 查询推导式来调用，将简单的解析器组合成复杂的解析器。
Parser<string> identifier =
from leading in Parse.WhiteSpace.Many()
from first in Parse.Letter.Once()
from rest in Parse.LetterOrDigit.Many()
from trailing in Parse.WhiteSpace.Many()
select new string(first.Concat(rest).ToArray());
var id = identifier.Parse(" abc123 ");
Assert.AreEqual("abc123", id);
完整的规则集，即语言语法，通常看起来像一个带有委托字段的静态类。要了解更多关于 Sprache 工具包的信息，请参阅 Nicholas Blumhardt 的这篇介绍性文章。
表达式求值器设计
表达式求值器支持三种模式：简单、科学和可扩展。简单求值器支持算术运算和十进制浮点数操作数、一元负号和括号。科学模式增加了对十六进制和二进制数字、指数表示法以及 `System.Math` 函数的支持。可扩展模式允许使用带重载支持的参数化表达式和自定义函数。
后续模式支持其前身的所有功能并添加自己的功能，因此描述表达式求值器输入语言的语法以层次结构组织。
表达式解析器是将其源字符串转换为 LINQ 表达式的函数，该表达式可以轻松地编译为委托并像普通 .NET 方法一样执行。
var expr = "4*(1/1-1/3+1/5-1/7+1/9-1/11+1/13-1/15+1/17-1/19+10/401)";
var func = calc.ParseExpression(expr).Compile();
var result = func();
简单求值器
简单求值器基于 Sprache LinqyCalculator 示例。语法经过优化，可以简化解析过程中 LINQ 表达式的实例化。
Expr ::= Term ("+"|"-" Term)*
Term ::= InnerTerm ("*"|"/"|"%" InnerTerm)*
InnerTerm ::= Operand ("^" Operand)
Operand ::= NegativeFactor | Factor
NegativeFactor ::= "-" Factor
Factor ::= "(" Expr ")" | Constant
Constant ::= Decimal
Sprache 解析器通常定义为静态 lambda 函数。静态字段不能在派生类中重新定义，因此我们将它们定义为虚拟属性。
// Original parser:
public static readonly Parser<Expression> ExpressionInParentheses =
from lparen in Parse.Char('(')
from expr in Expr
from rparen in Parse.Char(')')
select expr;
// Modified parser:
protected virtual Parser<Expression> ExpressionInParentheses =>
from lparen in Parse.Char('(')
from expr in Expr
from rparen in Parse.Char(')')
select expr;
进行此相当平凡的转换后，任何规则都可以在派生类中被覆盖。为了启用解析器的单元测试，请将属性声明为 `protected internal`。
简单计算器的完整语法可以在这里找到。它实际上与 Sprache 的 LinqyCalculator 示例相同。
科学模式
科学计算器继承自简单计算器，因此自动支持简单计算器的所有功能。为了支持二进制和十六进制数字，它引入了新的语法规则。
protected virtual Parser<string> Binary =>
Parse.IgnoreCase("0b").Then(x =>
Parse.Chars("01").AtLeastOnce().Text()).Token();
protected virtual Parser<string> Hexadecimal =>
Parse.IgnoreCase("0x").Then(x =>
Parse.Chars("0123456789ABCDEFabcdef").AtLeastOnce().Text()).Token();
仅添加新规则是不够的，因为基础语法不知道何时应用它们。二进制和十六进制数字是常量，因此我们将它们添加到基础语法的 `Constant` 规则中。请注意，`Binary` 和 `Hexadecimal` 解析器返回字符串，而 `Constant` 解析器返回 LINQ 表达式，因此我们需要辅助方法将字符串转换为 LINQ 表达式。最后，支持十进制、二进制和十六进制数字的 `Constant` 解析器如下所示：
protected override Parser<Expression> Constant =>
Hexadecimal.Select(x => Expression.Constant((double)ConvertHexadecimal(x)))
.Or(Binary.Select(b => Expression.Constant((double)ConvertBinary(b))))
.Or(base.Constant);
现在让我们添加对函数支持。我们需要另外两个规则：
protected virtual Parser<string> Identifier =>
Parse.Letter.AtLeastOnce().Text().Token();
protected virtual Parser<Expression> FunctionCall =>
from name in Identifier
from lparen in Parse.Char('(')
from expr in Expr.DelimitedBy(Parse.Char(',').Token())
from rparen in Parse.Char(')')
select CallFunction(name, expr.ToArray());
`CallFunction` 辅助方法简单地创建了一个用于调用 `System.Math` 静态方法的 LINQ 表达式。
protected virtual Expression CallFunction(string name, Expression[] parameters)
{
var methodInfo = typeof(Math).GetMethod(name, parameters.Select(e => e.Type).ToArray());
if (methodInfo == null)
{
throw new ParseException(string.Format("Function '{0}({1})' does not exist.",
name, string.Join(",", parameters.Select(e => e.Type.Name))));
}
return Expression.Call(methodInfo, parameters);
}
同样，我们需要覆盖一个基础语法规则来指示何时应用新规则。现在，找到一个需要覆盖的规则不像处理二进制和十六进制常量那样明显。应该根据函数调用操作的优先级来选择合适的规则。可以很容易地看出，它应该具有最高优先级，与括号相同。例如，在计算 Sin(2) \* Cos(3) 时，我们必须先计算函数值，然后执行乘法。
在基础语法中，括号包含在 `Factor` 规则中，因此我们将覆盖它。通过调用 `base.Factor`，我们表明我们仍然支持基础语法所支持的所有内容。
protected override Parser<Expression> Factor =>
base.Factor.XOr(FunctionCall);
添加自定义函数
表达式求值器最高级的版本继承自科学计算器类。添加自定义函数不引入新语法，因此我们无需添加新语法规则。我们唯一需要修改的是生成函数调用 LINQ 表达式的方法。这是它的伪代码：
override Expression CallFunction(string name, Expression[] parameters)
{
if there is a custom function named 'name',
{
return an expression to call this function
with the given parameters;
}
// otherwise, fall back to System.Math method
return base.CallFunction(name, parameters);
}
我们的计算器的任何自定义函数都可以表示为一个 `Func
"Min:2" -- Min function with two arguments
"Min:5" -- Min function with five arguments, etc.
上面的伪代码会变成这样：
protected override Expression CallFunction(string name, Expression[] parameters)
{
// try to find a custom function
var mangledName = name + ":" + parameters.Length;
if (CustomFuctions.ContainsKey(mangledName))
{
return Expression.Call(...); // call named function
}
// fall back to System.Math method
return base.CallFunction(name, parameters);
}
生成的 `Expression.Call` 表达式存在一个问题。问题在于 `Expression.Call` 需要一个 `MethodInfo` 实例，因此它只支持调用现有的方法，而自定义函数是在运行时创建的。为了解决这个问题，我们定义了一个适配器方法来调用命名函数：
private double CallCustomFunction(string name, double[] parameters) =>
CustomFuctions[name](parameters);
该方法在编译时存在，可用于创建 `Expression.Call` 表达式。为了获取此方法的 `MethodInfo` 实例，我们使用 `Func` 委托构造函数（它比使用 `System.Reflection` 更快、更安全）。参数列表应使用 `Expression.NewArrayInit` 转换为数组，如下所示：
protected override Expression CallFunction(string name, Expression[] parameters)
{
// try to find a custom function
var mangledName = name + ":" + parameters.Length;
if (CustomFuctions.ContainsKey(mangledName))
{
// prepare parameters for CallCustomFunction
var newParameters = new List<Expression>();
newParameters.Add(Expression.Constant(mangledName));
newParameters.Add(Expression.NewArrayInit(typeof(double), parameters));
// call this.CallCustomFunction(mangledName, double[]);
var callCustomFunction = new Func<string, double>(CallCustomFunction).Method;
return Expression.Call(Expression.Constant(this), callCustomFunction, newParameters.ToArray());
}
// fall back to System.Math method
return base.CallFunction(name, parameters);
}
向表达式添加参数
添加参数需要新的语法。参数只是一个标识符，可以出现在常量或函数调用出现的地方。
protected virtual Parser<Expression> Parameter => Identifier;
protected override Parser<Expression> Factor => Parameter.Or(base.Factor);
在这里，我们终于遇到了语法冲突！`Factor` 规则有两个选择，都以标识符开头：`Parameter` 和 `Function`。当解析器找到一个标识符时，它不知道接下来该解析什么（参数还是函数），除非它向前查看。如果标识符后面跟着“(”符号，它必须是函数，否则就是参数。
据我所知，Sprache 不会帮助查找此类冲突。ANTLR 或 Irony 等全功能工具集在处理您的语法时会自动检测到它们，但在 Sprache 中，您只能通过失败的单元测试来检测它们（这就是为什么测试对于基于 Sprache 的解析器如此重要）。
我们的冲突很容易解决：我们只需将 `Parameter` 定义为“后面没有“(”符号的标识符”。这个规则不会引起冲突，因为它消除了歧义。它看起来是这样的：
protected virtual Parser<Expression> Parameter =>
// identifier not followed by a '(' is a parameter reference
from id in Identifier
from n in Parse.Not(Parse.Char('('))
select GetParameterExpression(id);
`Parse.Not` 解析器类似于正则表达式中的负向前瞻：它不会移动当前位置，并且如果给定的解析器（在此例中为 `Parse.Char('(')`) 失败，它就会成功。
处理参数
与绑定到求值器实例的自定义函数不同，参数是绑定到表达式的。表达式可以使用不同的参数值多次进行求值。命名参数作为 `Dictionary
为了处理参数，我们需要将生成的表达式类型从 `Expression
var function = calc.ParseFunction("y/x").Compile();
var parameters = new Dictionary<string, double>{ { "x", 2 }, { "y", 4 } };
var result = function(parameters);
让我们生成一个访问命名参数的 LINQ 表达式。如果参数名称未知，我们可以尝试查找 `System.Math` 常量。此技巧允许自动使用内置的数学常量，如 PI 和 E。
protected virtual Expression GetParameterExpression(string id)
{
// TODO: try to get a named parameter
// return an expression for accessing parameters[id]
// try to find a constant (static field) in System.Math class
var systemMathConstants = typeof(System.Math).GetFields(BindingFlags.Public | BindingFlags.Static);
var constant = systemMathConstants.FirstOrDefault(c => c.Name == id);
if (constant == null)
{
throw new ParseException(string.Format("Parameter or constant '{0}' does not exist.", id));
}
// return System.Math constant value
return Expression.Constant(constant.GetValue(null));
}
生成类似“parameters[name]”的索引器访问表达式可能很棘手，除非您记得 C# 编译器将索引器视为名为“Item”的属性。根据约定，属性 getter 的名称类似于“get_PropertyName”，setter 的名称类似于“set_PropertyName”，因此读取命名参数只是调用“get_Item”方法。
var getItemMethod = typeof(Dictionary<string, double>).GetMethod("get_Item");
return Expression.Call(ParameterExpression, getItemMethod, Expression.Constant(name));
为了简单起见，我们生成的表达式不会检查是否存在具有给定名称的参数。`Dictionary` 类实际上会检查它，并在出现问题时抛出异常。这是参数访问生成器代码的完整主体：
protected virtual Expression GetParameterExpression(string name)
{
// try to find a constant in System.Math
var systemMathConstants = typeof(System.Math).GetFields(BindingFlags.Public | BindingFlags.Static);
var constant = systemMathConstants.FirstOrDefault(c => c.Name == name);
if (constant != null)
{
// return System.Math constant value
return Expression.Constant(constant.GetValue(null));
}
// return parameter value: Parameters[name]
var getItemMethod = typeof(ParameterList).GetMethod("get_Item");
return Expression.Call(ParameterExpression, getItemMethod, Expression.Constant(name));
}
参数的语法糖
本文开头的使用示例包含了指定参数值的这种语法糖：
var expr = calc.ParseExpression("Sin(y/x)", x => 2, y => System.Math.PI);
这种语法比创建和填充 `Dictionary
public Expression<Func<double>> ParseExpression(string text,
params Expression<Func<double, double>>[] parameters)
{
var paramList = new Dictionary<string, double>();
foreach (var p in parameters)
{
var paramName = p.Parameters.Single().Name;
var paramValue = p.Compile()(0);
paramList[paramName] = paramValue;
}
return ParseExpression(text, paramList);
}
关于单元测试的一点说明
语法继承为需要单元测试的 Sprache 解析器增加了额外的负担。单元测试必须确保每个解析器类仍然能够与新的和覆盖的规则一起工作。我们不仅要测试每个类中添加的方法，还要测试所有继承的方法。
解决此问题的直接方法是使用继承进行单元测试。基础测试类定义了一个虚拟方法 `CreateCalculator`，该方法创建用于单元测试的表达式求值器实例。派生测试类会覆盖 `CreateCalculator` 方法并返回超类实例，因此从基础测试类继承的所有测试方法都会自动测试该超类实例。
结论
语法继承是一种强大的技术，有助于控制复杂性并加速新解析器的开发。由于继承，基础语法中定义的大部分规则都在派生语法中得到了重用，这使得开发人员可以将精力集中在新规则和与基础版本不同的功能上。在基于 Sprache 的解析器中，语法继承促使定义更小、可重用的规则，以及逐步进行测试驱动的解析器开发。以下是快速总结：
- 将解析器声明为虚拟属性而不是静态字段
- 将语法分解为小型可重用规则
- 为每个原子解析器编写单元测试
- 使用“
protected internal”访问修饰符启用单元测试 - 单元测试必须按照与解析器类相同的层次结构组织
参考文献
Sprache.CalcNuGet 包：https://nuget.net.cn/packages/sprache.calc- GitHub 上的最新源代码：https://github.com/yallie/Sprache.Calc
- 本文的俄语版本：http://habrahabr.ru/post/228037/
历史
- 2014 年 7 月 10 日：初始发布
- 2016 年 2 月 20 日：更新文章以使用 C# 7.0 语法。
- 2019 年 3 月 10 日：添加了定义为 `string` 的自定义函数（感谢 Andrey Leskov）