symbolic-calc

Калькулятор символьных выражений.

Описание

Калькулятор арифметический выражений с поддержкой:

• Бинарных операций: +, -, *, /, ^ (возведение в степень).
• Унарных операций: +, -, ~ (в значении операции логического отрицания).
• Использования целых чисел и чисел с плавающей точкой одинарной точности.
• Констант, поддерживаемых языком арифметики: PI - число Пи, EXP - число Эйлера.
• Некоторых математических функций: sin, cos, tg, ctg, sqrt.
• Приоритизации посредством фигурных скобок: {}.
• Соблюдением приоритета операций, совпадающего с приоритетом соответствующих операций в стандарте языка C.
• Определения переменных - непосредственным значением или именованной константой.

Структура репозитория

• inc - директория, содержащая 'public 'заголовочные файлы - необходимые при использовании калькулятора в качестве библиотеки.
• lex - директория, содержащая правила для генерации лексического анализатора посредством Flex.
• src - директория, содержащая файлы с исходным кодом библиотеки.
• yacc - директория, содержащая правила для генерации парсера посредством Bison.
• driver - поддиректория, содержащая исходный код (src) и заголовочные файлы (inc) для драйвера запуска библиотеки из командной строки.
• tests - поддиректория, содержащая исходный код (src) для тестирования калькулятора.

Детали реализации

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

Для вычисления выражений в проекте использовались Flex и Bison.

Flex

Flex — инструмент для создания сканеров. Сканер — это программа, распознающая лексические закономерности в тексте. Flex считывает заданные входные файлы или стандартный ввод, если имена файлов не указаны, для получения описания создаваемого сканера. Описание представлено в виде пар регулярных выражений и кода C, называемых правилами. Flex генерирует в качестве вывода исходный файл C, который определяет функцию yylex(). Этот файл можно скомпилировать и связать с библиотекой времени выполнения Flex для создания исполняемого файла. При запуске исполняемого файла он анализирует входные данные на наличие регулярных выражений. Всякий раз, когда он его находит, он выполняет соответствующий код C.

Правила для создания сканера расположены в файле lex/lex.l. Примерами токенов, которые распознает лексер в данном проекте, являются: NUMINT и NUMFLT, соответствующие целым числам и числам с плавающей точкой; VAR_ID - идентификатор (имя) переменной; STD_FUNC - стандартная математическая функция из числа поддерживаемых и т.д.

В данном проекте Flex используется для создания лексического анализатора. С помощью него в строке, описывающей арифметическое выражение, распознаются допустимые лексемы и определяются соответствующие им типы токенов. Напрямую через метод yylex() анализатор в данном проекте не используется, так как его вызывает следующий модуль программы - парсер (cм. Bison).

Bison

GNU Bison — программа, предназначенная для автоматического создания синтаксических анализаторов по данному описанию грамматики. Синтаксический анализатор получает на вход поток токенов, распознанных с помощью лексического анализатора, и находит нетерминальные символы и выполняет заданный код согласно грамматике, определенной в соответствующем формате. В качестве точки входа в синтаксический анализатор Bison определяет функцию yyparse().

Bison является GNU-версией yacc (Yet Another Compiler Compile) - компьютерной программы, служащей стандартным генератором синтаксических анализаторов (парсеров) в Unix-системах.

Грамматика для генерации синтаксического анализатора описана в файле yacc/yacc.y.

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

result: expr

expr: term | expr ADD term | expr SUB term
term: power | term MUL power | term DIV power
power: factor | power POW factor
factor: OPEN_BR_CRVD expr CLOS_BR_CRVD | VAR_ID | constant | std_func | unary
unary: SUB factor | ADD factor | NOT factor

constant: STD_CONST | NUMINT | NUMFLT
std_func: STD_FUNC OPEN_BR_RND expr CLOS_BR_RND

Краткое описание грамматики:

• result - 'top-level' нетерминал, значение которого является результатом выполнения калькулятора.
• expr, term, power - нетерминалы, тела продукции для которых задают приоритет бинарных арифметических операций - сложения, вычитания, умножения, деления и возведения в степень.
• factor - может быть раскрыт в фигурные скобки, содержащие expr (приоритизация посредством скобок), а также в идентификатор переменной, константное значение constant или вызов математической функции.
• unary - нетерминал, задающий унарные операции - унарный плюс и унарный минус.
• constant - стандартная именованная константа (STD_CONST), целое число (NUMINT) или число с плавающей точкой (NUMFLT).
• std_func - вызов стандартной математической функции, аргументом которой является выражение expr в круглых скобках.

В прочих приложениях синтаксический анализатор, сгенерированный при помощи Bison может быть использован, к примеру, для построения Абстрактного Синтаксического Дерева (AST) в ходе процесса компиляции программы на некотором языке программирования.

В данном проекте поставлена другая задача, поэтому функционал предоставляемый Bison используется сразу для вычисления значения арифметического выражения. Код на языке C, исполняемый при обнаружении структуры, соответствующей некоторому правилу грамматики, вычисляет собственное значение на основании тела продукции. Приведем пример для term:

term:
  power { $<fval>$ = $<fval>1; }
  | term MUL power { 
    $<fval>$ = $<fval>1 * $<fval>3;
    YACC_VPRINT("%f * %f = %f \n", $<fval>1, $<fval>3, $<fval>$);
  }
  | term DIV power { 
    $<fval>$ = $<fval>1 / $<fval>3; 
    YACC_VPRINT("%f / %f = %f \n", $<fval>1, $<fval>3, $<fval>$);
  }

В примере выше в зависимости от обнаруженного токена арифметической операции, исполняется соответствующее вычисление - умножение или деление.

Еще один пример - вызов математической функции для std_func.

std_func: STD_FUNC OPEN_BR_RND expr CLOS_BR_RND {
  $<fval>$ = std_func_evaluate($<ival>1, $<fval>3);
}

Функция std_func_evaluate() здесь принимает значение аргумента и код функции, определенный на стадии лексического анализа, производит соответствующий вызов и возвращает полученное значение в качестве значения нетерминала std_func.

Сборка

Для сборки проекта необходима система сборки CMake версии 3.21 и выше, установленные утилиты Flex и Bison, а также пакет для тестирования GTest.

Для сборки всех доступных целей (драйвер, статическая библиотека, тесты), достаточно воспользоваться командой cmake -B build && cmake --build build

Чтобы собрать драйвер запуска из командной строки, воспользуйтесь следующими командами:

• cmake -B build
• cmake --build build --target driver

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

• cmake -B build
• cmake --build build --target calc
• cmake --build build --target install DESTDIR=[DIR]

После установки в директории [DIR] будет располагаться следующая структура файлов: -[DIR]

• lib
  • libcalc.a - статическая библиотека.
• inc
  • calc.h - публичный заголовочный файл библиотеки.

Директории lib и inc будут созданы, если они не существовали до установки библиотеки.

Запуск

По завершении сборки исполняемый файл драйвера находится в директории по пути bin/driver.

Использование: path-to-executable "expression" [OPTIONS]*

• "expression" - строка, содержащая выражение.
• OPTIONS - дополнительные опции запуска. Список доступных опций перечислен ниже.

Опции запуска:

1. --help - отобразить сообщение с информацией об использовании.
2. --var variable_name=variable_value - определить переменную с именем variable_name и значением variable_value. Имя заданной переменной можно использовать в выражении, где в качестве ее значения будет использовано variable_value. Допускается определение нескольких переменных сразу, но каждая переменная обязательно должна иметь уникальное имя. Значением переменной может является число с плавающей точкой или имя стандартной константы из списка поддерживаемых. Примеры использования опции: --var x=PI, --var y=2.5.

Пример запуска:

❯ ./bin/driver "2 + sin(x) / {y + cos(x)} * PI" --var x=4 --var y=2
Evaluating expression: 2 + sin(x) / {y + cos(x)} * PI
Evaluation result is 0.234074

Отладочные опции сборки:

• VERBOSE_LEX - включает вывод дополнительной debug информации, аннотирующей процесс лексического анализа. По умолчанию отключена. Чтобы собрать проект с включенной данной опцией, необходимо воспользоваться командой cmake -B build -DVERBOSE_LEX=ON

• VERBOSE_YACC - включает вывод дополнительной debug информации, аннотирующей процесс синтаксического анализа. По умолчанию отключена. Чтобы собрать проект с включенной данной опцией, необходимо воспользоваться командой cmake -B build -DVERBOSE_YACC=ON

Тестирование

Проект предоставляет в комплекте с собой тестирование на основе GTest.

Алгоритм сборки тестов и запуска тестирования:

1. Собрать желаемые тесты. Доступные цели сборки (передаются Cmake через флаг --target):

2. test-evaluation - тестирование вычислительных способностей калькулятора - значение констант, базовые арифметические операции, математические функции etc.

3. test-prioritization - тестирование соблюдения приоритетов выполнения операций.

4. test-variables - тестирование подстановки значений переменных.

5. Запустить тесты. Для этого необходимо перейти в директорию build/tests и исполнить команду ctest. Ниже приведен пример вывода:

❯ ctest
Test project /.../symbolic-calc/build/tests
    Start 1: test_evaluation
1/3 Test #1: test_evaluation ..................   Passed    0.00 sec
    Start 2: test_prioritization
2/3 Test #2: test_prioritization ..............   Passed    0.00 sec
    Start 3: test_variables
3/3 Test #3: test_variables ...................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 3

Total Test time (real) =   0.01 sec

В случае возникновения ошибки, следует запустить тестирование снова с опциями --rerun-failed и --output-on-failure для получения дополнительной информации об ошибке.

Ссылки

Схожие проекты:

1. Лексический анализатор с использованием Flex
2. Восходящий синтаксический анализатор типа "Перенос/свёртка"

Использованная документация/спецификация

1. Документация на Bison.
2. Репозиторий проекта Flex на GitHub
3. Полезный HOWTO по использованию связки Lex&YACC.

А теперь анекдот: Все люди делятся на 10 категорий: на тех, кто понимает двоичную систему счисления и на тех, кто её не понимает.