Analyse syntaxique de l'opérateur ternaire avec l'algorithme de shunt Yard

Question

Pour le contexte, veuillez d'abord lire this question about Ternary Operators.

Je construis mon propre langage de programmation qui vous permet de définir des opérateurs personnalisés. Parce que je veux qu'il y ait aussi peu compilateur ENCASTRÉS possible, il devrait permettre la définition des opérateurs ternaires personnalisés, de préférence sous la forme

infix operator ? : { precedence 120 } 

Mon (écrit à la main) Expression Parser transformera les opérateurs ternaires imbriqués en une liste d'opérandes séparés par des opérateurs.

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

La OperatorChain classe regarde maintenant les opérateurs de définitions de l'opérateur portée et convertit la liste en noeuds AST binaires en utilisant une version modifiée de l'algorithme de cour de triage, qui est indiqué ci-dessous:

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

Comment aurais-je besoin de modifier cet algorithme pour travailler avec des opérateurs ternaires, y compris ceux personnalisés?

Answer 1

J'ai implémenté un analyseur mathématique en Java qui peut gérer les opérateurs ternaires. Le cœur de ceci est la méthode expression. L'entrée est contenue dans un itérateur it avec une méthode it.peekNext() pour afficher le jeton suivant et it.consume() pour passer au jeton suivant. Il appelle le prefixSuffix() pour lire les constantes et les variables avec des opérateurs de préfixe et de suffixe possibles, par exemple ++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(); 
    } 
} 

Ainsi, lorsque l'un des jetons est rencontré, il appelle les méthodes pushOp de les pousser sur la pile. Chaque jeton a un opérateur associé qui est également analysé sous pushOp.

pushOp comparer le nouvel opérateur avec le haut de la pile, POPING si nécessaire

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

La logique pour faire face aux opérateurs tenary se produire dans 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; 
} 

Si les deux opérateurs sont le droit la main d'un opérateur ternaire puis compareOps renvoie vrai un opérateur sera sauté. Sinon, si les deux sont les opérateurs ternaires de gauche ou si l'un est à gauche et l'autre à droite, alors compareOps renvoie false et aucun opérateur ne s'affiche.

L'autre peu de manipulation se produit dans la méthode 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$ 
    } 
} 

Seul le côté droit de l'opérateur ternaire doit être rencontré. L'opérateur directement en dessous devrait être l'opérateur de gauche correspondant. (Tout opérateur ayant une priorité inférieure aura déjà été déplacé, les seuls opérateurs ayant une priorité plus élevée sont des opérateurs d'affectation qui ne peuvent pas se produire à l'intérieur d'un opérateur ternaire).

Les opérateurs de gauche et de droite sont maintenant désactivés. Je construis un arbre et les trois derniers nœuds produits sont supprimés avec un nouveau nœud d'opérateur ternaire construit.