Click here to Skip to main content
15,867,594 members
Articles / Programming Languages / C#

An Enhanced Mathematical Expression Recursive Descent Parser in C#

Rate me:
Please Sign up or sign in to vote.
4.25/5 (9 votes)
15 Jan 2018CPOL4 min read 19.7K   11   19
A very scalable recursive descent math expression parser with built in math functions and variable storage in C#

Image 1

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):

C#
 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.

C#
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.

C#
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'.

Image 2

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer PliaTech
United States United States
Software developer with interests in mathematics and statistics, particularly as applied to health care. CTO and founder of PliaTech.

Comments and Discussions

 
QuestionDownload links are broken? Pin
klinkenbecker15-Aug-18 9:30
klinkenbecker15-Aug-18 9:30 
QuestionDid you consider LLLPG or LES? Pin
Qwertie24-Jan-18 1:53
Qwertie24-Jan-18 1:53 
AnswerRe: Did you consider LLLPG or LES? Pin
Michael B Pliam18-Mar-18 10:18
Michael B Pliam18-Mar-18 10:18 
No. Unfortunately, I was completely unaware of it's existence, despite extensive Google searches for 'Recursive Descent Parsers in C#', etc.

I downloaded your Graphing Calculator example. It's truly magnificent. One small problem encountered in building the source code.

Quote:
Unable to find manifest signing certificate in the certificate store.
Unable to find code signing certificate in the current user's Windows certificate store. To correct this, either disable signing of the ClickOnce manifest or install the certificate into the certificate store.


After a little research I found the fix:
The following two steps enabled me to turn off ClickOnce(in Visual Studio 2017):
In the project properties,

Signing tab: Uncheck "Sign the ClickOnce manifests"
Security tab: Uncheck "Enable ClickOnce security settings"

As you might have guessed, the purpose of my little RDP was to serve in a graphics program.

I will need to look into LES and LLLPG. However, I find github extremely daunting at times, particularly when there seems no easy method of downloading the latest version of the entire package.

Thank you for pointing out LES and LLLPG. Makes me realize just what an amateur I am.
PraiseNice work and a useful learning tool Pin
asiwel16-Jan-18 19:35
professionalasiwel16-Jan-18 19:35 
GeneralRe: Nice work and a useful learning tool Pin
Michael B Pliam18-Mar-18 10:25
Michael B Pliam18-Mar-18 10:25 
GeneralRe: Nice work and a useful learning tool Pin
asiwel18-Mar-18 10:40
professionalasiwel18-Mar-18 10:40 
GeneralRe: Nice work and a useful learning tool Pin
Michael B Pliam18-Mar-18 10:51
Michael B Pliam18-Mar-18 10:51 
GeneralRe: Nice work and a useful learning tool Pin
asiwel18-Mar-18 11:25
professionalasiwel18-Mar-18 11:25 
GeneralRe: Nice work and a useful learning tool Pin
Michael B Pliam18-Mar-18 12:48
Michael B Pliam18-Mar-18 12:48 
GeneralRe: Nice work and a useful learning tool Pin
asiwel18-Mar-18 13:39
professionalasiwel18-Mar-18 13:39 
GeneralRe: Nice work and a useful learning tool Pin
Michael B Pliam18-Mar-18 15:33
Michael B Pliam18-Mar-18 15:33 
GeneralRe: Nice work and a useful learning tool Pin
asiwel18-Mar-18 19:26
professionalasiwel18-Mar-18 19:26 
QuestionSerializing in C# Pin
AnotherKen16-Jan-18 15:31
professionalAnotherKen16-Jan-18 15:31 
AnswerRe: Serializing in C# Pin
Michael B Pliam18-Mar-18 10:27
Michael B Pliam18-Mar-18 10:27 
GeneralRe: Serializing in C# Pin
klinkenbecker15-Aug-18 9:37
klinkenbecker15-Aug-18 9:37 
QuestionCan this parser handle complex variables too? Pin
Member 1361276616-Jan-18 8:17
Member 1361276616-Jan-18 8:17 
AnswerRe: Can this parser handle complex variables too? Pin
Michael B Pliam18-Mar-18 10:37
Michael B Pliam18-Mar-18 10:37 
QuestionProblems with sample and source download Pin
Julius Adam16-Jan-18 4:58
Julius Adam16-Jan-18 4:58 
AnswerRe: Problems with sample and source download Pin
Michael B Pliam18-Mar-18 10:41
Michael B Pliam18-Mar-18 10:41 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.