Разбор и представление арифметических выражений

Эта глава развивает содержимое шестого урока, отвечая на вопрос «А что делать, если простого разбиения строки на части недостаточно?». Одной из подобных ситуаций является разбор арифметических выражений. Для этого и других похожих случаев программисты придумали парсеры — специальные функции или объекты, выполняющие разбор сложных строк. Для написания парсеров используется теория формальных языков, которой мы (вкратце) коснёмся в этой главе.

Рассмотрим пример. Пусть во входном файле содержится строчка, содержащая описание функции от x, например:

Необходимо по имеющемуся списку значений x (например, 1, 2 и -1) рассчитать значения данной функции и вернуть их в виде ассоциативного массива (например, 1 → 7, 2 → 16, -1 → 13).

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

Как решать подобную задачу? Поэтапно.

1. Лексический анализ

Лексический анализ — первый этап решения. Его цель — разбиение исходного выражения на атомарные элементы, которыми в приведённом примере являются:

Обратите внимание, что в процессе лексического анализа из выражения выбрасываются пробелы.

Один из способов лексического анализа — применение регулярных выражений.

Заданное в этой функции регулярное выражение задаёт описание атомарного элемента. Это может быть x, знаки четырёх арифметических действий, знаки скобок, пробелы, и все прочие символы. Лямбда { it.isNotBlank() }убирает из имеющейся последовательности пробелы, оставляя всё остальное. После этого происходит переход к следующему этапу — собственно разбору. Но перед этим поговорим о том, а что, собственно, мы хотим получить в результате разбора.

2. Представление выражений

Зададимся вопросом: как представить арифметическое выражение с помощью структур данных, имеющихся в Котлине? Перед ответом на этот вопрос стоит ответить на другой: а что такое (формально) арифметическое выражение в нашей задаче? В теории формальных языков ответ может выглядеть так:

  • это x,
  • или же, это целая константа,
  • или же, это операция (сложение / вычитание / умножение / деление) над двумя другими выражениями
  • или, наконец, это операция «минус выражение» над другим выражением

Обратите внимание, что определение рекурсивно — понятие выражения использует в процессе определения себя же. Это довольно частый случай для подобных формальных описаний. Подобная рекурсивная структура с вариантами в Котлине может быть описана так называемым алгебраическим или запечатанным (sealed) классом.

Алгебраический класс используется не сам по себе, а в виде его разновидностей, причём по правилам Котлина, для алгебраического класса эти разновидности должны быть описаны внутри определения самого класса (для версии 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:

В данном when мы перебираем все возможные варианты выражения-получателя:

  • значение переменной равно заданному x: Int
  • значение константы равно её свойству value
  • значение Negate равно минус значению её выражения-аргумента
  • значение Binary рассчитывается аналогично с учётом конкретной операции

3. Синтаксический анализ

Этот этап иногда называется просто «разбор». Для его проведения, нам потребуется более подробное формальное описание выражения с учётом приоритетов операций. Скажем, операции в скобках всегда выполняются в первую очередь, умножение и деление — во вторую, сложение и вычитание — в третью. На основе этого описания можно составить формальную грамматику выражения, выглядящую примерно так:

  • ВЫРАЖЕНИЕ ::= СЛАГАЕМОЕ +|- СЛАГАЕМОЕ +|- …​ +|- СЛАГАЕМОЕ
  • СЛАГАЕМОЕ ::= МНОЖИТЕЛЬ *|/ МНОЖИТЕЛЬ *|/ …​ *|/ МНОЖИТЕЛЬ
  • МНОЖИТЕЛЬ ::= (ВЫРАЖЕНИЕ) | -ВЫРАЖЕНИЕ | КОНСТАНТА | ПЕРЕМЕННАЯ

То есть, выражение может включать в себя любое (в том числе одно) число слагаемых, разделённых операторами «плюс» и «минус». Слагаемое, в свою очередь, может включать в себя любое (в том числе одно) число множителей, разделённых операторами «умножить» и «разделить». Наконец, множитель — это выражение в скобках, или с минусом впереди, или константа, или переменная. К примеру, в выражении 2 + 3 * x / (1 - x) имеется два слагаемых — 2 и 3 * x / (1 - x). Слагаемое 2 состоит из одного множителя, который, в свою очередь, является слагаемым. Второе слагаемое состоит из трёх множителей — 3 (константа), x (переменная), (1 - x). Последний из множителей, в свою очередь, является выражением 1 - x в скобках, состоящим из двух слагаемых.

Знак ::= в этом определении приближённо означает «состоит из», то есть, мы описываем одно понятие через другие. А сама по себе формальная грамматика позволяет определить, является ли заданная строка выражением, а также разобраться, из каких частей это выражение состоит. Например:

Данный класс 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, и в качестве разделителей ищет знаки умножения и деления:

Наконец, разбор множителя parseFactor анализирует один из четырёх вариантов: выражение в скобках, выражение с минусом, константа, переменная.

Обратите внимание, что в процессе анализа выражения в скобках мы повторно вызываем parseExpression, то есть, налицо рекурсия. Глубина рекурсии зависит от количества вложенных скобок в выражении.

В результате действия подобного парсера упомянутое выше выражение 2 + 3 * x / (1 - x) превратится в структуру Binary(2, +, Binary(Binary(3, *, x), /, Binary(1, - x))).

4. Объединяем всё вместе

Наконец, рассмотрим функцию, решающую исходную задачу. Пусть во входном файле содержится строчка, содержащая описание функции от x. Необходимо по имеющемуся списку значений x (например, 1, 2 и -1) рассчитать значения данной функции и вернуть их в виде ассоциативного массива.

Данная функция читает первую строку файла inputName и разбирает её с помощью String.parseExpr(). Затем для каждого из значений из списка values вызывается функция Expression.calculate и результат кладётся в ассоциативный массив result. Таким образом, задача решена.

Добавить комментарий