使用 Coco/R 的数学表达式解析器
4.94/5 (8投票s)
这是“使用递归下降解析解析数学表达式”的替代方案
引言
这是对原始文章 使用递归下降解析的数学表达式解析器[^]中语言解析方式的替代方案。 你可以考虑使用一些解析器生成工具，而不是发明你自己的扫描器和解析器。 其中一个生成独立代码（无需链接到任何库）并且是原生 C# 的是 Coco/R 。
它非常容易使用
- 下载 coco.exe, Scanner.frame, Parser.frame
- 用嵌入的动作编写你的语法
- 编写一个钩子将解析集成到你的代码中
- 编译并运行
此替代方案的目的是展示使用解析器生成器时，相同的解析器有多紧凑。
随附的示例显示了原始文章中提供的语法的表达式求值器。
语言定义
我认为描述一种将作为递归下降解析器实现的语言最有效的方法是 EBNF[^]。 原始文章中给出的语法的 EBNF 形式（带有起始符号 "Expr"）是
Expr = Term { ( "+" | "-" ) Term } { "!" } .
Term = Factor { ( "*"|"/"|"%"|"^") Factor } .
Factor = Number | Name | "(" ["-"] Expr ")" .
Name = Letter { Letter|Digit } .
Number = Digit { Digit } [ "." Digit { Digit } ] .
可以使用像 EBNF 可视化工具[^]这样的工具可视化该语法。
如下面的代码示例中第 70 行开始所示，可以方便地实现此语法。
注意： 此语法相当奇怪。 我从原始文章中原样采用，并以 EBNF 和从 EBNF 定义派生的图形中正式记录了它。 幂运算和阶乘运算不符合通用定义。 此外，一元减号只允许在嵌套表达式中使用，这也很不常见。
使用代码
解析器生成器由几个部分组成
- 自定义代码，例如用于初始化等。
- 带有字符集、token、产生式等的语法。
- 嵌入在语法中的动作，这些动作将在解析元素时执行。
我在这里不解释 Coco/R 的语法 - 有很好的资源可用，例如 Coco/R 用户手册 和 Coco/R 教程。
这是 Coco/R 代码。 该文件由 Coco/R 编译，产生两个 C# 文件：Scanner.cs 和 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! ---------------------------- */
将此代码存储到一个名为 Eval.atg 的文件中，将 Scanner.frame、Parser.frame 和 coco.exe 复制到该源目录。 在命令提示符下编译
coco Eval.atg csc Scanner.cs Parser.cs Parser.exe "sin(45)*cos(45)^2*(len-1)"
输出结果如下
sin(45)*cos(45)^2*(len-1) = 30.5
我发现这些工具非常有价值 - 一旦掌握了基础知识（例如，通过一些关键字分隔的整体结构，语法和嵌入代码 (. ... .) 之间的区别），阅读代码就没什么大不了的。
同样，此替代方案并非旨在详细描述 Coco/R - 请参阅上面的相关链接。 目的是展示原始文章的替代技术。
作为手工解析器的替代方案
作为说明，你可以为这样一种简单的语言手工编写一个类似紧凑的解析器。 比较从第 57 行开始的两个文件。
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;
}
}
}
关注点
我必须承认，我有时忍不住为一些小问题编写自己的扫描器/解析器，而不是使用上面的工具... ;-)
查看 Coco/R 文档 - 它写得非常漂亮 - 非常简洁易懂。 如果你曾经得到 Hanspeter Mössenböck 的书：读它！ 我一次又一次地惊叹于他如何精彩地简洁地解释计算机语言，特别是他关于 C# 的书是一种享受。
历史
2012-03-09 第一个版本
2012-04-21 增强了介绍，添加了 EBNF，添加了一些链接，添加了手工版本作为比较
2014-09-11 修复了阶乘解析（感谢 markr007），更新了 EBNF 和图形