пишем калькулятор, понимаем компилятор

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

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

class Token:
    '''
    Supported kinds of tokens:
        - digits: 0-9
        - unary operators: -
        - binary operators: +, -, *, /,
        - parenthesis: (, )
        - floating point: .
    '''
    def __init__(self, kind, value=None):
        self.kind: str = kind           # kind of token
        self.value: float = value       # only for digits: a value

    def __repr__(self) -> str:
        if self.kind == 'NUM':
            return str(self.value)      # only for digits
        return str(self.kind)

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

from collections import deque


def lexer(lexeme_stream: str, Token: Token):
    '''
    The lexical analyzer translates lexemes into tokens.
    '''
    tokens = deque()
    lexeme_stream = deque(lexeme_stream)

    while lexeme_stream:
        c = lexeme_stream.popleft()

        if c in '0123456789':
            digits = [c]

            while lexeme_stream and lexeme_stream[0] in '0123456789':
                digits.append(lexeme_stream.popleft())

            # float number's case
            if lexeme_stream and lexeme_stream[0] == '.':
                digits.append(lexeme_stream.popleft())

                if lexeme_stream and lexeme_stream[0] in '0123456789':
                    while lexeme_stream and lexeme_stream[0] in '0123456789':
                        digits.append(lexeme_stream.popleft())
                else:
                    digits.append('0')

            t = Token('NUM', float(''.join(digits)))
            tokens.append(t)
            continue

        elif c in '+-*/()':
            t = Token(c)
            tokens.append(t)
            continue

        elif c == ' ':
            continue

        else:
            raise ValueError('Bad token.')

    return tokens

Запустим:

lexemes = input('input: ')
tokens = lexer(lexemes, Token)

print('=== Output ===')
print('Kind \t Value')
for token in tokens:
    print(f'{token.kind} \t {token.value}')

Вывод:

input: 1.1 + 2 / 3

=== Output ===
Kind  Value
NUM   1.1
+     None
NUM   2.0
/     None
NUM   3.0

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

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

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

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

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 (извлекает токен, если есть, иначе - выбрасываем исключение).

class TokenStream:
    def __init__(self, tokens) -> None:
        self.tokens = tokens

    def peek(self):
        try:
            return self.tokens[0]
        except IndexError:
            return False

    def next(self):
        try:
            return self.tokens.popleft()
        except IndexError:
            return None

Вторая сущность - класс 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).
Возвращаем левую часть выражения, которая является результатом вычисления.

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

class Parser:
    '''
    Grammar:
    expr: term | expr "+" term | expr "-" term
    term: factor | term "*" factor | term "/" factor
    factor: NUM | "-" NUM | "(" expr ")"
    '''
    def __init__(self, ts: TokenStream) -> None:
        self.ts = ts

    def parse(self):
        result = self._expr()
        return result

    def _expr(self):
        left = self._term()

        while self.ts.peek() and self.ts.peek().kind in '+-':
            op = self.ts.next()

            if op.kind == '+':
                left += self._term()

            elif op.kind == '-':
                left -= self._term()

            else:
                break

        return left

    def _term(self):
        left = self._factor()

        while self.ts.peek() and self.ts.peek().kind in '*/':
            op = self.ts.next()

            if op.kind == '*':
                left *= self._factor()

            elif op.kind == '/':
                divisible = self._factor()
                if divisible == 0:
                    raise ZeroDivisionError

                left = float(left) / float(divisible)

            else:
                break

        return left

    def _factor(self):
        left = self.ts.next()

        if left is None:
            return None

        elif left.kind == 'NUM':
            return left.value

        elif left.kind == '-':

            if self.ts.peek():
                t = self.ts.next()
                return -t.value

        elif left.kind == '+':
            if self.ts.peek():
                t = self.ts.next()
                return t.value

        elif left.kind == '(':
            left = self._expr()

            if self.ts.peek():
                t = self.ts.next()

                if t.kind != ')':
                    raise ValueError(') required.')

            return left

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

def calculate(expr: str):
    tokens = lexer(expr, Token)
    ts = TokenStream(tokens)
    parser = Parser(ts)

    try:
        expr_result = parser.parse()

    except Exception:
        raise

    else:
        return round(expr_result, 3)


expr = input()
print(calculate(expr))