递归下降分析器-添加统一变量

Question

因此，我有一个递归下降解析器，它在infix中分析一个数学表达式。表达式被标记化，用前面的解析器解析，解析器动态生成AST (每种表达式的节点)并计算最终值。我将所有这些值处理为doubles；因此，我使用这个解析器如下：

Parser parser = new Parser();

try {
    ExpressionNode expression = parser.parse("5 + 4*cos(pi)");
    System.out.println("The value of the expression is "
            + expression.getValue());
} catch (ParserException | EvaluationException e) {
    System.out.println(e.getMessage());
}

}

使用Exceptions，我定义了自己。行expression.getValue()返回一个double，我的解析器的工作方式是每个表达式节点都返回一个double，所以每个分支都是自下而上的，直到它最终得到一个double答案。

问题是，我希望处理表达式中的统一变量，就像我想解析5 + x (其中x不是先初始化的)一样，表达式的值将返回5 + x。

是否必须将表达式节点的getValue()返回类型更改为String？我觉得这会使程序变得复杂和臃肿，而且必须有更好的方法来完成这一任务。有人对这类事情有什么经验吗？

我知道解析器的描述可能有点模糊，所以这是我学习如何实现大部分解析器的地方。

Answer 1

我假设在表达式树中为运算符和常量定义了类。您需要为变量定义一个新的类。

然后，您需要添加一个像getAllVariables这样的方法，它可以返回树中任意点以下的所有变量。

我建议您更改getValue以接受Map<String, Double>，以便在计算时为任何变量提供值。除了变量之外，所有节点都需要忽略这一点，这些节点将从映射中返回自己的值。如果他们没有为自己找到一个映射作为密钥，他们应该抛出一个EvaluationException。

最后，如果希望将表达式打印为字符串，那么这实际上是getValue的一个单独的方法。也许是getExpressionText。然后，每个类都可以重写它以返回一个字符串，该字符串表示从该点向下的表达式，变量只返回变量名。

因此，一旦解析了表达式，就可以获得所有变量，提示用户为它们提供值，计算给定值的表达式(如果有未定义的异常，则捕获异常)，然后再次打印出来。

ExpressionNode expression = Parser.parse("x + 5 * y");
System.out.println(expression.getExpressionText());
System.out.println(expression.getAllVariables());
Map<String, Double> variableValues = new TreeMap<>();
variableValues.put("x", 4);
variableValues.put("y", -2);
System.out.println("Evaluates to " + expression.getValue(variableValues));

我希望您的Variable类最终看起来如下所示：

public class Variable implements ExpressionNode {
    private final String name;

    public double getValue(Map<String, Double> variableValues) {
        if (variableValues.containsKey(name)) {
            return variableValues.get(name);
        } else {
            throw new EvaluationException(name + " is undefined");
        }
    }

    public String getExpressionText() {
        return name;
    }

    public List<String> getAllVariables() {
        return Arrays.asList(name);
    }
}

在表达式树上执行的另一个常见操作是简化它。这实质上意味着将任何可以评估的值计算为常量。在我看来，最好的方法是返回一个新的简化树，而不是更改当前的树。因此，我建议在ExpressionNode中添加一种新方法

public ExpressionNode simplify();

对于变量和常量，这将只返回this。对于运营商来说，它需要做一些更复杂的事情。类似于：

class Operator implements ExpressionNode {
    public ExpressionNode simplify() {
    if (getAllVariables().isEmpty()) {
        return new Constant(getValue());
    } else {
        Operator simplified = new Operator(operation);
        for (ExpressionNode operand: operands) {
            simplified.addOperand(operand.simplify());
        }
        return simplified;
    }
}

希望你能看到它的作用。如果可以完全评估操作，则将其转换为常量。否则，它仍然是一个操作，但它的每个操作数依次被简化。

因此，如果您想简化一个表达式，您可以：

System.out.println(Parser.parse("7 * 2 + x * 3").simplify().getExpressionText());

它将返回"14 +x* 3“。

如果您想变得更加复杂，您可以将关联和分发的意识构建到您的操作符中，并更改simplify，以便将树重新组织为组变量。但我认为这超出了这个问题的范围！