Реферат: Системное программное обеспечение - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Системное программное обеспечение

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 23 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Системное программное обеспечение ЭВМ Разработка интерпретатора 1 . Общее описание. Данный интерпретатор реализует основных а рифметических действия в виде инфиксных опера ций над числами с плавающей точкой . Наприм ер входной поток имеет вид : r=2.5 area=pi*r*r (здесь pi имеет предопределенное значение ). Тогда программ а калькулятора выдаст : 2.5 19.635 Результат вычислений для первой входно й строки равен 2.5, а результат для второй строки - это 19.635. Программа интерпретатора состоит из четырех основных частей : анализатора , функции ввода , таблицы имен и драйвера . Анализатор проводит синтаксический анализ , функция ввода обрабатывает входные данные и проводит лексический анализ , таблица имен хранит постоянную информацию , нужную для ра боты , а драйвер выполняет инициализацию , вывод результатов и обработку ошибок. 2. А нализатор. Грамматика языка калькулятора определяется следующими правилами : программа : END // END - это конец ввода список-выражений END список-выражений : выражение PRINT // PRINT - это '\ n' или ';' выражение PRINT список-выражений выражение : выражение + терм выражение - терм терм терм : терм / первичное терм * первичное первичное первичное : NUMBER // число с плавающей запятой в С ++ NAME // имя в языке С ++ за исключением '_' NAME = выражение - первичное ( выражение ) Иными словам и , программа есть п оследовательность строк , а каждая строка соде ржит одно или несколько выражений , разделенны х точкой с запятой . Основные элементы выра жения - это числа , имена и операции *, /, +, - (унар ный и бинарный минус ) и =. Имена необязатель но описы в ать до использования. Для синтаксического анализа используется метод , обычно называемый рекурсивным спуском . Это распространенный и достаточно очевидный метод . В таких языках как С ++, то есть в которых операция вызова не сопряжена с большими накладными ра сходами , это метод эффективен . Для каждого правила грамм атики имеется своя функция , которая вызывает другие функции . Терминальные символы (наприме р , END, NUMBER, + и -) распознаются лексическим анализатором get_token(). Нетерминальные символы распознаются функциями синтаксического анализатора expr(), term() и prim(). Как только оба операнда выражения или подвыражения стали известны , оно вычисляется . В настоящем трансляторе в этот момент создаются команды , вычисляющие выражение. Анализатор использует для вв ода функцию get_token(). Значение последнего вызова get_token() храни тся в глобальной переменной curr_tok. Переменная curr_tok п ринимает значения элементов перечисления token_value: enum token_value NAME, NUMBER, END, PLUS='+', MINUS='-', MUL='*', DI V='/', PRINT=';', ASSIGN='=', LP='(', RP=')' ; token_value curr_tok; Для всех функций анализатора предполаг ается , что get_token() уже была вызвана , и поэтому в curr_tok хранится следующая лексема , подлежащая анализу . Это позволяет анализатору загляды вать на одну лексему вперед . Каждая функция анализатора всегда читает на одну лексему больше , чем нужно для распознаван ия того правила , для которого она вызывала сь . Каждая функция анализатора вычисляет "свое " выражение и возвращает его результат . Фу нкция e xpr() обрабатывает сложение и в ычитание . Она состоит из одного цикла , в котором распознанные термы складываются или вычитаются : double expr() // складывает и вычитает double left = term(); for(;;) // `` вечно '' switch(curr_tok) case PLUS: get_token(); // случай '+' left += term(); break; case MINUS: get_token(); // случай '-' left -= term(); break; default: return left; Отметим , что выражения вида 2-3+4 вычисляются как (2-3)+4, что предопределяется правилами грамма тики . Фун кция term() справляется с умножением и делением аналогично тому , как функция expr() со сложением и вычитанием : double term() // умножает и складывает double left = prim(); for(;;) switch(curr_tok) case MUL: get_token(); // случай '*' left *= prim(); break; case DIV: get_token(); // случай '/' double d = prim(); if (d == 0) return error(" деление на 0"); left /= d; break; default: return left; Проверка отсутствия деления на нуль н еобходима , поскольку результат деления на нуль неопределен и , как правило , приводит к катастрофе . Функция error() будет рассмотрена позже . Переме нная d появляется в программе там , где она действительно нужна , и сразу же инициализ ируется . Функция prim, обрабатывающая первичное , во многом похожа на функции expr и erm(). double number_value; char name_string[256]; double prim() // обрабатывает первичное switch (curr_tok) case NUMBER: // константа с плавающей точкой get_token(); return number_value; case NAME: if (get_token() == ASS IGN) name* n = insert(name_string); get_token(); n->value = expr(); return n->value; return look(name_string)->value; case MINUS: // унарный минус get_token(); return -prim(); case LP: get_token(); double e = expr(); if (curr_tok != RP) return error(" требуется )"); get_token(); return e; case END: return 1; default: return error("требуется первичное "); Когда появляется NUMBER (то есть константа с плавающей точкой ), возвращается ее значение . Функция ввода get_token() помещает значение к онстанты в глобальную переменную number_value. Если в программе используются глобальные переменные , т о часто это указывает на то , что струк тура не до конца проработана , и поэтому требуется некоторая оптимизация . Именно так о б стоит дело в данном случае . В идеале лексема должна состоять из дв ух частей : значения , определяющего вид лексемы (в данной программе это token_value), и (если не обходимо ) собственно значения лексемы . Здесь ж е имеется только одна простая переменная curr_to k , поэтому для хранения последнего прочитанного значения NUMBER требуется глобальная п еременная number_value. Такое решение проходит потому , ч то калькулятор во всех вычислениях вначале выбирает одно число , а затем считывает другое из входного потока . Если последнее значение NUMBER хранится в глобальной переменной number_value, то строковое пр едставление последнего значения NAME хранится в name_string. Перед тем , как что-либо делать с именем , интерпретатор должен заглянуть вперед , чтобы выяснить , будет ли е му присваив аться значение , или же будет только исполь зоваться существующее его значение . В обоих случаях надо обратиться к таблице имен . Эта таблица состоит из записей , имеющих в ид : struct name char* string; name* next; double value; ; Член next используется только служебными функциями , работающими с таблицей : name* look(const char*); name* insert(const char*); Обе функции возвра щают указатель на ту запись name, которая соо тветствует их параметру-строке . Функция look() "ругается ", если имя не было занесено в та блицу . Это означает , что в калькуляторе мо жно использовать имя без предварительного опи сания , но в первый раз оно может появи ться только в левой части присваивания. 3. Функция ввода Получение входных данных - часто самая запутанная час ть программы . Причина кроет ся в том , что программа должна взаимодейст вовать с пользователем , то есть "мириться " с его прихотями , учитывать принятые соглашени я и предусматривать кажущиеся редкими ошибки. Попытки заставить человека вести себя более удобным д ля машины образом , к ак правило , рассматриваются как неприемлемые , что справедливо. Задача ввода для функции низкого уров ня состоит в последовательном считывании симв олов и составлении из них лексемы , с к оторой работают уже функции более высокого уровня . В этом примере низкоуровневый ввод делает функция get_token(). Правила ввода для интерпретатора были специально выбраны несколько громоздкими для потоковых функций ввода . Незначительные изме нения в определениях лексем превратили бы get_token() в обманчиво простую функцию. Первая сложность состоит в том , что символ конца строки '\ n' важен для калькуля тора , но потоковые функции ввода воспринимают его как символ обобщенного пробела . Иначе говоря , для этих функций '\ n' имеет значение только как символ , заверша ющий лексем у. Поэтому приходится анализировать все о бобщенные пробелы (пробел , табуляция и т.п .). Это делается в операторе do : char ch; do // пропускает пробелы за исключением '\n' if(!cin.get(ch)) return curr_tok = END; while (ch!='\n' && issp ace(ch)); Функция cin.get(ch) читает один символ из стандартного входного потока в ch. Значение условия if(!cin.get(ch)) - ложь , если из потока cin нельзя получить ни одного символа . Тогда возвращается лексема END, чтобы закончить работ у калькулятора . Опе рация ! (NOT) нужна потому , что в случае успешного считывания get() возвра щает ненулевое значение . Функция-подстановка isspace() из проверяет , не является ли ее параметр обобщенным пробело м . Она возвращает ненулевое значение , если является , и н уль в противном случае . Проверка реализуется как обращение к табли це , поэтому для скорости лучше вызывать isspace(), чем проверять самому . То же можно сказа ть о функциях isalpha(), isdigit() и isalnum(), которые используются в get_token(). После пропуска обобщенных пробелов следующий считанный символ определяет , какой будет начинающаяся с него лексема . Прежде , чем привести всю функцию , рассмотрим некото рые случаи отдельно . Лексемы '\ n' и ';', завершающие выражение , обрабатываются следующим образом : switch (ch) case ';': case '\n': cin >> ws; // пропуск обобщенного пробела return curr_tok=PRINT; Необязательно снова пропускать пробел , но , сделав это , мы избежим повторных вызовов функции get_token(). Переменная ws, описанная в файле , используется только как приемник нену жных пробелов. Ошибка во входных данных , а также конец ввода не будут обнаружены до следую щего вызова функции get_token(). Обратите внимание , как несколько меток выбора помечают одну пос ледовательность операторов , задан ную для этих вариантов . Для обоих символов ('\ n' и ';') во звращается лексема PRINT, и она же помещается в curr_tok. Числа обрабатываются следующим образом : case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case ' 9': case '.': cin.putback(ch); cin >> number_value; return curr_tok=NUMBER; Поскольку оператор >> может читать константу с плавающей точкой типа double, программа тривиальна : прежде всего начальн ый символ (цифра или точка ) возвращается н азад в cin, а затем константу можно счи тать в number_value. Имя , т.е . лексема NAME, определяется как буква , за которой может идти несколько букв или цифр : if (isalpha(ch)) char* p = name_string; *p++ = ch; while (cin.get(ch) && isalnum(ch)) *p++ = ch; cin.putbac k(ch); *p = 0; return curr_tok=NAME; Этот фрагмент программы заносит в name_string строку , оканчивающуюся нулевым символом . Функци и isalpha() и isalnum() определены в . Результат isalnum(c) ненулевой , если c - буква или цифра , и нулевой в противном случае. Приведем функцию ввода полностью : token_value get_token() char ch; do // пропускает обобщенные пробелы за иск лючением '\n' if(!cin.get(ch)) return curr_tok = END; while (ch!='\n' && isspace(ch)); switch (ch) case ';': case '\n': cin >> ws; // пропуск обобщенного пробела return curr_tok=PRINT; case '*': case '/': case '+': case '-': case '(': case ')': case '=': return curr_tok=token_value(ch); case '0': case '1': case '2': case '3': case '4': case '5': cas e '6': case '7': case '8': case '9': case '.': cin.putback(ch); cin >> number_value; return curr_tok=NUMBER; default: // NAME, NAME= или ошибка if (isalpha(ch)) char* p = name_string; *p++ = ch; while (cin.get(ch) && isalnum(ch)) *p++ = ch; cin.putback(ch); *p = 0; return curr_tok=NAME; error(" недопустимая лексема "); return curr_tok=PRINT; Преобразование операции в значение лек семы для нее тривиально , поскольку в переч ислении token_value лексема операции была определена к ак це лое (код символа операции ). 4 Таблица имен. Есть функция поиска в таблице име н : name* look(char* p, int ins =0); Второй ее параметр пок азывает , была ли символьная строка , обозначающ ая имя , ранее занесена в таблицу . Инициали затор =0 задает стандартн ое значение параме тра , которое используется , если функция look() вызы вается только с одним параметром . Это удоб но , так как можно писать look("sqrt2"), что означает look("sqrt2",0), т.е . поиск , а не занесение в табли цу . Чтобы было так же удобно задавать оп е рацию занесения в таблицу , опре деляется вторая функция : inline name* insert(const char* s) return look(s,1); Как ранее упоминал ось , записи в этой таблице имеют такой тип : struct name char* string; name* next; double value; ; Член next исп ользуется для связи запи сей в таблице . Собственно таблица - это про сто массив указателей на объекты типа name: const TBLSZ = 23; name* table[TBLSZ]; Поскольку по умолчанию все статические объекты инициализируются нулем , такое тривиальное описание табли цы table обеспечивает также и нужную инициализацию. Для поиска имени в таблице функция look() использует простой хэш-код (записи , в ко торых имена имеют одинаковый хэш-код , связываю тся вместе ): int ii = 0; // хэш - код const char* pp = p; while (*pp) ii = ii<<1 ^ *pp++; if (ii < 0) ii = -ii; ii %= TBLSZ; Иными словами , с помощь ю операции ^ ("исключающее ИЛИ ") все символы входной строки p поочередно добавляются к ii. Раз ряд в результате x^y равен 1 тогда и только тогда , когда эти разряды в операндах x и y различны. До выполнения операции ^ значение ii сдвигае тся на один разряд влево , чтобы использова лся не только один байт ii. Эти действия можно записать таким образом : ii <<= 1; ii ^= *pp++; Для хорошего хэш-кода лучше использовать операцию ^, чем +. Операция сдвига важна для получения приемлемого хэш-кода в обоих случаях . Операторы if (ii < 0) ii = -ii; ii %= TBLSZ; гарантируют , что значение ii будет из ди апазона 0...TBLSZ-1. Напомним , что % - это операция взятия остатка . Ниже полностью прив едена функция look: #include name* look(const char* p, int ins =0) int ii = 0; // хэш - код const char* pp = p; while (*pp) ii = ii<<1 ^ *pp++; if (ii < 0) ii = -ii; ii %= TBLSZ; for (name* n=table[ii]; n; n=n->next) // поиск if (st rcmp(p,n->string) == 0) return n; if (ins == 0) error(" имя не найдено "); name* nn = new name; // занесение nn->string = new char[strlen(p)+1]; strcpy(nn->string,p); nn->value = 1; nn->next = table[ii]; table[ii] = nn; return nn; После вычисле ния хэш-кода ii идет пр остой поиск имени по членам next. Имена сравн иваются с помощью стандартной функции сравнен ия строк strcmp(). Если имя найдено , то возвращае тся указатель на содержащую его запись , а в противном случае заводится новая запис ь с этим им е нем. Добавление нового имени означает создание нового объекта name в свободной памяти с помощью операции new, его инициализацию и вклю чение в список имен . Последнее выполняется как занесение нового имени в начало сп иска , поскольку это можно сделать даже бе з проверки того , есть ли список во обще . Символьная строка имени также размещается в свободной памяти . Функция strlen() указывает , сколько памяти нужно для строки , операция new отводит нужную память , а функция strcpy() копирует в нее строку . Все строков ые функц ии описа ны в : extern int strlen(const char*); extern int strcmp(const char*, const char*); extern char* strcpy(char*, const char*); 5. Обработка ошибок Поскольку программа достаточно проста , не надо особо беспокоиться об обработке ош ибок . Функция error просто подсчитывает число ошибок , выдает сообщение о них и возв ращает управление обратно : int no_of_errors; double error(const char* s) cerr << "error: " << s << "\n"; no_of_errors++; return 1; Небуферизованный выходной по ток cerr обы чно используется именно для выдачи сообщений об ошибках . Управление возвращается из error() потому , что ошибки , как правило , встречаются посреди вычисления выражения . Значит надо либо полнос тью прекращать вычисления , либо возвращать зн ачение , которое не должно вызвать послед ующих ошибок . Для простого калькулятора больш е подходит последнее . Если бы функция get_token() о тслеживала номера строк , то функция error() могла бы указывать пользователю приблизительное мест о ошибки . Это было бы полезно п р и неинтерактивной работе с калькулятором. Часто после появления ошибки программа должна завершиться , поскольку не удалось пр едложить разумный вариант ее дальнейшего выпо лнения . Завершить ее можно с помощью вызов а функции exit(), которая заканчивает работу с выходными потоками и завершает программу , возвращая свой параметр в качестве ее результата. 6. Драйвер Когда все части программы определены , нужен только драйвер , чтобы инициализировать и запустить процесс . В нашем примере с этим справится функция mai n(): int main() // вставить предопределенные имена : insert("pi")->value = 3.1415926535897932385; insert("e")->value = 2.7182818284590452354; while (cin) get_token(); if (curr_tok == END) break; if (curr_tok == PRINT) continue; cout << expr( ) << '\n'; return no_of_errors; Принято , что функция main() возвращает нуль , если программа завершается нормально , и нен улевое значение , если происходит иначе . Ненуле вое значение возвращается как число ошибок . Оказывается , вся инициализация сводитс я к занесению предопределенных имен в таблиц у. В цикле main читаются выражения и выдаютс я результаты . Это делает одна строка : cout << expr() << '\n'; 7. Параметры командной строки Для удобства пользования интерпретатором используем параметры командной строки. Как уже было сказано , выполнение прогр аммы начинается вызовом main(). При этом вызове main() получает два параметра : число параметров ( обычно называемый argc) и массив строк параметров (обычно называемый argv). Параметры - это символьные строки , п оэтому argv имеет тип char*[argc+1]. Имя программы (в том виде , как оно было задано в к омандной строке ) передается в argv[0], поэтому argc всег да не меньше единицы . Например , для команд ной строки dc 150/1.1934 параметры имеют значения : argc 2 argv[0 ] "dc" argv[1] "150/1.1934" argv[2] 0 int main(int argc, char* argv[]) switch(argc) case 1: // считывать из стандартного входного потока break; case 2: // считывать из строки параметров cin = *new istream(argv[1],strlen(argv[1])); break; de fault: error("слишком много параметров "); return 1; // вставить предопределенные имена : insert("pi")->value = 3.1415926535897932385; insert("e")->value = 2.7182818284590452354; while (cin) get_token(); if (curr_tok == END) break; if (curr_tok == PRINT) continue; cout << expr() << '\n'; return no_of_errors; При этом istrstream - это функция istream, которая считывает символы из строки , являющейся ее первым параметром . Чтобы использовать istrstream нужно включить в програм му файл , а не обычный . В остальном же программа о сталась без изменений , кроме добавления парам етров в функцию main() и использования их в операторе switch. Можно легко изменить функцию main() так , чтобы она могла принимать неско л ько параметров из командной строки . О днако это не слишком нужно , тем более , что можно нескольких выражений передать как один параметр : dc "rate=1.1934;150/rate;19.75/rate;217/rate" Кавычки необходимы потому , что символ ';' служит в системе UNIX раздели телем команд . В других системах могут быть свои со глашения о параметрах командной строки. 8. Полный вариант программы : #include #include #include enum token_value NAME, NUMBER, END, PLUS = '+', MINUS = '-', MUL='*' , DIV='/', PRINT=';', ASSIGN='=', LP='(', RP=')' ; token_value curr_tok; struct name char* string; name* next; double value; ; const TBLSZ = 23; name* table[TBLSZ]; int no_of_errors; double error(char* s) cerr << "error: " << s << "\n"; no_of_errors++; return 1; name* look(char* p, int ins = 0) int ii= 0; char *pp = p; while (*pp) ii = ii<<1 ^ *pp++; if (ii < 0) ii = -ii; ii %= TBLSZ; for (name* n=table [ii]; n; n=n->next) if (strcmp(p,n->string) == 0) return n; if (ins == 0) error("name not found"); name* nn = new name; nn->string = new char[strlen(p) + 1]; strcpy(nn->string,p); nn->value = 1; nn->next = table[ii]; table[ii] = nn; return nn; inline name* insert(char* s) return look (s,1); token_ value get_token(); double term(); double expr() double left = term(); for (;;) switch (curr_tok) case PLUS: get_token(); left += term(); break; case MINUS: get_token(); left -= term(); break; default : return left; double prim(); double term() double left = prim(); for (;;) switch (curr_tok) case MUL: get_token(); left *= prim(); break; case DIV: get_token(); double d = prim(); if (d == 0) return error("divide by o"); left /= d; break; default: return left; int number_value; char name_string[80]; double prim() switch (curr_tok) case NUMBER: get_token(); return number_value; case NAME: if (get_token() == ASSIGN) name* n = insert(name_string); get_token(); n->value = expr(); return n->value; return look(name_string)->value; case MINUS: get_token(); return -prim(); case LP: get_token(); double e = expr(); if (curr_tok != RP) return error(") expected"); get_token(); return e; case END: return 1; default: return error ("primary expected"); token_value get_token() char ch = 0; do if(!cin.get(ch)) return curr_tok = END; while (ch!='\n' && isspace(ch)); switch (ch) case ';': case '\n': cin >> WS; return curr_tok=PRINT; case '*': ca se '/': case '+': case '-': case '(': case ')': case '=': return curr_tok=ch; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': case '.': cin.putback(ch); cin >> number_value; return curr_tok=NUMBER; default: if (isalpha(ch)) char* p = name_string; *p++ = ch; while (cin.get(ch) && isalnum(ch)) *p++ = ch; cin.putback(ch); *p = 0; return curr_tok=NAME; error ("bad token"); return curr_tok=PRINT; int main(int argc, char* argv[]) switch (argc) case 1: break; case 2: cin = *new istream(strlen(argv[1]),argv[1]); break; default: error("too many arguments"); return 1; // insert predefined names: insert("pi")->value = 3.1415926535897932385; insert("e")->value = 2.7182818284590452354; while (1) get_token(); if( curr_tok == END) break; if (curr_tok == PRINT) continue; cout << expr() << "\n"; return no_of_errors;
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Две блондинки у банкомата:
- Странно, на счету всего семнадцать рублей...
- Может, код не правильно набрала?
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Системное программное обеспечение", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru