Mathematical Expression Parser Using Coco/R
4.94/5 (8 votes)
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:
- 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.
using System.Collections.Generic;
using System.Text;
using System.IO;
using ValueList = System.Collections.Generic.List<double>;
/* ----------------------- Start Symbol ---------------------------- */
COMPILER Eval /* the "compiler" is named by the start symbol */
/* ----------------------- custom code ---------------------------- */
private double Eval(string name, ValueList args)
{
string symbol = args == null ? name : string.Format("{0}({1})", name, args.Count);
Func<ValueList, double> func;
if (_symbols.TryGetValue(symbol, out func)) return func(args);
errors.SemErr(string.Format("Symbol not found: {0}", name));
return 1.0;
}
private double Eval(string name, params double[] args)
{
return Eval(name, new ValueList(args));
}
public static void SetVar(string name, double val)
{
if (_symbols.ContainsKey(name)) _symbols[name] = a=>val;
else _symbols.Add(name, a=>val);
}
private const double DEG_RAD = Math.PI/180.0;
private static Dictionary<string, Func<ValueList, double>> _symbols =
new Dictionary<string, Func<ValueList, double>>(StringComparer.InvariantCultureIgnoreCase)
{
{ "+(2)", a=> a[0]+a[1] },
{ "-(2)", a=> a[0]-a[1] },
{ "*(2)", a=> a[0]*a[1] },
{ "/(2)", a=> a[0]/a[1] },
{ "%(2)", a=> a[0]%a[1] },
{ "^(2)", a=> Math.Pow(a[0],a[1]) },
{ "!(1)", a=> {double v=a[0]; int i = (int)v; while(--i > 0) v*=i; return v;} },
{ "-(1)", a=> -a[0] },
{ "(1)", a=> a[0] },
{ "pi", a=> Math.PI },
{ "sin(1)", a=> Math.Sin(DEG_RAD*a[0]) },
{ "cos(1)", a=> Math.Cos(DEG_RAD*a[0]) },
{ "tan(1)", a=> Math.Tan(DEG_RAD*a[0]) },
{ "exp(1)", a=> Math.Exp(a[0]) },
{ "ln(1)", a=> Math.Log(a[0]) },
{ "log(1)", a=> Math.Log10(a[0]) },
};
double _val = 0.0;
public static double Evaluate(string s)
{
using (var strm = new MemoryStream(Encoding.ASCII.GetBytes(s)))
{
Scanner scanner = new Scanner(strm);
Parser parser = new Parser(scanner);
parser.Parse();
if (parser.errors.count > 0) Console.WriteLine("Errors: {0}", parser.errors.count);
return parser._val;
}
}
/* ----------------------- Scanner ---------------------------- */
CHARACTERS
letter = 'A'..'Z' + 'a'..'z'.
digit = '0'..'9'.
TOKENS
ident = letter { letter | digit }.
number = digit { digit } [ '.' digit { digit } ] .
IGNORE ' ' + '\t'
/* ----------------------- Parser ---------------------------- */
PRODUCTIONS
Eval = Expr<ref _val> .
Expr<ref double val> (. double v = 0; string op; .)
= Term<ref v> (. val = v; .)
{ ("+"|"-") (. op=t.val; .) Term<ref v> (. val = Eval(op, val, v); .)
}
{ "!" (. val = Eval(t.val); .)
} .
Term<ref double val> (. double v = 0; string op; .)
= Factor<ref v> (. val = v; .)
{ ("*"|"/"|"%"|"^") (. op=t.val; .) Factor<ref v> (. val = Eval(op, val, v); .)
} .
Factor<ref double val> (. double v = 0; string op = ""; .)
= number (. val = double.Parse(t.val); .)
| Name<ref v> (. val = v; .)
| "(" ["-" (. op=t.val; .) ] Expr<ref v> ")" (. val = Eval(op, v); .)
.
Name<ref double val> (. ValueList args = null; string name; .)
= ident (. name = t.val; .)
["(" (. args = new ValueList(); .) [ArgList<ref args>] ")"] (. val = Eval(name, args); .)
.
ArgList<ref ValueList args> (. double v = 0; .)
= Expr<ref v> (. args.Add(v); .)
{ "," Expr<ref v> (. args.Add(v); .)
}
.
END Eval.
/* ----------------------- 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.
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;
using ValueList = System.Collections.Generic.List<double>;
namespace ExpressionParser
{
public class ManParser
{
// --------------------------- custom code ----------------------
private double Eval(string name, ValueList args)
{
string symbol = args == null ? name : string.Format("{0}({1})", name, args.Count);
Func<ValueList, double> func;
if (_symbols.TryGetValue(symbol, out func)) return func(args);
Error(string.Format("Symbol not found: {0}", name));
return double.PositiveInfinity;
}
private double Eval(string name, params double[] args)
{
return Eval(name, new ValueList(args));
}
public static void SetVar(string name, double val)
{
if (_symbols.ContainsKey(name)) _symbols[name] = a => val;
else _symbols.Add(name, a => val);
}
private const double DEG_RAD = Math.PI / 180.0;
private static Dictionary<string, Func<ValueList, double>> _symbols =
new Dictionary<string, Func<ValueList, double>>(StringComparer.InvariantCultureIgnoreCase)
{
{ "+(2)", a=> a[0]+a[1] },
{ "-(2)", a=> a[0]-a[1] },
{ "*(2)", a=> a[0]*a[1] },
{ "/(2)", a=> a[0]/a[1] },
{ "%(2)", a=> a[0]%a[1] },
{ "^(2)", a=> Math.Pow(a[0],a[1]) },
{ "!(1)", a=> {double v=a[0]; int i = (int)v; while(--i > 0) v*=i; return v;} },
{ "-(1)", a=> -a[0] },
{ "(1)", a=> a[0] },
{ "pi", a=> Math.PI },
{ "sin(1)", a=> Math.Sin(DEG_RAD*a[0]) },
{ "cos(1)", a=> Math.Cos(DEG_RAD*a[0]) },
{ "tan(1)", a=> Math.Tan(DEG_RAD*a[0]) },
{ "exp(1)", a=> Math.Exp(a[0]) },
{ "ln(1)", a=> Math.Log(a[0]) },
{ "log(1)", a=> Math.Log10(a[0]) },
};
public static double Evaluate(string s) { return new ManParser(s).Expr(); }
// ------------------- scanner ---------------------
private IEnumerator<Match> _tokens;
private bool Next() { return _valid && (_valid = _tokens.MoveNext()); }
private string Curr { get { return _valid ? _tokens.Current.Groups[1].Value : null; } }
private int Pos { get { return _valid ? _tokens.Current.Index : 0; } }
private bool _valid = true;
private TextWriter _errout;
private void Error(string msg, params object[] args)
{ _errout.Write("error: " + msg, args); _errout.WriteLine(" (at {0}: '{1}')", Pos, Curr ?? ""); }
// -------------------- parser ------------------------
public ManParser(string s)
{
_errout = Console.Error;
string p = @"\s*((?:[\-\+\*\/\%\!\(\)]|(?:\d+(?:\.\d+)?)|\w+)|(?:\S))\s*";
_tokens = Regex.Matches(s, p, RegexOptions.Compiled).Cast<Match>().GetEnumerator(); ;
Next();
}
private double Expr()
{
string[] ops = new [] { "+", "-" };
string op;
double v = Term();
while (ops.Contains(op = Curr) && Next()) v = Eval(op, v, Term());
while (Curr == "!") { v = Eval("!", v); Next(); }
return v;
}
private double Term()
{
string[] ops = new[] { "*", "/", "%", "^" };
string op;
double v = Factor();
while (ops.Contains(op = Curr) && Next()) v = Eval(op, v, Factor());
return v;
}
private double Factor()
{
string s = Curr;
char c = s[0];
if (char.IsDigit(c)) return Number();
else if ((char.IsLower(c) || char.IsUpper(c))) return Name();
else if (c == '(') return NestedExpr();
else Error("name, number or (...) expected");
return double.PositiveInfinity;
}
private double Number()
{
double v = double.Parse(Curr);
Next();
return v;
}
private double Name()
{
string name = Curr;
ValueList args = null;
if (Next()) if (Curr == "(") { args = ArgList(); }
return Eval(name, args);
}
private ValueList ArgList()
{
ValueList args = new ValueList();
if (Curr != "(") Error("'(' expected");
if (Next() && Curr != ")") { args.Add(Expr()); while (Curr == "," && Next()) args.Add(Expr()); }
if (Curr != ")") Error("')' expected");
Next();
return args;
}
private double NestedExpr()
{
if (Curr != "(") Error("'(' expected");
if (!Next()) Error("unexpected EOF");
double v = (Curr == "-" && Next()) ? -Expr() : Expr();
if (Curr != ")") Error("')' expected");
Next();
return v;
}
}
}
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