Mathematical Expression Parser Using Coco/R

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[^]:

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

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.

  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! ---------------------------- */
112  

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.

  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 _tokens.MoveNext(); }
 63          private string Curr { get { return _tokens.Current != null ? _tokens.Current.Groups[1].Value : null; } }
 64          private int Pos { get { return _tokens.Current != null ? _tokens.Current.Index : 0; } }
 65          private TextWriter _errout;
 66          private void Error(string msg, params object[] args)
 67          { _errout.Write("error: " + msg, args); _errout.WriteLine(" (at {0}: '{1}')", Pos, Curr ?? ""); }
 68  
 69          // -------------------- parser ------------------------
 70          public ManParser(string s)
 71          {
 72              _errout = Console.Error;
 73              string p = @"\s*((?:[\-\+\*\/\%\!\(\)]|(?:\d+(?:\.\d+)?)|\w+)|(?:\S))\s*";
 74              _tokens = Regex.Matches(s, p, RegexOptions.Compiled).Cast<Match>().GetEnumerator(); ;
 75              Next();
 76          }
 77          private double Expr()
 78          {
 79              string[] ops = new [] { "+", "-" };
 80              string op;
 81              double v = Term();
 82              while (ops.Contains(op = Curr) && Next()) v = Eval(op, v, Term());
 83              while (Curr == "!" && Next()) v = Eval("!", v);
 84              return v;
 85          }
 86          private double Term()
 87          {
 88              string[] ops = new[] { "*", "/", "%", "^" };
 89              string op;
 90              double v = Factor();
 91              while (ops.Contains(op = Curr) && Next()) v = Eval(op, v, Factor());
 92              return v;
 93          }
 94          private double Factor()
 95          {
 96              string s = Curr;
 97              char c = s[0];
 98              if      (char.IsDigit(c))                      return Number();
 99              else if ((char.IsLower(c) || char.IsUpper(c))) return Name();
100              else if (c == '(')                             return NestedExpr();
101              else Error("name, number or (...) expected");
102              return double.PositiveInfinity;
103          }
104          private double Number()
105          {
106              double v = double.Parse(Curr);
107              Next();
108              return v;
109          }
110          private double Name()
111          {
112              string name = Curr;
113              ValueList args = null;
114              if (Next()) if (Curr == "(") { args = ArgList(); }
115              return Eval(name, args);
116          }
117          private ValueList ArgList()
118          {
119              ValueList args = new ValueList();
120              if (Curr != "(") Error("'(' expected");
121              if (Next() && Curr != ")") { args.Add(Expr()); while (Curr == "," && Next()) args.Add(Expr()); }
122              if (Curr != ")") Error("')' expected");
123              Next();
124              return args;
125          }
126          private double NestedExpr()
127          {
128              if (Curr != "(") Error("'(' expected");
129              if (!Next()) Error("unexpected EOF");
130              double v = (Curr == "-" && Next()) ? -Expr() : Expr();
131              if (Curr != ")") Error("')' expected");
132              Next();
133              return v;
134          }
135      }
136  }

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