Программирование численных методов решение нелинейных уравнений итерационным методом

ПРИЛОЖЕНИЕ А

 

НЕГОСУДАРТСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ВОСТОЧНАЯ ЭКОНОМИКО-ЮРИДИЧЕСКАЯ ГУМАНИТАРНАЯ

АКАДЕМИЯ (Академия ВЭГУ)

 

Специальность – прикладная информатика (в экономике)

       Специализация – информационные системы в бухгалтерском учёте и аудите

 

 

 

КУРСОВАЯ РАБОТА

 

Программирование численных методов решение нелинейных уравнений итерационным методом

 

Научный руководитель

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Белорецк 2011

 

Содержание

 

 

	Лист
Введение	3
1 Задание	4
2 Организация таблицы идентификаторов	6
2.1 Исходные данные	6
2.2 Назначение таблиц идентификаторов	6
2.3 Метод цепочек	7
2.4 Метод бинарного дерева	7
2.5 Результаты	7
3 Проектирование лексического анализатора	10
3.1 Исходные данные	10
3.2 Принципы работы лексических анализаторов	10
3.3 Схема распознавателя	11
3.4 Результаты	12
4 Построение дерева вывода	14
4.1 Исходные данные	14
4.2 Синтаксический анализатор	14
4.3 Результаты	18
5 Генерация и оптимизация объектного кода	20
4.1 Исходные данные	20
4.2 Построение списка триад	20
4.3 Генерация ассемблерного кода	21
4.4 Результаты	22
Заключение	23
Список использованных источников	24
Приложение А. Исходный текст программы

 

Введение

 

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

С одной стороны, компьютеры традиционной архитектуры умеют понимать только язык машинных команд. С другой стороны, разработчики не имеют возможности создавать прикладные и системные программы на уровне машинных кодов – слишком велик процент ошибок и непомерно велика трудоемкость такой работы. Поэтому давно возникла потребность в появлении "переводчиков" с различных языков программирования (языков ассемблера и языков высокого уровня) на язык машинных кодов. Такими переводчиками стали трансляторы. Есть и более узкое понятие подобного рода – "компилятор".

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

На этих принципах и технологиях построены все средства разработки, которые в настоящее время являются не просто трансляторами и компиляторами, а комплексами, представляющими собой системы программирования.

 

 

 

 

 

1 Задание

 

Курсовая работа заключается в создании компилятора с заданного подмножества языка Паскаль с незначительными модификациями и упрощениями (полное описание входного и выходного языков дано далее в задании для каждого варианта). Результатами курсовой работы являются программная реализация заданного компилятора и пояснительная записка, оформленная в соответствии с требованиями ГОСТ, стандартов Университета и задания на курсовую работу.

Компилятор рекомендуется построить из следующих составных частей:

1. лексический анализатор;
2. синтаксический анализатор;
3. оптимизатор;
4. генератор результирующего кода.

Для построения компилятора рекомендуется использовать методы, освоенные в ходе выполнения лабораторных работ по курсу «Системное программное обеспечение».

Входной язык компилятора должен удовлетворять следующим требованиям:

• входная программа начинается ключевым словом program и заканчивается ключевым словом end;
• входная программа может быть разбита на строки произвольным образом, все пробелы и переводы строки должны игнорироваться компилятором;
• текст входной программы может содержать комментарии любой длины, которые должны игнорироваться компилятором (вид комментария задан в варианте задания);
• входная программа должна представлять собой единый модуль, содержащий линейную последовательность операторов, вызовы процедур и функций не предусматриваются;
• должны быть предусмотрены следующие варианты операторов входной программы:
• оператор присваивания вида <переменная>:=<выражение>;
• условный оператор вида if <выражение> then <оператор>, либо if <выражение> then <оператор> else <оператор>;
• составной оператор вида begin … end;
• оператор цикла, предусмотренный вариантом задания;
• выражения в операторах могут содержать следующие операции (минимум):
• арифметические операции сложения (+) и вычитания (-);
• операции сравнения меньше (<), больше (>), равно (=);
• логические операции «и» (and), «или» (or), «нет» (not);
• дополнительные арифметические операции, предусмотренные вариантом задания;
• операндами в выражениях могут выступать идентификаторы (переменные) и константы (тип допустимых констант указан в варианте задания);
• все идентификаторы, встречающиеся в исходной программе, должны восприниматься как переменные, имеющие тип, заданный в варианте задания (предварительное описание идентификаторов в исходной программе не требуется);

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

В качестве выходного (результирующего) языка должен использоваться язык ассемблера процессоров типа Intel 80x86 в модификации встроенного языка ассемблера компилятора Pascal производства фирмы Borland.

Дополнительные условия, соответствующие варианту задания:

– дополнительные арифметические операции: сдвиги влево (<<) и вправо (>>);

– оператор цикла входного языка: repeat <оператор> until <выражение>;

– оптимизация: исключение лишних операций;

– тип данных: Word;

– тип комментария: комментарий в круглых скобках со «звездочкой»: (*…*).

Для выполнения курсовой работы использована среда программной разработки Microsoft Visual Studio .NET 2003 (язык C++) с дополнительно установленной библиотекой классов Trolltech Qt v4.0.1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Таблица идентификаторов

 

2.1 Исходные данные

 

Требуется написать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла.

Выданному варианту задания соответствует построение таблицы идентификаторов по методу цепочек. Для сравнения кроме предложенного метода реализуем построение таблицы идентификаторов по методу бинарного дерева. Для большей эффективности второй метод будет являться комбинированным.

 

2.2 Назначение таблиц  идентификаторов

 

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

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

 

2.3 Метод цепочек

 

Метод цепочек работает по следующему алгоритму:

Шаг 1. Во все ячейки хеш-таблицы поместить пустое значение, таблица идентификаторов пуста, переменная FreePtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов; i:=1.

Шаг 2. Вычислить значение хеш-функции ni для нового элемента Ai. Если ячейка хеш-таблицы по адресу ni пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе перейти к шагу 3.

Шаг 3. Положить j:=1, выбрать из хеш-таблицы адрес ячейки таблицы идентификаторов mj и перейти к шагу 4.

Шаг 4. Для ячейки таблицы идентификаторов по адресу mj проверить значение поля ссылки. Если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5; иначе j:=j+1, выбрать из поля ссылки адрес mj и повторить шаг 4.

Шаг 5. Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента Ai (поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки. Если больше нет идентификаторов, которые надо разместить в таблице, то выполнение алгоритма закончено, иначе i:=i+1 и перейти к шагу 2.

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

 

 

 

 

 

 

2.4 Метод бинарного дерева

 

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

Алгоритм построения таблицы идентификаторов методом бинарного дерева можно представить следующим образом:

Шаг 1. Считать первый элемент во входном списке, создать корневой узел, поместить в него первый элемент и перейти к шагу 4.

Шаг 2. Если текущий узел пуст, заносим в него значение поступившего на вход элемента и переходим к шагу 4.. Иначе переходим к шагу 3.

Шаг 3. Если значение в текущем узле совпадает с поступившим на вход элементом, данный элемент уже есть в таблице идентификаторов, перейти к шагу 4. Иначе сравнить элемент со значением в текущем узле. Если это значение меньше значения, хранимого в текущем узле, сделать текущим левый дочерний узел текущего узла и перейти к шагу 2. Иначе сделать текущим правый дочерний узел и перейти к шагу 2.

Шаг 4. Если больше нет идентификаторов, которые надо разместить в таблице, то выполнение алгоритма закончено, иначе считать следующий идентификатор и перейти к шагу 2.

В разрабатываемой программе комбинированный метод бинарного дерева реализуется в модуле BinTree. Иллюстрация структуры полученной таблицы идентификаторов приводится в видет отдельного диалогового окна, реализованного в модуле TreeDialog.

 

 

 

 

2.5 Результаты

 

Для тестирования программы выбран исходный текстовый файл следующего содержания:

asgsg

hgrhrw

hgrasd

qwrhgfhxd

gjedr

jrerjew

qfwqf

azz

zaa

fdjdkdfkfdkfd

grgqwfq

asfasgas

reh

fdjdk

asgsjsrw

j

dj

e

tfdjtrkee

r

rwyt

qewteww

qewsdgswhwe

qewfdhtejtrektr

qewfhe5jrjt

qewfghjtrhltreh

qewgfhnrdklhdr

qewfdgusri

qew

qewasaagasg

qwe

z

0

qwerty

shrwaweh

tfkedthswe

reujeje

tktrkr

tykrktl

trkytlyt

dtkiek

utltyl

tekyt

utltu

rytkiro

jtrekirk

krloyl

tujreihred

tejtrj

tjhtrjtr

hredjher

rgreg

reyrey

rejejrejr

redyreyrey

erjekjyrekytk

ewygewhuewrujrwj

yerasgg

eyrfdahsjhs

eyrfxjnfd

eryfxdhnsfdjh

yer

eyrzdkmfklfxjnd

 

В результате работы программы получены следующие данные:

– метод цепочек:

– всего сравнений: 181;

– в среднем сравнений: 2,87;

– метод бинарного дерева:

– всего сравнений: 504;

– в среднем сравнений: 8.

 

На основе полученных результатов можно сделать следующие выводы: даже при относительно небольшом количестве идентификаторов метод цепочек оказывается значительно эффективнее метода бинарного дерева. В нашем случае при использовании 63 идентификаторов среднее количество требуемых сравнений для метода бинарного дерева оказалось в 2,78 раза больше, чем для метода цепочек.

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