Этюды для программистов

18. Читаем, пишем, считаем, или Конструирование интерпретатора форматов

Вам, вероятно, пришлось написать по крайней мере одну программу, которая исторгала из машины бумажный поток, несущий искусно оформленные данные. Строка за строкой сомкнутыми рядами выступали из печатающего устройства целые батальоны чисел под предводительством четких заголовков. Интересовали вас только лишь два или три числа, но не напечатать всего было как-то неловко — ведь это так просто! А вдруг кому-то и в самом деле захочется узнать точную сумму налога для служащего 1793 на рабочем месте 907, выплаченную им в сентябре пять лет назад.

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

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

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

(yf¹s¹f²s²…fⁿsⁿz),

где n может быть нулем,

у и z — последовательности наклонных черточек, возможно пустые,

fⁱ — либо одиночный код формата, либо формат общего вида, перед которым может стоять натуральное число[25],

sⁱ — разделитель, т. е. последовательность из запятых и наклонных черточек, которая в некоторых случаях может быть пустой.

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

Предположим, произошло обращение к операции ввода/вывода. Указатель текущей позиции в файле устанавливается на начало следующей записи[26]. Курсор в формате устанавливается на начальную открывающую скобку и движется вправо либо до первого кода, которому должна соответствовать переменная в списке переменных, либо до правого края формата. Такой процесс позволяет при помощи инструкции вывода напечатать строку данных, не пересылая никаких данных из переменных. Интерпретатор форматов будет иметь некоторую внутреннюю память (организованную, как правило, в виде стека), которая будет освобождаться и на которую мы будем время от времени ссылаться, говоря, что интерпретатор что-либо «запомнил». Основной цикл просмотра формата прост. Интерпретатор получает очередную переменную из списка переменных. Курсор начинает двигаться вправо по формату в поисках такого кода, который соответствует передаче элемента данных из переменной в файл или обратно. При движении курсора вправо могут встречаться такие коды, которые влияют на содержимое файла или устанавливают новые значения параметров, управляющих работой интерпретатора. Действия, предписываемые этими кодами, выполняются непосредственно в процессе сканирования. Перед некоторыми кодами допускаются коэффициенты повторения — такой код используется соответствующее число раз. То есть один и тот же код может использоваться с несколькими переменными списка, значит, интерпретатор должен помнить убывающее от цикла к циклу значение счетчика повторений кода. Если курсор дошел до крайней правой закрывающей скобки, то он возвращается к последней открывающей скобке первого уровня без коэффициента повторения, а если таковая отсутствует, то к начальной открывающей скобке формата. Вот три типичные ошибки, которые могут встречаться при форматном вводе/выводе: при вводе встретился конец файла; интерпретатор дважды подряд вышел на правую закрывающую скобку формата, не переслав при этом ни одного элемента данных; нет соответствия между типом кода формата, типом переменной в списке ввода/вывода и типом элемента данных, фактически находящегося в файле (последнее относится только к вводу). При завершении операции вывода последняя частично сформированная запись пишется в файл.

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

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

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

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

nX При вводе пропускается n литер файла, при выводе в файл записывается n пробелов. Код самозавершающийся, передачи данных не происходит.

nHh1···hn При вводе очередные n литер файла помещаются на место литер h1···hn формата. При выводе n литер h1···hn записываются в файл. Любая из литер hi может быть пробелом, это единственный случай, когда пробел является значащей литерой в формате. Код самозавершающийся. Обмена данными между файлом и переменными не происходит.

rAw Пусть g — число литер, помещающихся в переменной, которая участвует в данном цикле интерпретации формата. Если при вводе w ≥ g, то крайние правые g из очередных w литер файла передаются в переменную, иначе в переменную попадут очередные w литер файла, дополненные справа g − w пробелами. Если при выводе w ≥ g, то в файл выводятся w — g пробелов и затем g литер переменной, в противном случае в файл попадут w крайних левых литер переменной. Коэффициент повторения r необязателен, код несамозавершающийся.

rLw При вводе очередное поле из w литер файла должно представлять собой последовательность пробелов, за которой следует одна из букв Т или F, а далее произвольная последовательность литер, что воспринимается соответственно как значение истина или ложь. При выводе в файл помещаются w − 1 пробелов и одна из букв Т или F. Коэффициент повторения r может отсутствовать; код несамозавершающийся.

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

sPrFw.d При вводе число с плавающей точкой читается из поля длины w литер. Если поле ввода состоит только из цифр и пробелов или если левее (w − d + 1) -й литеры (начиная счет с 1) встретился только знак, то мы получим вводимое вещественное значение лишь после того, как будет вставлена десятичная точка между (w − d)-й и (w − d + 1)-й позициями поля ввода. Если вводимая цепочка литер содержит точку, то подразумеваемая позиция точки игнорируется. Если вводимая цепочка литер имеет вид вещественного или целого числа, за которым следует либо еще одно целое число со знаком, либо буква «Е» и целое число со знаком или без него, то это второе число воспринимается как порядок и значение вещественного числа умножается на десять в степени, равной порядку числа. Если присутствует только порядок числа с буквой «Е» вначале, то считается, что перед ним стоит вещественное число, равное единице Если показательная часть числа отсутствует, то прочитанное вещественное число, прежде чем оно будет присвоено переменной из списка ввода, умножается на степень десяти с показателем, равным текущему значению масштабирующего множителя. При выводе число с плавающей точкой записывается в виде x₁···x_n.y₁···y_d. Число округлено до d знаков после точки, и, если это необходимо, снабжается знаком минус. В поле вывода обязательно присутствует точка, так что при выводе по коду F всегда выполняется неравенство w ≥ d+1. И в этом случае тоже выводимое значение прижимается к правому краю поля вывода. Спецификация масштабирующего множителя sP, как и коэффициент повторения r, не обязательна. Новое значение s (s — любое целое число со знаком) действует до тех пор, пока не встретится еще одна спецификация масштабирующего множителя. Код F несамозавершающийся.

sPrEw.d Ввод осуществляется так же, как для кола F. Основная форма поля вывода имеет вид 0.y₁···y_dEz₁···z_m где перед первым нулем и после буквы Е может стоять знак минус, если он нужен, а значение m достаточно для размещения максимального порядка, даже если для данного числа это не нужно. Если текущее значение масштабирующего множителя равно q, то вещественная часть основной формы умножается на 10^q, а порядок уменьшается ка q единиц. При q > 0 будет q цифр слева от точки и max(d − q + 1, 0) цифр справа от нее: при q ≤ 0 слева от точки будет стоять нуль, а справа d + q цифр[27]. Так же как и код F, код Е — несамозавершающийся, а спецификация масштабирующего множителя sP и коэффициент повторения r могут отсутствовать.

sPrGw.d Ввод, а также интерпретация спецификаций sP и r осуществляется так же, как для кода F. Для вывода по коду G в зависимости от величины выводимого числа выбирается один из кодов F и Е. Пусть М — выводимое значение, причем 10^k−1 ≤ М < 10^k, где 0 ≤ k ≤ d, тогда вывод производится как для кода F(w − 4).(d − k), 4X; в противном случае используется код Ew.d. Отметим, что масштабирующий множитель игнорируется в случае, когда для вывода выбирается код F. Код G несамозавершающийся.

Тема. Создайте пакет программ форматного ввода/вывода для вашей ЭВМ. В общем случае он будет иметь ряд входных точек, доступных для пользователя (в роли которого, как правило, выступает сгенерированная компилятором объектная программа), а также ряд внутренних подпрограмм, которые должны быть защищены от доступа со стороны пользователя. Среди пользовательских входов должны быть: вход для инициализации с параметрами, определяющими операцию ввода или вывода, канал ввода/вывода и формат; входы для каждого типа переменных (вещественной, целой, логической и еще любой из них, используемой для представления текстовых данных), а также вход для терминирования ввода/вывода. Внутреннее представление данных может иметь вид, принятый на вашей ЭВМ, или вид, описанный в гл. 25 для ЭВМ УМ-1. Проведите основательное тестирование своих программ и убедитесь, что округление и обработка особых случаев выполняется правильно, а в случае ошибок выдаются соответствующие сообщения.

Указания исполнителю. Наиболее трудная часть задачи — составить ясное представление о поведении вещественных чисел на вашей ЭВМ. Преобразование данных текстового, целого и логического типов выполняется легко, а для сканирования формата и поддержания буферов годятся весьма простые методы. Однако вы, вероятно, обнаружите, что для реализации вполне правильного округления придется серьезно поразмыслить, а, быть может, и немного поэкспериментировать. Обязательно включите в свои тесты значения чуть больше и чуть меньше степеней 10, чуть меньше 10^−d и т. д. Не поддавайтесь соблазну выделять все увеличивающееся количество частных случаев с целью исправить допущенные ранее в работе промахи, попытайтесь вместо этого найти какой-то другой подход. Одной из наших досаднейших программистских неудач был пакет форматного ввода/вывода, разросшийся наподобие Топси до свыше 3000 строк на языке ассемблера. Как непросто теперь заменить его более ясной и эффективной программой примерно в 1000 строк, написанной еще кем-нибудь! С какой радостью мы бы навсегда избавились от этого монстра!

Инструментовка. Это одна из тех задач, для которых можно порекомендовать язык ассемблера. Пакеты форматного ввода/вывода должны быть достаточно эффективными, и к тому же они принадлежат к числу программ, время выполнения которых не концентрируется в нескольких компактных циклах, а сильно размазано (для большинства программ на 10% текста приходится 90% времени выполнения). Кроме того, языки более высокого уровня скрывают от программиста тонкости специфической работы с данными, необходимые для реализации форматного ввода/вывода. Если в вашем распоряжении имеется такой язык, как BLISS или PL/360 (или, быть может, XPL), то это самые лучшие кандидаты, поскольку они допускают достаточно хороший контроль над машиной и свободны от недостатков языка ассемблера.

Длительность исполнения. Одному исполнителю на 5 недель.

Развитие темы. Имеется масса возможностей расширить форматы. Можно добавлять новые коды. Например:

'x···x' То же самое, что nHX···x. Апостроф представляется парой подряд стоящих кавычек.

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

Tn Переместиться в n-ю позицию текущей записи. Такое передвижение может привести к повторному чтению или записи части вводного или выводного файла.

Можно также ослабить слишком строгие требования для ширины поля ввода/вывода. Так, формат E.d может означать при выводе, что система сама подберет ширину w поля, а одиночный код I при вводе может означать, что следующее целое число будет ограничено пробелом, запятой или концом записи, а не шириной поля. Почти в каждой системе ввода/вывода для Фортрана есть подобные расширения, которые вы также можете добавить.

USA Standart FORTRAN. United States ot America Standards Institute, New York, 1966.

Описанные нами коды формата несколько отличаются от тех, которые приняты в указанном стандарте. Нам кажется, что стандарт в этой области не вполне отражает потребности практического программирования, хотя, если вместо описанных здесь кодов будут реализованы спецификации, приведенные в стандарте, мы будем только рады (объем работы примерно одинаковый). Чтение стандарта уже само по себе есть некое испытание, которому надо подвергнуть каждого преданного пользователя Фортрана. Остается только удивляться: для какого же языка написаны существующие трансляторы, поскольку ясно, что они — не для стандартного Фортрана!?

*Катцан Г. Язык Фортран-77. Пер. с англ. — М.: Мир, 1982.

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