带函数和变量的递归下降解析器
4.60/5 (7投票s)
一个递归下降数学表达式解析器，带有内置函数和变量映射。
引言
这是一个基于递归下降解析器 (RDP) 的全功能数学表达式解析器。底层的 Java 代码用于实际的求值器，属于公共领域，可通过此处获取。为了实用，解析器应具备按名称和值存储和检索变量的方法，能够将这些值从一个会话持久化到下一个会话，并能够接受标准数学表达式作为纯文本进行处理，计算出正确的数学结果，而不受表达式复杂度的影响。尽管市面上有各种编程语言中的表达式求值器，但大多数都缺乏上述全部功能。
背景
大约二十年前，在处理医疗保健统计数据时，我偶然发现了 Herb Schildt 的 C++ 简单表达式解析器。我坚信这种方法可以帮助我定制和加速数学统计方面的工作。经过多年努力，我成功地使用 C++ 定制了 Schildt 的解析器，以适应更具统计学意义的变量，例如向量和矩阵。但令我沮丧的是，代码膨胀成了一个庞大、复杂、难以管理、不可重用的相互关联类集合。将这些模块移植到其他语言变得异常困难。从那时起，我一直在寻找一个更紧凑、易于修改的解析器，并发现了很多用 Pascal、C、C++、C#、Python、Java 以及各种伪代码编写的解析器，但都没有让我满意。使问题复杂化的是，已经描述了各种各样的解析技术，包括自顶向下、自底向上、递归下降、逆波兰表示法、Shunting-Yard 等等。当我在这里（此处）发现一个极其小巧的 Java 数学表达式解析器时，我立即开始着手扩展它以满足我自己的需求。本文就是我早期努力的成果。
使用代码
有三个类协同工作来完成解析，分别是 JVarMap、JPreScan 和 JParser。
JVarMap 使用一个名为 `Key` 的 `ArrayList
public class JVarMap {
// fields
private static ArrayList<String> Key;
private static ArrayList<Double> Value;
private byte[] BArray;
private int nOffset;
// constructors
public JVarMap()
{
Key = new ArrayList<String>();
Value = new ArrayList<Double>();
BArray = null;
nOffset = 0;
}
// methods
public int Add(String svarnam, double dval)
{
Key.add(svarnam);
Value.add(dval);
BArray = null;
nOffset = 0;
return 1;
}
public int Update(String svarnam, double dval)
{
int nIndex = getKeyIndex(svarnam);
if(nIndex < 0) return 0;
Value.set(nIndex, dval);
return 1;
}
public int Erase(String svarnam)
{
int nIndex = getKeyIndex(svarnam);
if(nIndex < 0) return 0;
Key.remove(nIndex);
Value.remove(nIndex);
return 1;
}
//..
public double getValue(String sKey)
{
int ndx = -1;
boolean bfound = false;
double dnull = NaN;
if( !Key.contains(sKey) ) return dnull;
for(int i = 0; i < Key.size(); i++)
{
if(Key.get(i).equals(sKey)) bfound = true;
if(bfound) ndx = i;
if(bfound) break;
}
if(!bfound) return dnull;
double dm = Value.get(ndx);
return dm;
}
//..
由于 JParser.eval 方法只能处理实际值而不能处理变量名，因此有必要将任何变量名转换为其实际值，以便将像 'm*x + b' 这样的表达式重新格式化为 '0.8 * 3.0 + 4.0'，换句话说，用实际值替换变量名。这是通过 `JPreScan` 类完成的。`Prescan` 方法将初始字符串表达式作为参数，进行必要的重新格式化以确保正确的空格，这对于将输入表达式分割成字符串标记是必需的，然后使用这些标记重新构建一个输出字符串，该字符串使用名为 varmap 的 `CVarMap` 变量，在必要时用实际值替换字面值名称。
public String Prescan(String sCommand)
{
String sCommand2, sv;
double dv = 0.0;
sv = "";
sCommand2 = sCommand;
// replace all delimiters with spaces
String sx = sCommand2;
System.out.println("sx =: " + sx);
sx = sx.replaceAll("\\(", " ");
sx = sx.replaceAll("\\)", " ");
sx = sx.replaceAll("\\*", " ");
sx = sx.replaceAll("\\+", " ");
sx = sx.replaceAll("\\-", " ");
sx = sx.replaceAll("\\/", " ");
sx = sx.replaceAll("\\^", " ");
System.out.println("sx =: " + sx);
String[] sar = sx.split(" ");
for(int i = 0; i < sar.length; i++) {
System.out.println(String.format("sar[%d] =: %s", i, sar[i]));
}
//String sCommand2 = sCommand;
System.out.println("sCommand2 =: " + sCommand2);
for(int i = 0; i < sar.length; i++)
{
if(sar[i].isEmpty()) continue; // blank space
if(sar[i].matches("[-+]?\\d*\\.?\\d+") ) continue; // numeric
System.out.println(String.format("sar[%d] =: %s", i, sar[i]));
if(varmap.isKey(sar[i])) {
// get the value for that key variable
dv = <varmap>.getValue(sar[i]); System.out.println("dv =: " + dv);
sv = Double.toString(dv); System.out.println("sv =: " + sv);
sCommand2 = sCommand2.replaceAll(sar[i], sv);
}
}
System.out.println("sCommand2 =: " + sCommand2);
return sCommand2;
}
使用 JParser 类的 eval(final String str) 方法对最终的预扫描表达式进行求值。算术表达式的 `eval` 方法支持加法、减法、乘法、除法、幂运算（使用 `^` 符号）以及一些基本函数，如 `sqrt`, log, atan, exp, sin, cos, and tan.。它支持使用 `(`...`)` 进行分组，并且能够正确处理运算符优先级和结合性规则。该解析器是一个递归下降解析器，因此它在内部为语法中的每个运算符优先级级别使用单独的解析方法。部分代码已发布，属于公共领域，可在此处找到。
public double eval(final String str) {
return new Object() {
int pos = -1, ch;
void nextChar() {
ch = (++pos < str.length()) ? str.charAt(pos) : -1;
}
boolean eat(int charToEat) {
while (ch == ' ') nextChar();
if (ch == charToEat) {
nextChar();
return true;
}
return false;
}
double parse() {
nextChar();
double x = parseExpression();
if (pos < str.length()) throw new RuntimeException("Unexpected: " + (char)ch);
return x;
}
// Grammar:
// expression = term | expression `+` term | expression `-` term
// term = factor | term `*` factor | term `/` factor
// factor = `+` factor | `-` factor | `(` expression `)`
// | number | functionName factor | factor `^` factor
double parseExpression() {
double x = parseTerm();
for (;;) {
if (eat('+')) x += parseTerm(); // addition
else if (eat('-')) x -= parseTerm(); // subtraction
else return x;
}
}
double parseTerm() {
double x = parseFactor();
for (;;) {
if (eat('*')) x *= parseFactor(); // multiplication
else if (eat('/')) x /= parseFactor(); // division
else if (eat('^')) x = Math.pow(x, parseFactor()); // exponentiation
else return x;
}
}
double parseFactor() {
if (eat('+')) return parseFactor(); // unary plus
if (eat('-')) return -parseFactor(); // unary minus
double x;
int startPos = this.pos;
if (eat('(')) { // parentheses
x = parseExpression();
eat(')');
} else if ((ch >= '0' && ch <= '9') || ch == '.') { // numbers
while ((ch >= '0' && ch <= '9') || ch == '.') nextChar();
x = Double.parseDouble(str.substring(startPos, this.pos));
} else if (ch >= 'a' && ch <= 'z') { // functions
while (ch >= 'a' && ch <= 'z') nextChar();
String func = str.substring(startPos, this.pos);
x = parseFactor();
if (func.equals("sqrt")) x = Math.sqrt(x);
else if (func.equals("log")) x = Math.log(x);
else if (func.equals("atan")) x = Math.atan(x);
else if (func.equals("exp")) x = Math.exp(x);
else if (func.equals("sin")) x = Math.sin(Math.toRadians(x));
else if (func.equals("cos")) x = Math.cos(Math.toRadians(x));
else if (func.equals("tan")) x = Math.tan(Math.toRadians(x));
else throw new RuntimeException("Unknown function: " + func);
} else {
throw new RuntimeException("Unexpected: " + (char)ch);
}
return x;
}
}.parse();
}
为了演示该程序，使用了 `Console` 类。关于类方法的更详细描述可在此处找到。请注意，JParser.eval 方法本身不具备赋值功能。也就是说，像 'r = 10.2 * x' 这样的表达式将被视为错误而被拒绝。解决此问题的方法是使用 Console 来识别初始输入表达式何时包含等号，如果包含，则将赋值部分与求值部分分开，分别处理，并在求值后重新建立它们的连接，以及添加或更新分配给变量映射的值。这是隐式变量初始化。换句话说，简单地赋值一个变量名，无论它是否已经被映射，如果它不存在，则会创建一个新变量，如果存在，则会更新现有变量。请注意，Console 类同时利用 NetBeans 的 StdOut 和它自己的控制台窗口输出，从而增强了调试任务。
从控制台输入 'help' 或 '?' 即可使用内置的帮助方法。将出现以下内容：
public class Console extends javax.swing.JFrame {
//..
public Path p;
public JParser parser = new JParser();
public JVarMap varmap = new JVarMap();
public JPreScan prescan = new JPreScan();
public Console() {
initComponents();
p = Paths.get("./data/varmap.dat");
try {
varmap.readMap(p);
varmap.dumpKeys();
}
catch (FileNotFoundException ex) {
System.out.println(String.format("%s", ex.getMessage()));
}
//..
}
//..
private void jTextArea1KeyPressed(java.awt.event.KeyEvent evt) {
// TODO add your handling code here:
//System.out.println("Key Pressed");
if (evt.getKeyCode() == KeyEvent.VK_ENTER) {
//..
boolean bAssign = false;
int nIndex = sCommand.indexOf('=');
//..
else if(nIndex >= 0)
{
System.out.println("Assignment of new or update of variable plus evaluation");
svarnam = sCommand.substring(0, nIndex-1);
sCommand = sCommand.substring(nIndex + 1, sCommand.length());
JPreScan prescan = new JPreScan(varmap, sCommand);
sCommand = prescan.getOutStr();
try {
double dval = parser.eval(sCommand);
if(varmap.isKey(svarnam)) varmap.Update(svarnam, dval);
else varmap.Add(svarnam, dval);
String smtx = Double.toString(dval);
smtx += "\n";
appendString(smtx); // result is appended to jTextArea1 text
}
catch (RuntimeException ex) {
System.out.println(String.format("Warning: %s", ex.getMessage()));
appendString("Unknown variable or function\n");
}
}
//..
关注点
主要的挑战是如何修改此解析器以处理更复杂的变量，例如向量和矩阵，以及需要多个输入参数的函数。到目前为止，我尚未成功。我甚至尝试使用逆波兰表示法的Shunting-Yard 算法解析器，取得了一些有限的成功。如果有人能够用公共领域中的代码来解决这个问题，并且该代码可读、可扩展、易于修改且可重用，那对许多程序员来说将是相当有价值的。但我发现的只有关于各种解析器类如何扩展的模糊暗示。
历史
版本 1.0.0.0 2017 年 5 月 26 日