Смекни!
smekni.com

Синтаксический анализатор полиномов (стр. 1 из 3)

Федеральное агентство по образованию РФ

Федеральное государственное образовательное

учреждение высшего профессионального образования

"ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ"

Факультет математики, механики и компьютерных наук

Кафедра информатики и вычислительного эксперимента

Курсовая работа

Синтаксический анализатор полиномов

Ростов-на-Дону

2009


Содержание

Введение

Глава 1. Алгоритм для реализации синтаксического анализатора полиномов

Глава 2. Реализация синтаксического анализатора полиномов в среде VisualStudio 2005 на языке C#

Глава 3. Тестирование разработанной программы и обсуждение результатов

Глава 4. Дополнительное задание по анализу двоичного кода простых чисел

Заключение

Список литературы



Введение

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

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

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


Глава 1. Алгоритм для реализации синтаксического анализатора полиномов

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

полином ::= '0' | одночлен | одночлен ('+'|'-') полином

одночлен ::= '1' | коэффициент | коэффициент произведение

произведение ::= множитель | множитель произведение

множитель ::= переменная | переменная '^' показатель

переменная ::= буква пробел

коэффициент ::= префикс | префикс целое-без-знака

целое-без-знака ::= цифра | цифра целое-без-знака

префикс ::= больше-1 | больше-0 цифра

больше-0 ::= '1' | больше-1

больше-1 ::= '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

цифра ::= '0' | больше-0

показатель ::= больше-1 | '1' цифра

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

Для выполнения перечисленных заданий необходимо провести синтаксический разбор исходных полиномов (или одного полинома), в результате которого будет извлечена информация о количестве одночленов, количестве и наименовании переменных, входящих в состав всех одночленов, их коэффициентах, а также показателях степеней переменных. Поскольку количество одночленов в полиноме и количество множителей-переменных в одночленах может быть произвольным, имело смысл использовать динамические структуры данных – списки [3, 4], позволяющие легко добавлять, удалять и упорядочивать содержащуюся в них информацию. Ниже приводятся краткие описания использованных алгоритмов для решения поставленных задач по анализу полиномов.

Преобразование полинома к приведенному виду

Одной из основных операций, которую должна реализовывать разрабатываемая программа, является преобразование полинома к приведенному виду. Полином называется приведённым, если в каждом его одночлене каждая из его переменных встречается не более одного раза, и нет подобных одночленов [5].

Последовательность операций по разбору и преобразованию полинома к приведенному виду, используемая в программе (функция ToReducedPol), схематически представлена на рис. 1 и включает следующее:

1. Разбор исходного полинома на слагаемые – одночлены;

2. Разбор каждого одночлена на коэффициент и множители (переменные в заданной степени).

3. Приведение подобных множителей в пределах каждого одночлена. Для этого выполняем следующие операции для каждого одночлена:

a) Разбор одночлена на переменные в заданной степени и занесение их в список.

b) Сортировка переменных в заданной степени в алфавитном порядке.

c) Разбор каждой переменной в заданной степени на переменную и соответствующий ей показатель степени и занесение их в список.

d) Анализ и обработка списка переменных (функция WithoutSimilarPowers): если встречаются одинаковые переменные, суммируем их показатели степени и полученной суммой заменяем в списке показатель степени одной из одинаковых переменных, другую переменную и соответствующий ей показатель степени удаляем из списков. При этом функция WithoutSimilarPowers возвращает значение False. В случае если подобных множителей в одночлене нет, функция WithoutSimilarPowers возвращает значение True.

e) Сборка переменных в заданной степени в их произведение – приведенный одночлен без коэффициента: переменные в нем теперь упорядочены по алфавиту и встречаются только один раз.

4. Приведение подобных одночленов в пределах всего полинома. Для этого выполняем следующие операции:

a) Анализ и обработка списка приведенных одночленов без коэффициентов (функция WithoutSimilarCoeffs): если встречаются одинаковые одночлены, суммируем их коэффициенты и полученной суммой заменяем в списке коэффициент одного из одинаковых одночленов, другой одночлен и соответствующий ему коэффициент удаляем из списков. При этом функция WithoutSimilarCoeffs возвращает значение False. В случае если подобных одночленов в полиноме нет, функция WithoutSimilarCoeffs возвращает значение True.

b) Собираем одночлены без коэффициентов и соответствующие им коэффициенты в полноценные одночлены

5. Сборка одночленов в приведенный полином. В случае если подобных множителей в одночлене и одночленов в полиноме не было, функция ToReducedPolвозвращает True, в противном случае – False).

Определение однородности полинома

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

Для работы с показателями степеней переменных, входящих в состав одночленов приведенного полинома, использовался динамический массив Powers,где первый индекс массива указывает номер одночлена, а второй – номер переменной в одночлене (переменные входят в одночлены приведенного полинома в алфавитном порядке).

Рис.1 Последовательность операций по разбору и преобразованию полинома к приведенному виду


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

Вычисление значения полинома

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

Информация о коэффициентах одночленов приведенного полинома хранится в списке коэффициентов CoeffList, а информация о показателях степеней переменных в каждом одночлене в двумерном массиве Powers, где первый индекс массива указывает номер одночлена, а второй – номер переменной в одночлене (переменные входят в одночлены приведенного полинома в алфавитном порядке). В случае если переменная из списка всех переменных полинома VarListне входит в данный одночлен, ее степень по умолчанию равна нулю.

Вычисление значения полинома осуществляется в двойном цикле путем перебора во внешнем цикле всех одночленов полинома, а во внутреннем – всех переменных в одночлене.

Нахождение полинома-производной исходного полиномапо заданной переменной

Полином-производная исходного полинома по заданной переменной формируется путем преобразования копий массива показателей степеней исходного полинома Power_dи списка коэффициентов его одночленов CoeffList_d по правилам дифференцирования степенных функций.

По преобразованному массиву степеней и списку коэффициентов строится искомый полином-производная.

Построение приведенного полинома-суммыдвух заданных полиномов

Построение приведенного полинома-суммы двух заданных полиномов осуществлялось в два этапа. На первом этапе две строки с заданными полиномами склеивались в один новый, в общем случае, неприведенный полином. На втором этапе осуществлялось преобразование этого полинома к приведенному виду по процедуре, описанной в пункте 2.1 (использовалась функция ToReducedPol).

Построение приведенного полинома-произведениядвух заданных полиномов

Построение приведенного полинома-произведения двух заданных полиномов осуществлялось в три этапа. На первом этапе производился разбор каждого из заданных полиномов на список коэффициентов и список одночленов без коэффициентов. На втором этапе формировался список коэффициентов, рассчитанных по коэффициентам одночленов исходных полиномов согласно правилам перемножения многочленов, а также список одночленов без коэффициентов, которые склеивались из одночленов без коэффициентов исходных полиномов. На третьем этапе из полученных списков коэффициентов и одночленов без коэффициентов осуществлялась сборка неприведенного полинома-произведения. На четвертом этапе производилось преобразование этого полинома к приведенному виду по процедуре, описанной в пункте 1.1 (использовалась функция ToReducedPol).