C# 中增强的数学表达式递归下降解析器

• 下载演示 - 8.3 KB
• 下载源码 - 32 MB

引言

这是一个基于递归下降解析器 (RDP) 的功能齐全的数学表达式解析器。解析器的底层 C# 代码是从 Herb Schildt 用 Java 编写的递归下降解析器翻译而来
来自 Herbert Schildt 和 James Holmes 合著的《JAVA艺术》，McGraw-Hill/Osborne ISBN 0-07-222971-3，版权所有 (C) 2003。在线参考资料可以在 这里找到。为了实用，数学解析器应该有一个方法来分配用户定义的变量，通过名称和值存储和检索这些变量，在会话之间持久保存这些变量和值，并且能够接受标准数学表达式作为简单文本并处理文本以计算正确的数学结果，无论表达式的复杂程度如何。此外，解析器应该能够识别和处理标准数学和三角函数。虽然几乎每种编程语言都有许多表达式求值器，但大多数都缺乏上述的全部功能。许多只提供质量差或无法编译的代码，有些代码过于复杂且不完整，以至于难以用于构建工作应用程序。

背景

正如之前的 文章中所述，我对递归下降解析器的兴趣可以追溯到几十年前。最近，长期而乏味地寻找一个可扩展、可靠、可编译的 C# 递归下降解析器，却收效甚微。最有价值的发现是 Herb Schildt 用 Java 编写的递归下降解析器，如上所述。作为一个新手 C# 程序员，我花了几天时间才将该解析器翻译成一个工作的 C# 应用程序，但它仍然缺乏存储和检索用户定义变量的能力。同样，它也缺乏识别和处理基本数学和三角函数（例如 sqrt, sin, cos 等）的能力。使用 C#，可以开发一个在类 KeyMap 中映射函数名称的类，以及一个类似的变量映射类 VarMap。将这些类链接到 Parser 类，我就能够开发一个 C# 递归下降解析器，该解析器包含所需的所有功能。

Using the Code

有三个类协同工作以完成解析，Parser.cs, VarMap.cs, 和 KeyMap.cs。只需将这三个类（加上 Error.cs）添加到您的项目中，确保它们都与您的 C# 项目共享相同的命名空间即可。您如何使用 Parser.Evaluate(string expr) 取决于您的界面。

这里显示了 Parser.cs 类的一部分（详细信息请参阅源代码下载）

 class Parser
{
   // Constructor
   public Parser()
   {
      m_keymap = new KeyMap();
      m_varmap = new VarMap();
      m_varmap.LoadVarMap(@"varmap.dat");
      m_keymap.DumpKeyWords();
      m_varmap.Dump();
   }

   // Fields
   const String EOE = "\0";
   private String exp; // refers to expression string
   private int expIdx; // current index into the expression
   private String token; // holds current token
   private int tokType; // holds token's type

   // These are the token types.
   const int NONE = 0;
   const int DELIMITER = 1;
   const int VARIABLE = 2;
   const int NUMBER = 3;

   // These are the types of syntax errors.
   const int SYNTAX = 0;
   const int UNBALPARENS = 1;
   const int NOEXP = 2;
   const int DIVBYZERO = 3;

   // These are the keywords
   private KeyMap m_keymap;

   // These are the currently mapped variables
   private VarMap m_varmap;

   // Methods
   // Parser entry point.
   public double Evaluate(String expstr)
   {
      double result = 0.0;
      exp = expstr;
      expIdx = 0;
      getToken();
      if (token.Equals(EOE))
      handleErr(NOEXP); // no expression present
      // Parse and evaluate the expression.
      result = EvalExp1();
      return result;
      if (!token.Equals(EOE)) // last token must be EOE
      handleErr(SYNTAX);
      return result;
   }
   // cycle through the parser methods 
}

VarMap 使用 C# Dictionary<String, Double> 变量存储变量名，其中 Key 是变量名，Value 是存储的值。有用于从映射中添加、更新和删除变量的方法。可以使用 GetVariableValue(token) 方法通过变量名访问命名变量的值。类方法 LoadVariableMap 和 SaveVariableMap 提供了数据的二进制磁盘存储和检索功能。VarMap 类的一部分如下所示：尝试序列化 Dictionary<String, Double> 失败，因此我最终使用 System.IO BinaryReader 和 BinaryWriter，事实证明这更简单。KeyMap 类也类似地构建。

class VarMap
{
   // Fields
   private static Dictionary<String, Double> m_varmap;
   private static int m_ncount;

   // Constructors
   public VarMap()
   {
      m_varmap = new Dictionary<String, Double>();
      m_ncount = 0;
   }
...
   public int AddVariable(String skey, Double dval)
   {
      if (m_varmap.ContainsKey(skey)) { UpdateVariable(skey, dval); return 1; }
      m_varmap.Add(skey, dval);
      return 1;
   }
...
    public int UpdateVariable(String skey, Double dval)
   {  
      m_varmap.Remove(skey);
      m_varmap.Add(skey, dval);
      return 1;
   }
...

   protected static Dictionary<String, Double> LoadDic(string sDicPath)
   {
      Dictionary<String, Double> theDic = new Dictionary<String, Double>();
      int nCount = 0;
      string svar = string.Empty;
      double dval = -1.0;
      using (BinaryReader rd = new BinaryReader(File.OpenRead(sDicPath)))
      {
         nCount = rd.ReadInt32();

         for (int n = 0; n < nCount; n++)
         {
            svar = rd.ReadString(); 
            dval = rd.ReadDouble(); 
            theDic.Add(svar, dval);
         }
   }
   return theDic;

}// LoadDic
...

    protected static int SaveDic(Dictionary<String, Double> theDic, string filePath)
   {
      using (BinaryWriter b = new BinaryWriter(File.Open(filePath, FileMode.Create)))
      {
         b.Write(theDic.Count);

         foreach (var s in theDic)
         {
            b.Write(s.Key);
            b.Write(s.Value);
         }
      }
      return 1;
   }// SaveDic

用于演示解析器的 C# 控制台应用程序 (.NET Framework) 程序如下所示。它允许列出当前映射的变量，列出可用的关键字，删除特定变量并调用帮助。

static void Main(string[] args)
{
   Parser parser = new Parser();

   double dval = -1.0;
   string expr = string.Empty;

   Console.WriteLine("\n\t\tEnhanced Recursive Descent Parser in C#");
   Console.Title = "Enhanced Recursive Descent Parser in C#";

   for (; ;)
   {
      Console.WriteLine();
      Console.Write(" << ");
      expr = Console.ReadLine();
      if (expr.ToLower() == "quit") break;
      if (expr.ToLower() == "cls") { Console.Clear(); Console.WriteLine
               ("\n\t\tEnhanced Recursive Descent Parser in C#"); continue; }
      if (expr.ToLower() == "list vars" || expr.ToLower() == "listvars") 
               { parser.ListVars(); continue; }
      if (expr.ToLower() == "list keys" || expr.ToLower() == "listkeys") 
               { parser.ListKeywords(); continue; }
      if (expr.ToLower() == "del var")
      {
         Console.Write(" Variable Name : ");
         expr = Console.ReadLine();
         parser.DeleteVariable(expr);
         continue;
      }
      if (expr.ToLower() == "help") { GetHelp(); continue; }

      dval = parser.Evaluate(expr);
      Console.WriteLine("\nresult =: " + dval);
}

程序中包含一个基本的帮助部分，可以通过键入 'help' 来调用。

关注点

我相信，这是一个可读、可扩展、易于修改和可重用的公共领域代码。因此，它应该对许多程序员具有一定的价值。可以修改解析器和变量映射类以使用更复杂的数据类型，例如复数和矩阵。虽然我最初对这个课题的探索主要涉及 C++ 和一些 Java，但我发现 C# 在可追溯性、可读性和维护方面是一种更优秀的语言。我遇到的一个最大的问题是尝试序列化一个包含 C# Dictionary 的类。我仍然不确定这是否可以使用 C# 实现。使用 System.IO 解决了这个问题。从 Java 翻译到 C# 并非易事，尽管我承认我对这两种语言都是新手。用 'const' 替换 'Final'，用 'Char' 替换 'Character'，用 'ElementAt( i )' 替换 'charAt( i )'，以及其他一些小细节，使一切都整合在一起。但真正的挑战，就像是'房间里的大象'一样，是理解这个递归下降解析器的工作原理，以及它为什么能如此出色地工作。我研究了代码很多周，重写并重新编辑了它，但仍然不清楚它是如何运行的。但它有效！！

历史

• 版本 1.0.0.0 2018 年 1 月 10 日