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

Mathematical Expression Parser Using Coco/R

Rate me:
Please Sign up or sign in to vote.
4.94/5 (8 votes)
26 Apr 2012CPOL3 min read 28.8K   15   6
This is an alternative for "Mathematical Expression Parser Using Recursive Descent Parsing"

Introduction

This is an alternative to how to parse the language as given in the original post Mathematical Expression Parser Using Recursive Descent Parsing[^]. Instead of inventing your own scanner and parser, you might consider to use some parser generator tools. One that generates stand alone code (no need to link to any library) and which is native C# is Coco/R .

It's very simple to use:

  1. download coco.exe, Scanner.frame, Parser.frame
  2. write your grammar with the embedded actions
  3. write a hook to integrate the parsing in your code
  4. compile and run

The aim of this alternative is to show how conpact the same parser is when employing parser generators.

The enclosed example shows the expression evaluator of the syntax provided in the original post.

The Language Definition

I think the most effective way to describe a language that is to be implemented as Recursive Descendent Parser is EBNF[^]. An EBNF form for the grammar given in the original post is (with start symbol "Expr"):

Expr    = Term { ( "+" | "-" ) Term } { "!" } .
Term    = Factor { ( "*"|"/"|"%"|"^") Factor } .
Factor  = Number | Name | "(" ["-"] Expr ")" .
Name    = Letter { Letter|Digit } .
Number  = Digit { Digit } [ "." Digit { Digit } ] .

One can visualize that grammar by tools like EBNF Visualizer[^]:

Image 1Image 2

Image 3Image 4

Image 5

This grammar is conveniently implemented as show in the code samples below from line 70 on.

Note: This grammar is rather odd. I took it over as-is from the original post and documented it formally in EBNF and as graphics derived from the EBNF definition. The power operation and the factorial operation are not according to common definitions. In addition, the unary minus is only allowed in nested expression which is also rather uncommon.

Using the code

Parser generators consist of several sections:

  • custom code, e.g. for initialization, etc.
  • grammar with character set, tokens, productions, etc.
  • embedded in the grammar the actions that shall be executed when the element is parsed

I don't explain the syntax of Coco/R here - there are good sources available, e.g. Coco/R Users Manual and Coco/R Tutorial.

Here is the Coco/R code. That file gets compiled by Coco/R which results in two C# files: Scanner.cs and Parser.cs.

C#
  1  using System.Collections.Generic;
  2  using System.Text;
  3  using System.IO;
  4  
  5  using ValueList = System.Collections.Generic.List<double>;
  6  
  7  /* ----------------------- Start Symbol ---------------------------- */
  8  
  9  COMPILER Eval  /* the "compiler" is named by the start symbol */
 10  
 11  /* ----------------------- custom code ---------------------------- */
 12  private double Eval(string name, ValueList args)
 13  {
 14      string symbol = args == null ? name : string.Format("{0}({1})", name, args.Count);
 15      Func<ValueList, double> func;
 16      if (_symbols.TryGetValue(symbol, out func)) return func(args);
 17      errors.SemErr(string.Format("Symbol not found: {0}", name));
 18      return 1.0;
 19  }
 20  
 21  private double Eval(string name, params double[] args)
 22  {
 23  	return Eval(name, new ValueList(args));
 24  }
 25  
 26  public static void SetVar(string name, double val)
 27  {
 28      if (_symbols.ContainsKey(name)) _symbols[name] = a=>val;
 29  	else _symbols.Add(name, a=>val);
 30  }
 31  
 32  private const double DEG_RAD = Math.PI/180.0;
 33  
 34  private static Dictionary<string, Func<ValueList, double>> _symbols =
 35  new Dictionary<string, Func<ValueList, double>>(StringComparer.InvariantCultureIgnoreCase)
 36  {
 37      { "+(2)", a=> a[0]+a[1] },
 38      { "-(2)", a=> a[0]-a[1] },
 39      { "*(2)", a=> a[0]*a[1] },
 40      { "/(2)", a=> a[0]/a[1] },
 41      { "%(2)", a=> a[0]%a[1] },
 42      { "^(2)", a=> Math.Pow(a[0],a[1]) },
 43      { "!(1)", a=> {double v=a[0]; int i = (int)v; while(--i > 0) v*=i; return v;} },
 44      { "-(1)", a=> -a[0] },
 45      { "(1)", a=> a[0] },
 46      { "pi", a=> Math.PI },
 47      { "sin(1)", a=> Math.Sin(DEG_RAD*a[0]) },
 48      { "cos(1)", a=> Math.Cos(DEG_RAD*a[0]) },
 49      { "tan(1)", a=> Math.Tan(DEG_RAD*a[0]) },
 50      { "exp(1)", a=> Math.Exp(a[0]) },
 51      { "ln(1)", a=> Math.Log(a[0]) },
 52      { "log(1)", a=> Math.Log10(a[0]) },
 53  };
 54  
 55  
 56  double _val = 0.0;
 57  
 58  public static double Evaluate(string s)
 59  {
 60      using (var strm = new MemoryStream(Encoding.ASCII.GetBytes(s)))
 61      {
 62          Scanner scanner = new Scanner(strm);
 63          Parser parser = new Parser(scanner);
 64          parser.Parse();
 65  		if (parser.errors.count > 0) Console.WriteLine("Errors: {0}", parser.errors.count);
 66          return parser._val;
 67      }
 68  }
 69  
 70  /* ----------------------- Scanner ---------------------------- */
 71  CHARACTERS
 72      letter = 'A'..'Z' + 'a'..'z'.
 73      digit  = '0'..'9'.
 74  TOKENS
 75      ident  = letter { letter | digit }.
 76      number = digit { digit } [ '.' digit { digit } ] .
 77  IGNORE ' ' + '\t'
 78  
 79  /* ----------------------- Parser ---------------------------- */
 80  PRODUCTIONS
 81  
 82  Eval = Expr<ref _val> .
 83  
 84  Expr<ref double val>                                           (. double v = 0; string op; .)
 85  = Term<ref v>                                                  (. val = v; .)
 86    { ("+"|"-") (. op=t.val; .) Term<ref v>                      (. val = Eval(op, val, v); .)
 87    }
 88    { "!"                                                        (. val = Eval(t.val); .)
 89    } .
 90  Term<ref double val>                                           (. double v = 0; string op; .)
 91  = Factor<ref v>                                                (. val  = v; .)
 92    { ("*"|"/"|"%"|"^") (. op=t.val; .) Factor<ref v>            (. val = Eval(op, val, v); .)
 93    } .
 94  Factor<ref double val>                                         (. double v = 0; string op = ""; .)
 95  =   number                                                     (. val = double.Parse(t.val); .)
 96    | Name<ref v>                                                (. val = v; .)
 97    | "(" ["-" (. op=t.val; .) ] Expr<ref v> ")"                 (. val = Eval(op, v); .)
 98    .
 99  Name<ref double val>                                           (. ValueList args = null; string name; .)
100  = ident                                                        (. name = t.val; .)
101    ["(" (. args = new ValueList(); .) [ArgList<ref args>] ")"]  (. val = Eval(name, args); .)
102    .
103  ArgList<ref ValueList args>                                    (. double v = 0; .)
104  = Expr<ref v>                                                  (. args.Add(v);  .)
105    { "," Expr<ref v>                                            (. args.Add(v);  .)
106    }
107    .
108  
109  END Eval.
110  
111  /* ----------------------- that's it folks! ---------------------------- */

Store this code into a file called Eval.atg, copy the Scanner.frame, Parser.frame, and coco.exe to that source directory. Compile on a command prompt:

coco Eval.atg

csc Scanner.cs Parser.cs

Parser.exe "sin(45)*cos(45)^2*(len-1)"

The output of this is

sin(45)*cos(45)^2*(len-1) = 30.5

I find these tools very valuable - no big deal to reade the code, I think, once you grasp the basics (e.g. the overall structure separated by some keywords, the distinction between grammar and embedded code (. ... .) ).

Again, this alternative does not aim in describing Coco/R in any detail - see the respective links above. The aim is to show an alternative technique to the original post.

Altrenative as a hand-crafted parser

As illustration, you can hand-craft a similarily compact parser for such a simple language. Compare both files from line 57 on.

C#
  1  using System;
  2  using System.Collections.Generic;
  3  using System.IO;
  4  using System.Linq;
  5  using System.Text.RegularExpressions;
  6  
  7  using ValueList = System.Collections.Generic.List<double>;
  8  
  9  namespace ExpressionParser
 10  {
 11      public class ManParser
 12      {
 13          // --------------------------- custom code ----------------------
 14  
 15          private double Eval(string name, ValueList args)
 16          {
 17              string symbol = args == null ? name : string.Format("{0}({1})", name, args.Count);
 18              Func<ValueList, double> func;
 19              if (_symbols.TryGetValue(symbol, out func)) return func(args);
 20              Error(string.Format("Symbol not found: {0}", name));
 21              return double.PositiveInfinity;
 22          }
 23  
 24          private double Eval(string name, params double[] args)
 25          {
 26              return Eval(name, new ValueList(args));
 27          }
 28  
 29          public static void SetVar(string name, double val)
 30          {
 31              if (_symbols.ContainsKey(name)) _symbols[name] = a => val;
 32              else _symbols.Add(name, a => val);
 33          }
 34  
 35          private const double DEG_RAD = Math.PI / 180.0;
 36  
 37          private static Dictionary<string, Func<ValueList, double>> _symbols =
 38          new Dictionary<string, Func<ValueList, double>>(StringComparer.InvariantCultureIgnoreCase)
 39          {
 40              { "+(2)", a=> a[0]+a[1] },
 41              { "-(2)", a=> a[0]-a[1] },
 42              { "*(2)", a=> a[0]*a[1] },
 43              { "/(2)", a=> a[0]/a[1] },
 44              { "%(2)", a=> a[0]%a[1] },
 45              { "^(2)", a=> Math.Pow(a[0],a[1]) },
 46              { "!(1)", a=> {double v=a[0]; int i = (int)v; while(--i > 0) v*=i; return v;} },
 47              { "-(1)", a=> -a[0] },
 48              { "(1)", a=> a[0] },
 49              { "pi", a=> Math.PI },
 50              { "sin(1)", a=> Math.Sin(DEG_RAD*a[0]) },
 51              { "cos(1)", a=> Math.Cos(DEG_RAD*a[0]) },
 52              { "tan(1)", a=> Math.Tan(DEG_RAD*a[0]) },
 53              { "exp(1)", a=> Math.Exp(a[0]) },
 54              { "ln(1)", a=> Math.Log(a[0]) },
 55              { "log(1)", a=> Math.Log10(a[0]) },
 56          };
 57  
 58          public static double Evaluate(string s) { return new ManParser(s).Expr(); }
 59  
 60          // ------------------- scanner ---------------------
 61          private IEnumerator<Match> _tokens;
 62          private bool Next() { return _valid && (_valid = _tokens.MoveNext()); }
 63          private string Curr { get { return _valid ? _tokens.Current.Groups[1].Value : null; } }
 64          private int Pos { get { return _valid ? _tokens.Current.Index : 0; } }
 65          private bool _valid = true;
 66          private TextWriter _errout;
 67          private void Error(string msg, params object[] args)
 68          { _errout.Write("error: " + msg, args); _errout.WriteLine(" (at {0}: '{1}')", Pos, Curr ?? ""); }
 69  
 70          // -------------------- parser ------------------------
 71          public ManParser(string s)
 72          {
 73              _errout = Console.Error;
 74              string p = @"\s*((?:[\-\+\*\/\%\!\(\)]|(?:\d+(?:\.\d+)?)|\w+)|(?:\S))\s*";
 75              _tokens = Regex.Matches(s, p, RegexOptions.Compiled).Cast<Match>().GetEnumerator(); ;
 76              Next();
 77          }
 78          private double Expr()
 79          {
 80              string[] ops = new [] { "+", "-" };
 81              string op;
 82              double v = Term();
 83              while (ops.Contains(op = Curr) && Next()) v = Eval(op, v, Term());
 84              while (Curr == "!") { v = Eval("!", v); Next(); }
 85              return v;
 86          }
 87          private double Term()
 88          {
 89              string[] ops = new[] { "*", "/", "%", "^" };
 90              string op;
 91              double v = Factor();
 92              while (ops.Contains(op = Curr) && Next()) v = Eval(op, v, Factor());
 93              return v;
 94          }
 95          private double Factor()
 96          {
 97              string s = Curr;
 98              char c = s[0];
 99              if      (char.IsDigit(c))                      return Number();
100              else if ((char.IsLower(c) || char.IsUpper(c))) return Name();
101              else if (c == '(')                             return NestedExpr();
102              else Error("name, number or (...) expected");
103              return double.PositiveInfinity;
104          }
105          private double Number()
106          {
107              double v = double.Parse(Curr);
108              Next();
109              return v;
110          }
111          private double Name()
112          {
113              string name = Curr;
114              ValueList args = null;
115              if (Next()) if (Curr == "(") { args = ArgList(); }
116              return Eval(name, args);
117          }
118          private ValueList ArgList()
119          {
120              ValueList args = new ValueList();
121              if (Curr != "(") Error("'(' expected");
122              if (Next() && Curr != ")") { args.Add(Expr()); while (Curr == "," && Next()) args.Add(Expr()); }
123              if (Curr != ")") Error("')' expected");
124              Next();
125              return args;
126          }
127          private double NestedExpr()
128          {
129              if (Curr != "(") Error("'(' expected");
130              if (!Next()) Error("unexpected EOF");
131              double v = (Curr == "-" && Next()) ? -Expr() : Expr();
132              if (Curr != ")") Error("')' expected");
133              Next();
134              return v;
135          }
136      }
137  }

Points of Interest

I must admit that I can not resist to write my own scanner/parser once in a while for some small problems instead of using the tools above... ;-)

Check out the Coco/R documentation - it's really nicely written - very concise and easy to read. If you ever get a book from Hanspeter Mössenböck under your fingers: read it! I'm amazed again and again how wunderfully concise he explains computer languages, especially his book on C# is a treat.

History

2012-03-09 first version
2012-04-21 introduction enhanced, EBNF added, some links added, hand crafted version added as comparison
2014-09-11 fixed factorial parsing (thanks to markr007), updated EBNF and graphics

License

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


Written By
Founder eXternSoft GmbH
Switzerland Switzerland
I feel comfortable on a variety of systems (UNIX, Windows, cross-compiled embedded systems, etc.) in a variety of languages, environments, and tools.
I have a particular affinity to computer language analysis, testing, as well as quality management.

More information about what I do for a living can be found at my LinkedIn Profile and on my company's web page (German only).

Comments and Discussions

 
BugCouple of bugs Pin
markr00710-Sep-14 9:49
markr00710-Sep-14 9:49 
GeneralRe: Couple of bugs Pin
Andreas Gieriet10-Sep-14 12:31
professionalAndreas Gieriet10-Sep-14 12:31 
GeneralRe: Couple of bugs Pin
markr00714-Sep-14 11:40
markr00714-Sep-14 11:40 
GeneralRe: Couple of bugs Pin
Andreas Gieriet14-Sep-14 12:01
professionalAndreas Gieriet14-Sep-14 12:01 
Questionmy vote of five Pin
alejandro29A10-Apr-14 8:09
alejandro29A10-Apr-14 8:09 
AnswerRe: my vote of five Pin
Andreas Gieriet10-Apr-14 9:38
professionalAndreas Gieriet10-Apr-14 9:38 

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.