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

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

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

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

Я хотел бы как-то разобрать это, чтобы я мог вычислять численные выражения в приложении просто вызывая функцию expr(float x, float y, float z). Количество параметров не должно быть исправлено (EDIT: каждое выражение будет иметь собственное определение с соответствующим количеством параметров или примет массив), и вложенность скобок должна быть разрешена для того, чтобы входные файлы были достаточно малыми.

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

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

Спасибо заранее!

EDIT: Пожалуйста, рассмотрите пример expr() выше только как таковой. Я думаю, лучший способ - иметь объекты шаблонного класса, которые содержат коэффициенты и степени переменных в разреженных массивах.

Ответ 1

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

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

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

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

Ответ 2

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

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

Компиляторы

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

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

Для чего это стоит, я считаю, что Mathematica имеет возможность преобразовать выражения Mathematica непосредственно в C. Кажется, что это тоже стоит проверить.

Ответ 3

Существует простой пример в Bison Manual.