Разработка обучающей программы по теме "Обыкновенные дифференциальные уравнения"
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
аграмма программного средства.
Для лучшего понимания принципов функционирования и алгоритмов работы данных модулей рассмотрим их более подробно.
3.3.1 Модуль лексико-грамматического анализа выражения и равенства
Модуль лексико-грамматического анализа выражения или равенства позволяет проверять корректность ввода ДУ. Данный модуль в качестве входной информации принимает значение строки с формулой в виде равенства, производит её разбиение на лексемы, каждая из которых представляет собой знак =, один из знаков арифметических операций, обозначение переменной или константы. Это необходимо для дальнейшего проведения анализа корректности ввода ДУ, в котором используются автоматные грамматики, построенные на идее построении КС-грамматик языка, а также построении на их основе LL(1)-грамматик языка и построение модели нисходящего LL(1)-анализатора [10]. Процесс разработки нисходящего LL-анализатора можно подразделить на следующие этапы:
-формальное описание синтаксиса с помощью нормальных форм Бекуса-Наура;
-формальное описание синтаксиса конструкции языка программирования в форме КС-грамматик;
-выполнение эквивалентных преобразований КС-грамматики iелью устранения недостижимых и бесплодных нетерминалов;
-описание множества классов лексем исходной конструкции и построение модели лексического анализатора;
-составление тестовых данных для проверки правильности работы лексического анализатора;
-приведение КС-грамматики к виду LL(1)-грамматики;
-построение нисходящего LL(1)-анализатора.
Прохождение данных этапов позволило разработать лексико-грамматический анализатор, обрабатывающий такие характерные ошибки ввода, как использование недопустимых лексем и неправильный синтаксис математического выражения или равенства; этапы разработки LL(1)-анализатора, используемого в программном средстве приведены в приложении В Построение LL(1)-анализатора.
Выходной информацией к данному модулю является допуск или запрет построения бинарного дерева, состоящего из вершин и связей между ними. Вершинами дерева являются математические операции переменные, константы и функции. Примером такого дерева может служить рисунок, изображающий дерево характерное для формулы .
Рисунок 3 - Пример бинарного дерева
Сохранение такой структуры в памяти компьютера осуществляется за счет создания пользовательского типа TTree с использованием перечисленных ниже полей.
TTree *left,*right - поля, предназначенные для хранения указателя на левую и правую вершины соответственно. Указатель характеризуется шестнадцатеричным кодом участка памяти, в котором расположена следующая вершина дерева. Данные указатели соответствуют связям между вершинами бинарного дерева.
double data - данное поле предназначено для хранения констант, встречающихся в выражении, что значительно упрощает вычисление значения функции и анализ ДУ.
AnsiString symbol - данное строковое поле предназначено для сохранения информации о функции, операции или переменной, используемой в математическом выражении.
Определение порядка следования операций при построении бинарного дерева, является достаточно важным моментом. Как видно из рисунка 3, наименьшим приоритетом обладают операции сложения/вычитания, далее идут операции умножения и деления, а также возведения в степень. Полная таблица приоритетов операций, используемых при построении корректного бинарного дерева по введенному ДУ, приведена в таблице 1.
Таблица 1 - Приоритеты операций
Знак, операция, функцияСтепень приоритета*= (знак равества)1+ (сложение)2- (вычитание)2* (умножение)4/ (деление)3^ (возведение в степень)5cos (косинус)6sin (синус)6ln (натуральный логарифм)6tg (такнгенс)6atan 6acos 6asin6
Для выделения лексем, проверяемых на корректность, используется специализированный массив типа, заданного пользователем. Данный пользовательский тип имеет следующие поля:
AnsiString handle - строковое поле для хранения лексемы;
short int priority - текущий приоритет лексемы для разбора;
bool useLec - признак того что данная лексема занесена в дерево;
TTree *rootLT- в случаях, когда лексема уже занесена в дерево, необходимо сохранить указатель на данную вершину, чтобы в дальнейшем производить связывание более приоритетных операций с менее приоритетным; в противном случае лексема не была занесена в дерево, данное поле принимает значение NULL.
Множество лексем хранится в массиве. Данный массив представляет собой 255 элементов (лексем). Процедура построения бинарного дерева работает таким образом, что в выражении не может присутствовать более 255 лексем.
В целом алгоритм работы программного модуля лексико-грамматического анализатора выражения или равенства представлен в виде блок схемы изображенной на рисунке 4.
Рисунок 4 - Блок-схема алгоритма работы модуля лексико-грамматического анализатора
В случаях возникновения ошибок на этапах лексического и грамматического анализа производится остановка работы лексико-грамматического анализатора с указанием места возникновения и возможной ошибки.
3.3.2 Модуль определения типа ДУ, канонической формы и метода решения
Как говорилось выше (пункт 2.1), для решения задачи, связанной с распознаванием типа ДУ, будем использовать метод рекурсивного синтаксического анализа частей бинарного дерева. Для проведения анализа необходимо определить основные признаки, используе