Что общего у калькулятора и компилятора

Цель статьи - вводный разбор логики работы лексического и синтаксического анализаторов (являющихся ключевыми механизмами трансляторов языков, в частности, компиляторов) на примере более простой задачи обработки математических выражений. Эти две задачи - понимание компилятором высокоуровневого кода и математические операции - имеют достаточно общего, чтобы написание калькулятора дало начальные представления о работе преобразования кода в низкоуровневые конструкции.

Финальный код по статье: https://gist.github.com/nilptrr/e0d4e4bd63639a41a9f3fc028f918e4e

Постановка задачи и определение требований

Напишем программу, принимающую на вход произвольную строку математического выражения и возвращающую результат.

Пример, где слева - математическое выражение, а справа - результат:

+100.1 -> 100.1

-0 -> 0

-7 / 34.2 -> -0.205

-6 * 2 -> -12.00

1. / 1. -> 2

2 * (1 + 2) -> 6

5 + - 4 -> 1

*1 + 7 -> ошибка

4 / 3 + -> ошибка

Литерал - это набор символов, представляющий конкретное значение. Например, числовой литерал `1`.

Формализуем требования:

1. Разрешенные форматы числовых литералов:
1. Целые операнды: `1, 2, 3, ...`
2. Дробные операнды: `1.1, 2.5, ...`
3. Унарные операторы: `-1`, допустим ввод `- 1` (через пробел)
4. Бинарные операторы: `+`, `-`, `*`, `/`
2. Поддержка приоритета математических операций: `2 * (1 + 2) -> 6`
3. Корректная обработка деления на ноль.
4. Формат вывода:
1. Десятичная запись
2. С завершающим нулем для дробных чисел: `1.0`
3. Количество значащих цифр после запятой: до 3 включительно, незначащие нули должны быть обрезаны
4. Округление математическое: 1.1235 -> 1.124
5. Ошибка обработки:
1. Ошибка, если бинарный оператор не имеет левого или правого операнда: `4 / 3 + -> ошибка`

Теперь, когда требования ясны, можно приступить к проектированию и декомпозиции задачи.

Размышление над задачей

Исходя из требований, мы должны принимать на вход выражение, содержащее отрицательные числа, скобки, а также соблюдать порядок операций. Например, в выражении `2 + 3 * 4` ответом должно быть 14, а не 20.

Когда мы вводим это выражение в калькулятор, программа принимает и разбирает по своим правилам переданный набор символов: 2, +, 3, *, 4 и пробелы между ними.

Для задачи разбора ввода существует два распространенных решения - алгоритм рекурсивного спуска, широко применяемый в компиляторах, и алгоритм сортировочной станции (за авторством Эдсгера Дейкстры). Для решения задачи подходят оба, но в рамках статьи мы рассмотрим только первый.

Напомню, механизм трансляции состоит из стадий лексического анализа, синтаксического анализа, семантического анализа, оптимизации (промежуточный этап) и генерации машинного кода (называемый также этапом синтеза).

Из перечисленных этапов нас интересуют первые два, а также произведение вычисления математического выражения. Семантический анализ, оптимизация и генерация машинного кода в статье не рассматриваются.

Остановимся на первом этапе подробнее.

Лексический анализ - это чтение потока символов (лексем) и построение из них токенов вида `<имя токена: значение атрибута>`. Например, из потока лексем: `1`, '.`, '5` можно построить токен с именем `1.5` и произвольно заданным значением `NUM` для обозначения, что этот конкретный токен - число.

Какие типы лексем и токенов можно выделить, когда идет речь о математических операциях?

- Лексемой может быть цифра, десятичный разделитель числа, оператор, скобки, пустая строка.

- Что касается токенов, то для решения задачи достаточно двух - операндов (уже обозначенный `NUM`) и операторов (унарный минус и другие поддерживаемые математические операции. Значением может быть `OP`, но в целом его задавать не обязательно (в дальнейшем станет ясно, почему)).

Лексический анализатор

Попробуем реализовать простейший лексический анализатор, принимающий на вход поток лексем и возвращающий имя токена и значение атрибута.

Алгоритм следующий:

• Функция lexer принимает поток лексем и преобразует ее в очередь (поскольку по алгоритму необходимо извлекать и возвращать символы в структуру, которую читаем последовательно).
• Читая очередь, lexer получает лексему. lexer определяет тип лексемы.
• Если тип лексемы - цифра, то необходимо научить анализатор "предсказывать" дальнейшую лексему, обрабатывая 2 сценария:
• это целое число, состоящее из одной или более цифр: `12`. В этом случае читаем следующую лексему, и, если она является цифрой, читаем в цикле до конца выражения, помещая цифры в массив.
• это дробное число, состоящее из цифры, десятичного разделителя и одной или более цифр в дробной части. В этом случае читаем следующую лексему.
• Если это десятичный разделитель `.`, читаем еще одну лексему. На этом шаге мы обрабатываем дробную часть числа.
• Если очередь пуста, выходим из цикла. В этом случае лексема вида `2.` преобразуется в токен `2.0`.
• Иначе читаем следующую лексему до тех пор, пока тип лексемы - цифра.
• Сформировав число, создаем токен, указывая его тип (атрибут `kind`). Для чисел тип токена - `NUM` (number), а значением является число. Добавляем к списку токенов.
• Если тип лексемы - это оператор или скобки:
• Создаем токен, указывая символ в качестве типа (`kind`) токена. Для описания токенов, не являющихся числом, типа `kind` достаточно. `value` по умолчанию можно задавать как `0`, но его мы использовать не будем.
• Если тип лексемы - пустая строка, то игнорируем символ.
• Если символ - не цифра, десятичный разделитель, оператор, скобки, пустая строка, поднимаем ValueError (обработка ошибок).
• Возвращаем очередь токенов.

Напишем класс `Token`, имеющий атрибуты `kind` (имя токена) и `value` (значение атрибута).

В соответствии с алгоритмом необходима очередь, поскольку требуется извлекать и возвращать символы (лексемы) в структуру, которую читаем последовательно. Напишем сам анализатор:

Запустим:

Вывод:

Теперь у нас есть очередь токенов и мы можем переходить ко второму этапу - синтаксическому анализу.

Синтаксический анализатор

Для дальнейшего чтения важно понять, что на этом уровне мы больше не мыслим символами, избавились от проблемы различения математических операций от самих чисел, а также умеем распознавать дроби. Теперь у нас есть два вида токенов: числа и математические операции.

Однако проблема математической корректности ввода все еще присутствует - мы по-прежнему не умеем обрабатывать порядок операций, и, например, следующие два выражения текущей логикой не обработать:

2 * 3 + 1 - как обрабатывать приоритет операций?

(2 + 1 - как обрабатывать не закрытую скобку?

Математические выражения (как и синтаксис языков программирования) следует определенным правилам. Вернемся к правилам, которые мы определили в требованиях:

- поддержка стандартного набора операций: сложение, вычитание, умножение, деление

- обработка отрицательных чисел

- учет скобок

- соблюдение порядка вычислений

Эти правила называются грамматиками, и интересующие нас правила обработки описываются следующим образом:

expr: term | expr "+" term | expr "-" term

term: factor | term "*" factor | term "/" factor

factor: NUM | "-" NUM | "(" expr ")"

Для не программистов: символ `|` означает логическое ИЛИ.

Здесь представлены три записи. Каждая запись - это правило продукции, состоящее из нетерминала в заголовке (левой части) и последовательностью терминалов либо нетерминалов в теле (правой части).

- Терминал - элементарный и однозначный символ, определенный грамматикой языка. Например, число или знак `+` являются терминалами.

- Нетерминал - это абстрактная последовательность терминалов и нетерминалов, определенных правилом продукции.

- Продукция - это правило грамматики, описывающее, как нетерминал может быть заменен на последовательность терминалов и нетерминалов.

Рассмотрим пример "раскрытия" нетерминала:

expr -> expr "+" NUM

Здесь `expr` - это выражение, которое состоит из выражения `expr`, плюса и NUM.

Таким образом, этим правилом можно описать следующее выражение: `1 * 2 + 3`, где `1 * 2` - expr, `+` - токен, означающий `+` (помним, что теперь мы оперируем только токенами) и `3` - токен c `kind=NUM` и `value=3`.

Таким образом, связывая понятие токена с грамматиками, терминал - всегда токен, а нетерминал - последовательность токенов.

(Ключевые слова для углубления в теорию: форма Бэкуса-Наура, контекстно-свободные грамматики, иерархия Хомского)

Для реализации потребуется еще две сущности - `TokenStream` и `Parser`.

Класс `TokenStream` - управляет потоком токенов типа `Token`. Имеет методы `peek` (просматривает токен без его извлечения) и `next` (извлекает токен, если есть, иначе - выбрасываем исключение).

Вторая сущность - класс `Parser`, разбирающий токены и на ходу вычисляющий результат выражения.

Прикладная реализация этой грамматики - метод рекурсивного спуска (Recursive descent parser). Следуя описанному выше правилу разбора и определенными сущностями, напишем алгоритм:

• Парсер читает грамматику, спускаясь с expr на нижний уровень продукции (левая часть выражения) до тех пор, пока не определит ее тип (т.е. `expr -> term -> factor`).
• Иначе, если тип не определен на уровне `factor`, токен ищется на уровне `term`. (Важно - поднимаемся на одно правило вверх и ищем на нем).
• Иначе - на уровне `expr`.

Пример: `1 + 2`.

• expr - это term, который factor, который является `NUM` (число).
• За операндом всегда следует оператор, поэтому на уровне term получаем следующий токен и сохраняем его в переменную op. Определяем ее тип на уровне term. `+` != `*` и `+` != `/`, поэтому возвращаем токен на уровень `expr`.
• Проверяем тип текущего токена на соответствие `+` или `-`, **не извлекая его**. Если соответствует, извлекаем токен и суммируем левую часть выражения (число `1`) с результатом вызова `term` (`term` аналогично является `factor`, который является `NUM = 2`).
• Возвращаем левую часть выражения, которая является результатом вычисления.

Реализация парсера:

Финальное использование: