Пользовательский интерпретатор для математических выражений

Question

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

Допустим, у нас есть файл с математическими выражениями и ограниченным набором объектов.Файл может выглядеть так:

expr[x,y,z] = 2*x*y + x^2 + 28/14*z*(x*y^2 + 15*z) + ...

Я бы хотел как-то разобрать это, чтобы я мог численно оценить выражения в моем приложении, просто вызвав функцию expr(float x, float y, float z).Число параметров не должно быть фиксированным (РЕДАКТИРОВАТЬ: каждое выражение будет иметь свое собственное определение с соответствующим количеством параметров или будет принимать массив), и вложения скобок должны позволять сохранять входные файлы достаточно маленькими.

Поскольку все выражения имеют полиномиальный тип, я могу думать о том, как должна выглядеть структура данных, но синтаксический анализ выглядит затруднительным.Я уже нашел некоторые ответы на несколько похожие вопросы здесь, в SO, например, с использованием Lua.

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

Заранее спасибо!

РЕДАКТИРОВАТЬ: Пожалуйста, рассмотрите только пример expr() выше как таковой.Я думаю, что наилучшим способом было бы иметь объекты из шаблонного класса, который содержит коэффициенты и степени переменных в разреженных массивах.

Answer 1

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

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

Что касается этой промежуточной формы - обычно для начала нужно использовать алгоритм Дейкстры "shunting-yard", чтобы преобразовать ваши инфиксные выражения в обратную польскую форму. Это дает вам последовательность «символов», «байтовых кодов», называете их как вам угодно, и легко написать оценщик выражений для этой формы - каждый оператор просто извлекает свои операнды из стека, выполняет операцию, затем выталкивает результат на стек, пока окончательное значение выражения не будет единственным, что осталось в конце. Числовые литералы и имена переменных похожи на «операторы», которые не выдают операндов и выдвигают свои значения.

[Редактировать - в зависимости от того, кто ваши пользователи, для вашей программы может быть целесообразным взять этот текстовый файл, сгенерировать из него программу на C, запустить компилятор и затем запустить результирующую программу (или открыть и вызвать полученную программу). DLL). Очевидно, что это зависит от множества специфических для системы вещей (например, от устанавливаемого компилятора), и выражения нужно будет оценивать достаточно много раз, чтобы преодолеть издержки компиляции.]

Answer 2

Вы указали проблему как «большие сложные выражения», и вас беспокоит снижение производительности.Тогда вам следует рассмотреть возможность их компиляции, а не интерпретации.(Хорошие интерпретаторы, как правило, в 10 раз медленнее, чем скомпилированный код; паршивые / специальные интерпретаторы, как правило, значительно хуже).

Обычный путь для этого состоит в том, чтобы как-то «скомпилировать» выражения, что включает в себя создание анализаторов, генераторов кода, оптимизаций и т. Д.

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

Но Если все эти выражения создаются Mathematica, они будут иметь довольно стандартную, но не сложную структуру.В этом случае, я думаю, вы могли бы написать переводчик на основе регулярных выражений, который мог бы отображать формы Mathematica в функции C без особых проблем;Perl был бы идеальным для этого.Это дает вам простое и быстрое решение для реализации.

Я думаю, что Mathematica имеет возможность конвертировать выражения Mathematica непосредственно в C. Похоже, это тоже стоит проверить.

Answer 3

В руководстве Bison есть простой пример.