Разбор троичного оператора с помощью алгоритма маневрового двора

Для контекста, пожалуйста, сначала прочитайте этот вопрос о троичных операторах.

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

infix operator ? : { precedence 120 }

Мой (написанный от руки) Expser 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);

Как мне нужно изменить этот алгоритм для работы с троичными операторами, включая пользовательские?

Источник

2 ответа

Решение

Я реализовал математический парсер в 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); 
}

Логика для работы с тенарными операторами происходит в 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$
    }
}

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

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

Источник

Следующее - это не совсем то, о чем просил ОП, но есть еще одно прагматичное решение, которое может помочь кому-то столкнуться...

У меня был довольно стандартный алгоритм маневровой станции с поддержкой префикса/2-операнд-инфикса, и мне нужно было, чтобы он дополнительно обрабатывал только один тернарный оператор (который, вероятно, единственный там, в любом случае... ;-)). Я также не заботился об ассоциативности или приоритете между?:операторы с момента написания чего-то вродеa ? b : c ? d : eпросто нехорошо, и я хотел, чтобы это было явно запрещено. (В этом случае следует использовать скобки:a ? b : (c ? d : e)или(a ? b : c) ? d : e.)

Учитывая это, есть простое решение:

  1. Создайте новый инфиксный оператор (с двумя операндами).
  2. Создайте новый инфиксный оператор (2 операнда) с более низким приоритетом, чем приоритет.

Оба приоритета должны быть ниже, чем у+/-/*и т. д. для разбораa > 1 ? x + 4 : y + 5как(a > 1) ? (x + 4) : (y + 5).

Теперь вы получите дерево синтаксического анализа с такими элементами для каждого изc ? a : b:

  1. Выполните шаг постобработки, заменив каждый элемент этого типа (узел с левым дочерним элементом) другим пользовательским узлом.?:(c, a, b).

Вот и все!

Вы получите дерево, содержащее или узлы тогда и только тогда, когда

  • в коде есть вложенные тернарные операции, которые не имеют правильных скобок или
  • есть некоторое синтаксическое неправильное использование?или:операторы.

В этом случае распечатайте сообщение об ошибке.

Источник
Другие вопросы по тегам