2020-04-07
134
Мы уже приводили пример, связанный с циклами, когда необходимо "экстренно" завершить выполнение нескольких вложенных конструкций и передать управление в точку продолжения. Проблема становится более трудной при наличии процедур и рекурсии. Продемонстрируем это на примере функции вычисления выражений. Напомним, что мы определили структуру внутреннего представления для простого языка выражений следующим образом:
struct Expr {
int tag;
enum ExprCode code;
union {
float value;
char name[8];
struct {
char op;
struct Expr * arg;
} unop;
struct {
char op;
struct Expr *left, *right;
} binop;
} choice;
};
Оставим пока в стороне вопрос о том, как порождается такая структура. Будем считать, что уже написана процедура
struct Expr * parse_expr(char * s);
преобразующая текстовое представление выражения в его внутреннее представление.
Процедура вычисления выражений
float eval_expr(struct Expr * e, Memory m);
получает на вход ссылку e на такую структуру и некоторый объект m, представаляющий память, над которой вычисляется выражение[31], и возвращает значение выражения.
Имея две такие функции мы можем просто написать процедуру, реализующую цикл "читать-вычислять-печатать", который по очереди вводит выражения и выдаёт их значения:
void read_eval_print(Memory m)
{
char s[256];
fputs("Привет!",stderr);
for (;;)
{
fputc('>',stderr);
fgets(s,stderr);
if (s[0]=='.')
break;
fprintf(stderr, "%d\n",
eval_expr(parse_expr(s), m));
error_exit:;
}
fputs("Пока.,stderr);
}
Всё кажется просто до тех пор, пока не оказывается, что при вычислении выражения (как, впрочем, и при его разборе), может произойти ошибка. Например, при вычислении выражения
(1 + (2 * ((3/(2-(1+1))) - 4)))
произойдёт деление 3/0. Чтобы наша программа вообще не прервалась, мы должны предусмотреть обработку исключительных ситуаций. Рассмотрим ветвь реализации eval_expr, связанную с делением:
float eval_expr(struct Expr * e, Memory m)
{
swith (e->code)
{
...
case EC_BINOP:
{
float v1 = eval_expr(e->choice.binop.left, m);
float v2 = eval_expr(e->choice.binop.right, m);
switch (e->choice.binop.op)
{
case '/':
{
if (v2 == 0)
{
fputs("Деление на ноль.",stderr);
goto error_exit;
}
return v1/v2;
}
}
...
}
...
}
}
Здесь перед выполнением деления мы проверяем, не равен ли делитель нулю, и если этот так, то выдаём сообщение и передаём управление в конец цикла "читать-вычислять-печатать", где предусмотрительно была поставлена метка error_exit.
Однако, такой метод некорректен, поскольку язык С не позволяет передать управление на метку, находящуюся в другой функции. Решение может быть связано с использованием вложенных процедур: мы могли бы поместить описания parse_expr и eval_expr внутрь функции read_eval_print. Однако, это не всегда возможно, например, если эти процедуры описаны в другом файле или вообще не нами. К тому же в используемом диалекте языка C может не быть вложенных процедур. В таком случае нам придётся переделать реализацию eval_expr так, чтобы она возвращала не только значение, но и признак того, что произошла ошибка. Поскольку ошибки бывают разных типов, то уместно завести тип перечисления, в котором они все указаны:
enum ErrorType
{
OK = 0,
ERR_SYNTAX,
ERR_DIV0,
ERR_OVERFLOW,
ERR_UNDEFINED_VARIABLE,
...
}
Для функций, выдающих код завершения, принято, что 0 означает нормальное завершение, а ненулевые значения - коды ошибок. Это позовляет рассматривать их как логические значения.
Теперь функция eval_expr будет возвращать код завершения, а собственно вычисленное значение передаваться через параметр res:
enum ErrorType Eval(struct Expr * e, Memory m, float * res)
{
swith (e->code)
{
...
case EC_BINOP:
{
float v1;
float v2;
enum ErrorType ec;
if ((ec=eval_expr(e->choice.binop.left, m, &v1))!= OK)
return ec;
if ((ec=eval_expr(e->choice.binop.right, m, &v2))!= OK)
return ec;
switch (e->choice.binop.op)
{
case '/':
{
if (v2 == 0)
return ERR_DIV0;
* res = v1/v2;
}
}
...
}
...
}
return OK;
}
Как видно, функция вообще не переходит к применению бинарной операции, если при вычислении одного из подвыражений произошла ошибка, а сразу возвращает её код. Кроме того, мы вынесли из функции печать текста сообщения, чтобы делать это централизованно в месте вызова, что является хорошим стилем с точки зрения принципа отделения логики вычислений от ввода/вывода. Функцию read_eval_print теперь следует переписать следующим образом:
void read_eval_print()
{
char s[256];
float res;
fputs("Привет!",stderr);
for (;;)
{
fputc('>', stderr);
fgets(s, stderr);
if (s[0]=='.')
break;
switch (eval_expr(parse_expr(s), m, &res))
{
case 0:
fprintf(stderr,"%d\n", res);
break;
case ERR_DIV0:
fputs("Деление на ноль",stderr);
break;
case ERR_OVERFLOW:
...
}
}
fputs(“Пока.”,stderr);
}
Недостатком такого метода является то, что пришлось существенно усложнить реализацию: кроме того, что приходится передавать дополнительные параметры, каждый вызов функции приходится обрамлять проверкой того, какой код она вернула, хотя всё, что нам требовалось - передать управление в нужную точку в случае возникновения ошибки. Стандартная библиотека языка C предоставляет для этой цели так называемые нелокальные переходы, специфицированные во включаемом файле setjmp.h. Она определяет тип jmp_buf, содержащий точку, в которую надо передать управление, а также всю необходимую информацию для корректного завершения (в том числе и рекурсивных) функций.
Функция
int setjmp(jmp_buf env);
запоминает в переданном параметре[32] обстановку вычислений и возвращает 0. Функция
void longjmp(jmp_buf env, int val);
восстанавливает запомненную setjmp обстановку вычислений, возвращается в то место, где setjmp собирался вернуть 0, но вместо этого заставляет выдать val. Таким образом, в следующей реализации
#include <setjmp.h>
jmp_buf env;
void read_eval_print(Memory m)
{
char s[256];
int res;
fputs("Привет!",stderr);
for (;;)
{
fputc('>', stderr);
fgets(s, stderr);
if (s[0]=='.')
break;
Switch (setjmp(env))
{
case 0:
fprintf(stderr,"%d\n",
eval_expr(parse_expr(s), m));
break;
case ERR_DIV0:
fputs("Деление на ноль",stderr);
break;
case ERR_OVERFLOW:
...
}
}
fputs("Пока.",stderr);
}
при вызове setjmp управление будет передано на альтернативу case 0, и если ничего не случится, то будет распечатано вычисленное значение выражения.
Функцию eval_expr вернём практически к её начальному виду, только вместо перехода goto используем longjmp, у которой первым параметром будет запомненная setjmp в глобальной переменной обстановка вычислений, а вторым - код ошибки:
float eval_expr(struct Expr * e, Memory m)
{
swith (e->code)
{
...
case EC_BINOP:
{
float v1 = eval_expr(e->choice.binop.left, m);
float v2 = eval_expr(e->choice.binop.right, m);
switch (e->choice.binop.op)
{
case '/':
{
if (v2 == 0)
longjmp(jmp_buf, ERR_DIV0);
return v1/v2;
}
}
...
}
...
}
}
Выполнение longjmp в этой функции вернёт управление в заголовок переключателя switch в функции read_eval_print, а после этого - к альтернативе case ERR_DIV0.
Таким образом, мы отделили обработку исключительных ситуаций от логики вычисления выражений. Обстановку вычислений cледовало бы хранить не в глобальной переменной, а передавать дополнительным параметром, что позоволило бы вызывать eval_expr из разных мест.
Как и переходы по вычисляемой метке, нелокальные переходы в языке C являются средством очень низкого уровня. С одной стороны, это позволяет использовать их не только для обработки исключительных ситуаций, но и, скажем, для реализации со-программ, в которых управление может быть многократно передано из одной процедуры в другую и обратно, что моделирует их (псевдо-) параллельное выполнение.
С другой стороны, при неаккуратном использовании нелокальные переходы приводят к очень тяжёлым ошибкам, типичными примерами которых являются использование longjmp прежде, чем была вызвана setjmp, либо случай, когда та процедура, в которой была вызвана setjmp, уже закончила выполнение. В современных языках есть специальные средства обработки исключительных ситуаций - try-блоки и исключения, которые в большинсве случаев позволяют избежать таких ситуаций. Так, в нашем пример оператор switch в процедуре read_eval_print является примером типичного шаблона, где первая альтернатива является охраняемым фрагментом, в котором может произойти исключительная ситуация, а остальные альтернативы - реакциями на исключения.
Распределение памяти
Все объекты программы можно классифицировать в зависимости от способа их создания и времени существования как глобальные, локальные (или автоматические) и динамические.
Глобальные объекты существуют всё время исполнения программы. Обычно они описываются на самом верхнем уровне. Достоинством глобальных объектов является то, что их адрес может быть вычислен статически во время сборки программы, и, следовательно, доступ к ним эффективен. Недостатком, естественно, является то, что даже если такой объект реально нужен только в течение ограниченного периода времени, он будет занимать пямять, пока программа не закончится.
Автоматическими называются локальные объекты процедур и функций. Как мы уже обсуждали, они появляются только в при вызове процедуры, а после её завершения удаляются, причём для этого не требуется ничего дополнительно указывать. Отсюда и название. Достоинством является, в частности, то, что если процедура никогда не вызывается, то и память под локальные объекты не отводится. Однако, если она вызывается многократно, то проявятся накладные расходы на создание и удаление. Кроме того, одна и та же локальная переменная или формальный параметр может при разных вызовах размещаться по разным адресам, что делает доступ к ним менее эффективным, чем к глобальным переменным.
Поскольку выделение памяти для локальных объектов соответствует дисциплине FIFO (first-in-first-out), означающей в данном случае, что первым будет удалён тот фрейм, который был создан последним, то для реализации может быть использован стек. Все фреймы будем хранить в одном байтовом массиве stack. Переменная sp (stack pointer) будет указывать на первый свободный байт:
char stack[10000];
char * sp = stack;
Тогда процедуры выделения и освобождения памяти в стеке могут быть реализованы следующим образом:
void * stack_alloc(int size)
{
void * f = (void *) sp;
sp += size;
return f;
}
void stack_free(int size)
{
sp -= size;
}
Осталось определить макросы
#define frame_new(p) p=stack_alloc(sizeof(*p))
#define frame_dispose(p) stack_free(sizeof(*p))
Рассмотренная реализация стека очень упрощённая: она отводит под стек массив фиксированной длины, не рассматривает случай переполнения стека, игнорирует выравнивание и т.п. Возможны и принципально другие методы организации хранения фреймов. Например, техника мелкого стека определяет для каждой функции (или даже для каждого параметра) свой стек, что, в частности, решает проблему с вложенными процедурами.
Динамические объекты появляются по специальному запросу в так называемой куче. Время их жизни явно не связано процедурами и функциями, в которых они были созданы. Стандартная библиотека языка C предоставляется следующие функции для создания и удаления динамических объектов, определённые в стандартном файле alloc.h (или malloc.h):
void * malloc(unsigned int size);
void free(void * ptr);
Функция malloc находит в куче свободное место размера size и выдаёт указатель на него, а процедура free отмечает указанное место, как свободное. Заметим, что функции free не требуется передавать размер освобождаемой памяти, что означает, что куча организована таким образом, что в ней запоминается размер, запрошенный при вызове malloc. Ни та, ни другая процедура не знает тип объекта, для которого запрашивается память, а только его размер.
Выделение динамической памяти весьма сложная процедура и существуют разные методы её реализации. Например, можно организовать списки для каждого запрашиваемого размера (или по-крайней мере для наиболее распространённых значений). При этом, конечно, придётся решать проблему, когда имеется много свободных фрагментов одного размера, а запрашивается другой. Для избежания фрагментации, т.е. ситуации, когда свободная память есть, но слишком мелкими фрагментами, можно соединять последовательно расположенные свободные фрагменты в один большего размера и т.п. Так или иначе, для организации кучи требуется дополнительная память, и если запросить 1 байт, то вполне возможно, что это займёт намного больше.
Для некоторой оптимизации в стандартной библиотеке определены также функции
void * calloc(unsigned int count, unsigned int size);
void * realloc(void * ptr, unsigned int size);
Функция calloc предназначена для динамического размещения массивов, но по сути
calloc(count, size)
эквивалентно
malloc(count * size)
с той разницей, что calloc обнуляет выдаваемой фрагмент памяти и может сделать это более эффективно за счёт использования специальных машинных команд.
Вызов функции
realloc(p, size)
функционально эквивалентен последовательности
(free(p), malloc(size))
но realloc может сделать (а может и не делать) это более эффективно, например, в случае, если размер size меньше, чем текущий размер фрагмента, на который указывает указатель p.
Низкий уровень процедур работы с динамической памятью является источником большого количества ошибок. Рассмотрим наиболее типичные из них. При размещении объекта объём выделяемой памяти может быть недостаточен для его представления. Например
int * p = malloc(2);
*p = 123;
может вполне хорошо работать, если размер целого в данной системе программирования равен 2, но будет приводить к непредсказуемым последствиям если он равен 4. Такие ошибки не возникают, скажем, в языке Паскаль, где размещение памяти выполняется псевдо-процедурой
new(p)
которая "знает" о типе, на который указывает p. В языке C это можно реализовать с помощью макроса
#define new(p) p = malloc(sizeof(*p))
Аналогично, попытка копирования строки
char * dest = strcpy((char *) malloc(strlen(source)), source);
приведёт к ошибкам, поскольку при выделении памяти не учтён 0, завершающей строку source.
Каждый размещённый фрагмент памяти должен быть освобождён. Если указатель на выделенный участок памяти потерян, то теряется и возможность осводить его. В простейшем случае при выполнении последовательности
new(p);
new(p);
первый из выделенных фрагментов станет "мусором". Если в ходе выполнения программы это происходит многократно, то происходит так называемая утечка памяти. Как мы увидим позже, определить причины и устранить утечки памяти бывает весьма непросто.
Ещё больше ошибок связано с процедурой освобождения памяти free. Повторное освобождение указателя, как в случае
new(p);
q = p;
free(p);
free(q);
может привести к разрушению структуры кучи, а ошибка проявится лишь в одном из последующих malloc. Аналогичный эффект может иметь и освобождение памяти через указатель, который не был получен путём выделения памяти. Например, это случится при
p = calloc(10, sizeof(*p));
p++;
free(p);
хотя указатель p и указывает в область кучи.
Обращение к ранее выделенной динамической памяти, которая к данному моменту уже была освобождена, приводит к непредсказуемым последствиям. Так последнее условие в следующем фрагменте
new(p);
p->a = 5;
free(p);
if (p->a == 5)
...
может оказаться ложным, поскольку вполне возможно, что free изменило память, на которую указывает p.
Ошибки, связанные с распределением памяти, относятся к самым трудным, поскольку
• проявляются далеко от места ошибки и внешне могут показаться не связанными с распределением памяти;
• могут возникать только при переносе программы в другую систему программирования;
• попытки обнаружения этих ошибок путём внесения в программу отладочных действий могут скрыть их или перебросить в другое место.
Поскольку большинство указанных ошибок связано с освобождением памяти, то кардинальным решением проблемы является автоматическая сборка мусора. В этом случае имеются только операции создания объектов, а удаление происходит автоматически. С логической точки зрения можно считать, что размещённый объект существует до конца исполнения программы. Система поддержки исполнения может удалить объект, если на него больше не существует ссылок. В простейшей реализации, как это сделано, скажем, в языке Visual Basic, с каждым объектом связывается счётчик ссылок, который увеличивается или уменьшается при присваивании указательных переменных. Когда же счётчик становится равным 0, объект можно удалять.
Такая реализация оказывается недостаточной в случае, если появляется множество объектов, которые ссылаются друг на друга, но ни одна переменная программы не ссылается ни на один из них. Тогда это множество объектов может быть удалено только всё целиком.
По многим причинам - наличия адресной арифметики, возможности некорректного приведения типов и др. - автоматическая сборка мусора принципиально невозможна в языке C. Впервые она была применена в 1959 году в языке Lisp и сейчас доступна во многих языках программирования, таких как Java, С# и др., особенно там, где надёжность ставится выше, чем эффективность. Главным аргументом против автоматической сборки мусора является то, что она происходит в непредсказуемые моменты времени и достаточно сложна. Это не позовляет использовать такие языки для задач реального времени, где требуется гарантированное время отклика. Однако, методы автоматической сборки мусора постоянно совершенствуются и область их использования расширяется.
В качестве примера размещения динамической стукуры данных рассмотрим реализацию процедуры разбора выражения parse_expr. Напомним, что грамматика выражения задана следующим образом
выр::= прост-выр [(= | < | <= | <>) прост-выр ]
прост-выр::= [ + | - ] слаг ((+ | -) слаг)*
слаг::= множ ((* | /) множ)*
множ::= (перем | конст | ( выр ))
Оставим в качестве упражнения реализацию лексического анализа и будем считать,что задан тип, в котором перечислены все типы лексем:
enum TokenCode
{
TC_EOF, // конец входной строки
TC_VALUE, // число
TC_VAR, // имя переменной
TC_LPAR, // (
TC_RPAR, //)
TC_PLUS, // +
TC_MINUS, // -
TC_MULT, // *
TC_DIV, // /
...
};
и определена структура, предстваляющая лексему, в которой, если необходимо, помимо её кода указана дополнительная информация о значении или имени:
struct Token {
enum TokenCode code;
union {
float value;
char name[8];
} choice;
};
Также будем считать, что определён тип Lexer, для которого реализована функция, вырабатывающая ссылку на очередную считанную лексему:
struct Token * get_token(Lexer lexer);
Поскольку нам потребуется «заглядывать» на шаг вперёд, то нужна и функция, которая возвращает обратно лексему:
void unget_token(Lexer lexer, struct Token * token);
Разбор выражения будем осуществлять методом рекурсивного спуска, сопоставив каждому нетерминалу грамматики по отдельной функции, каждая из которых будет возвращать считанное выражение:
struct Expr * parse_expr(Lexer lexer);
struct Expr * parse_simple(Lexer lexer);
struct Expr * parse_term(Lexer lexer);
struct Expr * parse_factor(Lexer lexer);
Для экономии места приведём реализацию только двух последних функций, оставив первые две в качестве простого упражнения:
#include <malloc.h>
#include <string.h>
struct Expr * parse_term(Lexer lexer)
{
struct Expr* res = parse_factor(lexer);
for (;;)
{
struct Token * t = get_token(lexer);
switch (t->code)
{
case TC_MULT:
case TC_DIV:
struct Expr* left = res;
struct Expr * right = parse_factor(lexer);
res = (struct Expr*) malloc(sizeof(*res));
res->code = EC_BINOP;
res->choice.binop.op =
(t->code == TC_MULT? '*': '/');
res->choice.binop.left = left;
res->choice.binop.right = right;
break;
default:
unget_token(lexer, t);
return res;
}
}
}
struct Expr* parse_factor(Lexer lexer)
{
struct Expr* res = NULL;
struct Token* t = get_token(lexer);
switch (t->code)
{
case TC_VALUE:
res = (struct Expr*) malloc(sizeof(*res));
res->code = EC_VALUE;
res->choice.value = t->choice.value;
break;
case TC_VAR:
res = (struct Expr*) malloc(sizeof(*res));
res->code = EC_VAR;
strcpy(res->choice.name, t->choice.name);
break;
case TC_LPAR:
res = parse_expr(lexer);
if (get_token(lexer)->code!= TC_RPAR)
longjmp(jmp_buf, ERR_SYNTAX);
default:
longjmp(jmp_buf, ERR_SYNTAX);;
}
return res;
}
В каждом из отмеченных вызовов функции malloc создаётся новая вершина дерева разбора. В случае бинарной операции в поля left и right присваиваются ссылки на уже построенные поддеревья. Отметим, что во всех случаях память для вершины выделяются по максимуму, хотя для вершины-числа её можно было бы выделять меньше, чем для вершины-операции.
В случае синтаксической ошибки нелокальный переход longjmp возвращает управление в цикл «читать-вычислять-печатать» с соответствующим кодом ответа.
После вычисления и печати значения полученного выражения его необходимо удалить, чтобы избежать утечки памяти. Для удаления рекурсивной структуры данных, какой является Expr, потребуется рекурсивная процедура free_expr, которая обходит дерево разбора и удаляет вершины, начиная с листьев:
void free_expr(struct Expr* e)
{
switch (e->code)
{
case EC_VALUE:
case EC_VAR:
break;
case EC_UNOP:
free_expr(e->choice.unop.arg);
break;
case EC_BINOP:
free_expr(e->choice.binop.left);
free_expr(e->choice.binop.right);
break;
}
free(e);
}
Тело цикла «читать-вычислять-печатать» теперь надо переделать следующим образом:
...
Switch (setjmp(env))
{
case 0:
struct Expr * e;
fprintf(stderr,"%d\n",
e = eval_expr(parse_expr(s), m));
free_expr(e);
break;
case ERR_DIV0:
fputs("Деление на ноль",stderr);
break;
case ERR_OVERFLOW:
...
}
...
К сожалению, исправленная таким образом программа не исключает полностью утечек памяти, которые могут возникнуть в случае обнаружения синтаксической ошибки. В этом случае уже созданные объекты, соответствующие успешно разобранным частям выражения, останутся недостижимым мусором. Оставляем в качестве упражнения устранение этой ошибки.
Ввод-вывод
Практически любая программа вводит входные данные и выводит полученные результаты. Для этой цели используются файлы. Если большинство рассмотренных выше конструкций (за исключением, может быть, распределения памяти) оперировали исключительно с объектами программы, то ввод-вывод обращается к объектам операционной системы.
Операционная система работает с физическими файлами, представляющими последовательность байтов, скрывая при этом, что именно за ней стоит. Это может быть хранящийся на диске файл, принтер, клавиатура, экран дисплея, сетевой ресурс и т.п.
Идентификация файлов осуществляется на основе понятия пути, которое может существенно зависеть от конкретной операционной системы. В некоторых системах путь к файлу может начинаться с указания устройства или места в локальной сети, за которым следует последовательность имён вложенных друг в друга директорий (папок, каталогов) и собственно имя файла. В других системах путь начинается с указания имени пользователя, которому принадлежит файл. Некоторые системы могут поддерживать несколько версий файла, и номер версии требуется указать в пути. Естественно, и способ записи пути различается в разных операционных системах. Кроме того, большинство операционных систем имеют средства ограничения прав доступа к файлам и, опять же, делают это каждая по-своему. В системе MS Windows пути могут выглядеть как
\\crimson\Users\user3891\Documents\photo.jpg
C:\НГУ\Программирование\2020\Пересдача.txt
С другой стороны, программа оперирует логическими файлами, которые являются объектами программы, т.е. переменными специального типа данных. Система программирования должна предоставлять возможность установить связь между логическим файлом и физическим. При этом в разные моменты исполнения с одним и тем же логическим файлом могут быть связаны разные физические файлы, а может быть и не связан никакой файл. После установления связи через переменную-файл можно что-то считать из физического файла или записать в него.
Стандартная библиотека языка C предоставляет следующие функции низкоуровневого ввода-вывода, определённые в стандартном включаемом файле fcntl.h:
// создание файла
int creat(char *filename, int permission);
// открытие файла
int open(char *filename, int access, int permission);
// чтение из файла в буфер
int read(int handle, void *buffer, int nbyte);
// запись из буфера в файл
int write(int handle, void *buffer, int nbyte);
// установка текущей позиции
long lseek(int handle, long offset, int whence);
// закрытие файла – освобождение ресурсов
int close(int handle);
// удаление файла
int unlink(char *filename);
Продемонстрируем использование этих функций на примере:
#include <fcntl.h>
...
int fd;
char buffer[10];
fd = open("C:\\НГУ\\Программирование\\2020\\Пересдача.txt",
O_RDONLY | O_TEXT);
lseek(fd,4,SEEK_SET);
read(fd, buffer, 10);
close(fd);
...
В качестве типа, предстваляющего логический файл, используется просто целое число. На самом деле это индекс элемента в таблице, представляющей все файлы программы. Эта таблица формируется операционной системой перед запуском программы и является связующим звеном между логическими и физическими файлами. При открытии (open) или создании (creat)[33] файла система поддержки исполнения выбирает свободный элемент в этой таблицы, заполняет его, устанавливая связь с физическим файлом, и выдаёт индекс элемента. Размер этой таблицы определяет ограничение на количество одновременно открытых файлов. Для того, чтобы освободить элемент таблицы, необходимо вызвать функцию close.
Первые три элемента таблицы файлов формируются автоматически при запуске программы и означают 0 - стандартный ввод, 1 - стандартный вывод, 2 - файл ошибок. Стандартный ввод по умолчанию связываются с клавиатурой, а другие два файла - с выводом на дисплей. Они могут быть перенаправлены. Например, при запуске из командной строки в системе MS Windows
MyProg.exe < StudentData.txt > Report.txt
в качестве стандартного ввода откроется файл StudentData.txt, а стандартного вывода - Report.txt.
Для каждого открытого файла известна текущая позиция, изначально устанавливаемая в начало файла. Её можно явно переместить, используя функцию lseek. Функция read считывает с текущей позиции файла указанное количество байтов и помещает их по указанному адресу, перемещая при этом текущую позицию. Функция write осуществляет запись в файл аналогичным образом.
В принципе, этих средств достаточно для реализации обмена. Однако надо учитывать, что вызов любой из этих функций является обращением к операционной системе, что является очень дорогостоящей операцией. Так, считывание по очереди тысячи байтов потребует во много раз больше времени, чем их считывание за одно обращение к read.
Для минимизации количества обращений к операционной системе используется буферизованный ввод-вывод, типы и функции которого определёны в стандартном включаемом файле stdio.h. Идея заключается в том, что с каждым файлом связывается буфер - достаточно большой байтовый массив, размер которого может определяться характеристиками физических устройств. Например, память на жёстком диске разбивается на блоки фиксированного размера и блок всегда считывается целиком. Тогда размер буфера файла разумно сделать кратным размеру блока на диске. При использовании буферизованного ввода-вывода данные сначала перемещаются с физического файла в буфер, а лишь затем из буфера по конечному назначению. Если при последующем чтении требуемые данные уже находятся в буфере, то обращения к физическому файлу не происходит.
Определённая в stdio.h cтрукутра FILE содержит номер файла, буфер и дополнительную информацию, необходимую для реализации описанной выше схемы обмена. Для стандартного ввода, вывода и файла ошибок определены переменные stdin, stdout и stderr, соответственно.
Перечень функций буферизованного вывода практически дублирует функции низкоуровнего ввода-вывода:
// открытие файла
FILE *fopen(char *filename, char *mode);
//mode == “r” – чтение
//mode == “w” – запись
//mode == “a” – дозапись
// чтение из файла count элементов размера size
long fread(void* ptr, long size, long count, FILE * stream);
// запись в файл count элементов размера size
long fwrite(void* ptr, long size, long count, FILE * stream);
// установка текущей позиции
int fseek(FILE * stream, long offset, int origin);
// установка текущей позиции
long ftell(FILE * stream);
// закрытие файла – освобождение ресурсов
int fclose(FILE * stream);
Использования буферизованного и низкоуровневого ввода-вывода также очень похожи:
FILE * f;
char bname[8], bmarks[6];
f = fopen("C:\\НГУ\\Программирование\\2020\\Пересдача.txt",
"r");
fread(bname,7,1,f);
fread(bmarks,6,1,f);
fclose(f);
но здесь второй вызов fread уже не будет обращаться к операционной системе.
Поскольку как низкоуровневый, так и буферизованный ввод-вывод входят в стандартные библиотеки, то не всего понятно, какой из двух следует использовать. Понятно, что буферизованный вывод, несмотря на описанные выше преимущества, тоже не бесплатный. Во-первых, он требует памяти для буфера, и, во-вторых, все данные будут перемещаться дважды: из файла в буфер, а затем - из буфера по назначению. В случае, если требуется считать файл целиком и для этого достаточно памяти, то низкоуровневый ввод-вывод будет эффективнее.
Как низкоуровневый, так и буферизованный ввод-вывод может приводить к ошибкам, подобным ошибкам при работе с указателями:
· чтение из закрытого или неоткрытого файла, как и повторное закрытие файла могут сразу прервать выполнение программы, поскольку в таблице файлов имеется соответствующая информация;
· незакрытие файла, которое может привести к исчерпанию таблицы свободных файлов;
· несоответствие размера запрашиваемых данных и размера буфера - наиболее тяжёлая ошибка, приводящая к непредсказуемым последствиям.
Все рассмотренные выше процедуры чтения и записи работают только с байтовыми массивами. Это значит, что вызов
int x = 1234;
fwrite(&i, sizeof(int), 1, f);
запишет в файл f бинарное представление числа x, а не текст "1234".
Для преобразования данных в текст используется форматный ввод-вывод. Мы уже рассматривали функцию printf, которая делает это в языке C, а также проблемы с ней связанные. Например, при вызове
fprintf(f, "%6.2f + %6.2f = %7.2f\n", x, y, x+y);
транслятор не может проверить, что элемент формата %7.2 соответствует параметру x+y, если в него не заложены специфические знания о функции fprintf. И даже если это так, то строка-формат может не быть константой, а формироваться динамически, например, считываться из файла.
В языке C имеются достаточно развитые средства форматирования, позволяющие печатать десятичные, восьмеричные и шестнадцатеричные числа, вещественные числа в различном виде, вставлять дополнительные пробелы по левому или правому краю поля вывода и т.д. Подробнее об этом можно узнать в стандарте языка C. Однако, набор этих средств ограничен и нет возможности его расширить. Например, если возникнет потребность печатать числа в двоичном виде или выражения, заданные указателем на рассматривавшуюся выше структуру struct Expr, то встроить эту функциональность в printf не удастся.
Простым решением проблемы является использование отдельных функций ввода-вывода для каждого типа данных. Например, в языке Modula-2 те же действия можно выполнить с помощью последовательности операторов
FWriteFloat(f, x, 6, 2);
FWriteString(f, ' + ');
FWriteFloat(f, y, 6, 2);
FWriteString(f, ' = ');
FWriteFloat(f, y, 7, 2);
FWriteLn(f);
что замечательно с точки зрения статического контроля, но гораздо менее наглядно и, вероятно, менее эффективно.
Многие языки программирования вводят для форматного ввода-вывода специальные конструкции. В языке Паскаль для вывода используются стандарные псевдо-процедуры Write и WriteLn:
WriteLn(f, x:6:2, ' + ', y:6:2, ' = ', x+y:7:2);
Эти псевдо-процедуры, в отличии от обычных процедур, могут иметь произвольное количество параметров, а также в параметрах можно указывать способ форматирования, специфичный для конкретного типа. То есть процедурами они называются только для удобства восприятия, а на самом деле являются специальными синтаксическими конструкциями.
В некоторых языках операторы ввода-вывода имеют весьма развитый синтаксис. Например, в языке Фортран оператор
READ (f, 2) (X(I), I=1,100)
2 FORMAT (16F5,1)
содержит внутри цикл, который считывает 100 элементов массива X. Отметим, что в данной конструкции действия, связанные с преобразованием числа в текст, отделены от собственно ввода и задаются специальной конструкцией FORMAT. Это даёт возможность использовать один и тот же формат в нескольких командах ввода-вывода.
В языке C# отделение форматирования от ввода-вывода привело к понятию интерполяции строк, которая позволяет вставить в строковую константу форматированные параметры. Например, интерполированная строка
$"{x,6:f2} + {y,6:f2} = {x+y,7:f2}"
по существу представляет собой достаточно сложную последовательность вызовов операций форматирования, которую порождает и может полностью проконтролировать транслятор.
[1] Здесь и далее в этой главе нас интересуют в первую очередь содержательные понятия, а не способ их оформления в конкретном языке. Поэтому здесь можно не вникать в подробности способа записи, пунктуации, обозначений и т.п.
[2] Здесь слово «проще» не означает, что языки программирования простые. Правильнее будет понимать это утверждение так, что языки программирования сложные, а естественные языки – совсем сложные.
[3] Если уж быть совсем точным, то исходным представлением является последовательность битов в памяти программы, а сопоставление им символов из входного алфавита требует дополнительного объяснения.
[4] Под потоком здесь понимается последовательность, конструируемая по мере необходимости. Так, рассматриваемому ниже синтаксическому анализу, который использует результаты лексического, может не требоваться вся последовательность сразу, поскольку он выбирает очередные лексемы одну за одной. Это, в частности, даёт возможность совместной работы лексического и синтаксического анализов.
[5] Формально мы должны выписать все 26 правил для букв и 10 правил для цифр.
[6] Назначение любого языка программирования - это, во-первых, способ передачи алгоритмического знания от человека к машине и, во-вторых, средство накопления такого знания.
[7] В общем случае исчисление типов в современных языках программирования может быть весьма сложно как с точки зрения формального описания, так и с точки зрения реализации.
[8] Формально нам нужны три разные семантические функции - отдельно для вычисления выражений, для вычисления операторов и для вычисление последовательности операторов. Мы будем их все обозначать одинаково, подразумевая, что то, какая именно функция используется в конкретном месте, понятно из контекста.
[9] Точнее сказать: получаемое применением памяти (как функции) к имени переменной.
[10] Соображения о размере исходного кода иногда звучат и сейчас, когда код программы в исходном виде передаётся по сети, например, для языка JavaScript.
[11] На самом деле текст может выглядеть несколько иначе, поскольку в нём должны остаться команды, обеспечивающие его привязку к исходному тексту.
[12] Типичный пример неустойчивого синтаксиса!
[13] В общем случае вычисление чисел Фибонначи в таком виде требует экспоненциального количества сложений, а после такой оптимизации - линейного.
[14] Отметим, что становятся не вполне точными сделанные ранее утверждения о том, что синтаксис препроцессора никак не согласован с синтаксисом языка C, и о том, что препроцессор лишь манипулирует с последовательностями лексем.
[15] Конечно, это только естественное предположение. На самом деле может оказаться, что одноимённые функции делают совершенно разные вещи.
[16] Заметим, что то, как символ изображается, является несомненно важной, но всё-таки вторичной его характеристикой, и символы "латинская-прописная-o" и "кириллическая-прописная-o" - это совершенно разные символы, хотя и имеют одинаковое изображение. Также, отдельно рассматриваются вопросы шрифтов, размеров и т.п.
[17] Формально говоря, последнее можно было бы оспорить, поскольку при фиксированном размере памяти, отводимом на представление вещественного числа, в нём может быть лишь конечное множество значений, которые, очевидно, можно перечислить.
[18] Конечно, транслятор может быть достаточно "умным" и не вставлять проверку там, где в этом нет необходимости. Однако, в общем случае статическое определение по тексту программы того, лежит ли значение индекса в нужных границах, является алгоритмически неразрешимой проблемой.
[19] Конечно, правильнее было бы ввести для этого соответствующий тип перечисления, а не пользоваться директивами препроцессора.
[20] А может быть и отрицательным, если в данной реализации int совпадает с short.
[21] Хотя, казалось бы, можно было заметить, что переменная A описана именно как массив, а не просто указатель, и для неё выполнять контроль индексов.
[22] Этот пример демонстрирует в основном то, каким образом можно можно манипулировать указателями. Подробности, касающиеся управляющих структур и динамического размещения памяти (malloc) будут рассмотрены далее.
[23] Понятно, что в рамках выполнения всей программы, если рассмотренное выше выражение вычисляется многократно, то вычисление аргументов может выполняться и после умножения, выполненного на предыдущей итерации.
[24] Транслятор может выдать об этом предупреждение. А может и не выдать...
[25] В языке Фортран метки обозначаются числами, а не идентификаторами.
[26] Существенность здесь понимается неформально, в том смысле, что исходная задача гораздо проще формулируется с помощью рекуррентных соотношений, но не как невозможность реализовать задачу без использования рекурсии.
[27] Это пример очень плохой оптимизации, и так делать не следует. Во первых, мы использовали три дополнительные операции типа сложения, а, во-вторых, что более существенно, эта процедура будет работать неправильно в случае потери точности при арифметических операциях, например, когда x очень большое, а y очень маленькое.
[28] Именно массивов, а не ссылок на первый элемент массива, как в языке C.
[29] Слово thunk является субстандартной или диалектной совершенной формой глагола think (думать).
[30] Надо признать, что аналогичная проблема возникает и при передаче параметров по необходимости: формировать thunk нужно ровно в том месте, где находится фактический параметр, поскольку в противном случае он не будет иметь доступа к использованным локальным переменным. Приведённые в обсуждении примеры корректны только в предположении, что в фактическим параметре встречаются только глобальные переменные.
[31] Для дальнейших рассуждений нам неважно, как именно устроен этот объект и как, используя его, получить значение переменной, входящей в выражение.
[32] На самом деле setjmp является макросом, поскольку в противном случае она не могла бы изменить параметр, переданный по значению.
[33] Здесь нет опечатки, хотя "создать" по-английски будет "create". Авторы библиотеки заявляли о желании переименовать эту функцию, которое, к сожалению, невыполнимо по причинам обратной совместимости.
