使用調車場算法解析三元運算符

Question

關於上下文，請首先閱讀this question about Ternary Operators。

我正在構建自己的編程語言，允許您定義自定義運算符。因爲我希望它儘可能少的編譯器的內置插件越好，它應該允許自定義的三元運營商的定義，最好的形式

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

我需要如何修改這個算法才能使用三元運算符（包括自定義運算符）？

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

對付tenary運營商的邏輯發生在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$ 
    } 
} 

只有三元運算符的右側應該會遇到。正下方的操作員應該是相應的左手操作員。 （具有較低優先級的任何運算符將被彈出，唯一具有較高優先級的運算符是不能在三元運算符內出現的賦值運算符）。

左手和右手操作員現在都彈出。我正在構建一棵樹，並且生成的最後三個節點被刪除，並構建了一個新的三元運算符節點。