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

4. Печатник-подмастерье, или Автоматическое форматирование текста

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

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

Система подготовки публикаций состоит из четырех компонентов. Во-первых, необходима хорошая файловая система, в которой можно хранить готовящиеся и архивные текстовые файлы. Обычно память для хранения файлов предоставляется операционной системой, но известен случай, когда в качестве такой памяти использовался шкаф для перфокарт в кабинете автора. Конечно, перфокарты не самый практичный носитель, когда речь идет об операциях над большими объемами информации, например при издании газет. Во-вторых, нужен редактор текстов, для того чтобы вносить изменения и поправки в файлы перед выдачей на печать. Редакторы текстов также имеются, в большинстве операционных систем, но может понадобиться специальный редактор издания, обладающий именно теми возможностями, которые требуются при подготовке публикаций. Третий элемент — форматор, который умеет размещать заголовки, выбирать размер страницы, располагать материал в таблицах, выделять абзацы и т. п. Форматор работает с такими элементами текста, как слова, предложения, абзацы, т. е. уже на том уровне, на котором текст воспринимается человеком. Наконец, имеется программа-наборщик, которая преобразует форматированный текст в его образ на внешнем носителе. Работа этой программы связана в первую очередь с особенностями шрифтов, физическими размерами, командами выводного устройства, отдельными литерами и тому подобными вещами. Программа-наборщик, так же как и оператор линотипа, готова выдать на печать любой вздор, лишь бы он поместился в отведенное ему место. Функционально файловая система и редактор текстов заботятся о содержании текста, а форматор и наборщик — о том, как он будет выглядеть. Этот этюд посвящен форматированию[8] текстов.

Процесс форматирования текста вручную проходит несколько этапов. Вначале автор создает черновик рукописи, и он перепечатывается набело. Затем автор вместе с редактором (по крайней мере, когда речь идет о больших публикациях) принимаются терзать эту рукопись, пока там не останется живого места, после чего автор начинает работу над новым вариантом рукописи. Этот цикл повторяется до тех пор, пока и автор, и редактор не будут удовлетворены. Затем рукопись еще раз перепечатывается (как правило, через два интервала) и передается техническому редактору. Он размечает рукопись, давая всевозможные указания относительно наборных шрифтов, размера и расположения заголовков, полосы набора, курсива и прочих деталей, определяющих в конечном счете внешний вид издания. Разметка делается при помощи специальных обозначений, и каждый значок ставится в то место рукописи, к которому он относится. Размеченная рукопись отправляется в наборный цех, где текст набирают и делают корректурный оттиск в нескольких экземплярах, называемый версткой. Верстка возвращается в редакцию, где редактор и корректор сверяют ее с окончательным вариантом рукописи. Мелкие ошибки легко исправить в наборном цехе, заменив одну строку набора другой. Но как быть, если автор вдруг решит, что вся четвертая глава никуда не годится, или художнику покажется, что гарнитура бодони будет выглядеть лучше литературной? Такие изменения повлекут за собой новый набор и обойдутся недешево. Можно только диву даваться, насколько по-разному воспринимаются типографский текст и тот же текст, напечатанный на машинке.

Система подготовки публикаций с помощью ЭВМ исключает из этого цикла большую часть работы и множество людей. Как и прежде, автор должен подготовить первоначальный вариант рукописи. Но затем рукопись поступает не в машинописное бюро, а в файловую систему машины. Текст рукописи можно ввести, как и любую информацию для ЭВМ, либо с перфокарт, либо непосредственно через терминальное устройство машины. (Большая часть этой рукописи была отперфорирована.) Автор исполняет также и функции технического редактора, сопровождая текст простейшими командами для форматора. Текстовый файл с рукописью обрабатывается форматором и наборщиком, в результате чего получается черновая верстка окончательного печатного текста. Эта черновая верстка выглядит куда как более чисто, чем машинописный вариант, — она оформлена в виде отпечатанных типографским способом страниц с правильными номерами, радующим глаз шрифтом и т. п. Заметим, что все это происходит еще до начала какого-либо пересмотра рукописи.

Затем автор и редактор начинают работать над рукописью. Интеллектуальная часть работы точно такая же, как и раньше, но теперь им значительно проще представить себе конечный результат, поскольку рукопись выглядит почти как готовое печатное издание. Да и процесс редактирования уже не такой трудоемкий. Для того чтобы добавить или убрать фразу, не нужно ничего перепечатывать — все изменения вносятся при помощи редактора текстов, подобно тому как заменяются строки в программах. Переупорядочение больших разделов, а также вызов текстов, временно отсутствующих в основной памяти, осуществляется средствами файловой системы. Поскольку текст в любом случае придется переформатировать, то можно поменять и команды форматора, тоже просто изменив содержимое текстового файла. Наконец, выполнение программы форматора на ЭВМ стоит такие пустяки, что все множество сеансов форматирования текста обойдется наверняка несравненно дешевле, чем одна перепечатка его на машинке при старом способе работы. Имеется, правда, единственное опасение — авторы, зачарованные столь аккуратно оформленной рукописью, будут неохотно вносить в нее изменения; ведь в течение долгих лет за всякое исправление в верстке, противоречащее рукописи, им приходилось расплачиваться из авторского гонорара. Поэтому если мы хотим правильно использовать ЭВМ для подготовки публикаций, то и авторов необходимо должным образом перестроить[9].

Как работает типичный форматор? В исходном файле текст, предназначенный для редактирования, оформлен как обычная машинопись (с той разницей, что здесь не нужно заботиться об интервале, полях и т. п.) с добавленными командами форматирования. Команды должны располагаться с первой позиции записи и начинаться со знака «?», чтобы их можно было отличить от обычного текста, по крайней мере в нашем примере. Для самого простого вывода достаточно иметь команды для установки размера страницы и для разбиения текста на абзацы. В пределах одного абзаца исходный текст можно вывести в одном из трех режимов:

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

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

Выравнивание — сначала из исходного текста формируется полный абзац в плотном режиме. Затем в каждую строку, кроме последней, добавляются пробелы между словами так, чтобы последнее слово заканчивалось у правого края страницы. Ни в один промежуток нельзя добавить (n + 1)-й пробел, пока во всех остальных промежутках данной строки не стало по n пробелов, а пробел после символа конца предложения можно добавить, лишь если во всех других промежутках строки уже есть по два пробела. Пробелы следует добавлять в случайно выбираемые промежутки между словами; если пробелы вставлять по какому-нибудь заранее выбранному правилу, то в выводном тексте образуются неприятные для глаза белые полосы. Выровненный текст по внешнему виду приближается к книжному, но не так совершенен, поскольку не учитываются неодинаковые размеры букв.

Для обработки простого текста достаточно иметь команды ?размер, ?абзац и ?режим. Действие этих команд продемонстрировано на рис. 4.1 и 4.2.

Рисунок 4.1. Пример необработанного исходного текста.

Рисунок 4.2. Тот же текст после форматирования.

?размер высота ширина

Команда ?размер устанавливает размер страниц текста; страница измеряется аргументами высота, равным количеству строк, и ширина, равным количеству литер в каждой строке. Как только выведены очередные строки в количестве высота штук, форматор начинает новую страницу. Выводные строки могут заполнять все пространство между колонками с номерами 1 и ширина. Новую команду ?размер можно выдать в любом месте текста, но она приводит к автоматическому завершению текущего абзаца. Формирование прерванного абзаца завершается со старыми значениями высота и ширина, а затем начинают действовать новые значения. Изменение размера страницы может привести также к переходу на новую страницу, если новое значение высота меньше прежнего. В начале сеанса форматирования значение высота равно 40, а ширина — 72, и если пользователя эти значения устраивают, то команда ?размер необязательна.

?режим тип заполнения

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

?абзац отступ отбивка

По команде ?абзац начинается новый абзац. Первая строка нового абзаца начинается на отступ позиций правее левого поля (отступ может быть нулевым, а позже вы увидите также, что он может быть отрицательным), а между предыдущим и новым абзацем оставляются пустые строки, количество которых задает аргумент отбивка. Если не указана отбивка или отбивка и отступ, то их значения берутся из последней команды ?абзац, где они были указаны. Начальное значение отступ равно 3, а отбивка — 0; если эти значения удовлетворительны, то в команде ?абзац можно не указывать аргументы. Заметим, что при значении отступ, равном 3, первая строка нового абзаца начинается в колонке 4.

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

?поле слева справа

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

?интервал отбивка

Команда ?интервал устанавливает, что между строками вывода нужно оставлять отбивка − 1 пустых строк. Установка значения отбивка, равного 1, соответствует указанию для машинистки печатать через один интервал. Отбивка 2 соответствует печати через два интервала, отбивка 3 — через три интервала и т. д. Эта команда прерывает текущий абзац.

?пусто n

По команде ?пусто завершается текущий абзац, выводится n пустых строк с текущим значением интервала между строками. Эта команда по своему действию эквивалентна (n + 1) возвратам каретки на пишущей машинке. Если из-за вывода пустых строк происходит переход на следующую страницу, то новая страница действительно начинается, но пустые строки в начале страницы не выводятся. По умолчанию значение n нулевое.

?пропуск n

Команда ?пропуск работает так же, как ?пусто, но выводится точно n пустых строк; текущее значение аргумента команды ?интервал не учитывается. Это действие эквивалентно повороту валика пишущей машинки на n + 1 интервалов.

?центр

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

?страница

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

?остаток n

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

?колонтитул глубина место позиция

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

?номер n

По команде ?номер номер текущей страницы устанавливается равным n; текущий абзац не прерывается.

?прерывание

Команда ?прерывание означает переход к новому абзацу.

?сноска глубина

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

?имя фиктивное настоящее

Эта команда сообщает форматору, что впредь до следующей команды ?имя вместо литеры, имеющей настоящее имя будет использоваться литера, имеющая фиктивное имя. Каждый раз перед выдачей строки на печать все фиктивные литеры заменяются соответствующими настоящими литерами. Например, пробелы используются специальным образом для разделения слов; при помощи команды ?имя можно включить в выводной текст пробелы, не разрывая при этом слов. Команда ?имя не прерывает текущий абзац. Все переименования можно отменить, выдав команду ?имя без аргументов.

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

. ? ! .) ?) !) ." ?" !" .") ?") !") :

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

Если ваш форматор будет работать в системе разделения времени, которая умеет вводить прописные и строчные буквы и допускает вывод на терминал, то, несомненно, алфавит языка, на котором реализован форматор, должен включать большие и малые буквы. Но если вы работаете в системе, ориентированной на ввод с перфокарт, то у вас возникнут трудности с чтением букв двух видов, поскольку на перфораторах, как правило, отсутствует переключатель регистров (лучше, если системе все-таки удастся каким-то образом печатать буквы обоих видов, иначе ваше начинание обречено на провал). Для ввода с перфокарт выберите какую-нибудь литеру, например ↑, которая будет служить признаком прописной буквы. Так, текст

Машина БЭСМ-6

нужно перфорировать как

↑машина ↑б↑э↑с↑м-6

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

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

Тема. Напишите для вашей системы форматор текстов, понимающий описанные выше команды. Поскольку форматирование текста не имеет большого смысла без возможности вывода прописных и строчных букв, то следует использовать выводное устройство с буквами обоих видов. Скорее всего, такое устройство окажется довольно дорогим, и вы не сможете позволить себе достаточное количество тестовых пусков. И хотя, естественно, вы рассчитываете, что у вас с первого же раза все правильно заработает, полезно все же уметь делать тестовые выдачи, по форме аналогичные вводу с перфокарт. Такие выдачи можно делать на обычном АЦПУ.

Указания исполнителю. Вы обнаружите, вероятно, что ваша программа тратит большую часть времени на ввод и вывод и совсем немного времени — на перемещение слов в строке. Значительная часть времени обработки будет уходить, по-видимому, на поиск пробелов между словами. С учетом всего этого ясно, что львиную долю усилий по оптимизации программы следует направить на центральный алгоритм сканирования и на взаимодействие форматора с внешним миром. Обработка команд и алгоритм размещения слов должны быть запрограммированы так, чтобы все было понятно. Как правило, для ввода/вывода следует пользоваться стандартными языковыми средствами, но в данной задаче мы сталкиваемся с тем случаем, когда особенности вашей операционной системы можно употребить с пользой для дела. Важно помнить только, что использование этих особенностей должно быть сконцентрировано в пределах подпрограмм ввода-вывода, а не рассеяно по всему форматору.

Набор команд был подобран с таким расчетом, чтобы требуемый вывод можно было получить за один просмотр входных данных. Ни для одной команды алгоритм не должен требовать повторного просмотра ввода. Если для некоторых алгоритмов потребуется рабочее пространство, как, например, для алгоритма обработки сноски, то попробуйте применить двойную буферизацию вывода и использовать свободный буфер в качестве рабочего пространства. Для оценки времени работы укажем, что форматор, с помощью которого был получен английский оригинал настоящего издания, тратил на одну страницу вывода примерно 2 с времени ЦП, а написан он был на некоем диалекте языка Трак (см. гл. 28). Да и большинство других форматоров тратит на оформление каждой страницы вывода тоже примерно 1–2 с независимо от скорости ЭВМ, на которой они работают. Единственное разумное объяснение этому факту — то, что пользователи находят такую скорость приемлемой, и программисты соответственно не считают нужным тратить усилия на ускорение форматоров.

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

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

Развитие темы. В этой книге можно встретить полужирный шрифт, курсив, греческие буквы, латинские рукописные и другие специальные символы. Все это имелось на выводных устройствах, но, как нетрудно догадаться, ни перфораторы, ни файловая память подобными возможностями не обладают. Для представления таких специальных литер используются специальные соглашения. Пусть, например, слова “et cetera” требуется набрать курсивом. Для этого нужно ввести текст “&i+ et cetera &i−”, и тогда на выводе получится “et cetera”. Тройка литер, начинающаяся значком “&”, называется переключателем шрифта. В данном примере вы видели включение и выключение курсива[10]. Рассматривая подчеркивания, верхние и нижние индексы и т. п. как специальные начертания шрифтов, можно таким образом обеспечить доступ ко всем дополнительным средствам, имеющимся на вашем устройстве вывода. Разумеется, можно включить одновременно несколько переключателей, например чтобы вывести подчеркнутые греческие верхние индексы. (Возможно, вам понадобится также переключатель шрифта для возвратов по тексту вида & × n, где n — цифра от 1 до 9.)

Керниган, Черри (Kernighan B. W., Cherry L. L.). A System for Typesetting Mathematics, CACM, 18, 3, pp. 151–157, 1975.

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

Керниган, Плоджер (Kernighan В. W., Plouger P. J.). Software Tools. Addison-Wesley, Reading MA, 1976.

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

*Баяковский Ю. М., Мишакова С. Т. Автоматизированная система подготовки публикаций и документов (АСПИД), ИПМ АН СССР им. М. В. Келдыша. Препринт № 19, 1977.

Система АСПИД написана на Фортране и на машине БЭСМ-6 тратит на подготовку страницы вывода также около 2 с.