4

有关上下文，请先阅读有关三元运算符的这个问题。

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

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);

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

4

1 回答 1

2

I've implemented a mathematical parser in java which can handle ternary operators. The heart of this is the expression method. The input is contained in an iterator it with a it.peekNext() method to view the next token and it.consume() move to the next token. It calls the prefixSuffix() to read constants and variables with possible prefix and suffix operators eg ++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();
    }
}

So when either of the tokens is encountered it calls the pushOp methods to push them on the stack. Each token has an associated operator which is also parsed to pushOp.

pushOp compare the new operator with the top of the stack, poping if necessary

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

The logic for dealing with tenary operators happen in 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;
}

If both operators are the right hand of a ternary operator then compareOps returns true one operator will be popped. Otherwise if both are the left hand ternary operators or one is a left and one is a right then compareOps returns false and no operators are popped.

The other bit of handling happens in the popOp method:

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$
    }
}

Only the right hand side of the ternary operator should be encountered. The operator directly below it should be the corresponding left hand operator. (Any operator with a lower precedence will have already been popped, the only operators with higher precedence are assignment operators which can't occur inside a ternary operator).

Both the left and right hands operators are now popped. I'm constructing a tree and the last three nodes produced are removed with a new ternary operator node constructed.

于 2016-04-01T00:41:24.080 回答