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

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

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

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

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

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

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

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

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

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

2009

Содержание

Введение

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

Глава 2. Реализация синтаксического анализатора полиномов в среде Visual Studio 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).

Определение делимости без остатка одного полинома (от одной переменной) на другой

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

Нахождение остатка от деления одного полинома на другой, очевидно, основано на операциях сложения и умножения полиномов. Поэтому для выполнения этого задания есть смысл воспользоваться процедурами сложения и умножения, описанных в пунктах 1.5 и 1.6.

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

Программа "Синтаксический анализатор" была написана на языке C# в среде Visual Studio 2005 [3, 4]. Язык С# - один из современных и широко используемых языков объектно-ориентированного программирования. Для реализации программы использовался шаблон Windows Forms Application, обеспечивающий наиболее удобный способ ввода и отображения информации. Для ввода полиномов использовался визуальный компонент ComboBox. Этот компонент удобен тем, что позволяет не только вводить свою собственную информацию (полином), но и использовать имеющуюся по умолчанию, что предпочтительно для демонстрации возможностей программы.

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

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

Интерфейс разработанной программы представлен на рис. 2.

1. Кнопка "Приведенный полином" строит по заданному полиному приведённый. Если это невозможно или полином уже приведенный, программа выдает сообщение.

2. Кнопка "Значение" позволяет по заданному полиному и целым значениям всех его переменных вычислить его значение. При отсутствии хотя бы одного значения переменной выдается сообщение об ошибке.

3. Кнопка "Произведение" позволяет по двум заданным приведённым полиномам построить третий, который является произведением двух первых.

4. Кнопка "Производная" позволяет по заданному приведённому полиному построить новый приведённый полином, который является производной первого полинома по заданной переменной.

5. Кнопка "Сумма" позволяет по двум заданным приведённым полиномам построить третий приведённый полином, который является суммой двух первых.

6. Кнопка "Деление" позволяет по двум заданным приведённым полиномам от одной переменной определить, делится ли первый полином на второй без остатка.

7. Кнопка "Однородность" позволяет по заданному полиному определить его однородность.

Рис. 2. Интерфейс программы "Синтаксический анализатор"

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

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

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

А

Б

Рис. 4. Демонстрация работы программы при делении одного полинома на другой (в случае полиномов от одной переменной (а) и от многих переменных (б))

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

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

Передо мной была поставлена дополнительная задача по определению простых чисел, не превосходящих заданного N, в двоичной записи которых содержится максимальное число единиц. Эта программа была реализована в среде MS Visual Studio 2005 на языке C++ в виде консольного приложения.

Алгоритм решения этой задачи включает три этапа:

1. поиск простых чисел, не превышающих заданного N;

2. преобразование десятичного вида простых чисел в бинарный вид;

3. поиск максимального числа единиц в бинарном представлении простых чисел.

Поиск простых чисел, не превышающих заданного N основан на алгоритме, называемом "Решето Эратосфена" [6]. Этот алгоритм заключается в следующем: берем число 2 и выбрасываем все числа кратные 2. Из оставшихся чисел оставляем наименьшее (в данном случае это число 3) и выбрасываем все числа кратные 3, и так далее. Если первое оставшееся число превышает , то работу прекращаем, поскольку все отобранные и оставшиеся числа являются простыми.

Преобразование десятичного вида простых чисел в бинарный вид реализован по следующей схеме. Для каждого простого числа берется строка длиной в 33 символа (размер переменной типа int, равный 4 байтам, умноженный на количество бит в одном байте, т. е. 8, и плюс один символ для "\0"). В нее заносятся нули или единицы. Затем для каждого простого числа выполняется поразрядный сдвиг вправо на количество бит от 31 до 0 с операцией поразрядное "и" (операция наложения маски вида 0x1). Сдвиг целого числа вправо на n разрядов эквивалентен целочисленному делению его на 2ⁿ. Результат этих операций сравнивается с 1 и в зависимости от истинности или ложности этого выражения увеличиваем счетчик единиц и заносим в строку 1 или увеличиваем счетчик нулей и заносим в строку 0 соответственно.

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

Ниже приведен код программы нахождения простых чисел, не превосходящих заданного N, с максимальным количеством единиц в бинарном представлении.

#include "stdafx.h"

#include <iostream>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int i, j, x;// счетчики

int *a, *b;

//ввод n

int n;

cout<<"Input n: "; cin>>n;

a = new int [n]; //массив натуральных чисел

b = new int [n]; //массив простых чисел

//массив натуральных чисел

for (i=1; i<=n; i++)

a[i]=i;

//поиск простых чисел

for (i=2; i<=sqrt((float)n); i++)

{

if (i==0) continue;

x=2*i;

while (x <= n)

{

a[x]=0;//зануляем непростые числа

x=x+i;

}

}

//массив простых чисел

for (i=2, j=0; i <= n; i++)

if (a[i] != 0)

{

b[j]=a[i];

j++;

}

//печать простых чисел

int s = j;

for (i=0; i < s; i++) cout<<b[i]<<" ";

cout<<endl;

int s1,s0;//кол-во единиц и кол-во нулей

//размер массива равен размеру числа, умноженному на кол-во бит в байте,

//т.е. 8, и 1 для закрывающего 0

char* str = new char[sizeof(n)*8+1];

//ставим закрывающий 0

str[sizeof(n)*8]='\0';

int s1max=0;//макс. кол-во единиц в простом числе

int bmax[100]; //массив с простыми числами, сод-щими макс. число единиц

int kmax=0;

j=0;//счетчик

//цикл по простым числам

for (int k = 0; k < s; k++)

{

s1 = 0;

s0 = 0;

//ставим закрывающий 0 в начало,

//чтоб потом можно было цеплять к концу 1 или 0

str[0]='\0';

//цикл по битам числа b[k]

for (int i = sizeof(b[k])*8-1; i >= 0; i--)

{

//b[k]>>i - побитовый сдвиг вправо на i бит

//0x1 - число 1 в бинарном представлении

//((b[k]>>i) & 0x1) == 1 - позволяет определить бинарный вид числа

if (((b[k]>>i) & 0x1) == 1)

{

s1++;//увелич. кол-во единиц

strcat(str,"1");//цепляем "1"

}

else

{

s0++; //увелич. кол-во нулей

strcat(str,"0");//цепляем "0"

}

}

cout<<b[k]<<" "<<str<<" kol-vo '1'="<<s1<<" kol-vo '0'="<<s0<<endl;

//поиск макс. числа единиц

if (s1>s1max)

{

s1max=s1;

//массив bmax заполняется числами по возрастанию кол-ва единиц

//в их двоичной записи

bmax[j]=b[k];

j++;

kmax=0;//кол-во чисел с макс. на текущий момент числом единиц

}

if (s1==s1max)

{

kmax++;//увелич., т.к. s1 равно s1max

//массив bmax заполняется числами по возрастанию кол-ва единиц

//в их двоичной записи

bmax[j]=b[k];

j++;

}

}

int jmax=j-1;//кол-во элементов в массиве bmax

//печать простых чисел, в двоичной записи которых

//содержится максимальное число единиц

cout<<endl;

cout<<"Result: "<<endl;

for (i=jmax; i>jmax-kmax; i--)

cout<<bmax[i]<<" ";

cout<<endl;

delete str;

delete a;

delete b;

system("PAUSE");

return 0;

}

Интерфейс программы приведен на рис. 5.

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

Заключение

За время выполнения курсовой работы я ознакомилась с основами синтаксического анализа (на примере анализа полинома), с основами программирования на языке C#, приобрела опыт разработки визуальных приложений в среде MS Visual Studio 2005. Разработанная мною программа осуществляет синтаксический анализ полиномов, и, в частности, преобразует заданный полином к приведенному виду, вычисляет его значение, определяет, является ли полином однородным, находит его производную по заданной переменной, строит сумму и произведение двух заданных приведенных полиномов, определяет делимость одного полинома на другой без остатка.

Кроме этого мною было выполнено дополнительное задание по определению простых чисел, не превосходящих заданного N, в двоичной записи которых содержится максимальное число единиц. Эта программа была реализована в среде MS Visual Studio 2005 на языке C++ в виде консольного приложения.

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

1. Ахо, А. В. Компиляторы: принципы, технологии и инструментарий, 2_е изд./ А. В. Ахо, М. С. Лам, Р. Сети, Д. Д. Ульман. - М.: Издательский дом "Вильямс", 2008.

2. Хантер, Р. Основные концепции компиляторов / Р. Хантер. - М.: Издательский дом "Вильямс" , 2002. - 256 с.

3. Баженова, И.Ю. Введение в программирование: Учебное пособие / И.Ю. Баженова, В.А. Сухомлин. - М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007. - 326 с.

4. Харт, Д.М. Системное программирование в среде Windows, 3-е издание: Пер. с англ./ Д.М. Харт. - М.: Издательский дом "Вильямс", 2005. - 592 с.

5. Бронштейн, И.Н. Справочник по математике / И.Н. Бронштейн, К.А. Семендяев. - М.: Наука, 1980. - 976 с.

6. Черемушкин, А.В. Лекции по арифметическим алгоритмам в криптографии. - М.: МЦНМО, 2002. - 104 с