10. Основы Kotlin. Дополнительные главы

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

 
Додати коментар