Эта глава развивает содержимое шестого урока, отвечая на вопрос "А что делать, если простого разбиения строки на части недостаточно?". Одной из подобных ситуаций является разбор арифметических выражений. Для этого и других похожих случаев программисты придумали парсеры — специальные функции или объекты, выполняющие разбор сложных строк. Для написания парсеров используется теория формальных языков, которой мы (вкратце) коснёмся в этой главе.
Рассмотрим пример.
Пусть во входном файле содержится строчка, содержащая описание функции от x, например:
3*x*x - (2 / x) + 7 -xНеобходимо по имеющемуся списку значений x (например, 1, 2 и -1)
рассчитать значения данной функции и вернуть их в виде ассоциативного массива
(например, 1 → 7, 2 → 16, -1 → 13).
Предполагается, что функция является целочисленной, и в ней могут присутствовать четыре арифметических действия и круглые скобки.
Как решать подобную задачу? Поэтапно.
Лексический анализ — первый этап решения. Его цель — разбиение исходного выражения на атомарные элементы, которыми в приведённом примере являются:
3, *, x, *, x, -, (, 2, /, x, ), +, 7, -, xОбратите внимание, что в процессе лексического анализа из выражения выбрасываются пробелы.
Один из способов лексического анализа — применение регулярных выражений.
fun String.parseExpr(): Expression {
val matchResults = Regex("""x|\+|-|\*|/|\(|\)|\d+?| +?|.+?""").findAll(this)
val groups = matchResults.map { it.value }.filter { it.isNotBlank() }.toList()
return Parser(groups).parse()
}Заданное в этой функции регулярное выражение задаёт описание атомарного элемента.
Это может быть x, знаки четырёх арифметических действий, знаки скобок,
пробелы, и все прочие символы.
Лямбда { it.isNotBlank() } убирает из имеющейся последовательности пробелы,
оставляя всё остальное.
После этого происходит переход к следующему этапу — собственно разбору.
Но перед этим поговорим о том, а что, собственно, мы хотим получить в результате разбора.
Зададимся вопросом: как представить арифметическое выражение с помощью структур данных, имеющихся в Котлине? Перед ответом на этот вопрос стоит ответить на другой: а что такое (формально) арифметическое выражение в нашей задаче? В теории формальных языков ответ может выглядеть так:
-
это
x, -
или же, это целая константа,
-
или же, это операция (сложение / вычитание / умножение / деление) над двумя другими выражениями
-
или, наконец, это операция "минус выражение" над другим выражением
Обратите внимание, что определение рекурсивно — понятие выражения использует в процессе определения себя же. Это довольно частый случай для подобных формальных описаний. Подобная рекурсивная структура с вариантами в Котлине может быть описана так называемым алгебраическим или запечатанным (sealed) классом.
sealed class Expression {
object Variable : Expression()
class Constant(val value: Int) : Expression()
enum class Operation {
PLUS,
MINUS,
TIMES,
DIV;
}
class Binary(
val left: Expression,
val op: Operation,
val right: Expression
) : Expression()
class Negate(val arg: Expression) : Expression()
}Алгебраический класс используется не сам по себе, а в виде его разновидностей, причём по правилам Котлина, для алгебраического класса эти разновидности должны быть описаны внутри определения самого класса (для версии 1.1 и выше — внутри того же файла).
Для описания разновидностей Expression используется уже знакомый синтаксис class Something(…) : Expression().
Разновидности алгебраического класса содержат дополнительную информацию по сравнению с ним самим:
-
целая константа
Constantсодержит своё значениеvalue -
инвертированное выражение
Negateсодержит свой аргумент (например, для-xаргумент будет равенx) -
выражение с двумя аргументами (бинарное)
Binaryсодержит два своих аргумента и выполняемую операцию
Обратите внимание на enum class Operation.
Это не разновидность выражения (нет : Expression()),
а просто дополнительный класс для описания операций с двумя аргументами.
Слово enum означает перечисление в том смысле, что существует ограниченное (в данном случае — 4)
количество операций — сложение, умножение, вычитание, деление.
Все операции перечисляются через запятую, в конце (необязательно) ставится точка с запятой.
Последняя разновидность выражения object Variable : Expression().
В отличие от прочих разновидностей, эта является не классом, а объектом.
В Котлине объект отличается от класса тем,
что для данного типа существует ровно один объект данного типа — в данном случае это переменная x.
У объекта нельзя вызывать конструкторы, а обращаются к нему просто по имени: в данном случае Variable.
Если бы нас интересовали выражения с несколькими переменными,
Variable тоже превратился бы в класс со свойством name: имя конкретной переменной.
Подобное описание выражения позволяет с лёгкостью рассчитать его значение при заданном x:
fun Expression.calculate(x: Int): Int = when (this) {
Variable -> x
is Constant -> value
is Binary -> when (op) {
PLUS -> left.calculate(x) + right.calculate(x)
MINUS -> left.calculate(x) - right.calculate(x)
TIMES -> left.calculate(x) * right.calculate(x)
DIV -> left.calculate(x) / right.calculate(x)
}
is Negate -> -arg.calculate(x)
}В данном when мы перебираем все возможные варианты выражения-получателя:
-
значение переменной равно заданному
x: Int -
значение константы равно её свойству
value -
значение
Negateравно минус значению её выражения-аргумента -
значение
Binaryрассчитывается аналогично с учётом конкретной операции
Этот этап иногда называется просто "разбор". Для его проведения, нам потребуется более подробное формальное описание выражения с учётом приоритетов операций. Скажем, операции в скобках всегда выполняются в первую очередь, умножение и деление — во вторую, сложение и вычитание — в третью. На основе этого описания можно составить формальную грамматику выражения, выглядящую примерно так:
-
ВЫРАЖЕНИЕ ::= СЛАГАЕМОЕ +|- СЛАГАЕМОЕ +|- … +|- СЛАГАЕМОЕ
-
СЛАГАЕМОЕ ::= МНОЖИТЕЛЬ *|/ МНОЖИТЕЛЬ *|/ … *|/ МНОЖИТЕЛЬ
-
МНОЖИТЕЛЬ ::= (ВЫРАЖЕНИЕ) | -ВЫРАЖЕНИЕ | КОНСТАНТА | ПЕРЕМЕННАЯ
То есть, выражение может включать в себя любое (в том числе одно) число слагаемых,
разделённых операторами "плюс" и "минус".
Слагаемое, в свою очередь, может включать в себя любое (в том числе одно) число множителей,
разделённых операторами "умножить" и "разделить".
Наконец, множитель — это выражение в скобках, или с минусом впереди, или константа, или переменная.
К примеру, в выражении 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))).
Наконец, рассмотрим функцию, решающую исходную задачу.
Пусть во входном файле содержится строчка, содержащая описание функции от 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. Таким образом, задача решена.