An Enhanced Mathematical Expression Recursive Descent Parser in C#

• Download demo - 8.3 KB
• Download source - 32 MB

Introduction

This is a fully functional math expression parser based on a recursive descent parser (RDP). The underlying C# code for the parser was translated from Herb Schildt's Recursive Descent Parser written in Java
from "THE ART OF JAVA", by Herbert Schildt and James Holmes, McGraw-Hill/Osborne ISBN 0-07-222971-3, Copyright (C) 2003. The online reference can be found here. To be useful, a mathematical parser should have a method assigning user defined variables, of storing and retrieving those variables by name and value, persistence of those variables and values from session to session, and the ability to accept standard math expressions as simple text and process the text to calculate the correct mathematical result, regardless of the complexity of the expression. In addition, the parser should have the ability to recognize and process standard mathematical and trigonometric functions. While there are numerous expression evaluators available in virtually every programming language, most lack the full functionality referred to above. Many provide only poor quality or uncompilable code, and some are so complicated and incomplete that they defy use to build a working application.

Background

As described in a previous article, my interest in recursive descent parsers goes back decades. More recently, a long and tiresome search for a scaleable, reliable, compilable recursive descent parser in C# yielded very little. The most valuable find was Herb Schildt's Recursive Descent Parser but written in Java as cited above. As something of a novice C# programmer, it took me several days to translate that parser into a working C# application, but it still lacked the capability to store and retrieve user defined variables. As well, it lacked the ability to recognize and process basic math and trigonometric function such as sqrt, sin, cos, etc. Using C#, it was possible to develop a mapping of function names in a class KeyMap and a similar variable mapping class, VarMap. Linking those classes to the Parser class, I was able to develop a C# recursive descent parser that contained the full functionality desired.

Using the Code

There are three classes that work together to accomplish the parsing, Parser.cs, VarMap.cs, and KeyMap.cs. Simply add these three classes (plus the Error.cs) to your project, making certain that they each share the same namespace as your C# project. How you use the Parser.Evaluate(string expr) depends upon your interface.

A portion of the Parser.cs class is shown here (see source code download for details):

 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 
}

The VarMap stores variable names using the C# Dictionary<String, Double> variable, where Key is the variable name and Value is the stored value. There are methods for adding, updating, and erasing variables from the mapping. The value of a named variable can be accessed through the variable name using the GetVariableValue(token) method. Class methods LoadVariableMap and SaveVariableMap provide for binary disk storage and retrieval of data. Portions of the VarMap class are shown below: Attempts to serialize the Dictionary<String, Double> failed, so I resorted to simply using System.IO BinaryReader and BinaryWriter which turned out to be much simpler. The KeyMap class is similarly constructed.

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

The C# Console App (.NET Framework) program used to demo the parser is shown below. It allows for listing the currently mapped variables, listing the available key words, deleting a specific variable, and summoning help.

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);
}

A basic help section is contained in the program and can be brought up by typing 'help'.

Points of Interest

Here is, I believe, a code in the public domain that is readable, expandable, easily modified, and reusable. As such, it should be of some value to many programmers. It is possible to modify the parser and variable mapping class to use more complex data types such as complex numbers and matrices. While my initial forays into this subject largely involved C++ and some Java, I have found that C# is a superior language for tractability, readability, and maintenance. One of the biggest problems I encountered was trying to Serialize a class that contained a C# Dictionary. I am still uncertain as to whether or not this is possible using C#. Using System.IO solved the problem. Translating from Java to C# wasn't all that easy, though admittedly I'm a novice at both languages. Substituting 'const' for 'Final', 'Char' for 'Character', 'ElementAt( i )' for 'charAt( i )', and a few other tidbits, made it all come together. But the real challenge, the 'Elephant In The Room', if you like, is understanding how this recursive descent parser really works as well as it does. I have studied the code for many weeks, rewritten and reedited it, but still am not crystal clear on how it flows. But it works!!

History

• Version 1.0.0.0 Jan 10, 2018