| ||||||||||||
| ||||||||||||
|
2004 г.
Разбор и трансляция математических формулАлексей Кузнецов, «Королевство Delphi»ВведениеТе, кто занимаются различными научными расчетами или написанием научного программного обеспечения часто сталкиваются со следующей проблемой: "Каким образом добавить возможность интерактивно вводить и вычислять математические формулы в своей программе?". Традиционно существует два подхода:
К достоинствам первого подхода можно отнести скорость выполнения и минимальные размеры исполняемого модуля (если конечно все оптимально и аккуратно запрограммировано), а также возможность реализовать сколь угодно сложные и неформализованные задачи. Но этот подход не очень гибкий, так как пользователь может настраивать только параметры задачи, а если необходимо что-либо добавить или изменить - требуется изменять исходный код программы (что чревато известными трудностями, например, любые изменения требуют тестирования и отладки программы). Второй подход можно разделить на три основных направления:
Конечно, можно использовать такие пакеты как MathLab, MathCad и т.п. для проведения научных и инженерных вычислений, но эти пакеты достаточно дорого стоят и, на мой взгляд, несколько "громоздкие". Этот подход можно рекомендовать тем, кто уже владеет подобными пакетами и знает, как их использовать для своих нужд. Основное преимущество данного подхода заключается в том, что эти пакеты "умеют" очень много. К недостаткам же можно отнести то, что они не поставляются в исходных кодах и поэтому представляют собой "черный ящик" со всеми вытекающими из этого неудобствами. Интерпретация формул - достаточно распространенный подход и существует множество его реализаций. Достоинства: простота реализации, подробное диагностирование ошибок во время вычисления. Основным недостатком является крайне низкая скорость вычислений (хотя мне известны реализации с использованием кэширования и представления формул с использованием древовидных структур которые этим недостатком практически не обладают). Компиляция - анализ и трансляция формул непосредственно в машинный код или в программу на языке высокого уровня. Преобразование формул в машинный код сопряжено со значительными трудностями, так как требует от разработчика глубоких знаний в этой области и к тому же привязывает реализацию к определенной аппаратной платформе. Гораздо более гибким способом является трансляция формул в программу на языке высокого уровня, так как это, во-первых, значительно упрощает сам процесс трансляции и, во-вторых, позволяет использовать этот подход практически без ограничений для любых программно-аппаратных платформ. К достоинствам этого подхода можно отнести высокую скорость вычислений, а к недостаткам, несколько более сложную обработку формул по сравнению с интерпретацией. Далее в этой статье будет рассмотрен именно этот подход - анализ и трансляция формул в программу на язык высокого уровня (на момент написания статьи реализована поддержка Object Pascal). Язык описания математических формулВ качестве формулы выступает функция многих переменных F(x), x=(x1,…, xn). Алфавит языка описания формулОсновные символы языка описания формул это - буквы, цифры и специальные символы:
Элементарные конструкцииЭлементарные конструкции языка описания формул включают в себя идентификаторы и числа. Идентификаторами называют элементы языка: переменные, функции и константы. Идентификатор это последовательность букв и чисел, начинающаяся с буквы. Идентификаторы не чувствительны к регистру букв. Запрещается использовать в качестве идентификаторов ключевые слова. Типы данныхПредполагается, что все элементы формулы являются действительными числами, кроме следующих случаев: <Переменная цикла> (см. далее в описании грамматики), начальный и конечный индексы цикла (в функциях SUM и PROD), а так же константа DIM (размерность вектора входящих переменных) являются целыми положительными числами. КомментарииКомментарии представляют собой текстовые строки, предназначенные для аннотирования формулы. В языке описания формул поддерживается два типа комментариев: однострочные и многострочные. Первый тип начинается с последовательности "//" и при этом комментируется весь текст после нее до конца строки. Второй тип комментария может быть использован для выделения в комментарий многострочного текста, его начало и конец обозначаются соответственно "{" и "}" или " (*" и "*)", весь текст размещенный между этими символами, считается комментарием. Структура формулыФормула может состоять из следующих элементов:
Первые три элемента могут присутствовать в произвольном количестве и порядке, однако переменные и локальные функции необходимо явно определять до их использования. Четвертый элемент всегда присутствует в формуле и находится в ее конце, весь дальнейший текст формулы после него игнорируется. Грамматика языка описания формулЯзык описания математических формул можно задать более формально с использованием грамматики в расширенной форме Бэкуса-Наура с использованием следующих соглашений:
Список правил грамматики<Буква>::= А|В|С|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z| a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z <Цифра>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <Целое число>::= {/Цифра/}
<Вещественное число>::= (<Целое число>.<Целое число>) |
(<Целое число>[.<Целое число>]E[-|+]<Целое число>) |
.<Целое число>[E[-|+]<Целое число>]
<Число>::= <Целое число> | <Вещественное число> <Входная переменная>::= X(<Целое число> | _i | _"("i ± <Целое число>")")
Примечание: <Входную переменную> у которой в индексе присутствует "i" можно использовать только внутри спец. Функций SUM и PROD <Переменная цикла>::= i Примечание: <Переменную цикла> можно использовать только внутри спец. функций SUM и PROD <Аргумент локальной функции>::= U Примечание: <Аргумент локальной функции> можно использовать только в <Описании локальной функции> <Дополнительная переменная>::= <Буква>{<Буква>}[<Целое число>]
Примечание: Значение <Дополнительной переменной> не может принимать значения зарезервированные за <Переменной цикла>, <Аргументом локальной функции>, <Результатом> и <Ключевым словом> <Переменная>::= <Входная переменная> | <Дополнительная переменная> <Перечисление аргументов>::= <Переменная1>, ..., <Переменная2> Примечание: <Переменная1> и <Переменная2> - должны иметь одинаковое имя и обязательно должны быть с числовым индексом! Причем индекс <Переменной1> должен быть меньше индекса <Переменной2> <Аргумент функции>::= <Выражение>{, <Выражение>} |
{<Выражение>,}<Перечисление аргументов>{,<Выражение>}
<Имя функции>::= см.таблицу имен функций <Функция>::= <Имя функции> "("<Аргумент функции>")"
Примечание: У некоторых <Функций> (например, SUM или PROD) аргументы анализируются особым образом <Имя локальной функция>::= Y<Целое число> <Локальная функция>::= <Имя локальной функция>"("<Аргумент функции>")"
<Константа>::= PI | DIM Примечание: <Константа> DIM описывает размерность вектора входящих переменных <Ключевое слово>::= IF | THEN | ELSE | NOT | AND | OR | BEGIN | END <Операнд>::= <Число> | <Переменная> | <Переменная цикла> |
<Функция> | <Константа> |
<Локальная функция> | <Аргумент локальной функции>
<Операция>::= + | - | * | o |· | / | ^ <Унарный знак выражения>::= + | - <Выражение>::= <Операнд> |
<Унарный знак выражения> <Выражение> |
<Выражение> [<Операция>] <Выражение> |
"("<Выражение>")" |
"|"<Выражение>"|"
Примечание: Если между выражениями пропущена <Операция>, то по умолчанию полагаем, что это операция умножения <Разделитель>::= ; | <Перевод строки> | <Конец файла> <Определение переменной>::= <Дополнительная переменная> =
<Выражение> <Разделитель>
<Операция сравнения>::= = | "<" | ">" | "<>" | ">"= | "<"= <Условие>::= <Выражение> <Операция сравнения> <Выражение> |
<Условие> (AND|OR) <Условие> |
"(" <Условие> ")"
<Определение локальной функции>::= <Имя локальной функция>
"("<Аргумент локальной функции>")" = <Выражение>
Примечание: <Выражение> в <Определении локальной функции> не может содержать: <Переменную> и спец. функции SUM и PROD <Определение>::= <Определение переменной> | <Условное определение> <Блок определений>::= BEGIN { <Определение> } END
<Условное определение>::= IF <Условие> THEN <Блок определений> | <Определение> [ELSE <Блок определений> | <Определение>] <Результат>::= F <Результирующие определение>::= <Результат> = <Выражение> <Разделитель выражений> Примечание: Весь текст формулы после <Результирующего определения> при анализе игнорируется <Комментарий>::== "//" <Любой текст> <Перевод строки>|
"{"{<Любой текст> [<Перевод строки>]}"}"
"(*"<Любой текст> [<Перевод строки>] "*)"
Примечание: Все <Комментарии> в процессе анализа пропускаются <Формула>::= {<Определение локальной функции> | <Определение>}
<Результирующие определение>
Программная реализация трансляции формулыОбработка формулы состоит из следующих этапов:
Описанный подход можно представить в виде следующей схемы:
Таблица функций(см. таблицу)Примеры формул
1.
Z1 = sin(X1)
Z2 = cos(X2)
F= Z1^2 + Z2^2
2.
Z1 = 3 // Уровень помехи
Z2 = |X1| // Модуль X1
Z3 = abs(X2) // Это тоже модуль X2
F = Z2 - Z3 + Z1R(-1, 1)
3.
// пример использования "умножения" по умолчанию
Alfa=3X1
Beta=4Sin(2Pi*X1X2)
F = Alfa + Beta
4.
// пример использования локальных функций
Y1(U) = |U|
Y2(U) = (U-3)^2 - 1
Y3(U) = |U-5|
F=min(Y1(X1), Y2(X1), Y3(X1))+
min(Y1(X2), Y2(X2), Y3(X2))
5.
// пример использования суммы и произведения
Z1= sum(1, dim-1, Xi+1-Xi)
// явно указываем пределы суммирования
Z2= sum(Xi^i)+prod(cos(Xi))
// пределы суммирования по умолчанию i=1,dim
F= Z1+Z2
6.
// пример использования условного определения
if (|X1| <= 1) then I0=1 else I0=0
F= X1^2 + I0*R(-1,1)
ЗаключениеСледует отметить, что рассмотренный в данной статье подход к разбору и трансляции математических формул вот уже более трех лет эффективно используется для описания тестовых задач глобальной оптимизации, которые состоят не только из функции качества, но еще и из произвольного количества ограничений в пакете глобальной поисковой непараметрической оптимизации "kaOptima". В упомянутом пакете, после трансляции формулы в программу (в данной реализации на языке Object Pascal), производится ее компиляция в динамически подключаемую библиотеку (dll) с помощью компилятора командной строки. Описанный подход можно легко адаптировать под любые другие языки программирования (например, язык С), при этом фактически надо только переписать процедуру трансляции списка обработанных лексем в программу на требуемом языке программирования. ЛитератураСкачать "Библиотеку для разбора и трансляции математических формул: optMathParser": ParserDemo.zip (177K)
|
 | |||||||||
| |||||||||
|
CITForum © 1997–2025