15,039,470 members
Articles / Programming Languages / C#
Alternative
Article
Posted 26 Apr 2012

24.6K views
15 bookmarked

Mathematical Expression Parser Using Coco/R

Rate me:
26 Apr 2012CPOL3 min read
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:

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.

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

Share

 Founder eXternSoft GmbH 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).

 First Prev Next
 Couple of bugs markr00710-Sep-14 9:49 markr007 10-Sep-14 9:49
 Re: Couple of bugs Andreas Gieriet10-Sep-14 12:31 Andreas Gieriet 10-Sep-14 12:31
 Hello markr007, thanks for your feedback. The factorial parsing was indeed broken. I've fixed it in lines 62...65 and 84 (submission of these changes are pending at the time of writing this). For your convenience, these are the changed lines: Copy Code ``` 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; ... 84 while (Curr == "!") { v = Eval("!", v); Next(); }``` The other remarks are no bugs according to the given grammar: the factorial is *not* part of the Term and there is no general unary sign operator (it is only allowed within a nested expression). The power operator is uncommon too: it is usually defined as right associative, which is not given here and it is usually not on the same priority as multiplication operators. Please see the note at the end of "The Language Definition" section. The grammar is odd, but I decided those days to take the grammar from the original post and document it as-is. Feel free to modify it such that it is useful for you. Cheers Andi PS: A grammar that is more common grammar was: Copy Code ```Expr = Term { ( "+" | "-" ) Term } . Term = Factor { ( "*"|"/"|"%") Factor } . Factor = { "+" | "-" } Factorial . Factorial = Power { "!" } . Power = { Primary "^" } Primary . Primary = Number | Name | "(" Expr ")" . Name = Letter { Letter|Digit } . Number = Digit { Digit } [ "." Digit { Digit } ] .```
 Re: Couple of bugs markr00714-Sep-14 11:40 markr007 14-Sep-14 11:40
 Re: Couple of bugs Andreas Gieriet14-Sep-14 12:01 Andreas Gieriet 14-Sep-14 12:01
 my vote of five alejandro29A10-Apr-14 8:09 alejandro29A 10-Apr-14 8:09
 Re: my vote of five Andreas Gieriet10-Apr-14 9:38 Andreas Gieriet 10-Apr-14 9:38
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Sep-21 23:44 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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