Мы можем разбить его на две части. Существует одно правило для выражений в квадратных скобках и другое для умножений.
В отличие от статьи в Википедии, которая преднамеренно упрощена для пояснения, я хотел бы привести более подробный пример, например Parsing Expressions by Recursive Descent, который касается выражений в квадратных скобках.
Это код, который я использую для своего парсера, который может работать с неявным умножением. У меня есть многобуквенные имена переменных и используйте пробел для разделения разных переменных, чтобы вы могли иметь «2 pi r».
protected void expression() throws ParseException {
prefixSuffix();
Token t = it.peekNext();
while(t!=null) {
if(t.isBinary()) {
pushOp(t);
it.consume();
prefixSuffix();
}
else if(t.isImplicitMulRhs()) {
pushOp(implicitMul);
prefixSuffix();
}
else
break;
t=it.peekNext();
}
while(!sentinel.equals(ops.peek())) {
popOp();
}
}
Для этого требуется несколько других функций.
Я использовал отдельный шаг токенизации, который разбивает входные данные на дискретные маркеры. Класс Tokens
имеет ряд методов, в частности Token.isBinary()
, если оператор является двоичным оператором типа +, =, *, /. Другой метод: Token.isImplicitMulRhs()
проверяет, может ли токен отображаться с правой стороны неявного умножения, это будет верно для чисел, имен переменных и левых скобок.
Для входного потока используется Iterator<Token>
. it.peekNext()
смотрит на следующий токен и it.consume()
переходит к следующему токену на входе.
pushOp(Token)
толкает токен на стек оператора, а popOp
удаляет один и.У pushOp есть логика для обработки приоритета разных операторов. Выталкивание оператора, если они имеют более низкий приоритет
protected void pushOp(Token op)
{
while(compareOps(ops.peek(),op))
popOp();
ops.push(op);
}
Особо следует отметить implicitMul
искусственный маркер с тем же приоритетом, что и умножение, которое натягивается на стек оператора.
prefixSuffix()
обрабатывает выражения, которые могут быть числами и переменными с необязательным префиксом операторов суффиксов. Это распознает «2», «x», «-2», «x ++», удаляя маркеры с входа и добавляя их соответственно в стек вывода/оператора.
Мы можем думать об этой процедуре в BNF, как
<expression> ::=
<prefixSuffix> (<binaryOp> <prefixSuffix>)* // normal binary ops x+y
| <prefixSuffix> (<prefixSuffix>)* // implicit multiplication x y
Обработка скобок делается в prefixSuffix()
. Если это обнаружит левый кронштейн, он затем рекурсивно вызовет expression()
. Чтобы обнаружить подходящую правую скобку, в стек оператора помещается специальный сигнальный токен. Когда на входе встречается правая скобка, основной цикл прерывается, и все операторы в стеке оператора выскакивают до тех пор, пока не появится столбец, и управление вернется к prefixSuffix()
. Код для этого может быть как
void prefixSuffix() {
Token t = it.peekNext();
if(t.equals('(')) {
it.consume(); // advance the input
operatorStack.push(sentinel);
expression(); // parse until ')' encountered
t = it.peekNext();
if(t.equals(')')) {
it.consume(); // advance the input
return;
} else throw Exception("Unmatched (");
}
// handle variable names, numbers etc
}