 |
Реализация модулей в современных компиляторах Pascal
|
|
|
|
Программные модули.
Наиболее сложная часть программирования это удержание интеллектуального контроля над создаваемой программой, это становится сложнее, по мере того как в нее включается все больше деталей. Для поддержания контроля существенно, чтобы части программы проектировались и прятались, чтобы не было необходимости изучать их детали снова. Программный модуль – это механизм инкапсуляции идей программы именно таким образом. Несколько программных модулей, один для управления счетчиком, другие – для управления очередью будут разработаны в этой главе. Модуль отличается от процедуры тем, что он может сохранять информацию между успешными операциями, которые он выполняет. В этом смысле он ведет себя как формальный объект, называемый конечным автоматом.
Стратегия пошаговой детализации предназначения для разработки любой программы как иерархии шагов проектирования, которые определяют задачи, затем расширяют задачи в разделы проекта в соответствии с требованиями задач. Каждая детализация задачи – часть программы, для которой задается спецификация в терминах функции частного значения, которой она должна удовлетворять. Эта функция описывает преобразования данных, которые должна выполнять часть программы.
Основная идея этой главы – расширить концепцию части программы до новой, более мощной проектной конструкции, программного модуля. Программный модуль, или более просто, модуль, определяется как группа объявлений данных и процедур, которые задаются в одном блоке программы со следующими ограничениями:
· Данные, описанные в модуле, будут доступны только операторам процедур модуля и не доступны операторам вне модуля.
|
|
|
· Операторы внутри процедур модуля работают только с параметрами процедур и данным модуля и не работают с данными вне модуля.
Программный модуль обеспечивает механизм для хранения, обработки и выборки данных для программы. Иллюстрацией такого подхода является объявление файлов типа TEXT и операторы READ и WRITE, которые управляют такими файлами. Эти операторы предоставляют единственный способ для сохранения и выборки данных. Взаимодействие между модулем и остальной частью программы осуществляется через символьные параметры в операторах READ и WRITE.
Определение модуля не является явной частью синтаксиса стандартного языка Pascal, так же как и раздел проекта в методе пошаговой детализации. Скорее, модуль предоставляет другой способ проектирования и организации программ в режиме ориентированном на пошаговую детализацию.
Ограничения модуля позволяют защищать данные модуля от других частей программы, то есть, будучи корректно обработанными процедурами модуля, его данные не могут быть по невнимательности изменены или разрушены. Такой метод защищенного программирования называется скрытием информации, и горят, что данные инкапсулированы в модуле.
Такой метод принуждает выполнять все взаимодействие с модулем посредством его процедур и их параметров. Следовательно, не существует возможности для данных в модуле быть измененными иначе, чем с помощью процедурного оператора, который вызывает одну из процедур модуля. Также для такой процедуры невозможно изменить данные за пределами модуля иначе, чем через передаваемые ей параметры.
Модуль с исключительно сохранением и выборкой данных – важный особый случай. Данные попадают в модуль через параметры процедур и в дальнейшем могут быть возвращены без изменений через другие параметры. Файлы CF Pascal иллюстрируют это свойство: данные помещенные в файл, всегда снова появляются в той же самой форме при выборке.
|
|
|
Другой важный специальный случай модуля, когда он не имеет объявлений данных, в нем выполняются чистые вычисления. Процедура, не использующая глобальных данных, удовлетворяет всем ограничениям. Группа процедур, которые, например, образуют библиотеку, например,. для обработки целых чисел, предложенную в главе 9, образуют чисто-вычислительный модуль.
Модули предоставляют новые возможности для проектирования программ. Они позволяют разработку операций над данными на любом уровне необходимом для решения задачи. возможности для проектирования программ. Они позволяют разработку операций над данными на любом уровне необходимом для решения задачи. Например, если задача связана со словами текста, могут быть разработаны модули для обработки слов как отдельных блоков. Операции с данными для кроссворда, головоломки, шахмат или игры в бейсбол могут быть рассмотрены в терминах модулей с данными и процедурами для работы с особенными свойствами соответствующих игр.
Числа.
Для иллюстрации идеи модуля будет разработан и использован трехразрядный счетчик.
Как иллюстрация простого модуля который обеспечивает как сохранение/выборку так и вычисления рассмотрим задачу, которая включает счет до 999, например, подсчет пробелов в строке. В некоторых случаях требуется увеличивать счетчик по единице, или определить текущее значение, сохраняемое счетчиком, или обнулить счетчик. Для этого может быть разработан модуль, в котором счет организован в трех символьных переменных как в программе CountChars в разделе 1.6.3.
VAR
Ones, Tens, Hundreds:CHAR;
и процедуры:
Start {обнуляет счетчик}
Bump {Увеличивает счетчик на единицу}
Value(VAR V100, V10, V1: CHAR) {Возвращает значение счетчика}
Модуль разрабатывается таким образом, что после выполнения Start модуль содержит натуральное число из трех цифр. Если счетчик содержит 999, Bump не меняет значение счетчика. В Pascal-программе использующей этот модуль, переменные модуля должны быть помещены в раздел VAR.
{начало модуля счетчика}
{В разделе VAR}
Ones, Tens, Hundreds:CHAR;
{После раздела VAR}
PROCEDURE Start;
{Сбрасывает счетчик в ноль}
BEGIN{Start}
|
|
|
Ones:= '0';
Tens:= '0';
Hundreds:= '0'
END;{Start}
PROCEDURE Bump;
{Увеличивает 3-значный счетчик определенный Ones, Tens, Hundreds
на единицу,если он находится в диапaзоне от 0 до 999 }
PROCEDURE NextDigit(VAR Digit: CHAR);
BEGIN {NextDigit}
IF Digit = '0' THEN Digit:='1' ELSE
IF Digit = '1' THEN Digit:='2' ELSE
IF Digit = '2' THEN Digit:='3' ELSE
IF Digit = '3' THEN Digit:='4' ELSE
IF Digit = '4' THEN Digit:='5' ELSE
IF Digit = '5' THEN Digit:='6' ELSE
IF Digit = '6' THEN Digit:='7' ELSE
IF Digit = '7' THEN Digit:='8' ELSE
IF Digit = '8' THEN Digit:='9' ELSE
IF Digit = '9' THEN Digit:='0'
END;{NextDigit}
BEGIN {Bump}
NextDigit(Ones);
IF Ones = '0'
THEN
BEGIN
NextDigit(Tens);
IF Tens= '0'
THEN
BEGIN
NextDigit(Hundreds);
IF Hundreds= '0'
THEN
BEGIN
Ones:= '9';
Tens:= '9';
Hundreds:= '9'
END
END
END
END; {Bump}
PROCEDURE Value (VAR V100, V10, V1: CHAR);
{Возвращает содержимое счетчика}
BEGIN {Value}
V100:= Hundreds;
V10:= Tens;
V1:= Ones
END; {Value}
{Конец модуля счетчика}
Объявление трех переменных и трех процедур задет модуль счетчика, который может быть вставлен в любую программу, в которой есть необходимость в таком счетчике. Для соблюдения ограничений модуля достаточно, чтобы оставшаяся часть программы не использовала глобальные переменные Ones, Tens, Hundreds. Тогда счетчик полностью скрыт за тремя процедурами Start, Bump и Value.
Этот модуль счетчика может быть использован для решения задач подсчета количества пробелов в строке.
PROGRAM CountingBlanksInText(INPUT, OUTPUT);
VAR
Ch, X100, X10, X1: CHAR;
{Включить модуль счетчика}
BEGIN {CountingBlanksInText}
Start; {обнулить счетчик}
WHILE NOT EOF
DO
BEGIN
WHILE NOT EOLN
DO
BEGIN
READ(Ch);
IF Ch = ‘ ‘
THEN
BEGIN
Bump; {Увеличиваем счетчик на едеинцу}
Ch:= ‘#’;
END;
WRITE(Ch);
END;
READLN;
WRITELN
END;
WRITELN;
Value(X100, X10, X1); {получаем значение счетчика}
IF (X100 = ‘9’) AND (X10 = ‘9’) AND (X1 = ‘9’)
THEN
WRITELN(‘Количество пробелов как минимум 999’)
ELSE
WRITELN(‘Количество пробелов ’, X100, X10, X1)
END. {CountingBlanksInText}
INPUT:
Now is
the time for
all good men.
OUTPUT:
##Now#is#
the##time#for
all#good##men.
Количество пробелов 010
Для выделения, процедурные операторы, обращающиеся к счетчику, снабжены комментариями. В эхо ввода пробелы заменяются # чтобы они могли быть видны. Основная стоимость использования модуля в собранной программе – это дублирование переменных Hundreds, Tens и Ones в модуле переменными X100, X10, X1 в блоке вне модуля. Если бы вызов Value был удален, могли бы быть исключены и переменные X100, X10, X1 и значения Hundreds, Tens и Ones распечатаны напрямую. Но это нарушает ограничение, что данные описанные в модуле доступны только операторам внутри модуля. Несколько лишних переменных – небольшая цена за возможность повторного использования модуля, который тщательно проверен и протестирован раз и навсегда и использован многократно в других программах. Библиотека модулей может быть более полезной, чем библиотека процедур, если модули будут хорошо подобраны и правильно написаны.
|
|
|
Реализация модулей в современных компиляторах Pascal
В современных реализациях языка Pascal, как правило, присутствует поддержка модулей и дисциплины работы с модулями на уровне компилятора. Модуль размещается в отдельном файле, структура которого может быть описана с помощью следующего правила BNF.
<модуль>::= UNIT <имя модуля>;
INTERFACE
<объявления модуля>
IMPLEMENTATION
<тексты процедур модуля>
BEGIN
<список операторов>
END.
Как и Паскаль-программа, модуль имеет заголовок, UNIT <имя модуля>; раздел объявлений (интерфейс модуля), начинающийся с ключевого слова INTERFACE и блок реализации, начинающийся с ключевого слова IMPLEMENTATION (реализация). Также блок содержит оператор BEGIN, выполняющий инициализацию данных модуля. Как и программа, модуль точкой.
UNIT Count3;
{Модуль счетчика}
INTERFACE
VAR
Ones, Tens, Hundreds: CHAR;
PROCEDURE Start;
PROCEDURE Bump;
PROCEDURE Value (VAR V100, V10, V1: CHAR);
IMPLEMENTATION
{Тексты процедур Start, Bump и Value модуля}
...
BEGIN
{Инициализация данных модуля}
END.
Для использования модулей в программе необходимо указать эти модули явно с помощью ключевого слова USES <список модулей>, которое помещается перед разделом объявлений.
Например:
PROGRAM CountingBlanksInText(INPUT, OUTPUT);
USES
Count3;
VAR
Ch, X100, X10, X1: CHAR;
BEGIN {CountingBlanksInText}
...
END. {CountingBlanksInText}
Абстракция данных.
Модуль может быть рассмотрен как введение нового уровня объектов в программу – абстрактного уровня. В абстрактных терминах, модуль содержит новые, высокоуровневые объекты, чем те, что были доступны прежде, и когда эти объекты используются (через процедуры модуля), нет необходимости вникать в низкоуровневые детали.
Исходя из дисциплины доступа к данным в модуле, функции частных значений его процедур могут быть определены полностью из текста модуля безотносительно к данным, определенным вне модуля. Однако, необходимо рассмотреть два различных взгляда – проектировщика модуля и пользователя.
Для работы над модулем, проектировщик нуждается в комментариях, которые описывают действие процедур модуля над его скрытыми данными, которые иногда называются конкретными данными. Поскольку пользователь модуля не может ссылаться на эти данные, для него необходимы комментарии, объясняющие как использовать процедуры модуля в терминах абстрактных данных, реализуемых модулем.
|
|
|
В модуле счетчика комментарии проектировщика будут описывать действие каждой процедуры в терминах Ones, Tens и Hundreds, тогда как пользовательские комментарии раскрывают эффект тех же процедур в терминах абстрактного объекта, названного Counter. Counter не появляется, как другие переменные в состоянии выполнения, потому что он не был описан и не может быть использован напрямую в операторах вызывающей программы. Вместо этого, программист устанавливает значение счетчика через процедуры Start и Bump и обращается к его значению с помощью процедуры Value.
Например, комментарий к вызову Start
{обнулить счетчик}
может быть заменен на более точные комментарии
{конкретный: Ones, Tens, Hundreds:= ‘0’, ‘0’, ‘0’ }
{абстрактный: Counter:= 0 }
Первый комментарий – одновременное присваивание, которое обобщает действие операторов CF Pascal. Но второй комментарий использует переменную, которая может рассматриваться как целочисленная, не доступная в CF Pascal.
Значение абстрактного объекта может быть сконструировано отображением переменных значений переменных, использованных для представления объекта значению объекта. Это отображение является частью функции представления (representation function), которая ставит в соответствие (конкретные) состояния (абстрактным) состояниям. Функция представления выделяет абстрактное значение из состояния выполнения и скрывает переменные, которые составляют абстрактный объект (который именуется новым идентификатором). Например, в ContingBlanksInText, следующие состояния выполнения могут существовать после вызова Value.
(Абстрактное состояние)
{Counter·210, Ch·#, X100·2, X10·1, X1·0}
функция представления
{Hundreds·2, Tens·1, Ones·0, Ch·#, X100·2, X10·1, X1·0}
(Конкретное состояние)
(INPUT и OUTPUT опущены для экономии места)
Для того, чтобы определить функцию представления формально, будет удобно определить функцию Number, которая ставит в соответствие список символов, натуральному числу в десятичной системе исчисления, которое они представляют. Например:
Number(<’0’, ‘0’, ‘0’>) = 0 (ноль)
Number(<’0’, ‘1’, ‘3’>) = 13 (тринадцать)
Функция представления R для приведенной выше абстракции счетчика может быть записана следующим образом:
R = {(s, t): t такое же как s за исключением того, что оно содержит новый идентификатор Counter и t(Counter) = Number(<Hundreds(s), Tens(s), Ones(s)>)
и t не содержит идентификаторов Hundreds, Tens и Ones}
R отображает три символьных переменных в одну целочисленную.
Конкретная функция частного значения для Value:
V100, V10, V1:= Hundreds, Tens, Ones
Абстрактная функция:
(0 <= Counter <= 999 ->
символьное представление разряда сотен Counter,
символьное представление разряда десятков Counter
символьное представление разряда единиц Counter)
Даже если абстрактная функция частного значения определена только для цифр, нет требования в конкретной функции частного значения, чтобы Hundreds, Tens и Ones были цифрами. Если Value было выполнено до Start, обращение к значениям в Hundreds, Tens и Ones произойдет до инициализации и функция возвратит неизвестное значение.
Сложности в конкретной функции частного значения для Bump возникают не только из арифметики, которая должна быть симулирована, если Ones, Tens и Hundreds цифры, но и обработки случаев, когда она или более этих переменных цифрами не являются.
((‘0’ <= Ones < ‘9’ -> next(Ones)) |
(Ones = ‘9’ AND ‘0’ <= Tens < ‘9’ ->
Ones, Tens:= ‘0’, next(Tens)) |
(Ones = ‘9’ AND Tens = ‘9’ AND ‘0’ <= Hundreds < ‘9’ ->
Ones, Tens, Hundreds:= ‘0’, ‘0’, next(Hundreds)) |
(Ones = ‘9’ AND Tens = ‘9’ AND Hundreds = ‘9’ ->)) |
(‘0’ > Ones OR Ones > ‘9’ ->)
где next определяется как:
next = {(x, y): x и y – цифры и у следует за x в последовательности 01234567890}
С другой стороны, абстрактный комментарий для Bump вполне компактен.
(0 <= Counter <= 999 -> Counter:= Counter + 1) |
(Counter < 0 OR Counter >= 999 ->)
Автоматы с памятью.
Поведение программного модуля похоже на формальную машину, с особенностью, что ее ответы на входные данные зависят от ее внутреннего состояния. После выполнения каждой операции ее внутреннее состояние может меняться и таким образом, прошлые действия могут влиять на будущие.
Автомат с памятью (State machine) это механизм (реальный или представляемый) который содержит определенное состояние, называемое начальным состоянием, может принимать входные данные (воздействия), затем производить новое состояние и выходные данные которые зависят только от предыдущего состояния и входных данных.
Таким образом, автомат с памятью описывается функцией, которая ставит в соответствие паре (вход, состояние) пару (выход, состояние). Например, файл типа TEXT ведет себя как автомат с памятью, в котором состояние это значение файловой переменной, а входы и выходы определяются операторами READ и WRITE.
Для файла F1 в состоянии выполнения s со значением
F1(s) = <†AB†, †CD†, R>
и оператора READ(F1, Ch) как входа для TEXT-машины, результатом будет новое состояние t, такое что
F1(t) = <†ABС†, †D†, R>
Выход TEXT-машины может быть значением Ch:
Ch(t) = C
Тот же вход для состояния t не произведет тот же выход, потому что внутренне состояние иное.
Изложенное далее предлагает точку зрения, что выполнение Паскаль-программы может быть рассмотрено как последовательные действия автомата, состоянием которого является состояние выполнения программы. Входами являются объявления и операторы программы, и здесь не требуется выходов, потому что вся информация появляется в состоянии выполнения.
Программные модули могут быть прямо смоделированы как конечные автоматы, следующим образом:
Имена и значения объектов данных скрытых модулем образуют состояние автомата.
Каждый процедурный оператор, использующий процедуру модуля, является входом, который является причиной изменения состояния автоматом и, возможно, производит выход.
Например, в модуле счетчика, состояние конечного автомата счетчика задается именованными значениями Hundreds, Tens и Ones как конкретное состояние, которое является подмножеством состояния выполнения всей программы, скажем
{Hundreds·3, Tens·5, Ones·2}
(соответствующее абстрактное состояние содержит Counter·352).
Процедурный оператор
Value(V100, V10, V1)
является входом, который не меняет состояния автомата и возвращает как выход значения V100, V10 и V1, а именно 3, 5 и 2. Напротив, процедурный оператор Bump является входом, который создает новое конкретное состояние выполнения
{Hundreds·3, Tens·5, Ones·3}
и не производит выхода.
Автомат с памятью с конечным количеством состояний называется конечным автоматом с памятью (finite state machine) или просто конечный автомат. Этот автомат может быть описан диаграммой, в которой каждое состояние представлено кругом, содержащим имя состояния и переходами между состояниями, представленных стрелками, помеченными входными символами, которые являются причиной изменения состояния автоматом. В следующей диаграмме символ x производит изменение состояния из S в T.
 |
Одно состояние автомата обозначается как начальное состояние – оно будет иметь непомеченную входящую стрелку, не имеющую другого, исходного состояния. Например, S начальное состояние в
Несколько состояний конечного автомата могут быть конечными состояниями, они представлены двойными кругами. Одно и то же состояние может быть как начальным, так и конечным состоянием автомата как в следующем примере.
 |
Когда автомат, который начинает работу в его стартовом состоянии, делает переход для каждого входного символа и заканчивает в одном из финальных состояний, говорят, что он распознал или принял вход. Автомат, изображенный выше, начинает в состоянии S и останавливается в состоянии S, если его вход – пустая строка или строка из четного числа элементов x.
Автоматы, как изображенный выше, называют распознавателями (recogniser) или приемщиками (acceptor) – они обеспечивают только один выход: успех, если они в финальном состоянии в конце входа и ошибка в противном случае.
Другие автоматы, называемые преобразователями (transducer), могут производить выходной символ для каждого считанного входного. Метка стрелки с символами, разделенными наклонной чертой / означает, что когда первый символ считывается, второй записывается.
Распознаватель приведенный выше может быть переделан в преобразователь, который выводит половину # от количества прочитанных x.
 |
Модуль с внутренними данными только типа CHAR, как модуль счетчика, может быть смоделирован конечным автоматом с памятью. Модуль с внутренними данными типа TEXT не может быть смоделирован конечным автоматом, потому нет ограничения на длину файла типа TEXT и, следовательно, на количество возможных состояний.
Конечные автоматы очень полезны для описания ситуаций, в которых требуется сделать конечное число выборов для входных строк произвольной длины. Например, конечный автомат может быть использован для определения, содержит ли входная строка возрастающий набор длиной не менее 10 символов. Состоянием выполнения могут быть последние 9 символов. Существует конечное число возможных состояний, потому что ограничено количество возможных символов. Для каждого нового входного символа может быть принято решение, образуют ли 9 ранее считанных символов и последний считанный требуемый набор данных. Если это так, что ответом будет “да”, если не образуют и входная строка закончилась, ответом будет “нет”. В новое состояние включается последний считанный символ, самый старый отбрасывается.
С другой стороны, конечный автомат не может быть использован для определения, является ли строка палиндромом сохранением первой половины строки как состояния. Вне зависимости от того насколько велико состояние, еще большая строка может быть использована как вход.
Конечный автомат может также быть полезен при разработке тестов программ. Тестовые данные должны обеспечить, чтобы каждый переход должен быть выполнен как минимум однажды. Следующий оператор BEGIN достигает этой цели для модуля счетчика.
BEGIN {модуль тестирования счетчика}
Start;
Value(Ch1, Ch2, Ch3);
WRITELN(Ch1, Ch2, Ch3);
WHILE (Ch1 <> ‘9’ OR Ch2 <> ‘9; OR Ch3 <> ‘9’)
DO
BEGIN
Bump;
Value(Ch1, Ch2, Ch3);
WRITELN(Ch1, Ch2, Ch3);
END;
Bump;
Value(Ch1, Ch2, Ch3);
WRITELN(Ch1, Ch2, Ch3);
END {модуль тестирования счетчика}
Тест проверяет все значения счетчика и переход к следующему значению, но он пропускает неограниченное количество переходов, которое может выполнить модуль, а именно из состояния 999 в себя, тест проверяет только один такой переход. Если выход будет тщательно исследован, это будет хороший тест для данного модуля.
Модуль очереди.
Очередь – это полезная структура данных для хранения информации в упорядоченной последовательности, подобно человеческой очереди, когда люди стоят один за другим. Очередь символов будет организована в виде модуля, реализованного двумя различными способами, и использована для решения задачи удаления лишних пробелов из текста.
Переменная типа TEXT предоставляет возможность хранения и извлечения символов в последовательности с использованием операторов READ/WRITE. Переменные типа TEXT и соответствующие операции над ними соблюдают правила программного модуля, потому что единственным способом сохранения и извлечения данных является использование операторов READ/WRITE.
Очередь – это подобное средство хранения и извлечения данных. Она работает по принципу FIFO (first-in, first-out): элементы добавляются в хвост очереди и извлекаются из головы очереди. Таким образом, очередь похожа на файл за исключением того, что добавления и удаления могут чередоваться в произвольном порядке.
Например, рассмотрим очередь, элементами которой являются символы. Типичный набор операций включает:
| Операция | Результат |
| EmptyQ | Инициализация очереди - очистка |
| AddQ(VAR Elt: CHAR) | Добавляет элемент Elt в очередь |
| DelQ | Удаляет первый элемент из очереди |
| HeadQ(Var Elt: CHAR) | Присваивает Elt в значение первого элемента очереди |
Если очередь содержит один или более элементов, DelQ удаляет первый из очереди, а HeadQ возвращает первый из очереди копированием его в Elt (но не изменяет при этом очередь). Если очередь пуста, DelQ ничего не делает, а HeadQ возвращает #.
В следующих разделах даны две реализации модуля для очереди символов. Первая реализация, названная SlowQueue основывается на очень простом представлении данных, которое не позволяет оптимизаций или повышения эффективности в процедурах модуля. Вторая реализация, FastQueue, использует более сложное представление данных и более сложные процедуры для увеличения скорости выполнения операций. Хотя обе реализации довольно различны внутренне, они имеют абсолютно одинаковое внешнее представление. Единственная разница во времени выполнения. То есть эти два модуля взаимозаменяемы в программах, которые их используют. Когда FastQueue заменяет SlowQueue, не требуется других изменений в программе использующей модуль. Программа изолирована от изменений в модуле, поскольку и программа и модуль соблюдают правила разработки и использования модулей.
SlowQueue
Для первой реализации очереди рассмотрим стратегию управления очередью в единственном текстовом файле, названном Q:
VAR
Q: TEXT;
Пустая очередь представляется файлом, содержащим только маркер строки. Поскольку конец очереди отмечен таким образом, очередь не может содержать внутренние маркеры конца строки. Каждая процедура завершается операцией RESET над файлом, поэтому когда любая процедура начинает выполнение, она считает, что файл готов для чтения.
Добавление в или удаление элемента из очереди требует операторов WRITE, поскольку текстовый файл, представляющий очередь, открыт для чтения, текущее содержимое файла должно быть скопировано во временный файл, а потом обратно в исходный. Набросок модуля очереди с абстрактными комментариями показан ниже.
{модуль очереди}
VAR
Q: TEXT;
{включить PROCEDURE CopyOpen(VAR Fin, Fout: TEXT)
добавляет строку будущего Fin в Fout}
PROCEDURE EmptyQ;
{Queue:= <>}
PROCEDURE AddQ(VAR Elt: CHAR);
{Queue:= Queue & <Elt>}
PROCEDURE DelQ;
{(Queue = <> ->) | Queue = <X>&Y -> Queue:= Y}
PROCEDURE HeadQ(VAR Elt: CHAR);
{(Queue = <> -> Elt:= ‘#’) | Queue = <X>&Y -> Elt:= X}
{конец модуля очереди}
Конкретные функции, соответствующие данным абстрактным функциям будут сейчас реализованы.
EmptyQ переписывает Q, как пустую строку. В конкретном комментарии используется символ / для обозначения конца строки.
PROCEDURE EmptyQ;
{Q:= <, /, R>}
BEGIN {EmptyQ}
REWRITE(Q);
WRITELN(Q);
RESET(Q)
END; {EmptyQ}
AddQ копирует Q во временный файл и добавляет содержимое Elt, потом временный файл копируется обратно в Q.
PROCEDURE AddQ (VAR Elt: CHAR);
{Q = <,x/,R>,где x строка И Elt = a --> Q = <,xa/,R> }
VAR
Temp: TEXT;
BEGIN {AddQ}
REWRITE(Temp);
CopyOpen(Q,Temp);
WRITELN(Temp,Elt);
{копируем Temp в Elt}
RESET(Temp);
REWRITE(Q);
CopyOpen(Temp,Q);
WRITELN(Q);
RESET(Q)
END {AddQ};
PROCEDURE DelQ;
{(Q = <,/,R> -->)|
(Q = <,ax/,R>,где a символ и x строка -->
Q:= <,x/,R> }
VAR
Ch: CHAR;
BEGIN {DelQ}
{удаляем первый элемент из Q};
READ(Q,Ch);
IF NOT EOF (Q)
THEN {не пустой}
BEGIN
REWRITE(Temp);
CopyOpen(Q,Temp);
WRITELN(Temp);
{копируем Temp в Q}
RESET(Temp);
REWRITE(Q);
CopyOpen(Temp,Q);
WRITELN(Q);
END;
RESET(Q)
END {DelQ};
PROCEDURE HeadQ(VAR Elt: CHAR);
{(Q = <,/,R> --> Elt:= '#')|
(Q = <,ax/,R>,где a символ и x строка --> Elt:= 'a' }
BEGIN {HeadQ}
IF NOT EOLN(Q)
THEN
READ(Q,Elt)
ELSE
Elt:= '#';
RESET(Q)
END{HeadQ};
|
|
|
