3. Синтаксический анализ
Этот этап иногда называется просто “разбор”. Для его проведения, нам потребуется более подробное формальное описание выражения с учётом приоритетов операций. Скажем, операции в скобках всегда выполняются в первую очередь, умножение и деление — во вторую, сложение и вычитание — в третью. На основе этого описания можно составить формальную грамматику выражения, выглядящую примерно так:
- ВЫРАЖЕНИЕ ::= СЛАГАЕМОЕ +|- СЛАГАЕМОЕ +|- … +|- СЛАГАЕМОЕ
- СЛАГАЕМОЕ ::= МНОЖИТЕЛЬ *|/ МНОЖИТЕЛЬ *|/ … *|/ МНОЖИТЕЛЬ
- МНОЖИТЕЛЬ ::= (ВЫРАЖЕНИЕ) | -ВЫРАЖЕНИЕ | КОНСТАНТА | ПЕРЕМЕННАЯ
То есть, выражение может включать в себя любое (в том числе одно) число слагаемых, разделённых операторами “плюс” и “минус”. Слагаемое, в свою очередь, может включать в себя любое (в том числе одно) число множителей, разделённых операторами “умножить” и “разделить”. Наконец, множитель — это выражение в скобках, или с минусом впереди, или константа, или переменная. К примеру, в выражении 2 + 3 * x / (1 - x) имеется два слагаемых — 2 и 3 * x / (1 - x). Слагаемое 2 состоит из одного множителя, который, в свою очередь, является слагаемым. Второе слагаемое состоит из трёх множителей — 3 (константа), x (переменная), (1 - x). Последний из множителей, в свою очередь, является выражением 1 - x в скобках, состоящим из двух слагаемых.
Знак ::= в этом определении приближённо означает “состоит из”, то есть, мы описываем одно понятие через другие. А сама по себе формальная грамматика позволяет определить, является ли заданная строка выражением, а также разобраться, из каких частей это выражение состоит. Например:
class Parser(private val groups: List<String>) {
private var pos = 0
fun parse(): Expression {
val result = parseExpression()
if (pos < groups.size) {
throw IllegalStateException("Unexpected expression remainder: ${groups.subList(pos, groups.size)}")
}
return result
}
private fun parseExpression(): Expression {
var left = parseItem()
while (pos < groups.size) {
val op = operationMap[groups[pos]]
when (op) {
PLUS, MINUS -> {
pos++
val right = parseItem()
left = Expression.Binary(left, op, right)
}
else -> return left
}
}
return left
}
private val operationMap = mapOf("+" to PLUS, "-" to MINUS, "*" to TIMES, "/" to DIV)
// ...
}
Данный класс Parser (разборщик, или просто парсер) имеет свойство groups — список атомарных частей строки, полученный при лексическом анализе, а также изменяемое свойство pos — оно указывает, до какой из частей мы дошли в процессе разбора. Его функция parse осуществляет разбор всего выражения и проверяет, что была разобрана вся найденная строка и не осталось ничего в хвосте.
Функция parseExpression соответствует определению выражения из грамматики. В соответствии с определением она разбирает первое слагаемое parseItem, затем, если найден плюс или минус — второе, и составляет из них Expression.Binary. При наличии следующего плюса или минуса процедура повторяется. Для преобразования обозначения операции в объект перечисления Operation используется отображение operationMap.
Результат функции parseExpression, как и других функций разбора — Expression, то есть любая из описанных нами выше разновидностей алгебраического типа Expression. Обратите внимание, что для выражения с тремя и более слагаемыми, например, 2 + x - 1, мы получим в итоге следующую структуру: Binary(Binary(2, +, x), -, 1). То есть первым аргументом внешнего бинарного выражения 2 + x - 1, в свою очередь, является бинарное выражение 2 + x.
Аналогичным образом устроена функция parseItem. Она соответствует определению слагаемого, для разбора множителей использует parseFactor, и в качестве разделителей ищет знаки умножения и деления:
class Parser(val groups: List<String>) {
var pos = 0
// ...
private fun parseItem(): Expression {
var left = parseFactor()
while (pos < groups.size) {
val op = operationMap[groups[pos]]
when (op) {
TIMES, DIV -> {
pos++
val right = parseFactor()
left = Expression.Binary(left, op, right)
}
else -> return left
}
}
return left
}
}
Наконец, разбор множителя parseFactor анализирует один из четырёх вариантов: выражение в скобках, выражение с минусом, константа, переменная.
class Parser(val groups: List<String>) {
var pos = 0
// ...
private fun parseFactor(): Expression =
if (pos >= groups.size) throw IllegalStateException("Unexpected expression end")
else {
val group = groups[pos++]
when (group) {
"x" -> Expression.Variable
"-" -> Expression.Negate(parseFactor())
"(" -> {
val arg = parseExpression()
val next = groups[pos++]
if (next == ")") arg
else throw IllegalStateException(") expected instead of $next")
}
else -> Expression.Constant(group.toInt())
}
}
}
Обратите внимание, что в процессе анализа выражения в скобках мы повторно вызываем parseExpression, то есть, налицо рекурсия. Глубина рекурсии зависит от количества вложенных скобок в выражении.
В результате действия подобного парсера упомянутое выше выражение 2 + 3 * x / (1 - x) превратится в структуру Binary(2, +, Binary(Binary(3, *, x), /, Binary(1, - x))).
4. Объединяем всё вместе
Наконец, рассмотрим функцию, решающую исходную задачу. Пусть во входном файле содержится строчка, содержащая описание функции от x. Необходимо по имеющемуся списку значений x (например, 1, 2 и -1) рассчитать значения данной функции и вернуть их в виде ассоциативного массива.
fun parseExpr(inputName: String, values: List<Int>): Map<Int, Int> {
val expr = File(inputName).readLines().firstOrNull()?.parseExpr() ?: throw IllegalArgumentException()
val result = mutableMapOf<Int, Int>()
for (value in values) {
result[value] = expr.calculate(value)
}
return result
}
Данная функция читает первую строку файла inputName и разбирает её с помощью String.parseExpr(). Затем для каждого из значений из списка values вызывается функция Expression.calculate и результат кладётся в ассоциативный массив result. Таким образом, задача решена.
Как создать приложение для Android на языке Kotlin
