使用 C# 构建通用解释器、数学引擎和解析器

• MathProcessor 类库和示例应用程序的源代码
• MathProcessor_1.0.1.9.zip (编译后的二进制文件)

2014年10月8日：Math Processor 现在已 开源。

目录

1. 引言
2. 使用示例应用程序
3. Math Processor 简介
4. 使用 Math Processor 库
5. 理解核心引擎

1. 引言

首先，这篇文章最好的地方在于我们将尽量让所有内容都极其简单。您不 需要是解析器、编译器等细节的专家，甚至不需要熟悉这些细节。

在深入细节之前，让我们先来看一些我们将要创建的解析器/引擎可以执行的命令示例。

Commands	结果	注释
>> primes(1000000)	2 3 5 ...	前一百万个素数
>> gcd(24,12, 124, 136)	4	给定数字的最大公约数
>> a = array(50, 10, 50) >> b = array(60, 40, 50) >> c = array(80, 60, 10) >> m = matrix(a, b, c) >> d = det(m)	-76000	矩阵的行列式
{ t = vectorin(-16, 0.05, 16); x = sin(8*t/5) * cos(t); y = sin(8*t/5) * sin(t); plot(x, y); }		一个极坐标曲线。

您还可以创建更有趣/高级的图形，例如 MP 用户创建的以下花瓣线图（要了解有关花瓣线数学以及这些图是如何创建的，请参阅这些花瓣线数学教程/示例）。

 

2. 使用示例应用程序

更新于 2013 年 8 月 28 日：此部分是为旧版本编写的。由于有了新的、文档齐全的软件（热门下载），我删除了 此部分的内容，以使文章对新读者来说更容易/更短。旧的下载仍然保留在这些链接中以保留历史记录。

• 所有二进制文件和示例
• 二进制文件源代码
• MathProcessor 类库代码（旧版本）

3. Math Processor 简介

我希望到目前为止您已经对 Math Processor 应用程序进行了一些试用。如果没有，我建议您现在就去做，并尝试熟悉它的工作方式。

Math Processor 引擎提供了比本文讨论的更多的函数和命令。如果您有兴趣了解 Math Processor 提供的更多功能，可以查阅Math Processor 文档。

3.1. 前进方向

我们将构建一个用于数学表达式的解释器，以及一个简单的 MPCL 小语言（但仍然比您想象的更强大）。关于 MPCL 以及我们将实现的内容将在下一节中介绍。在此之前，以下是我们不 会做的事情：

• 支持符号数学
• 执行任意精度计算
• 采用复杂的方式实现

3.2. Math Processor 命令语言 (MPCL)

MPCL 是 Math Processor 解析器/计算引擎可以运行时解释以执行支持的操作的简单松散类型语言。MPCL 支持：

• 包含 +, -, *, /, % 等常见运算的基本数学表达式。
• 布尔/逻辑运算
• 对数字（包括数字列表）的操作
• 矩阵运算
• 使用if和if-else结构进行条件处理
• 循环（repeat和while）
• 某些指令，用于控制处理环境的几个方面
• .Net 框架 System.Math 类的主要功能以及许多其他操作的内置函数。有关支持函数的完整列表，请访问Math Processor 函数页面。
• 用户定义函数
• 一种极其简单的机制，允许程序员编写更有用的函数并在运行时将它们插入主引擎。

4. 使用 Math Processor 库

Math Processor 通过使用 Token 类，为内部模块和编程接口提供了一个统一的应用程序存储和通信机制。Token 能够存储文本、数字、矩阵、布尔数据以及 MP 内部使用的更多内容。Token 中包含的内容取决于其类型，该类型由 TokenType 类型的公共属性 TokenType 确定。此属性只是一个定义如下的枚举：

public enum TokenType 
{ 
    Void, Error, Operator, Bool, Vector, Matrix, Text, Function, UserFunction, Directive, 
    Block, LoopOrCondition, FunctionDefiner, Break 
}

对于 Math Processor 的用户来说，并非此枚举的所有成员都相关。有些仅供内部使用。我们将在后面的文本中了解重要的成员。Token 类中定义的各种字段声明如下：

TokenType type;
string name = "";
string data = "";
List<double> vector = new List<double>();
double extra; 

这就是支持我们想要处理的所有数据类型所需的一切。从数字到布尔值，从列表到矩阵，应有尽有。令人惊叹！不是吗？诀窍在于根据令牌的类型对字段进行不同的解释。因此，对于类型为 Void 的 Token，大多数字段都没有意义。它就是它名字的含义：Void。对于布尔类型，列表中的0表示false，1表示true。对于矩阵，我们将使用 'extra' 来存储行数。我们将把实际矩阵值存储在 List<double> 字段中。我们将在运行时计算矩阵的行数和列数。

请注意，通过将所有内容打包到 Token 中，我们为了简洁性牺牲了一些效率（在速度和内存方面）。我相信这里的权衡是值得的，因为我们避免了创建复杂数据结构的需要。如果您愿意，可以设计一个更复杂的模型。对我来说，没有解析表、表达式树和成千上万个查找字段，生活要简单得多！

现在我们已经理解了 Token 类的作用和形式，是时候了解如何使用 Math Processor 库了。有两种可能性：

1. 直接将原始表达式发送到解析引擎，获取结果，然后对其进行任何需要的处理。
2. 在代码中创建 Token 类的实例，然后使用类库的各种公共方法来操作它们。

这两种方法都相当简单。然而，在大多数情况下，第一种方法是首选。在示例应用程序中，我们主要使用了第一种方法。但是，在基于控制台的示例中，我们也展示了如何使用第二种方法。

第二种方法仅在您想通过提供更多函数来扩展应用程序的功能，或者当您想直接使用主类库中已定义的函数时需要。我们将在稍后看到这种方法的一个用例。

使用第一种方法与调用 MathProcessor.Calculator 类的以下静态方法一样简单：

public static Token ProcessCommand (string expression) { ... }

参数 expression 是任何有效的 MPCL 命令文本。有关构成有效 MPCL 命令的广泛列表，请参阅第 3.2 节。此方法返回的结果将是以下任何类型的 Token：

• TokenType.Void 操作成功完成，但没有返回值得注意的内容给调用者。请注意，操作本身可能已生成变量或函数等，具体取决于所执行操作的性质。
• TokenType.Error 操作导致错误。
• TokenType.Text 结果 Token 只是纯文本。
• TokenType.Vector 返回的 Token 包含一个或多个数值。
• TokenType.Matrix 返回的 Token 是一个矩阵。
• TokenType.Bool 返回的 Token 包含布尔数据（true/false）。

另一个值得注意的事实是，一些操作会在整个代码块被解析和执行之前产生中间结果。例如，以下 MPCL 代码块通过使用repeat 循环多次产生输出（将其粘贴到演示应用程序中，看看它做了什么！）。

{
    format(G);:
    a = 1;:
    repeat(10)
    {
        echo("4 x ", a, "= ", 4*a):
        a = a + 1;:
    }:
}

为了通知前端中间输出，Calculator 类使用以下委托引发事件：

public delegate void IntermediateResult(Token result);

现在我们已经理解了通信机制，让我们构建一个非常简单的 MP 引擎前端。执行以下步骤：

• 在 Visual Studio 中创建一个新的控制台应用程序。
• 添加对“MathProcessor.dll”的引用（可在本文的下载中找到）。
• 按如下方式修改您的 Program 类：

  class Program
  {
      static void Main(string[] args)
      {
          Calculator.IntermediateResultProduced += new IntermediateResult(IntermediateResultProduced);
          string input = "";
          Console.ForegroundColor = ConsoleColor.White;
          Console.WriteLine("Enter MP expressions to process. Enter 'exit' to quit:");
          Console.ForegroundColor = ConsoleColor.Gray;
          while (true)
          {
              input = Console.ReadLine();
              if (input.Trim().ToLower() == "exit")
              {
                  break;
              } 
              Token result = Calculator.ProcessCommand(input);
              DisplayResult(result);
          }
      }
  
      static void IntermediateResultProduced(Token result)
      {
          DisplayResult(result);
      }
  
      static private void DisplayResult(Token result)
      {
          if (result.TokenType == TokenType.Error)
          {
              Console.ForegroundColor = ConsoleColor.Red;
              Console.WriteLine(">> " + result.GetString());
              Console.ForegroundColor = ConsoleColor.Gray;
          }
          else if (result.TokenType == TokenType.Matrix)
          {
              int rows = (int)result.Extra;
              if (rows > 0)
              {
                  List<double> data = result.Vector.ToList();
                  Token temp;
                  temp = new Token(TokenType.Vector, data.GetRange(0, result.Count / rows).ToArray());
                  Console.WriteLine(">> " + temp.GetString());
                  for (int i = result.Count / rows; i < result.Count; i += result.Count / rows)
                  {
                      temp = new Token(TokenType.Vector, data.GetRange(i, result.Count / rows).ToArray());
                      Console.WriteLine("   " + temp.GetString());
                  }
              }
          }
          else if (result.TokenType != TokenType.Void)
          {
              Console.WriteLine(">> " + result.GetString());
          }
      }
  } 
  

• 就是这样！

编写完这个小程序后，几乎所有 MP 函数现在都可以在命令行中使用了。但是，plot 函数将不可用，因为它会创建一个 Windows 窗体并调用其 Show() 方法，而该方法需要一个在此示例中不可用的消息循环。示例应用程序使用了一种变通方法。请查看可下载的代码，了解该变通方法是如何实现的。

4.1. 通过添加更多命令行函数来扩展核心

我们遇到的另一个问题是无法在控制台应用程序中粘贴多行代码块。此类操作不直接可用。让我们编写一个新的 MP 命令行函数，允许我们直接从剪贴板“粘贴”文本内容（示例应用程序包含此功能）。向项目中添加对 Windows.Forms 程序集的引用，并将以下方法放在您的 Program 类中：

public static Token Paste(string operation, List<Token> arguments)
{
    try
    {
        string text = System.Windows.Forms.Clipboard.GetText();
        return Calculator.ProcessCommand(text);
    }
    catch (Exception)
    {
        return new Token(TokenType.Error, "Could not paste text from Clipboard.");
    }
} 

现在按如下方式修改您的 Main() 方法：

[STAThread]
static void Main(string[] args)
{
    Function.AddDirective("paste", Paste);
    /* Everthing as before */
}

请注意 Main() 方法使用了 [STAThread] 属性。这对于使用剪贴板是必需的。进行上述更改后，您将拥有一个名为“paste”的新指令。如果您愿意，您也可以将其制作为函数，如下所示：

Function.AddFunction("paste", Paste);

在 MPCL 中，指令和函数的区别在于，函数后面始终跟着一对括号，其中包含零个或多个参数。此外，函数的参数在函数调用之前进行处理。对于指令，参数不进行预处理。有关指令的更多详细信息，请参阅Math Processor 指令页面。

大多数情况下，您将使用函数。指令数量很少，并且主要处理引擎的配置，不用于实际处理。

5. 理解核心引擎

让我们从一个显示 Math Processor 工作流程的简单图表开始。

客户端的表达式首先由解析器/标记生成器转换为标记。然后，标记列表从中缀转换为后缀（逆波兰）表示法。之后，标记由计算引擎处理，并将结果发送回客户端。

从中缀到后缀的转换是为了方便评估阶段。由于表达式在后缀表示法中的表示方式，更改运算优先级不需要使用括号，这简化了评估过程。您可以使用 Math Processor 的postfix 指令查看从中缀到后缀表示法的转换。这里有几个例子：

>> postfix 2*9+3
>> 2 9 * 3 +
>> postfix 2*(9+3)
>> 2 9 3 + *

在上面的例子中，我们可以看到在后缀形式中不需要使用括号，因为运算优先级内置于表达式本身中。在第一个例子中，根据数学的一般规则，乘法具有更高的优先级。然而，在第二个例子中，中缀形式通过使用括号改变了优先级。这种改变的优先级通过重新排序标记反映在后缀形式中，这使我们能够摆脱括号。

到目前为止一切顺利。但是过程是如何开始、继续和结束的呢？实际上，这是分阶段完成的。首先，我们需要解析普通表达式以创建标记。然后，我们需要以适当的方式安排这些标记以进行处理。之后才是实际计算。最后，结果被返回给用户。

整个过程发生在 7 个核心类中，代码行数很少。这些类的详细信息如下：

5.1. Token

这是 Math Processor 中无处不在的数据持有者。我们已经在本文第 4 部分的前面详细讨论过 Token。

5.2. Tokenizer

此类负责解析输入并将其转换为 Token 对象。整个过程在一个静态函数中进行：

public static Token TokenizeString(String expression, out List<token> tokens)

第一个参数 'expression' 是要标记化的表达式。表达式是任何有效的 MPCL 命令（包括数学表达式、函数、指令等）。第二个参数 out List<Token> tokens 将包含输入表达式中找到的标记的结果。最后，返回值将告知解析结果，在成功的情况下可以是 TokenType.Void 类型，在输入表达式错误的情况下可以是 TokenType.Error 类型。

5.3. Variables

此类负责存储保留字、命名常量和变量。它定义了一个小的内部类 NamedToken 来存储命名的 Token 对象。变量可以使用赋值运算符创建。某些 MP 函数也可以创建变量。变量名必须以字母或下划线开头，并且可以包含字母和数字。下面是如何创建和使用变量：

>> a = 10
>> 10
>> b = a + 100
>> 110

5.4. Function

此类存储所有可以通过 MPCL 函数调用使用的函数。每个 MP 命令行函数都应该遵循以下委托定义的格式：

public delegate Token FunctionDelegate(string operation, List<token> arguments); 

让我们看看整个过程是如何进行的。MP 提供了一个名为 contains 的函数，用于检查一个数字是否存在于数字矩阵或数组中。该函数实现如下：

public static Token Contains(string operation, List<Token> arguments)
{
    if (arguments.Count != 2)
        return Token.Error("Exactly two arguments expected");

    if ((arguments[0].TokenType != TokenType.Matrix && arguments[0].TokenType != TokenType.Vector) ||
        (arguments[1].TokenType != TokenType.Matrix && arguments[1].TokenType != TokenType.Vector) ||
         arguments[1].Count != 1)
        return Token.Error("First argument should be an array or matrix and second a single numeric value");

    if (arguments[0].Vector.Contains(arguments[1].FirstValue))
        return new Token(TokenType.Bool, 1, 1);
    else 
        return new Token(TokenType.Bool, 1, 0);
} 

现在让我们看看如何使用这个函数：

>> a = array(1,2,3,4);
>> contains(a, 1)
>> true
>> contains(a, 5)
>> false
>> if (contains(a, 2)) { echo("Number found in the array."): }
>> Number found in the array.

5.5. FunctionDefiner

此类负责创建、管理和执行用户定义函数，这是允许用户在运行时创建少量代码以扩展引擎功能的非常重要的方式。用户定义函数由于其解释性质，效率不是很高。但是，它们对于执行您需要重复执行的小块工作仍然很有用。

我们已经在本文前面看到了一个非常有趣的用户定义函数示例，当时我们创建了一些非常有趣的曲线（花瓣线曲线）。要获取更多详细信息并查看其他用户定义函数的示例，您可以参考在线 MP 文档的用户定义函数页面。

5.6. BlockCommands

此类负责管理和执行 if/if-else、while 和 repeat 结构。将这些结构放在一起的原因是它们具有共同的语法形式：

key_word(expression) { one or more statements }

有关其中每个结构的解释，请参阅条件语句和循环页面。

5.7. Calculator

我们已经看到了 Calculator.ProcessCommand() 方法的实际应用，该方法用于将所有表达式发送到引擎进行处理。除了提供该功能外，此类还包含执行基本算术计算的所有代码，这些计算涉及支持的运算符，如 +、-、* 等。它还负责从中缀到后缀表示法的转换，确定运算符的优先级，并将这些运算符应用于操作数以获得结果。

结论

最后，我们到达了终点。我希望您觉得本文、主引擎和示例应用程序很有帮助。我也希望我能够兑现我的承诺，为您创建并提供一个简单的解析库和计算引擎，供您在自己的项目中使用。