2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Анализатор формул (нужна здоровая критика)
Сообщение19.07.2006, 02:55 


01/07/06
9
Украина, Харьков, НТУ "ХПИ"
Цитата:
Те, кто занимаются различными научными расчетами или написанием научного программного обеспечения часто сталкиваются со следующей проблемой: "Каким образом добавить возможность интерактивно вводить и вычислять математические формулы в своей программе?". Традиционно существует два подхода:
- "зашить" расчеты в исходный код программы
- разрешить пользователю вводить в некотором редакторе описание задачи в виде совокупности формул, с последующей их обработкой некоторым математическим ядром.

К достоинствам первого подхода можно отнести скорость выполнения и минимальные размеры исполняемого модуля (если конечно все оптимально и аккуратно запрограммировано), а также возможность реализовать сколь угодно сложные и неформализованные задачи. Но этот подход не очень гибкий, так как пользователь может настраивать только параметры задачи, а если необходимо что-либо добавить или изменить - требуется изменять исходный код программы (что чревато известными трудностями, например, любые изменения требуют тестирования и отладки программы).
Второй подход можно разделить на три основных направления:
1. Использование спец. мат. пакетов в качестве серверов для вычисления формул
2. Интерпретация
3. Компиляция.

Конечно, можно использовать такие пакеты как MathLab, MathCad и т.п. для проведения научных и инженерных вычислений, но эти пакеты достаточно дорого стоят и, на мой взгляд, несколько "громоздкие". Этот подход можно рекомендовать тем, кто уже владеет подобными пакетами и знает, как их использовать для своих нужд. Основное преимущество данного подхода заключается в том, что эти пакеты "умеют" очень много. К недостаткам же можно отнести то, что они не поставляются в исходных кодах и поэтому представляют собой "черный ящик" со всеми вытекающими из этого неудобствами.

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

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

(С) http://www.delphikingdom.com/asp/viewitem.asp?catalogid=1019

Было решено использовать идею приведенную в статье и реализовать анализатор формул на основе компиляции. В качестве среды разработки была выбрана Micosoft Visual Studio .NET 2005. Данный анализатор предназначается для применения в разрабатываемом программном комплексе по решению задач оптимизации - http://dxdy.ru/viewtopic.php?t=3235

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

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

[-]
1. Нельзя создавать пользовательские функции, т.е. расширять функциональность анализатора
2. Имена переменных не могут включать в себя имена функций
3. Набор стандартных функций весьма невелик, как из-за незавершенности проекта в целом, так и по сложности реалиции анализа специфических функций (x^y)
4. Пока нет механизмов информирования пользователя о возникших при анализе ошибках, т.е. программа может "заглючить" как минимум при некорректно введенной функции
5. Недостаток самой технологии (проект будет работать только при установленном .NET Framework 2.0)

Архив с исходниками и исполняемыми файлами - http://forums.realcoding.net/index.php? ... st&id=1184

 Профиль  
                  
 
 
Сообщение19.07.2006, 03:58 


13/07/06
68
Удивительно странное средство разработки выбрано для такой задачи. Что нужно от него:
    поддержка списков и деревьев на уровне языка. Для парсинга.
    вычисления с произвольной точностью. Понятно зачем.
    динамическая компиляция. Для большей скорости вычисления оттранслированных формул.
    максимальная производительность. Иначе быстрее будет на бамашке посчитать

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


Советую пересмотреть, в сторону например CMUCL или SBCL. Полистайте также готовые проекты, там есть чему поучиться.
http://sourceforge.net/projects/maxima
http://sourceforge.net/projects/octave

 Профиль  
                  
 
 
Сообщение19.07.2006, 08:48 


13/09/05
153
Москва
А что мешает написать свой интерпретатор, используя готовые - на том же http://www.codeproject.com их куча.

Если нужны пользовательские функции - то это уже больше, чем простой парсер мат. выражений.
Цитата:
Имена переменных не могут включать в себя имена функций

Это результат неправильного разбора строки - после имени функции идут скобки, после переменной нет, и по наличию скобок после символов [a-z A-Z _] обычно и выявлется, что в строке идет вызов функции.

И такой вопрос - зачем Вам вообще понадобился .NET Framework 2.0?

Парсер я бы вообще вынес в отдельную DLL для удобства его дальнейшего использования. И ему самому интерфейсные фичи не нужны, голая расчетная ДЛЛ.

По компиляторам и интерпретаторам лучше книги Ахо и Сети ничего не видел - книга есть здесь.

 Профиль  
                  
 
 
Сообщение19.07.2006, 11:43 


01/07/06
9
Украина, Харьков, НТУ "ХПИ"
bugmaker писал(а):
Удивительно странное средство разработки выбрано для такой задачи. Что нужно от него:
    поддержка списков и деревьев на уровне языка. Для парсинга.
    вычисления с произвольной точностью. Понятно зачем.
    динамическая компиляция. Для большей скорости вычисления оттранслированных формул.
    максимальная производительность. Иначе быстрее будет на бамашке посчитать
Ни то ни другое выбранным инструментарием не поддерживается. Особенно порадовало, что тянете с собой такого слонопотама, а существующие характеризуете как
Цитата:
несколько "громоздкие"


Хм. Я, конечно, прошу прощения, если написал свой первый пост несколько непонятно. Цитата в начале поста не моя, я же на нее ниже ссылку привел ((С) http://www.delphikingdom.com/asp/viewit ... logid=1019). Там проект создавался на Delphi, я же взял оттуда только идею создания анализатора с использованием компиляции. Я ничего не имею против MatLab и MatCad, просто задачу я себе поставил такую - создать анализатор под .Net, так как я планирую его потом использовать в программном комплексе, который пишется тоже под .NET. Что же до остального, то я думаю, что будет лучше, если я подробней опишу работу программы. Сделаю это в следующем посте.

bugmaker писал(а):
Советую пересмотреть, в сторону например CMUCL или SBCL. Полистайте также готовые проекты, там есть чему поучиться.
http://sourceforge.net/projects/maxima
http://sourceforge.net/projects/octave


Спасибо, посмотрю.

VLarin писал(а):
А что мешает написать свой интерпретатор, используя готовые - на том же www.codeproject.com их куча.


Спасибо за ссыку. Правда, я про этот сайт и раньше знал, но все равно спасибо. Я на нем действительно находил анализаторы формул на C#(где-то 5 штук), но ни один меня не устроил. Надо было поискать на других языках, это мой недочет. К тому же я написал не интерпретатор, а компилятор. Об этом в следующем посте.

VLarin писал(а):
Если нужны пользовательские функции - то это уже больше, чем простой парсер мат. выражений.


Так и есть.

VLarin писал(а):
Цитата:
Имена переменных не могут включать в себя имена функций

Это результат неправильного разбора строки - после имени функции идут скобки, после переменной нет, и по наличию скобок после символов [a-z A-Z _] обычно и выявлется, что в строке идет вызов функции.


Я уже говорил, что приведенные недостатки будут устранены.

VLarin писал(а):
И такой вопрос - зачем Вам вообще понадобился .NET Framework 2.0?


В уже упоминаемом мной разрабатываемом проргаммном комплексе по методам оптимизации необходимо было предусмотреть расширяемость проекта новыми методами оптимизации без изменения основного модуля и пользовательского интерфейса. Для этого было решено классы всех методов реализовывать в качестве DLL-библиотек (не путать dll-библиотеки .NET с обычными), которые будут читаться из определенного места на жестком диске и динамически подключаться к проекту.
Да и вообще просто было интересно изучить новую технологию.
А именно 2.0 был выбран без особого умысла, просто если есть 2.0, то зачем использовать более ранние .NET Framework.

VLarin писал(а):
Парсер я бы вообще вынес в отдельную DLL для удобства его дальнейшего использования. И ему самому интерфейсные фичи не нужны, голая расчетная ДЛЛ.


Так и сделано, об этом в следующем посте.

VLarin писал(а):
По компиляторам и интерпретаторам лучше книги Ахо и Сети ничего не видел - книга есть здесь.


Спасибо, скачал, буду читать.

 Профиль  
                  
 
 
Сообщение19.07.2006, 12:43 


01/07/06
9
Украина, Харьков, НТУ "ХПИ"
Проект был разработан на языке C# в среде MS VS .NET 2005. Сам анализатор формул представляет собой класс Function, скомпилированный в DLL-библиотеку (на самом деле в .NET все *.exe и *.dll файлы состоят из кода на MSIL и только во время выполнения компилируются JIT-компилятором в исполняемый код), которую можно подключать к другим проектам .NET.

1. С помощью функции void analyse(String functionString) задается анализирующая строка;
2. Из ресурсного файла Substitutions.xml читаются все стандартные подстановки
3. Строка анализируется на наличие переменных
4. Строка конвертируется:
- заменой перемеменных на x[1], x[2] и т.д.
- заменой стандартных функций (sin - Math.Sin, cos - Mah.Cos, pow - Math.Pow и т.д.)
5. Генерируется текст кода класса FunctionAnalyser со статическим методом double getY(double[] x), состоящим из кода "return конвертированная строка;" ;
6. Код компилируется - создается динамическая сборка
7. Динамическая сборка подключается к проекту, который может использовать ее для вычисления введенной функции.

 Профиль  
                  
 
 
Сообщение19.07.2006, 12:49 


01/07/06
9
Украина, Харьков, НТУ "ХПИ"
Диаграмму класса Function можно посмотреть на следующем рисунке - http://forums.realcoding.net/index.php?act=Attach&type=post&id=1185

Скачать файл Function.cs можно отсюда - http://forums.realcoding.net/index.php?act=Attach&type=post&id=1186

 Профиль  
                  
 
 
Сообщение19.07.2006, 15:19 


13/09/05
153
Москва
На CodeProject есть MathParser'ы на С++, о них я и говорил, что стоит посмотреть.
А так идея конечно хорошая - перевести строку в С# и скомпилировать:))
Просто, ИМХО, все это медленно будет - быстрее просто разложить по полочкам и вычислить и без всяких С# (недолюбливаю я С# :)). Предварительно упостить выражение, сделать проверку выражения на ошибки и т.д. Но здесь будут траблы с userdefined-функциями.

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

 Профиль  
                  
 
 
Сообщение19.07.2006, 16:16 


01/07/06
9
Украина, Харьков, НТУ "ХПИ"
VLarin писал(а):
На CodeProject есть MathParser'ы на С++, о них я и говорил, что стоит посмотреть.


Посмотрю.

VLarin писал(а):
А так идея конечно хорошая - перевести строку в С# и скомпилировать:))
Просто, ИМХО, все это медленно будет - быстрее просто разложить по полочкам и вычислить и без всяких С# (недолюбливаю я С# :)).


Компиляция будет, конечно же, длинной, но не то, чтобы особо. А вот вычисление функции с помощью подключенной динамической сборки будет быстрее. Идею использования динамических сборок на .NET я нашел здесь: http://gzip.rsdn.ru/Forum/?mid=623554. А вот пост, где VladD2 приводит результаты тестирования своей программы - http://gzip.rsdn.ru/Forum/Message.aspx? ... 887&only=1 Это не значит, что я во всем согласен с Vlad2, но то, что вычисление с помощью скомпилированного кода быстрее, очевидно.

 Профиль  
                  
 
 
Сообщение20.07.2006, 09:42 


01/07/06
9
Украина, Харьков, НТУ "ХПИ"
Требуется алгоритм (скорее идея) преобразования строки типа:
2x(sinx+10^|x^2+6|)-tany+e^env
в строку типа:
2*x[0]*(Math.Sin(x[0])+Math.Pow(10, Math.Abs(Math.Pow(x, 2)+6))-Math.Tan(x[1])+Math.Pow(Math.E, x[3])

 Профиль  
                  
 
 
Сообщение20.07.2006, 13:10 


13/09/05
153
Москва
Ну ето уже транслятор в чистом виде:) и тут можно взять yacc и прочую хрень.
Или режем строку на токены, составляем дерево разбора и переводим с нашего на С#.
Здесь можно сделать и ту самую проверку правильности входной строки.

Если "2x(sinx+10^|x^2+6|)-tany+e^env " - одно из самых сложных преобразований, то можно в лоб, последовательными проходами делать замены:
1. sinx => sin(x) => Math.Sin(x[0])
2. Число+x => число*x[0], Число + скобка => Число * скобка
3. Модуль - здесь аналогично pow - нашли первую скобку, нашли вторую, все внутренности засунули в Math.Abs().
4. (символ или число)^ => pow(символ или число,
смотрим, какой символ после ^ - если скобка, то нужно найти правую и все что между ними добавить к pow(.... и закрыть скобку, или, если число или символ, то найти его окончание и добавить.
5..........................
и т.д.

 Профиль  
                  
 
 Re: Анализатор формул (нужна здоровая критика)
Сообщение09.03.2010, 18:58 


09/03/10
1
А как насчет отображения формул? Есть какие либо модули, библиотеки или компоненты дабы сделать в своей программе отображение сложных формул (интегралы, корни, и т.д.) наподобие как это сделано в MS Word?

з.ы. блин, я некропостер.... все равно, есть кто? ответье плз((

 Профиль  
                  
 
 Re: Анализатор формул (нужна здоровая критика)
Сообщение13.03.2010, 21:34 
Аватара пользователя


20/12/08
236
изниоткуда
генерация LaTeX-кода?

 Профиль  
                  
 
 Re: Анализатор формул (нужна здоровая критика)
Сообщение17.03.2010, 15:35 


09/06/06
367
Рекомендую разыскать старые версии Турбо Паскаля для ДОС . В дистрибутивах имеются исходные тексты крупноформатных электронных таблиц , предшественников Эксела . Есть там анализаторы .
Или найти тексты Визикалка , тот кажись на Бэйсике был написан . Здоровее в голову не приходит .

 Профиль  
                  
 
 Re: Анализатор формул (нужна здоровая критика)
Сообщение17.03.2010, 17:37 


15/01/07
19
http://www.yann-ollivier.org/maths_info с табуляцией только глючек нашел

(Оффтоп)

хорошо бы автору отписать
, sp cr lf игнорирует. Пролизводные считает зачемто

-- Ср мар 17, 2010 18:53:18 --

Цитата:
Советую пересмотреть, в сторону например CMUCL или SBCL. Полистайте также готовые проекты, там есть чему поучиться.
http://sourceforge.net/projects/maxima
http://sourceforge.net/projects/octave

Такого калибра вещи даже скомпилировать проблема, не то что выдернуть чего нибудь

 Профиль  
                  
 
 Re: Анализатор формул (нужна здоровая критика)
Сообщение17.03.2010, 20:05 
Аватара пользователя


20/12/08
236
изниоткуда
Цитата:
Такого калибра вещи даже скомпилировать проблема, не то что выдернуть чего нибудь

А в чем проблема, собстно?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group