">
Информатика Программирование
Информация о работе

Тема: Создание программного продукта в виде набора взаимодействующих модулей (Интерпретатор LISP-подобного языка)

Описание: Список требований заказчика. Функциональная спецификация. Вводимые функции. Проектная спецификация. Эксплуатационная документация.. Указания для работы с программой:. Проектная документация. Методы, которые используются в данной программе.
Предмет: Информатика.
Дисциплина: Программирование.
Тип: Курсовая работа
Дата: 15.08.2012 г.
Язык: Русский
Скачиваний: 3
Поднять уникальность

Похожие работы:

МИНОБРНАУКИ РОССИИ  Федеральное государственное бюджетное образовательное учреждение

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

"Московский государственный технический университет радиотехники,

электроники и автоматики"

МГТУ МИРЭА

  ФАКУЛЬТЕТ ИНФОРМАЦИОНЫХ ТЕХНОЛОГИЙ

 КАФЕДРА

ПРИКЛАДНОЙ МАТЕМАТИКИ

  КУРСОВОЙ ПРОЕКТ (РАБОТА)  по дисциплине  «Теория создания программного продукта»

  Тема курсового проекта (работы) «Создание программного продукта в виде набора

взаимодействующих модулей

(Интерпретатор LISP-подобного языка)»

 Студент группы ИТП-1-10

Чикина Анна Геннадьевна  Руководитель курсового проекта (работы)

Федотов Илья Евгеньевич  

     

Работа представлена к защите «__»_______2012 г. 

     «Допущен к защите» «__»_______2012 г. 

 

Форма задания на курсовой проект (работу)     МИНОБРНАУКИ РОССИИ  Федеральное государственное бюджетное образовательное учреждение

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

"Московский государственный технический университет радиотехники,

электроники и автоматики"

МГТУ МИРЭА

  ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КАФЕДРА

ПРИКЛАДНОЙ МАТЕМАТИКИ

    Утверждаю   Заведующий

Кафедрой Александр Борисович Самохин   «____» __________2012 г.  

ЗАДАНИЕ  на выполнение курсового проекта (работы)  по дисциплине «Теория создания программного продукта»    Студент Чикина Анна Геннадьевна Группа ИТП-1-10  Тема "Создание программного продукта в виде набора взаимодействующих модулей

(Интерпретатор LISP-подобного языка)”

 Исходные данные:        Перечень вопросов, подлежащих разработке, и обязательного графического материала:        Срок представления к защите курсового проекта (работы): до «___» _______2012 г.    Задание на курсовой

проект, (работу) выдал «___»______2012г. 

Федотов Илья Евгеньевич  Задание на курсовой

проект, (работу) получил «___»______2012г.  Чикина Анна Геннадьевна  

Рекомендуемая форма оборота листа задания на курсовой проект (работу)  5. Мониторинг процесса выполнения курсового проекта (работы)

№ этапа Этап курсового проекта, работы выполнил и представил результаты руководителю проекта (работы),

Работу по этапу курсового проекта (работы) принял на рассмотрение,

Рекомендации и замечания по
этапу курсового проекта (работы)
выдал
исполнителю,

Оценка выполнения этапа курсового проекта, (работы)
(в соответствии с балльно-рейтинговой системой) Комментарии
руководителя курсового проекта (работы)

 1       2       3       4       5       

Содержание

1. Список требований заказчика

2. Функциональная спецификация

3. Проектная спецификация

4. Эксплуатационная документация

5. Проектная документация

Приложение 1. Текст программы Список требований заказчика

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

Должны быть предусмотрены следующие встроенные функции:

Сложение: +

Вычитание: -

Умножение: *

Деление: /

Присваивание переменной значения: =

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

Функциональная спецификация

Данная консольная программа является транслятором инфиксных выражений в LISP-подобный язык.

В качестве входных параметров программа получает обычное алгебраическое выражение. Например:

a = (-3.4)

a * 2

c=( b / (-a) ) + (3.14 + 1.2 * (-a))/7

В транслятор могут вводиться:

Присваивания =

Различные арифметические знаки: +, - , * , /

Скобки ( , )

Десятичные положительные и отрицательные цифры -1.2, 3.1564

Положительные и отрицательные переменные ABC, -E

В результате работы, программа выведет выражение в LISP-подобной (префиксной) форме. Например:

#(=, a, -3.4)’

#( *, a, 2)’

#(=, c, #(+, #(/, b, -a), #(/,#(+, 3.14, #(*,1.2, -a),7))))’

Ограничения на вводимые функции:

Максимальная длина строки 1000 символов

Максимальная длина названия переменной 15 символов

Максимальная длина числа 15 символов

В десятичных числах вместо запятой используется точка

(Например выражению 3,14 соответствует 3.14)

В именах переменных могут использоваться только латинские символы.

В выражении не может быть более одного знака “=”

Отрицательные числа и переменные должны быть заключены в скобки. Например, выражению -2*2 соответствует (-2)*2

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

Проектная спецификация

.

Для реализации данной программы необходимо использовать за шаблон LISP-подобный язык. Формат перевода функции должен быть в виде:

#(имя_функции, параметр1, …)’

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

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

Исходные выражения в инфиксной форме принимаются программой построчно через stdin в строчную переменную.

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

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

4+5*6

6*5+4

4(56*)+

(*65)4+

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

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

Далее необходимо вывести полученное выражение в stdout и удалить рабочий дек.

Эксплуатационная документация

Указания для работы с программой:

1) Для начала работы нажмите на файл zapusk.bat.

2) Перед вами высветится черное консольное окно с надписью:

«Введите выражение. Максимальная длина 1000 символом».

3) В данное окно введите Ваше алгебраическое выражение, по описанным выше правилам (см. Функциональная спецификация) и нажмите Enter.

4) В случае, если программа выдает ошибку, перепроверьте правильность введенных данных.

Если ошибка «Проверьте баланс скобок», то следует проверить количество открывающихся и закрывающихся скобок

Если ошибка «Ошибка синтаксиса», то следует перепроверить правильность введенных переменных, знаков, точек и тд(см. Функциональная спецификация)

Далее следует повторить ввод выражения, исправив ошибки.

5) В случае, если выражение было введено правильно, то программа выведет на экран выражение в требуемой форме.

Если необходимо завершить работу программы, то нажмите крестик в левом верхнем углу.

Проектная документация

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

int main()

Рабочая функция, в которой происходит принятия потока в stdin построчно, считывает из нее функция cin.getline() в переменную string. Далее идет вызов функций: удаления пробелов(delite_space()), проверка баланса скобок(string_work()). В случае если проверка пройдена успешно, main передает строку в функцию работы со строкой (string_work()). В случае завершения работы, функция возвращает 0.

char *delite_space(const char *str)

В данной функции происходит удаление всех пробелов.

Создается строка(char *result), в которую копируется из string все, кроме пробелов. В результате работы функции возвращается строка result.

int bkt(char *str)

В данном методе идет подсчет баланса скобок.

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

int string_work(char *str)

В данной функции идет работа со строкой. Сначала вызывается функции проверки синтаксиса (check_syntax()). В случае, если проверка не пройдена, выдается сообщение об ошибке. Далее вызывается функция трансляции дека (translation() ) и вывод преобразованного выражения.

int check_syntax(char *str, deque & deq)

Функция проверяет, какого вида у нас выражение (a=b+c или b+c ). Далее она передает полученную строку во вторую часть проверки(proverka()), которая в свою очередь возвращает результат работы (true или false).

int proverka(char *str, int i, deque & deq )

В данном методе идет вызов функции деления строки на лексемы и проверка коррекции последовательности этих лексем. Выполнено на основе автомата Мура. Возвращает значения SUCCESS или FAIL.

void tokens(char *str, int k, deque & target )

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

int avtomat(char *str)

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

void translation(deque & deq, int st)

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

void reverse(deque & deq)

Данная функция инвертирует дек (записывает наоборот) .

void form_postfix(deque & deq)

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

void converter(deque & deq, int st)

В данном методе происходит правильная расстановка скобок, запятых и служебных символов. Расстановка идет с учетом того, какого вида является выражение (a=b+c или b+c ).

string rus(char s[ ])

Данная функция выполняет перевод строки Windows в Dos для удобства общения с пользователем.

Приложение 1. Текст программы.

#include

#include

#include

#include

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

студента: Чикина Анна

группа: ИТП-1-10

вариант: LISP-интерпретатор, вариант 1 */

enum {

START=0,

//конечные состояния

VARIABLE=1,

CIFRA=2,

MINUS=3,

PLUS=4,

UMN=5,

DEL=6,

OS=7,

ZS=8,

SPACE=32,

ZNAK=33,

SUCCESS=100,

FAIL=-1,

TOCHKA=19,

CIFRA_TOCHKA=20,

//переходные состояния

VARIABLE1=11,

CIFRA1=12,

MINUS1=13,

PLUS1=14,

UMN1=15,

DEL1=16,

OS1=17,

ZS1=18,

//вспомогательные состояния

S1=30,

S2=31,

WITHOUT=40,

//максимальная длина строки

max_str=1000,

//максимальная длина 1 переменной

max_p=16

};

string rus(char s[ ]) //переводит кодировку выводимой строки Windows в Dos

{

string t;

int i=0;

t=s;

while (s[i]!=0)

{

if(s[i]>=А&& s[i]<=п ) t[i]-=64;

if(s[i]>=р&& s[i]<=я ) t[i]-=16;

if(s[i]==Ё )t[i]=240;

if(s[i]==ё ) t[i]=241;

i++;

}

return t;

}

//удаление лишних пробелов

char *delite_space(const char *str)

{

char *result = new char [max_str];

int i = 0, j = 0;

while (str[i] != )

{

if (str[i] != )

{

result[j] = str[i];

j++;

}

i++;

}

result[j] = ;

return result;

}

//проверка баланса скобок

int bkt(char *str)

{

int i=0;

int count=0; // счетчик скобок

while(str[i]!=)

{

if(str[i]==()

count++;

if(str[i]==))

{

count--;

if (count < 0)

return 1;

}

i++;

}

return count;

}

//выделение лексемы и запись ее в дек.

void tokens(char *str, int k, deque & target )

{

int i=k;

while(str[i]!=)

{

char *slovo = new char[max_p];

int j=0;

if(str[i]==( && str[i+1]==-)

{

i++;

while (str[i]!=) )

{

slovo[j]=str[i];

i++;

j++;

}

slovo[j]=;

i++;

}

else

{

if( isalpha(str[i]) || isdigit(str[i]) )

{

while( isalpha(str[i]) || isdigit(str[i]) ||

str[i]==. )

{

slovo[j]=str[i];

i++;

j++;

}

slovo[j]=;

}

else

{

slovo[j]=str[i];

slovo[j+1]=;

i++;

}

}

target.push_back(slovo);

}

target.push_back("");

}

//функция проверяет коррекцию каждого отдельного слова

int avtomat(char *str)

{

int state=START;

int idx=0;

while(state!=CIFRA && state!=VARIABLE && state!=MINUS &&

state!=PLUS && state!=UMN && state!=DEL &&

state!=OS && state!=ZS && state!=FAIL && state!=SUCCESS)

{

switch(state)

{

case START:

state=(isdigit(str[idx]))? CIFRA1:

(isalpha(str[idx]))? VARIABLE1:

(str[idx]==-)? MINUS1:

(str[idx]==+)? PLUS1:

(str[idx]==*)? UMN1:

(str[idx]==/)? DEL1:

(str[idx]==()? OS1:

(str[idx]==))? ZS1:

(str[idx]== || str[idx]== )? SUCCESS: FAIL;

break;

case CIFRA1:

state=(isdigit(str[idx]))? CIFRA1:

(str[idx]==.)? TOCHKA:

(str[idx]== || str[idx]== )? CIFRA: FAIL;

break;

case VARIABLE1:

state=(isalpha(str[idx]))? VARIABLE1:

(str[idx]== || str[idx]== )? VARIABLE: FAIL;

break;

case MINUS1:

state=(isdigit(str[idx]))? CIFRA1:

(isalpha(str[idx]))? VARIABLE1:

(str[idx]== || str[idx]== )? MINUS: FAIL;

break;

case PLUS1:

state=(str[idx]== || str[idx]== )? PLUS: FAIL;

break;

case UMN1:

state=(str[idx]== || str[idx]== )? UMN: FAIL;

break;

case DEL1:

state=(str[idx]== || str[idx]== )? DEL: FAIL;

break;

case OS1:

state=(str[idx]== || str[idx]== )? OS: FAIL;

break;

case ZS1:

state=(str[idx]== || str[idx]== )? ZS: FAIL;

break;

case TOCHKA:

state=(isdigit(str[idx]))? CIFRA_TOCHKA: FAIL;

break;

case CIFRA_TOCHKA:

state=(isdigit(str[idx]))? CIFRA_TOCHKA:

state=(str[idx]== || str[idx]== )? CIFRA: FAIL;

break;

}

idx++;

}

return state;

}

/*в функции идет вызов функции деления строки на лексемы,

и проверка правильной последовательности этих лексем */

int proverka(char *str, int i, deque & deq )

{

char *st=new char[max_p];

int s;

tokens(str, i, deq); //деление на лексемы

int j=0;

int state = START;

//в st хранится слово, в s - результат проверки слова

while(state!=SUCCESS && state!=FAIL)

{

if(j>deq.size())

{

state=FAIL;

}

else

{

st = deq[j];

s=avtomat(st); //проверка каждой лексемы

switch(state)

{

case START:

case OS:

state=(s==CIFRA)? CIFRA1:

(s==VARIABLE)? VARIABLE1:

(s==OS)? OS: FAIL;

break;

case CIFRA1:

case VARIABLE1:

state=(s==MINUS || s==PLUS ||

s==UMN || s==DEL )? ZNAK:

(s==SUCCESS)? SUCCESS: FAIL;

break;

case ZNAK:

state=(s==CIFRA)? CIFRA:

(s==VARIABLE)? VARIABLE:

(s==OS)? OS: FAIL;

break;

case CIFRA:

case VARIABLE:

case ZS:

state=(s==MINUS || s==PLUS ||

s==UMN || s==DEL )? ZNAK:

(s==ZS)? ZS:

(s==SUCCESS)? SUCCESS: FAIL;

break;

}

j++;

}

}

return state;

}

/*функция проверяет, какого вида выражение:

a=b+c или b+c и т.д. */

int check_syntax(char *str, deque & deq)

{

//проверка начала синтаксиса:

int state=START;

int idx=0;

while(state!=S1 && state!=WITHOUT)

{

switch(state)

{

case START:

state=(isalpha(str[idx]))? VARIABLE: WITHOUT;

break;

case VARIABLE:

state=(isalpha(str[idx]))? VARIABLE:

(str[idx]=== && str[idx+1]!==)? S1 : WITHOUT;

break;

}

idx++;

}

//вызов второй части проверки

if(state == S1)

{ //если выражение вида: a=b+c

state=proverka(str, idx, deq);

}

if(state == WITHOUT)

{ //если выражение вида: b+c

idx=0;

state=proverka(str, idx, deq);

if(state!=FAIL)

state=WITHOUT;

}

return state;

}

//функция реверсии записи

void reverse(deque & deq)

{

deque d(deq);

int j=0;

for (int i=deq.size()-1; i>=0; i--)

{

if (deq[i][0]==()

d[j]=")";

else

if (deq[i][0]==))

d[j]="(";

else

d[j]=deq[i];

j++;

}

d.push_back("%");

d.pop_front(); //удалили первый элемент, т.к. там был ""

deq=d;

d.clear();

}

//запись в постфиксную систему

void form_postfix(deque & deq)

{

deque result;

deque znaki;

char *st = new char;

int i=0;

znaki.push_back("%");

while(deq[i][0]!=%)

{

//если в деке открывающаяся скобка

if(deq[i][0]==()

znaki.push_back("(");

else //если в деке закрывающаяся скобка

if(deq[i][0]==))

{

st=znaki.back();

znaki.pop_back();

while(st[0]!=()

{

result.push_back(st);

st=znaki.back();

znaki.pop_back();

}

}

else //если в деке арифметические знаки + или -

if( (deq[i][0]==+ || deq[i][0]==-) && deq[i][1]== )

{

st=znaki.back();

znaki.pop_back();

if(st[0]==%||st[0]==()

{

znaki.push_back(st);

znaki.push_back(deq[i]);

}

else

if (deq[i][0]==+ || deq[i][0]==-|| deq[i][0]==* || deq[i][0]==/)

{

result.push_back(st);

znaki.push_back(deq[i]);

}

}

else //если в деке аривметические знаки * или /

if(deq[i][0]==*|| deq[i][0]==/)

{

st=znaki.back();

znaki.pop_back();

if ( st[0]==%||st[0]==(||st[0]==+||st[0]==- )

{

znaki.push_back(st);

znaki.push_back(deq[i]);

}

if (st[0]==*||st[0]==/)

{

if(st[0] == * && deq[i][0] == /)

{

znaki.push_back(st);

znaki.push_back(deq[i]);

}

else

{

result.push_back(st);

znaki.push_back(deq[i]);

}

}

}

else

result.push_back(deq[i]);

i++;

}

st=znaki.back();

znaki.pop_back();

//кладем в резуьтивный стек оставшиеся знаки

while (st[0]!=%)

{

result.push_back(st);

st=znaki.back();

znaki.pop_back();

}

deq=result;

result.clear();

znaki.clear();

}

//функция расставляет в правильном порядке скобки, запятые и #

void converter(deque & deq, int st)

{

deq.push_front("%"); // добавили в начало знак конца

int i=deq.size()-1;

deque d;

int state; // если S1 - то первый параметр функции, если S2 – то второй

int brk; // количество открытых скобок

if(st==WITHOUT)

{

state = S1;

brk = 0;

}

else

{

state = S2;

brk = 1;

}

while (deq[i][0]!=%)

{

if ( (deq[i][0]==+ || deq[i][0]==- ||

deq[i][0]==* || deq[i][0]==/) && deq[i][1]==)

{

if (state == S2)

d.push_back(",");

d.push_back("#");

d.push_back("(");

d.push_back(deq[i]);

d.push_back(",");

state = S1;

brk++;

}

else

{

if (state == S2)

{

d.push_back(",");

d.push_back(deq[i]);

d.push_back(")");

brk--;

}

else if (state == S1)

{

d.push_back(deq[i]);

state = S2;

}

}

i--;

}

while (brk>0)

{

d.push_back(")");

brk--;

}

deq=d;

d.clear();

}

//последовательно вызываются функции

void translation(deque & deq, int st)

{

deque d(deq); //рабочий дек

reverse(d); //запись наоборот

form_postfix(d); //перевод в постфиксную систему

converter(d, st); //расстановка скобок

deq = d;

d.clear();

}

//функция работы со строкой

int string_work(char *str)

{

deque deq;

int state = check_syntax(str, deq); //вызываем функцию проверки синтаксиса

if(state==FAIL)

{

cerr< system ("PAUSE");

}

else

{

translation(deq,state); //вызываем функцию трансляции дека

if(state!=WITHOUT)

{ // записали имя переменной слева от знака присвоения

char *st = new char [max_p];

int i = 0;

while (str[i] != =)

{

st[i] = str[i];

i++;

} st[i] = ;

//дописали в начало очереди начало выходной строки вида #(=,a

deq.push_front(st);

deq.push_front(","); //добавили остальные знаки

deq.push_front("=");

deq.push_front("(");

deq.push_front("#");

}

//вывод дека

deq.push_back("");

while (!deq.empty())

{

cout << deq[0];

deq.pop_front();

}

}

cout<< ;

deq.clear();

return 0;

}

int main()

{

char *string = new char[max_str];

cout<

while(!feof(stdin))

{

cin.getline(string,max_str, );

if(strcmpi(string, "")!=0)

{

string=delite_space(string); //удаление пробелов

if(bkt(string)!=0)

{

cerr< system ("PAUSE");

}

else

{

string_work(string);

cout << ;

}

}

}

return 0;

}