Анализ тернарных операторов с алгоритмом шунтирующего двора

Question

Для контекста, пожалуйста, прочтите сначала this question about Ternary Operators.

Я создаю свой собственный язык программирования, который позволяет вам определять пользовательские операторы. Потому что я хочу, чтобы иметь несколько компилятор встроенные модулей, как это возможно, она должна позволить определение пользовательских трехкомпонентных операторов, предпочтительно в форме

infix operator ? : { precedence 120 } 

Мой (рукописный) Expression Parser будет превращать вложенные тройные операторы в список операндов, разделенных операторами.

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 возвращает истинный один оператор. В противном случае, если оба являются левыми тернарными операторами, либо один - левым, а один - правым, тогда 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$ 
    } 
} 

Только правая часть троичного оператора должны встречаться. Оператор непосредственно под ним должен быть соответствующим левым оператором. (Любой оператор с более низким приоритетом уже был выбит, единственными операторами с более высоким приоритетом являются операторы присваивания, которые не могут встречаться внутри тернарного оператора).

Операции с левой и правой стрелками теперь выведены. Я создаю дерево, и последние три произведенных узла удаляются с созданным новым тернарным узлом оператора.