Розбір і трансляція математичних формул

Олексій Кузнєцов, «Королівство Delphi»

Вступ

Ті, хто займаються різними науковими розрахунками або написанням наукового програмного забезпечення часто стикаються з такою проблемою: "Яким чином додати можливість інтерактивно вводити і обчислювати математичні формули в своїй програмі?". Традиційно існує два підходи:

"Зашити" розрахунки в вихідний код програми;
дозволити користувачеві вводити в деякому редакторі опис завдання у вигляді сукупності формул, з подальшою їх обробкою деяким математичним ядром.

До переваг першого підходу можна віднести швидкість виконання і мінімальні розміри виконуваного модуля (якщо звичайно все оптимально і акуратно запрограмовано), а також можливість реалізувати як завгодно складні і неформалізовані завдання. Але цей підхід не дуже гнучкий, так як користувач може налаштовувати тільки параметри завдання, а якщо необхідно щось додати або змінити - потрібно змінювати вихідний код програми (що загрожує відомими труднощами, наприклад, будь-які зміни вимагають тестування і налагодження програми). Другий підхід можна розділити на три основні напрямки:

Використання спец. мат. пакетів в якості серверів для обчислення формул;
інтерпретація;
Компіляція.

Звичайно, можна використовувати такі пакети як MathLab, MathCad і т.п. для проведення наукових та інженерних обчислень, але ці пакети досить дорого коштують і, на мій погляд, дещо "громіздкі". Цей підхід можна рекомендувати тим, хто вже володіє подібними пакетами і знає, як їх використовувати для своїх потреб. Основна перевага даного підходу полягає в тому, що ці пакети "вміють" дуже багато. До недоліків же можна віднести те, що вони не поставляються у вихідних кодах і тому представляють собою "чорний ящик" з усіма наслідками, що випливають з цього незручностями.

Інтерпретація формул - досить поширений підхід і існує безліч його реалізацій. Переваги: простота реалізації, докладний діагностування помилок під час обчислення. Основним недоліком є вкрай низька швидкість обчислень (хоча мені відомі реалізації з використанням кешування та подання формул з використанням деревовидних структур які цим недоліком практично не мають).

Компіляція - аналіз і трансляція формул безпосередньо в машинний код або в програму на мові високого рівня. Перетворення формул в машинний код пов'язане зі значними труднощами, так як вимагає від розробника глибоких знань в цій області і до того ж прив'язує реалізацію до певної апаратній платформі. Набагато більш гнучким способом є трансляція формул в програму на мові високого рівня, так як це, по-перше, значно спрощує сам процес трансляції та, по-друге, дозволяє використовувати цей підхід практично без обмежень для будь-яких програмно-апаратних платформ. До переваг цього підходу можна віднести високу швидкість обчислень, а до недоліків, дещо складнішу обробку формул у порівнянні з інтерпретацією. Далі в цій статті буде розглянуто саме цей підхід - аналіз і трансляція формул в програму на мову високого рівня (на момент написання статті реалізована підтримка Object Pascal).

Мова опису математичних формул

Як формули виступає функція багатьох змінних F (x), x = (x1, ..., xn).

Алфавіт мови опису формул

Основні символи мови опису формул це - букви, цифри і спеціальні символи:

26 великих і малих латинських букв: A, ..., Z, a, ..., z
10 цифр: 0, ..., 9
знаки операцій: + - * / ^
знаки умовних операцій: = <> <= <= <>
обмежувачі і роздільники:, () | ; ...
ключові (зарезервовані) слова: if then else and or begin end

елементарні конструкції

Елементарні конструкції мови опису формул включають в себе ідентифікатори і числа. Ідентифікаторами називають елементи мови: змінні, функції і константи. Ідентифікатор це послідовність букв і чисел, що починається з букви. Ідентифікатори не чутливі до регістру букв. Забороняється використовувати в якості ідентифікаторів ключові слова.

типи даних

Передбачається, що всі елементи формули є дійсними числами, крім наступних випадків: <Мінлива циклу> (див. Далі в описі граматики), початковий і кінцевий індекси циклу (у функціях 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) за допомогою компілятора командного рядка. Описаний підхід можна легко адаптувати під будь-які інші мови програмування (наприклад, мова С), при цьому фактично треба тільки переписати процедуру трансляції списку оброблених лексем в програму потрібною мовою програмування.

література

http://www.softcraft.ru/translat/lect/content.shtml

Завантажити "Бібліотеку для розбору і трансляції математичних формул: optMathParser": ParserDemo.zip (177K)
Примітка до архіву:

Для того що б скомпілювати цей проект в настройках проекту треба прописати SearchPath до папок:
kaOptima
MathExprDraw
QStrings
Чи не ВСІ файли присутні у вигляді вихідних текстів, то що я вважаю своїм "know-how" присутній у вигляді * .dcu (Delphi 7)
Ця бібліотека є частиною пакета глобальної пошукової непараметричної оптимізації kaOptima і успішно використовується на протязі 3-х років
Як деякої документації по бібліотеці см. Папку Doc, в якій знаходиться інтерфейсна частина модуля opt MathParser.
Бібліотека QStrings: Copyright (C) 2000, 2001 Andrew N. Driazgov
Portions (C) 2000, Sergey G. Shcherbakov
Бібліотека MathExprDraw: Григор'єв Антон і деякі модифікації внесені - мною, в тексті позначені {kuaw}

Разработка сайта для Вашего бизнеса. Веб дизайн. Дизайн логотипа, фирменного стиля, рекламная фотография . Комплексный рекламный креатив.

Розбір і трансляція математичних формул