Üçlü Operatör Algoritması ile Ayrışan Üçlü Operatör

Question

Bağlam için, önce this question about Ternary Operators'u okuyun.

Özel işleçleri tanımlamanıza olanak tanıyan kendi programlama dilimi yapıyorum. Bunun mümkün olduğunca az derleyici olarak inşa eklentileri istiyorum olduğundan,

infix operator ? : { precedence 120 } 

Benim (elle yazılmış) İfade Ayrıştırıcı içine yuvalanmış üçlü operatörler dönecek tercihen formda, özel üçlü operatörlerin tanımını izin vermelidir operatörler tarafından ayrılan işlenenlerin listesi.

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

OperatorChain sınıf artık kapsamında operatör tanımları operatörleri yukarı bakar ve aşağıda gösterilmiştir şant yarda algoritması, değiştirilmiş bir versiyonunu kullanarak ikili AST düğümler dönüştüren:

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

Özel algoritmalar da dahil olmak üzere üçlü operatörlerle çalışmak için bu algoritmayı nasıl değiştirmem gerekir?

Answer 1

Üçlü operatörleri işleyebilen bir Java çözümleyicisi geliştirdim. Bunun kalbi expression yöntemidir. Giriş, bir sonraki belirteci görüntülemek için it.peekNext() yöntemiyle bir it yineleyicisinde bulunur ve it.consume() bir sonraki belirtecin hareket ettirilmesi. ++x gibi olası önek ve sonek işleçleri ile sabitleri ve değişkenleri okumak için prefixSuffix()'u çağırır.

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

Böylece jeton ya karşılaşıldığında istifin üzerine itmek pushOp yöntemlerini çağırır. Her belirteci, aynı zamanda pushOp'a ayrıştırılan ilişkili bir işleç vardır.

pushOp poping, yığının en yeni operatörünü karşılaştırmak gerekirse

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

tenary operatörleri ile başa çıkmak için mantık compareOps meydana:

/** 
* 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; 
} 

her iki operatörün doğruysa Üçlü bir operatörün el sonra compareOps döndürür gerçek bir operatör atılır. Aksi takdirde, her ikisi de soldaki üçlü işleçler veya biri sol, diğeri ise compareOps yanlış döndürür ve hiçbir operatör atılmaz.

elleçleme diğer bit popOp yöntem olur: üçlü operatörün

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

Sadece sağ taraftaki karşılaştı edilmelidir. Doğrudan altında bulunan operatör ilgili sol el operatörü olmalıdır. (Daha düşük önceliğe sahip herhangi bir operatör daha önce atılmış olacaktır, daha yüksek önceliğe sahip tek operatörler, üçlü operatörde gerçekleşmeyen atama operatörleridir).

Artık hem sol hem de sağ el operatörleri atılıyor. Bir ağaç yapıyorum ve üretilen son üç düğüm, inşa edilen yeni bir üçlü operatör düğümü ile kaldırıldı.