递归下降解析器（Recursive Descent Parser, RDP）是一种用于解析语言语法的算法，它通过递归地调用函数来处理输入字符串。本文将介绍如何基于Herb Schildt的Java实现，将其翻译为C#代码，并扩展其功能，以支持用户定义的变量存储和数学表达式的计算。
递归下降解析器的概念可以追溯到数十年前。近年来，尽管市场上存在许多编程语言的表达式求值器，但大多数缺乏完整的功能。它们要么代码质量差，要么复杂且不完整，难以用于构建实际应用。
在寻找一个可扩展、可靠、可编译的C#递归下降解析器的过程中，发现Herb Schildt的Java实现非常有价值。尽管是一名C#新手，但经过几天的努力，将其翻译为一个工作的C#应用程序。然而，它仍然缺乏存储和检索用户定义变量的能力，也无法识别和处理基本的数学和三角函数，如sqrt、sin、cos等。
为了实现一个完整的数学表达式解析器，需要三个类：Parser.cs、VarMap.cs和KeyMap.cs。这些类共同工作，以完成解析任务。
Parser类是解析器的入口点，它负责解析和计算表达式。VarMap类用于存储和检索变量，而KeyMap类用于映射函数名。
Parser类的主要功能是解析和计算数学表达式。它使用一个表达式字符串作为输入，并返回计算结果。以下是Parser类的一个示例：
class Parser {
// Constructor
public Parser() {
m_keymap = new KeyMap();
m_varmap = new VarMap();
m_varmap.LoadVarMap("varmap.dat");
m_keymap.DumpKeyWords();
m_varmap.Dump();
}
// Fields
const String EOE = "\0";
private String exp;
private int expIdx;
private String token;
private int tokType;
// These are the token types.
const int NONE = 0;
const int DELIMITER = 1;
const int VARIABLE = 2;
const int NUMBER = 3;
// These are the types of syntax errors.
const int SYNTAX = 0;
const int UNBALPARENS = 1;
const int NOEXP = 2;
const int DIVBYZERO = 3;
// These are the keywords
private KeyMap m_keymap;
private VarMap m_varmap;
// Methods
public double Evaluate(String expstr) {
double result = 0.0;
exp = expstr;
expIdx = 0;
getToken();
if (token.Equals(EOE))
handleErr(NOEXP);
result = EvalExp1();
return result;
if (!token.Equals(EOE))
handleErr(SYNTAX);
return result;
}
}
VarMap类用于存储变量名和值。它使用一个字典来存储变量名和对应的值。以下是VarMap类的一个示例：
class VarMap {
// Fields
private static Dictionary m_varmap;
private static int m_ncount;
// Constructors
public VarMap() {
m_varmap = new Dictionary();
m_ncount = 0;
}
// Methods
public int AddVariable(String skey, Double dval) {
if (m_varmap.ContainsKey(skey)) {
UpdateVariable(skey, dval);
return 1;
}
m_varmap.Add(skey, dval);
return 1;
}
public int UpdateVariable(String skey, Double dval) {
m_varmap.Remove(skey);
m_varmap.Add(skey, dval);
return 1;
}
protected static Dictionary LoadDic(string sDicPath) {
Dictionary theDic = new Dictionary();
int nCount = 0;
string svar = string.Empty;
double dval = -1.0;
using (BinaryReader rd = new BinaryReader(File.OpenRead(sDicPath))) {
nCount = rd.ReadInt32();
for (int n = 0; n < nCount; n++) {
svar = rd.ReadString();
dval = rd.ReadDouble();
theDic.Add(svar, dval);
}
}
return theDic;
}
protected static int SaveDic(Dictionary theDic, string filePath) {
using (BinaryWriter b = new BinaryWriter(File.Open(filePath, FileMode.Create))) {
b.Write(theDic.Count);
foreach (var s in theDic) {
b.Write(s.Key);
b.Write(s.Value);
}
}
return 1;
}
}
要使用这个解析器，需要将Parser.cs、VarMap.cs、KeyMap.cs和Error.cs这四个类添加到项目中，并确保它们共享相同的命名空间。以下是如何在控制台应用程序中使用Parser类的一个示例：
static void Main(string[] args) {
Parser parser = new Parser();
double dval = -1.0;
string expr = string.Empty;
Console.WriteLine("\n\t\tEnhanced Recursive Descent Parser in C#");
Console.Title = "Enhanced Recursive Descent Parser in C#";
for (;;) {
Console.WriteLine();
Console.Write("<< ");
expr = Console.ReadLine();
if (expr.ToLower() == "quit")
break;
if (expr.ToLower() == "cls") {
Console.Clear();
Console.WriteLine("\n\t\tEnhanced Recursive Descent Parser in C#");
continue;
}
if (expr.ToLower() == "list vars" || expr.ToLower() == "listvars") {
parser.ListVars();
continue;
}
if (expr.ToLower() == "list keys" || expr.ToLower() == "listkeys") {
parser.ListKeywords();
continue;
}
if (expr.ToLower() == "del var") {
Console.Write("Variable Name : ");
expr = Console.ReadLine();
parser.DeleteVariable(expr);
continue;
}
if (expr.ToLower() == "help") {
GetHelp();
continue;
}
dval = parser.Evaluate(expr);
Console.WriteLine("\nresult =: " + dval);
}
}
本文介绍的递归下降解析器是一个可读、可扩展、易于修改和重用的代码。它可以被修改以支持更复杂的数据类型，如复数和矩阵。尽管在C++和Java方面有一些经验，但发现C#在可维护性、可读性和可管理性方面更胜一筹。