三元算子用调车场算法解析

Question

上下文，请先阅读。

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

的形式

infix operator ? : { precedence 120 }

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

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

OperatorChain class 现在从范围内的运算符定义中查找运算符，并使用调车场算法的修改版本将列表转换为二进制 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);

我需要如何修改此算法以使用三元运算符，包括自定义运算符？

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 returns true 将弹出一个运算符。否则，如果两者都是左手三元运算符，或者一个是左三元运算符，一个是右三元运算符，则 compareOps returns 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$
    }
}

应该只遇到三元运算符的右侧。它正下方的运算符应该是相应的左手运算符。（任何具有较低优先级的运算符都将被弹出，唯一具有较高优先级的运算符是赋值运算符，它不能出现在三元运算符中）。

左右手运算符现在都弹出了。我正在构建一棵树，最后生成的三个节点被移除，并构建了一个新的三元运算符节点。

三元算子用调车场算法解析

Ternary Operator Parsing with the Shunting Yard Algorithm

java

algorithm

ternary-operator

shunting-yard