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:
- download coco.exe, Scanner.frame, Parser.frame
- write your grammar with the embedded actions
- write a hook to integrate the parsing in your code
- 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.
1 using System.Collections.Generic;
2 using System.Text;
3 using System.IO;
4
5 using ValueList = System.Collections.Generic.List<double>;
6
7
8
9 COMPILER Eval
10
11
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
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
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
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
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
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
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
