Как я писал калькулятор

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

Токенизация

Сперва введенное выражение нужно разобрать на отдельные части, удобные для парсера. Так, за токены можно считать отдельные знаки, вроде «+», «-«, «*», «/», «(«, «)», так и группы знаков, обозначающие как числа «123», так и имена «abc». Так в сумме, в текущей реализации токенайзера описано порядка 24-х типов токенов, 4 из которых служебные.

К примеру, выражение вида «y(x)=(10+x)/x» может быть разобрано на 12 токенов:

  • Имя — «y»
  • Открывающая скобка — «(«
  • Имя — «x»
  • Закрывающая скобка — «)»
  • Символ оператора присвоения — «=»
  • Открывающая скобка — «(«
  • Число — «10»
  • Символ оператора сложения — «+»
  • Имя — «x»
  • Закрывающая скобка — «)»
  • Символ оператора деления — «/»
  • Имя — «x»

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

Дерево операторов

После того, как выражение «y(x)=(10+x)/x» токенизировано, его можно разобрать на абстрактное синтаксическое дерево либо на дерево операторов. Реализация данного калькулятора составляет прямо дерево операторов.

  • Оператор присвоения
    • Оператор вызова функции — «y»
      • Оператор обращения к переменной — «x»
    • Оператор деления — «/»
      • Скобки
        • Оператор сложения — «+»
          • Число — «10»
          • Оператор обращения к переменной — «x»
      • Оператор обращения к переменной — «x»

Алгоритм самого парсера вышел достаточно сложный как для пересказа принципа его работы на естественном языке, так и для восприятия. Основной цикл алгоритма устроен следующим образом. На каждой итерации происходит считывание следующего токена из потока. Если токен число, открывающая скобка или имя, то из него происходит создание правого оператора. В том числе, если оператор сложный, состоящий из большого числа токенов, вроде скобок или вызова функции, то рекурсивно вызванные функции просто перемотают поток токенов. Если токен — арифметический оператор, то правый оператор становится левым, сам токен сохраняется. Если заполнены правый и левый оператор и токен оператора, то на их базе создается новый арифметический оператор, который становится правым оператором. На каждой итерации цикла парсер перематывает поток токенов, чтобы проверить, что следующий оператор не более приоритетный. Если следующий оператор более приоритетный, то процедура парсинга рекурсивно вызывается, чтобы получить дерево операторов с более приоритетным оператором.

Выполнение выражения

Полученное дерево операторов подлежит выполнению. Все операторы выполняются в рамках некоего контекста. В рамках контекста определяются список переменных и список функций. У пользователя есть возможность определить функцию самостоятельно. В таком случае определенные пользователем функции содержат деревья операторов, которые они вычисляют в переопределенном контексте с подставленными значениями аргументов в качестве переменных. Большинство операторов вычисляют значения дочерних операторов и вычисляют свое значение на их основе. Операторы присвоения в зависимости от левого оператора могут так или иначе изменять контекст операции(сохранить новое значение переменной, либо новую функцию).

Сгенерированный парсер на ANTLR

Также была реализована вторая версия калькулятора, у которого вместо описанного выше парсера, парсер был генерирован на основе грамматики, которая описывает язык выражений всего в 45 строк. Притом, что язык выражений остался почти такой же. Вместе с парсером был автоматически сгенерирован шаблон Visitor’а, на основе которого был реализован Visitor, который преобразовывает абстрактное синтаксическое дерево в дерево операторов.

Обе версии калькулятора можно найти на GitHub