Разработка программного приложения для решения информационно–логических задач

КП — НТИ СевКавГТУ — 230 201.65.ОН. 174- 11

Разрабoтка программного приложения для решения инфoрмационно — лoгических задач Кубота Александр Сергеевич ИС-091

Сoдержание

1. Разработка технического задания на проектирование

1.1 Общая постановка задачи

1.2 Определение требований к программе

1.3 Предварительный выбор метода решения задачи

1.4 Определение требований к системе

1.4.1 Требoвания к системе в целом

1.4.2 Требования к техническому и программному обеспечению

1.4.3 Требoвания к программному обеспечению

2. Проектирование программного приложения

2.1 Разработка технологии обработки информации

2.2 Разработка структуры и формы представления данных

2.3 Разработка алгоритма решения задачи

2.4 Разработка программы решения задачи

2.4.1 Выбор инструментальных средств

2.4.2 Разработка структуры программы

2.4.3 Проектирование программных модулей

2.4.4 Проектирование программного интерфейса

2.5 Определение конфигурации технических средств

2.6 Тестирование программы

2.6.1 Общие сведения

2.6.2 Процесс тестирования программы

2.6.3 Оценка надежности программы Заключение Список использованных источников Приложение А. Блок-схема алгоритма программы анализа арифметического выражения Приложение Б. Блок-схема алгоритма анализа текста простой программы на языке С Приложение В. Исходный код программы анализа арифметического выражения Приложение Г. Исходный код простой программы синтаксического анализа простой программы на языке С

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

Одной из важнейших информационно — логических задач является синтаксический анализ текста.

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

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

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

1. Разработка технического задания на проектирования

1.1 Общая постановка задачи

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

1) синтаксический анализ простой программы на языке С;

2) форматирование текста программы на языке С.

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

1) Описание библиотек;

2) Описание переменных;

3) Арифметические и логические выражения;

4) Операторы;

5) Функции ввода и вывода;

6) Однострочные и многострочные комментарии.

1.2 Определение требований к программе

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

— проверка правильности синтаксиса написания простой программы на языке С;

— проверка, является ли введенная логическая функция совершенной конъюнктивной нормальной функцией (СКНФ).

Требование к надежности:

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

Требования к информационной и программной совместимости:

— для запуска программы необходимо использовать среду Microsoft Visual Studio 2008.

1.3 Предварительный выбор метода решения задачи

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

В процессе синтаксического анализа обязательно должны проверяться:

— разделение операторов символом «;»;

— парность скобок «(…)», «[…]», «{…}»;

— правильность оформления комментариев «/*…*/»;

— переменные должны состоять из одного символа латинского алфавита «a, b… z»;

— правильность присвоения данных переменным «:=».

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

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

Для проверки функции на правильность написания СКНФ необходимо проверять:

— парность скобок «(…)»;

— правильность написания конъюнкций «…)&(…»;

— правильность написания дизъюнкций «(…|…)»;

— правильность написания отрицания элементов «!a… a».

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

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

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

:= - определение понятия;

?? — ограничители терминалов;

< > - ограничители нетерминалов;

| - конструкция «или»;

[ ] - повторение 0 или 1 раз;

{ } - повторение 0 или более раз;

() — группировка;

? — пустая синтаксическая цепочка;

. — завершение формы.

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

Рисунок 1 — Обозначения элементов синтаксических диаграмм

Ниже приведены РБНФ и синтаксические диаграммы упрощенного определения нетерминала «выражения языка С»:

<�Выражение языка C> :=

<�Выражение> «) <�Выражение>.

Рисунок 2 — РБНФ для анализа СКНФ

<�СКНФ> :=

<�Выражение> «(«.

Рисунок 3 — РБНФ для анализа арифметического выражения

Синтаксический разбор выражения будет осуществляться посимвольно.

1.4 Определение требований к системе

1.4.1 Требования к системе в целом

К общим требованием в эксплуатации данного программного приложения можно отнести:

— квалификация персонала может находиться на уровне пользователя ПК;

— знание назначения данного программного обеспечения;

— знание основ синтаксиса языка С.

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

Условия эксплуатации:

— знать и правильно указывать путь к файлу программы;

— правильность ввода функции СКНФ, с содержанием специальных символов (| - дизъюнкция, & - конъюнкция, ! — отрицание);

— правильность ввода данных с учетом регистра.

1.4.2 Требования к техническому обеспечению

Технические требования:

— устройства ввода и вывода информации, такие как клавиатура и монитор;

— процессор класса Pentium 3 и выше;

— объем оперативной памяти не менее 128 Мб;

— от 500 Мб свободного места на жестком диске, для обеспечения запуска и работы программы;

— встроенный графический чип или видеоплата.

1.4.3 Требования к программному обеспечению

Система должна работать на IBM совместимых персональных компьютерах.

Наличие операционной системы Windows версии 5.1 и выше с установленным Net Framework версии 3.5 и выше. Наличие программного обеспечения для ввода и вывода данных.

2. Проектирование программного приложения

2.1 Разработка технологии обработки информации

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

— создание файла с текстом простой программы;

— размещение файла на носителе;

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

Структура технологического процесса:

— считать с экрана пользователя введенную функцию СКНФ;

— посимвольно провести синтаксический анализ введенной функции;

— считать файл .txt с программой;

— удалить из файла все комментарии и многострочные и однострочные;

— провести синтаксический и арифметический анализ каждой строки.

Необходимо использование соглашений:

— объявление переменных типа int должно сопровождаться обязательной инициализацией числовой переменной, может объявляться как отдельно, так и сразу несколько переменных вместе;

— все конструкции языка разделяет один пробел, обязательно ставится «;» в конце строки там, где это предусмотрено синтаксисом языка С;

— наименование всех переменных может обозначаться только одной буквой латинского алфавита [a…z];

— в одной строке может размещаться только один оператор;

алгоритм программа модуль

— в программе не должны использоваться сложные арифметические выражения.

2.2 Разработка структуры и формы представления данных

Загрузка текста программы для проверки осуществляется из файла. Предварительной подготовкой является:

— создание файла с текстом простой программы;

— размещение файла на носителе;

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

— считать файл .с с программой;

— построчно провести синтаксический анализ введенной функции;

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

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

2.3 Разработка алгоритма решения задачи

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

2.4 Разработка программы решения задачи

2.4.1 Выбор инструментальных средств

На выбор языка С повлияло то что он содержит простые средства для обработки текстовых данных, а так же то что он наиболее прост в изучении. Были выбраны регулярные выражения для проверки операторов. Остальной текст программы было решено разбирать посимвольно.

2.4.2 Разработка структуры программы

Основными функциями программы является синтаксический и арифметический анализ текста. Программа состоит из частей:

— вывод на экран пользователя меню, для выбора проверки СКНФ или проверки синтаксиса программы;

— при выборе пункта меню «проверка СКНФ» пользователем вводится функция для проверки. Программой производится посимвольный разбор введенной функции, после чего выводится сообщение с ответом, является или нет введенная функция СКНФ, и выводит подменю с возможностью повторного ввода функции или перехода в главное меню;

— при выборе пункта меню «проверка синтаксиса программы», пользователю необходимо будет указать место хранения проверяемого файла (d:programma.txt), после чего программа будет часть программы проверять посимвольно, а часть построчно, после чего на экран пользователя выведется сообщение об ошибке, либо если в случае правильности написания программы будет выдано сообщение о правильности проверяемой программы, затем будет выведено подменю с возможностью повторной проверки программы, либо переход в главное меню.

2.4.3 Проектирование программных модулей

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

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

— для второй части необходимо считать путь к файлу и обработать;

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

2.4.4 Проектирование программного интерфейса

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

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

— запуск программы пользователя с указанием имени файла, обработка и вывод результата;

— выход из программы.

Программа будет всегда выводит пользователю отформатированные данные:

— «Данная функция является СКНФ»;

— «Данная функция не является СКНФ из-за неверного количества скобок»;

— «Данная функция не является СКНФ из-за неверно введенной конъюнкции»;

— «Данная функция не является СКНФ из-за неверно введенной дизъюнкции»;

— «Данная функция не является СКНФ из-за несоответствия элементов функции»;

— «Ошибок нет!»;

— «Ошибка: коментарии — /* */»;

— «Ошибка: фигурные скобки — { }»;

— «Ошибка: с оператором — do while»;

— «Ошибка: в вункциях оператора…»;

— «Ошибка: Break»;

— «Ошибка: с оператором Switch».

2.4.5 Обеспечение надежности программы

Данная программа не нуждается в защите от сбоев, так как информация не хранится.

2.5 Определение конфигурации технических средств

— устройства ввода и вывода информации, такие как клавиатура и монитор;

— процессор класса Pentium 3 и выше;

— объем оперативной памяти не менее 128 Мб;

— от 500 Мб свободного места на жестком диске, для обеспечения запуска и работы программы;

— встроенный графический чип или видеоплата.

2.6 Тестирование программы

2.6.1 Общие сведения

Контрольными данными является файл с информацией, который обладает следующими свойствами:

— описание переменных типа int;

— арифметические операции (a|b|c)&(!a|!b|c)&(a|!b|c);

— операторы: if. goto, do. while, switch;

— комментарии;

2.6.2 Процесс тестирования программы

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

— создать файл на носителе;

— заполнить его данными;

— запустить программу, указав путь к файлу;

— подождать вывода программы;

— ввести функцию СКНФ;

— подождать вывода программы;

— сравнить полученные результаты с теоретическими.

2.6.3 Оценка надежности

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

Заключение

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

— синтаксический анализ простой программы на языке С;

— форматирование текста программы на языке С.

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

— создание файла с текстом простой программы;

— размещение файла на носителе;

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

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

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

— запуск программы пользователя с указанием имени файла, обработка и вывод результата;

— выход из программы.

При тестировании программы выданы были верные результаты.

1. Иванова, Г. С. Технология программирования [Текст]: Учебник для вузов / Иванова Г. С. — М.: Изд-во МГТУ им. Н. Э. Баумана, 2002. — 320 с.: ил. — (Информатика в техническом университете). — ISBN 5−7038−2077;4.

2. Полный справочник по С. Четвертое издание [Текст]: Пер. с англ./ Шилдт, Герберт. — М.: Издательский дом «Вильямс», 2002. — 704 с.: ил. — Парал. Тит. Англ. — ISBN 5−8459−0226−6 (рус.).

3. Теория и реализация языков программирования [Электронный ресурс] / Интернет-Университет Информационных технологий. — Электрон. текст. дан. — Режим доступа: http//www.INTUIT.ru, свободный.

Приложение А

Блок-схема решения задачи арифметического анализа

Приложение Б

Блок-схема алгоритма задачи синтаксического анализа

Приложение В

Исходный код программы арифметического анализа

#include

int main ()

{

char *dnf="a&b|b&c" ;

int form[255][255];

int j;

j=0;

int k;

k=0;

int dnfsize;

dnfsize=0;

do

{

dnfsize=dnfsize+1;

}

while (dnf[dnfsize]≠'');

int max;

max='a';

int neqzero;

neqzero=0;

int flag;

flag=0;

for (int i=0 ;i<=dnfsize; i=i+1)

{

if (dnf[i]=='|')

{

k=k+1;

j=0;

}

if (i≠0 && dnf[i]≠'|' && dnf[i]≠'&')

{

form[j][k]=dnf[i];

j=j+1;

if (dnf[i]≠'&')

if (max

max=dnf[i];

}

}

int z;

z=max-'a'+1;

int pow;

pow=1<

int table2[pow];

for (int i=0;i

table2[i]=0;

for (int i=0;i

{

int table[z];

for (int j=0;j

table[j]=2;

int nm;

nm=0;

for (int j=0;form[j][i]; j=j+1)

{

int hgy;

hgy=form[j-1][i];

if (j==0||hgy=='|')

{

if (form[j][i]=='!')

{

int nmb;

nmb=form[j+1][i]-'a';

if (table[nmb]==1)

nm=1;

if (table[nmb]==2)

table[nmb]=0;

if (form[j][i]≠'!')

{

int nmb;

nmb=form[j][i]-'a';

if (table[nmb]==0)

nm=1;

if (table[nmb]==2)

table[nmb]=1;

}

}

}

if (nm==0)

{

neqzero=1;

for (int j=0;j

{

int show;

show=1;

for (int k=0;k

{

if (table[k]≠2)

if (table[k]==1)

int r;

r=1<

int e;

e=j

if (table[k]==0)

{

// заполнение числа 1 и отнимание 1 сдвинутой на к влево

int jh;

jh=max-'a'+2;

int jj;

jj=1<

int jk;

jk=1<

int exp;

exp=j&jj-1-jk;

if (exp≠j)

show=0;

}

}

if (show==1)

if (table2[j]==0)

{

table2[j]=1;

switch (flag)

{

case 1:

printf («) & («);

break;

case 0:

printf («(«);

flag=1;

break;

}

for (int k=0;k

1<

if (hg≠j)

printf («!»);

printf («%c», k+'a');

}

}

}

}

switch (neqzero)

{

case 0:

printf («1»);

break;

case 1:

printf («) n»);

break;

}

system («pause»);

}

Приложение Г

Исходный код программы синтаксического анализа простой программы на языке С

using System;

using System.Collections.Generic;

using System. IO;

using System. Text;

class Program

{

static List vars = new List ();

static List uvars = new List ();

static List labels = new List ();

static List nlabels = new List ();

static void test (string expr, string line)

{

if (expr.EndsWith («++») || expr. EndsWith («—»))

{

if (!(vars.IndexOf (expr.Substring (0, expr. Length — 2)) > -1))

{

Console.Error.WriteLine («Переменая {0} не обьявлена в выражении {1}, строке {2}», expr. Substring (0, expr. Length — 2), expr, line);

}

return;

}

string[] nvars = expr. Split (new String[] { «+», «-», «*», «<», «>», «==», «≠», «=» }, StringSplitOptions. None);

foreach (string var in nvars)

{

if (var ≠ «»)

{

try

{

Convert.ToDouble (var);

}

catch (FormatException)

{

if (vars.IndexOf (var) > -1)

uvars.Add (var);

else

Console.Error.WriteLine («Переменая {0} не обьявлена в выражении {1}, строке {2}», var, expr, line);

}

}

else

Console.Error.WriteLine («В выражении {0} не хватает операндов, в строке {1}», expr, line);

}

}

static void Main (string[] args)

{

string path = args[1];

StreamReader read = new StreamReader (path);

string code = read. ReadToEnd ();

while (code.IndexOf («(») ≠ -1)

code = code. Replace («(», «(«);

string tmp_code = «», tmp = «» ;

bool in_for = false;

for (int i = 0; i < code. Length; i++)

{

if ((code[i] == '}') || (code[i] == '{'))

{

tmp += «n» ;

}

tmp += code[i];

if (in_for == true)

if (code[i] == ')')

{

tmp_code += «n» + tmp. Trim ();

tmp = «» ;

tmp_code = tmp_code.Trim ();

in_for = false;

}

if (in_for == false)

if (tmp.Trim () == «else»)

{

tmp_code += «n» + tmp. Trim () + «n» ;

tmp_code = tmp_code.Trim ();

tmp = «» ;

in_for = false;

}

else if (code[i] == ';')

{

if (tmp.Trim ().StartsWith («for (»))

{

in_for = true;

}

else

{

tmp_code += «n» + tmp. Trim ();

tmp_code = tmp_code.Trim ();

tmp = «» ;

}

}

if ((code[i] == '}') || (code[i] == '{'))

{

tmp_code += «n» + tmp. Trim ();

tmp_code = tmp_code.Trim ();

tmp = «» ;

}

}

code = tmp_code;

string[] cod = code. Split ('n');

bool in_main = false;

int incl = 0;

int if_c = 0;

int need_op = 0;

foreach (string ln in cod)

{

string line = ln. Trim ();

if (line ≠ «»)

{

if (line == «int main ()»)

in_main = true;

else

if (in_main == true)

{

if (line.Length > 2)

{

if (line.StartsWith («if (»))

{

string expr = line. Substring (3, line. Length — 4);

test (expr, line);

if_c++;

need_op = 1;

}

else if (line.StartsWith («else»))

{

if_c—;

need_op = 1;

}

else if (line.StartsWith («for (»))

{

string[] expr = line. Substring (4, line. Length — 5).Split (';');

foreach (string exp in expr)

test (exp, line);

need_op = 1;

}

else

if (line.StartsWith («while (»))

need_op = 1;

else if (line.StartsWith («goto»))

nlabels.Add (line.Substring (4, line. Length — 5));

else if (line.IndexOf («=») > -1)

{

need_op = 0;

string var = line. Substring (0, line. IndexOf ('='));

if (vars.IndexOf (var) > -1)

{

string expr = line. Substring (line.IndexOf ('=') + 1, line. Length — line. IndexOf ('=') — 2);

test (expr, line);

}

else

Console.Error.WriteLine («Переменая {0} не обьявленна», var);

}

else if (line.EndsWith («:»))

labels.Add (line.Substring (0, line. Length — 1));

else

Console.WriteLine («Error, line is wrong»);

}

else if (line == «{»)

{

incl++;

need_op = 0;

}

else if (line == «}»)

if (need_op == 0)

incl—;

else

Console.Error.WriteLine («Нельзя закрыть блок, требуется оператор»);

else if (line == «;»)

need_op = 0;

else

Console.Error.WriteLine («Строка не распознана»);

if (incl < 0) Console.Error.WriteLine («Код за пределами главной функции»);

if (if_c < 0) Console.Error.WriteLine («Else без открывающего If»);

}

else

{

Console.Error.WriteLine («Код за пределами главной функции»);

}

}

}

foreach (string ln in cod)

{

string line = ln. Trim ();

if (line ≠ «»)

{

if (line == «{»)

{

incl++;

}

else if (line == «}»)

incl—;

if (line == «int main ()»)

in_main = true;

else

if (in_main == true)

{

if (line.StartsWith («float «))

{

if (need_op == 1)

Console.Error.WriteLine («Нельзя обьявлять переменые здесь»);

string[] varsl = line. Substring (6, line. Length — 7).Split (',');

foreach (string var in varsl)

if (uvars.IndexOf (var) > -1) Console. Write («{0}float {1};n», new String (' ', incl * 2), var);

}

else

if (line.IndexOf («=») > -1)

{

string var = line. Substring (0, line. IndexOf ('='));

if (vars.IndexOf (var) > -1)

{

if (uvars.IndexOf (var) > -1) Console. WriteLine («{0}{1}», new String (' ', incl * 2), line);

}

else Console. WriteLine («{0}{1}», new String (' ', incl * 2), line);

}

else

Console.WriteLine («{0}{1}», new String (' ', incl * 2), line);

}

}

}

foreach (string label in nlabels)

if (labels.IndexOf (label) ≠ -1) Console.Error.WriteLine («Прыжок к необьявленой метке {0}», label);

Console.ReadLine ();

}

}