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

Тема. Напишите процессор Трака для вашей системы. Процессор должен реализовывать описанные выше алгоритм Трак и встроенные функции. Если в вашей системе имеется возможность хранения файлов, используйте ее для организации внешней памяти бланков. Блоки, записанные в каком-либо сеансе работы с процессором, должны быть доступны в последующих сеансах. Разумно будет включить в ваш процессор как можно больше внутренних средств отладки. Рекомендации исполнителю. В каждой системе приняты свои соглашения относительно набора литер и способа завершения строки. Один из шагов алгоритма Трак выбрасывает из сканируемого текста незащищенные литеры возврата каретки, перевода строки и табуляции. Это позволяет спокойно вводить исходные данные, не думая о возможности случайного разбиения программы на несколько строк вследствие ограничений на длину строки физических устройств. Но выбрасывание этих литер означает также, что их следует явно указывать во входном потоке, чтобы мы могли при желании управлять форматом вывода программы. Так, например, если CR-LF обозначает последовательность литер «возврат каретки — перевод строки», то при вводе цепочки Один CR-LF Два мы увидим на печати ОдинДва в одной строке, в то же время исходные данные Один(CR-LF)Два приведут к печати слова Один на одной строке, а Два — на следующей. Позаботьтесь о том, чтобы ваш процессор правильно работал в этой ситуации. Описывая алгоритм, мы лихо проскочили вопрос об установке и поиске меток аргументов и функций в нейтральной цепочке. На самом деле весьма важно всегда иметь точный список функций и аргументов, в котором указан, в частности, порядок их появления. Проще всего добиться этого с помощью стека. Этим стеком распоряжается исключительно процессор. Каждый раз, когда алгоритм выполняет шаг 1, стек устанавливается в пустое состояние. При маркировке любого начала функции на стек помещается новый блок функции. В блоке функции имеется основная часть постоянного вида, включающая, как минимум, положение в стеке ближайшего нижнего, блока функции, режим вызова данной функции, положение в нейтральной цепочке первой литеры функции, число аргументов функции, обработка которых начата, и число законченных аргументов и положение в нейтральной цепочке начала аргумента, который в данный момент сканируется. Выше постоянной части в стеке располагаются элементы, указывающие для каждого законченного аргумента его начало и конец. Часть этой информации может неявно присутствовать в других местах. Среди типичных ошибок реализации — неправильная работа с пустой цепочкой и потеря информации о функциях, расположенных в нижней части стека, при обработке вышележащих функций.

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