使用Shunting Yard算法解析三元运算符

Question

为了背景，请先阅读有关三元运算符的这个问题。

我正在构建自己的编程语言，允许定义自定义运算符。因为我希望它尽可能少地使用编译器内置函数，所以应该允许定义自定义三元运算符，最好是以下形式：

infix operator ? : { precedence 120 }

我的（手写的）表达式解析器将把嵌套的三元运算符转换为由运算符分隔的操作数列表。

a ? b ? c : d : e
(a) ? (b) ? (c) : (d) : (d)
OperatorChain(operators: [?, ?, :, :], operands: [a, b, c, d, e])

OperatorChain类现在从作用域中的运算符定义中查找运算符，并使用修改版逆波兰算法将列表转换为二进制AST节点。修改后的逆波兰算法如下所示：

// Note: OperatorElement is a class that merely stores an Identifier, an associated source code position and the resolved operator.
// IValue is the base interface for all Expression AST nodes

final Stack<OperatorElement> operatorStack = new LinkedList<>();
final Stack<IValue> operandStack = new LinkedList<>();
operandStack.push(this.operands[0]);

for (int i = 0; i < this.operatorCount; i++)
{
    final OperatorElement element1 = this.operators[i];
    OperatorElement element2;
    while (!operatorStack.isEmpty())
    {
        element2 = operatorStack.peek();

        final int comparePrecedence = element1.operator.comparePrecedence(element2.operator);
        if (comparePrecedence < 0
                || element1.operator.getAssociativity() != IOperator.RIGHT && comparePrecedence == 0)
        {
            operatorStack.pop();
            this.pushCall(operandStack, element2);
        }
        else
        {
            break;
        }
    }
    operatorStack.push(element1);
    operandStack.push(this.operands[i + 1]);
}
while (!operatorStack.isEmpty())
{
    this.pushCall(operandStack, operatorStack.pop());
}

return operandStack.pop().resolve(markers, context);

我需要如何修改此算法才能与三元运算符一起使用，包括自定义的三元运算符？

- Clashsoft

Answer 1

我在Java中实现了一个数学解析器，可以处理三元运算符。核心是expression方法。输入包含在迭代器it中，具有it.peekNext()方法来查看下一个令牌和it.consume()移动到下一个令牌。它调用prefixSuffix()方法来读取可能具有前缀和后缀运算符的常量和变量，例如++x。

protected void expression() throws ParseException  {

    prefixSuffix(); 

    Token t = it.peekNext();
    while(t!=null) {
        if(t.isBinary()) {
            OperatorToken ot = (OperatorToken)t;
            Operator op = ot.getBinaryOp();
            pushOp(op,ot);
            it.consume();
            prefixSuffix();
        }
        else if(t.isTernary()){
            OperatorToken ot =(OperatorToken)t;
            Operator to = ot.getTernaryOp();
            pushOp(to,ot);
            it.consume();
            prefixSuffix();
        }
        else
            break;
        t=it.peekNext();
    }
    // read all remaining elements off the stack
    while(!sentinel.equals(ops.peek())) {
        popOp();
    }
}

当遇到任何一个标记时，就会调用pushOp方法将其推入栈中。每个标记都有一个相关联的运算符，也会被解析为pushOp。 pushOp方法会将新的运算符与栈顶进行比较，如果必要则执行弹出操作。

protected void pushOp(Operator op,Token tok) throws ParseException 
{
    while(compareOps(ops.peek(),op))
        popOp();
    ops.push(op); 
}

处理三元运算符的逻辑发生在 compareOps 中：

/**
 * Compare operators based on their precedence and associativity.
 * @param op1
 * @param op2
 * @return true if op1 has a lower precedence than op2, or equal precedence and a left assoc op, etc.
 */
protected boolean compareOps(Operator op1,Operator op2)
{
    if(op1.isTernary() && op2.isTernary()) {
        if(op1 instanceof TernaryOperator.RhsTernaryOperator &&
                op2 instanceof TernaryOperator.RhsTernaryOperator )
            return true;
        return false;
    }
    if(op1 == sentinel ) return false;
    if(op2 == sentinel ) return true;
    if(op2.isPrefix() && op1.isBinary()) return false;
    if(op1.getPrecedence() < op2.getPrecedence()) return true;
    if(op1.getPrecedence() == op2.getPrecedence() && op1.isLeftBinding()) return true;
    return false;
}

如果两个运算符都是三元运算符的右操作数，那么compareOps返回true，将弹出一个操作数。否则，如果两者都是左操作数或者其中一个是左操作数而另一个是右操作数，则compareOps返回false，并且不会弹出任何操作数。

另一部分处理发生在popOp方法中：

protected void popOp() throws ParseException
{
    Operator op = ops.pop();

    if(op == implicitMul) {
        Node rhs = nodes.pop();
        Node lhs = nodes.pop();
        Node node = nf.buildOperatorNode(
                jep.getOperatorTable().getMultiply(), 
                lhs, rhs);
        nodes.push(node);
    }
    else if(op.isBinary()) {
        Node rhs = nodes.pop();
        Node lhs = nodes.pop();
        Node node = nf.buildOperatorNode(op, lhs, rhs);
        nodes.push(node);
    }
    else if(op.isUnary()) {
        Node lhs = nodes.pop();
        Node node = nf.buildOperatorNode(op, lhs);
        nodes.push(node);
    }
    else if(op.isTernary() && op instanceof TernaryOperator.RhsTernaryOperator ) {
        Operator op2 = ops.pop();
        if(!(op2 instanceof TernaryOperator ) || !((TernaryOperator) op2).getRhsOperator().equals(op)) {
            throw new ParseException(
                    MessageFormat.format(JepMessages.getString("configurableparser.ShuntingYard.NextOperatorShouldHaveBeenMatchingTernaryOp"),op2.getName())); //$NON-NLS-1$

        }

        Node rhs = nodes.pop();
        Node middle = nodes.pop();
        Node lhs = nodes.pop();
        Node node = nf.buildOperatorNode(op2, new Node[]{lhs,middle,rhs});
        nodes.push(node);
    }
    else {
        throw new ParseException(MessageFormat.format(JepMessages.getString("configurableparser.ShuntingYard.InvalidOperatorOnStack"),op.getSymbol())); //$NON-NLS-1$
    }
}

只有三目运算符的右侧应该被遇到。它下方的运算符应该是相应的左手操作符。（任何优先级较低的运算符都已经被弹出，唯一具有更高优先级的运算符是赋值运算符，在三目运算符内不会发生）。

左右手操作符现在都已弹出。我正在构建一棵树，最后产生的三个节点被用新的三目运算符节点替换。

- Salix alba

---

非常感谢！我成功地将我的 OperatorChain 类适配成支持自定义三元运算符。唯一的区别是它将没有前置 ? 的 : 视为右结合，尽管这是有意的。 - Clashsoft

Answer 2

以下内容不完全符合OP的要求，但有另一个实用的解决方案，可能对遇到类似问题的人有所帮助...

我有一个相当标准的调车场算法，支持前缀/2元中缀表达式，并需要它额外处理仅有的一个三目运算符?:（可能是唯一的...;-)）我也不在乎?:运算符之间的结合性或优先级，因为像a？b：c？d：e这样的写法并不好看，我希望明确禁止。 （在这种情况下应使用括号：a？b：（c？d：e）或（a？b：c）？d：e。）

鉴于此，有一个简单的解决方案：

1. 创建一个新的（2元）中缀运算符“？”。 2. 创建一个新的（2元）中缀运算符“：”，其优先级低于“？”优先级。

双重优先级都应该低于+/-/*等，以便将a > 1 ? x + 4 : y + 5解析为(a > 1) ? (x + 4) : (y + 5)。

现在，对于每个c ? a : b，您将得到一个类似于此类元素的解析树：

执行一个后处理步骤，将每个具有左子节点为?的类型为:的元素替换为另一个自定义节点?:(c, a, b)。

这就是了！

当且仅当代码中存在没有正确括号的嵌套三元操作或者存在对 ? 或 : 运算符的语法误用时，才会得到一棵包含 ? 或 : 节点的树。

在这种情况下，请打印错误消息。

- Duke