Б3.в.од.8 системное программное обеспечение
АКАДЕМИЯ МАРКЕТИНГА
И СОЦИАЛЬНО-ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ – ИМСИТ
Г. Краснодар
Факультет информатики и вычислительной техники
Кафедра математики и вычислительной техники
УТВЕРЖДАЮ
Протокол № 1 от 30.08.2015 г.
Зав. кафедрой ___________ Н.С.Нестерова
Б3.В.ОД.8 СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
самостоятельные работы по дисциплине
для студентов направления подготовки
09.03.01 «Информатика и вычислительная техника»
Направленность (профиль) образовательной программы
«Автоматизированные системы обработки информации и управления»
Квалификация (степень выпускника) бакалавр
Краснодар, 2015
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
В соответствии с учебным планом студенты заочного отделения выполняют контрольную работу, состоящую из теоретических вопросов и решения задачи. Задания по контрольным работам построены таким образом, чтобы выяснить подготовку студента по различным разделам изучаемой дисциплины.
Целью настоящих методических рекомендаций является оказание практической помощи студенту в выполнении контрольной работы. Выполнить контрольную работу следует после ознакомления со всеми темами дисциплины. Темы, вынесенные в задание, требуют от студента углубленного изучения.
Ответ на каждый вопрос должен излагаться подробно, с разъяснениями, со ссылкой на нормативно-правовые акты.
К каждому варианту прилагается список литературы, по своей инициативе студент может использовать другие дополнительные источники.
Контрольная работа выполняется письменно в тетради с условием ясного, читаемого почерка или машинописным способом до полного освещения вопросов. Вопросы задания и текст задачи должен быть переписан студентом с указанием варианта. Обязательной является ссылка на соответствующие статьи нормативных актов.
Студент выполняет контрольную работу в соответствии с требованиями к оформлению: на титульном листе следует указать фамилию, имя, отчество студента, название дисциплины и фамилию преподавателя. В конце работ приводится список использованной литературы.
Тематика всех контрольных работ связана с решением конкретных задач по реализации отдельных компонентов командного интерпретатора языка программирования высокого уровня.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
Тема 1: Автоматные распознаватели
1.1 Цель работы
Изучить конечные автоматы (КА), научиться создавать диаграммы КА, воссоздавать эквивалентные им грамматики, строить матирицы переходов состояний КА и реализовывать программно КА с помощью матрицы переходов.
1.2 Основные теоретические положения
Основные теоретические сведения можно найти в [1, 2] или в электронном учебном пособии [3].
1.3 Порядок выполнения работы
Программа должна выполняться в командной строке системной консоли. Например,
e:\prg.exe
>2*4-5
Программа должна проверить принадлежность входной цепочки символов языку, порождённому эквивалентной грамматикой, и сообщить о результатах проверки: КА принял входную цепочку или отверг.
В отчёте о работе должны быть представлены:
1. условие задачи;
2. листинг программы с комментариями;
ПРИМЕР ОТЧЁТА
Задание: Разработать программу для ДКА, распознающего язык идентификаторов.
Порядок выполнения работы:
1. Создание диаграммы переходов ДКА;
2. Воссоздание по диаграмме переходов грамматики, эквивалентной ДКА.
3. Построение матрицы переходов.
4. Разработка программы, распознающую входную цепочку с помощью матрицы переходов.
Результат:
1. Диаграмма переходов данного ДКА имеет вид:
2. Эквивалентная ДКА автоматная грамматика задаётся следующим набором правил:
N → aB
B → aB|bB|ε
3. Исходя из правил грамматики, построим таблицу переходов:
| Состояние автомата | Символ алфавита | |
| a | b | |
| N | B | E |
| B | B | B |
| E | E | E |
2. Программа
Назначение
Программа реализует автоматный распознаватель, использующий в качестве структуры данных таблицу переходов.
Программный интерфейс
Командная строка.
Ввод
Строка символов.
Вывод
Результат проверки в форме текстового сообщения.
Состав программы
1. Типы данных:
tCond – перечисляемый тип данных состояний автомата.
2. Константы:
EOL – символ конца строки.
3. Переменные:
ch – переменная символьного типа для текущего символа входной цепочки;
i – номер (индекс) текущего символа входной цепочки;
alpha – массив для входной цепочки;
сond – переменная типа tCond для хранения текущего состояния автомата;
Alph – массив для хранения символов алфавита автомата;
Jump – двухмерный массив типа tCond для хранения матрицы перехода.
Листинг программы на языке C
#include <stdio.h>
#include <string.h>
//признак конца строки:
#define EOL '\0'
//тип состояний автомата:
typedef enum {N=0, B=1, E=2} tCond;
int main ()
{
//алфавит автомата:
char Alph[] = {'a', 'b'};
//таблица переходов:
tCond Jump[sizeof(tCond)][sizeof(Alph)/sizeof(char)] = {
{B, E},
{B, B},
{E, E}
};
//текущее состояние:
tCond cond;
//входная цепочка:
char alpha[128];
//входной символ:
char ch;
//индекс входного символа:
int i = 0;
//начальное состояние:
cond = N;
//ввод входной цепочки:
printf("Введите входную цепочку:\n> ");
gets(alpha);
alpha[strlen(alpha)] = EOL;
while ((ch = alpha[i++]) != EOL && cond != E)
{
switch (ch) {
case 'a':
cond = Jump[cond][0];
break;
case 'b':
cond = Jump[cond][1];
break;
default:
cond = E;
}
}
if(cond == B)
printf("\nЦепочка принята\n");
else
printf("\nЦепочка не принята\n");
return 0;
}
Листинг программы на языке C#
using System;
using System.Collections.Generic;
using Automatic;
namespace Automatic
{
class FinitAutomat
{
//создание перечисления:
enum tCond {N = 0, B = 1, E = 2};
//статический метод, реализующий автоматный распознаватель:
static public bool IdLanguage(string alpha)
{
//начальное состояние:
tCond cond = tCond.N;
//матрица перехода:
tCond[,] Jump = new tCond[,] {
{ tCond.B, tCond.E },
{ tCond.B, tCond.B },
{ tCond.E, tCond.E }
};
//массив символов алфавита:
char[] liters = new char[] { 'a', 'b' };
//входной алфавит:
List<char> Alph = new List<char>(liters);
/*реализация чтения символов из входной строки и перехода в новое
состояние: */
for (int i = 0; i < alpha.Length && cond != tCond.E; i++) {
if (Alph.Contains (alpha [i])) {/*если символ принадлежит алфавиту -
переход в новое состояние: */
cond = Jump [(int)cond, Alph.IndexOf (alpha [i])];
} else {//... и если не принадлежит - переход в состояние ошибки:
cond = tCond.E;
}
}
if (cond == tCond.B)// -цепочка принята:
return true;
else //-цепочка не принята:
return false;
}
}
}
class Program
{
static void Main()
{
Console.Write ("Введите строку:\n> ");
if (FinitAutomat.IdLanguage (Console.ReadLine ()))
Console.WriteLine ("Цепочка принята!");
else
Console.WriteLine ("Цепочка не принята!");
}
}
ЗАДАНИЯ К САМОСТОЯТЕЛЬНЫМ РАБОТАМ
Задание: Разработать программу для КА в соответствии с вариантом работы (вариант выбирается по последней цифре зачётки).
Вариант 0. Арифметическое простое арифметическое выражение. Операндами выражения являются вещественные и целые числа, а операциями – сложение, умножение, деление и вычитание.
Вариант 1. Прямая польская запись арифметических выражений. Операнды – вещественные и целые числа, операции – сложение, умножение, деление и вычитание.
Вариант 2. Обратная польская запись арифметических выражений. Операнды – вещественные и целые числа, операции – сложение, умножение, деление и вычитание.
Вариант 3. Квадратное уравнение с целыми и вещественными коэффициентами.
Вариант 4. Линейное алгебраическое уравнение.
Вариант 5. Сумма обыкновенных дробей.
Вариант 6. Комплексное число ( с целочисленными значениями действительной и мнимой частей ).
Вариант 7. Линейное однородное дифференциальное уравнение с постоянными целочисленными коэффициентами.
Вариант 8. Неравенство вида:
Операнд1 ⊗ Операнд2,
где Операнд1 и Операнд2– целые числа;
⊗ – знак отношения ( >, <, =, <>, >=, <= ).
Вариант 9. Двуместный логический предикат. Операнды – числа 1 (истина) или 0 (ложь). Операции – AND (логическое умножение) и OR (логическое сложение).
Тема 2. Синтаксические диаграммы
2.1 Цель работы
Изучить основные синтаксические диаграммы и научиться строить алгоритмы по их реализации.
2.2 Основные теоретические положения
Основные теоретические сведения можно найти в [1, 2] или в электронном учебном пособии [3].
2.3 Порядок выполнения работы
Программа должна выполняться в командной строке системной консоли. Текст исходного кода должен вводиться в командной строке и из текстового файла. Программа должна проверить синтаксис и сообщить о результатах проверки: есть ошибки или нет ошибок.
В отчёте о работе должны быть представлены:
1. условие задачи;
2. листинг программы с комментариями;
ПРИМЕР ОТЧЁТА
Задание: разработать программу синтаксического анализатора указателя языка программирования C.
1 Синтаксические диаграммы
Указатель
Имя
Цифра
Буква
2 Программа синтаксического анализатора
Назначение
Программа реализует синтаксический анализ нетерминала, основываясь на построенных синтаксических диаграммах.
Программный интерфейс
Командная строка.
Порядок работы
На вход подается строка, содержащую нетерминал, который необходимо проанализировать на соответствие синтаксису указателя. На выходе – результат проверки в форме текстового сообщения.
Ввод данных
1. Ввод исходной строки ходе выполнения программы.
2. Использование текстового файла, содержащего исходную строку, с последующим указанием его имени в качестве параметра в командной строке программы.
Состав программы
1. Константы:
eol – константа, равная символу конца строки.
2. Переменные:
ch – переменная символьного типа для текущего символа исходной строки;
i – номер (индекс) текущего символа входной строки;
S – массив для входной строки.
3. Функции:
NextChar() – извлечение следующего символа из входной строки;
Pointer() – синтаксический анализ входной строки на предмет соответствия указателю;
Name() – синтаксический анализ входной строки на предмет соответствия имени объекта;
ResetConsole() – чтение и подготовка входной строки к синтаксическому анализу;
ResetFile() – чтение из файла, имя которого задано параметром командной строки программы, входной строки и её подготовка к синтаксическому анализу;
Error() – вывод сообщения об ошибке.
Листинг программы на языке C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
char ch;
const char eol='\n';
char S[128];
int i;
void NextChar();
void Pointer();
void Name();
void ResetFile();
void ResetConsole();
void Error();
int main (int argc, char * const argv[])
{
ResetConsole();
Pointer();
if(ch == eol)
printf("\nСинтаксические ошибки отсутствуют!");
else
Error();
return 0;
}
void ResetConsole()
{
printf("\nВведите указатель\n> ");
gets(S);
i=0;
NextChar();
}
void NextChar()
{
if(i < strlen(S))
ch=S[i];
else
ch=eol;
i++;
}
void Pointer()
{
if(ch == '*')
{
NextChar();
Name();
}
else
Error();
}
void Error()
{
printf("\nОшибка в синтаксисе!");
exit(0);
}
void Name()
{
if(isalpha(ch) != 0)
{
while(ch != eol)
{
if(isdigit(ch) != 0 || isalpha(ch) != 0)
NextChar();
else
Error();
}
}
else
Error();
}
using System;
using System.Collections.Generic;
using Automatic;
namespace Automatic
{
public class FinitAutomat
{
//создание перечисления состояний:
enum tCond {N = 0, B = 1, E = 2};
/*
статический метод, реализующий автоматный распознаватель
языка идентификаторов: */
static public bool IdLanguage(string alpha)
{
//начальное состояние:
tCond cond = tCond.N;
//матрица перехода:
tCond[,] Jump = new tCond[,] { { tCond.B, tCond.E }, { tCond.B, tCond.B }, { tCond.E, tCond.E } };
//массив символов алфавита:
char[] leters = new char[] { 'a', 'b' };
//входной алфавит:
List<char> Alph = new List<char>(leters);
//реализация чтения символов из входной строки и перехода в новое состояние:
for (int i = 0; i < alpha.Length && cond != tCond.E; i++) {
if (Alph.Contains (alpha [i])) {/*если символ принадлежит алфавиту -
переход в новое состояние: */
cond = Jump [(int)cond, Alph.IndexOf (alpha [i])];
} else {//... и если не принадлежит - переход в состояние ошибки:
cond = tCond.E;
}
}
if (cond == tCond.B)// -цепочка принята:
return true;
else //-цепочка не принята:
return false;
}
}
Листинг на языке программирования C#:
public class SintaxPointAnalizator
{
//входная цепочка:
string alpha;
//признак конца строки:
const char eol = '\0';
//индекс:
int i;
//текущий символ входной цепочки:
char ch;
//конструктор:
public SintaxPointAnalizator(string Alpha)
{
alpha = Alpha;
}
/* статический метод, реализующий автоматный распознаватель языка
указателей: */
public bool PointLanguage()
{
i = 0;
NextChar ();
if (Pointer () && ch == eol)
return true;
else
return false;
}
//чтение очередного символа из входной строки:
void NextChar()
{
if (i < alpha.Length)
ch = alpha [i];
else
ch = eol;
i++;
}
//синтаксический анализ указателя:
bool Pointer()
{
if (ch == '*') {
NextChar ();
if (Name ())
return true;
else
return false;
} else
return false;
}
//синтаксический анализ идентификатора:
bool Name()
{
if (char.IsLetter (ch)) {
while (ch != eol) {
if (char.IsLetterOrDigit (ch))
NextChar ();
else
return false;
}
} else
return false;
return true;
}
}
}
class Program
{
static void Main()
{
Console.Write ("Введите строку:\n> ");
string str = Console.ReadLine ();
if (FinitAutomat.IdLanguage (str))
Console.WriteLine ("Это - идентификатор!");
else if ((new SintaxPointAnalizator (str)).PointLanguage ())
Console.WriteLine ("Это - указатель!");
else
Console.WriteLine ("Цепочка не принята!");
}
}
ВАРИАНТЫ САМОСТОЯТЕЛЬНЫХ РАБОТ
Вариант 0. Сумма – последовательность натуральных чисел и имен, разделенных знаками плюс и минус. Возможен и знак перед первым слагаемым.
Вариант 1. Сумма вещественных чисел в форме с фиксированной точкой.
Вариант 2. Произведение вещественных чисел с фиксированной точкой.
Вариант 3. Сумма вещественных чисел с плавающей точкой.
Вариант 4. Произведение вещественных чисел с плавающей точкой.
Вариант 5. Квадратное уравнение с целыми коэффициентами.
Вариант 6. Сумма обыкновенных дробей.
Вариант 7. Произведение обыкновенных дробей.
Вариант 8. Разность обыкновенных дробей.
Вариант 9. Комплексное число ( с целочисленными значениями действительной и мнимой частей ).
Список рекомендованных источников
а) основная литература
1. Бужан В.В. Объектно-ориентированное программирование: учебно-методическое пособие для студентов очной и заочной форм обучения направления подготовки 230100.62 – Информатика и вычислительная техника. – Краснодар: ИМСИТ, 2013. – 52 с.
2. Голицина О.Л., Попов И.И. Программирование на языках высокого уровня. М.: ФОРУМ, 2011. 496 с.
3. Васильев, А.Н. Java: Объектно-ориентированное программирование: базовый курс для магистров и бакалавров. – СПб: ПИТЕР, 2011. – 400 с.
б) дополнительная литература
4. Свердлов С.З. Языки программирования и методы трансляции / С.З. Свердлов. – СПб.: – Питер, 2007. – 630 с.
5. Системное программное обеспечение / А.Ю. Молчанов. – СПб.: – Питер, 2010. – 400 с.
6. Информатика и программирование. Компьютерный практикум: учеб. пособие для вузов / Гуда, А.Н., Бутаков, М.А., Нечитайло, Н.М., Чернов, А.В. – М.: Дашков и К, 2010. – 240 с.