如何使用Java编码SQL查询的求值顺序？

Question

我正在尝试使用JSQLParser开发一个SQL查询求值器，我真的很困惑于如何决定求值顺序，例如，如果我有一个以下形式的查询

Select * 
From A,B,C 
Where A.id=B.id 
  And B.id=C.id 
  And A.id=C.id

问题是如何构建解析树或表达式树。我需要一些指针来解决这个问题。另外，我正在考虑使用两个堆栈来解决这个问题，这两个堆栈是一个运算符栈和一个操作数栈。我需要一些确认，这是否是理解这个问题的一种可能的方式？

Answer 1

这是一个有趣的问题。因此，请允许我介绍JSqlParser (https://github.com/JSQLParser/JSqlParser)的另一个分支。到目前为止，我将它用于SQL元数据分析，到目前为止还没有进行评估。

下面是我的两点看法。运算符的优先级部分是在JSqlParsers文法中伪造的。(@jbaliuka:我看了你的fork，我想它是基于旧版本的JSqlParser。sourceforge的最新进展(2010?)引入了加法和乘法的运算符优先。另外，您的解析表达式解析在我的fork中触发了一些更改。如果你能试一试，那就太好了。)

下面是一个使用JSqlParser V0.8.8进行加法和乘法的非常简单的表达式求值器。首先，JSqlParser提供了一个解析树，或者更准确地说，是从该树继承的对象层次结构，我使用JSqlParser的访问器结构遍历了该层次结构。当然，对于一个完整的版本，还有很多工作要做。这更多的是一种概念的证明。对我来说很有趣的是，我的例子中甚至连括号的优先顺序都是正确的。

import java.util.Stack;
import net.sf.jsqlparser.JSQLParserException;
import net.sf.jsqlparser.expression.Expression;
import net.sf.jsqlparser.expression.LongValue;
import net.sf.jsqlparser.expression.operators.arithmetic.Addition;
import net.sf.jsqlparser.expression.operators.arithmetic.Multiplication;
import net.sf.jsqlparser.parser.CCJSqlParserUtil;
import net.sf.jsqlparser.util.deparser.ExpressionDeParser;

public class SimpleEvaluateExpr {

    public static void main( String[] args ) throws JSQLParserException {
        //examples
        evaluate("4+5*6");
        evaluate("4*5+6");
        evaluate("4*(5+6)");
        evaluate("4*(5+6)*(2+3)");
    }

    static void evaluate(String expr) throws JSQLParserException {
        //here is the stack you mentioned ;)
        final Stack<Long> stack = new Stack<Long>();

        System.out.println("expr=" + expr);
        Expression parseExpression = CCJSqlParserUtil.parseExpression(expr);
        //Deparser traverses the complete expression hierarchy. It was mainly used
        //for SQL output but this is now done using toString but is always a useful
        //traversal tool.
        ExpressionDeParser deparser = new ExpressionDeParser() {
            @Override
            public void visit(Addition addition) {
                super.visit(addition); 

                long sum1 = stack.pop();
                long sum2 = stack.pop();

                stack.push(sum1 + sum2);
            }

            @Override
            public void visit(Multiplication multiplication) {
                super.visit(multiplication); 

                long fac1 = stack.pop();
                long fac2 = stack.pop();

                stack.push(fac1 * fac2);
            }

            @Override
            public void visit(LongValue longValue) {
                super.visit(longValue); 
                stack.push(longValue.getValue());
            }
        };
        StringBuilder b = new StringBuilder();
        deparser.setBuffer(b);
        parseExpression.accept(deparser);

        System.out.println(expr + " = " + stack.pop() );
    }
}

下面是输出：

expr=4+5*6
4+5*6 = 34
expr=4*5+6
4*5+6 = 26
expr=4*(5+6)
4*(5+6) = 44
expr=4*(5+6)*(2+3)
4*(5+6)*(2+3) = 220

因此，第一个示例表达式的解析树类似于：

(4)

• Multiplication
• LongValue(5)
• LongValue(6)

的

• Addition
  • LongValue

​

​

访问者首先进行深度遍历。

Answer 2

运算符优先级通常由语法定义，访问者应该以定义的顺序递归地访问节点，在访问者实现中应该可以使用普通递归来计算表达式。堆栈方法也是正确的，但不是必须的。

我不确定jsqlparse语法，它对AST转换很好，但我没有测试它的评估。如果它不能工作，那么你将不得不自己修复它，因为这个库不再维护了，我自己也维护了一个jsqlparser forks，这个fork忽略了运算符的优先级。