Процедуры обработки строк.

 

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

 

Рассмотрим задачу сравнения длин строк, сохраненных в файлах F1 и F2. Результат сравнения возвращается в переменной Result:

1, если строка в F1 короче;

2, если строка в F2 короче;

0, если строки равной длины.

 

Раздел проекта 1 [DP 1]

 

PROCEDURE Length(VAR F1, F2: TEXT; VAR Result: CHAR);

{Result 0, 1, 2 если длина F1 =, <, > длины F2 соответственно.

Фактические параметры, соответствующие F1 и F2 должны быть различными}

VAR

Ch1, Ch2: CHAR;

BEGIN {Length}

RESET(F1);

RESET(F2);

WHILE NOT EOF(F1) AND NOT EOF(F2)

DO

BEGIN

READ(F1, Ch1);

READ(F2, Ch2)

END

{Анализировать F1, F2 и установить Result

в соответствии с длиной}

END {Length}

 

Раздел проекта 1.1 [DP 1.1]

 

BEGIN {Анализировать F1, F2 и установить Result

в соответствии с длиной}

IF EOF(F1)

THEN {в F1 уже пусто}

IF EOF (F2)

THEN {и в F1 и в F2 пусто}

Result:= ‘0’

ELSE {в F1 пусто, в F2 еще есть символы}

Result:= ‘2’

ELSE {в F1 есть символы, а F2 уже пуст (из условия в WHILE)}

Result:= ‘1’

END

 

Лексикографический порядок строк – это их порядок появления как слов в словаре – алфавитный порядок, где алфавит – набор символов Паскаль-машины. Из двух строк различной длины, имеющих одинаковые последовательности символов, короткая предшествует. Например, †ABC† предшествует †ABCDEF†, но †XYZ† предшествует †YZ†.

Определять лексикографический порядок строк простое дело: сравнивать их символы попарно, пока не встретятся неравные символы или одна из строк не закончится. Хотя Lexico предназначена для использования с 1-строками, она может быть использована и для сравнения n-строк.

 

Раздел проекта 2 [DP2]

 

PROCEDURE Lexico(VAR F1, F2: TEXT; VAR Result: CHAR);

{Result 0, 1, 2 если лексикографический порядок F1 =, <, > чем F2 соответственно. Фактические параметры, соответствующие F1 и F2, должны быть различными}

VAR

Ch1, Ch2: CHAR;

BEGIN {Lexico}

RESET(F1);

RESET(F2);

Result:= ‘0’;

WHILE (NOT EOF(F1) AND NOT EOF(F2)) AND (Result = ‘0’)

DO

BEGIN

READ(F1, Ch1);

READ(F2, Ch2);

IF (Ch1 < Ch2) OR (EOF (F1))

THEN {Ch1 < Ch2 или F1 короче F2}

Result:= ‘1’

ELSE

IF (Ch1 > Ch2) OR (EOF (F2))

THEN {Ch1 > Ch2 или F2 короче F1}

Result:= ‘2’

END {WHILE}

END {Lexico}

 

Length и Lexico – полезные “кирпичики”, которые можно использовать при разработке приложений, работающих со строками. Программы SelectSort и SelectReverse, разработанные в разделе 4.2 также могут быть преобразованы в процедуры. Эти частицы могут быть преобразованы в библиотеку подпрограмм для работы со строками. Конкретный набор процедур для работы со строками - вопрос вкуса и опыта. По мере использования такой библиотеки и чем больше будет узнано о алгоритмах работы со строками, она может вырасти до мощного средства решения задач.

Когда процедуры из библиотеки будут использоваться в проекте, будет удобно включать их имена и комментарий. Комментарий к процедуре в библиотеке должен в основном отражать информацию о том, как используется процедура, т.е. что она делает не как, хотя можно упомянуть и о некоторых моментах реализации важных с точки зрения использования. Например, о том, что вызов процедуры потребует больших затрат процессорного времени. Комментарий должен быть достаточен для корректного использования каждой процедуры. Такой комментарий обычно называют комментарием включения (include comment). Например, если мы включаем в проект Lexico, комментарий может быть следующим:

 

{Включить PROCEDURE Lexico(VAR F1, F2: TEXT; VAR Result: CHAR);

Result 0, 1, 2 если лексикографический порядок F1 =, <, > чем F2 соответственно. Фактические параметры, соответствующие F1 и F2, должны быть различными}

 

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

В нашем случае подразумевается, что строки в файлах-параметрах не содержат маркеров строки, к входному файлу применяется RESET, но он не остается в этом состоянии по завершению процедуры, к выходному файлу применяется REWRITE, алиасинг фактических параметров не допускается.

 

PROCEDURE InString(VAR F1: TEXT);

{Создает строку в файле F1 из символов в INPUT до следующего маркера конца строки}

 

PROCEDURE OutString(VAR F1: TEXT);

{Печатает строку в файле F1 в OUTPUT, завершая ее маркером конца строки}

 

PROCEDURE CopyOpen(VAR F1, F2: TEXT);

{Копирует строку из F1 в F2 без выполнения RESET или REWRITE, F1 должен быть подготовлен для чтения, а F2 – для записи. Строка прошлого этих файлов может быть непустой}

 

PROCEDURE Sort(VAR F1, F2: TEXT);

{Помещает в F2 отсортированную строку символов из F1}

 

PROCEDURE Reverse(VAR F1, F2: TEXT);

{Помещает в F2 строку символов из F1 в обратном порядке}

 

PROCEDURE Concatenate(VAR F1, F2, F3: TEXT);

{Создает F3 из символов F1, за которыми следуют символы из F2}

 

Библиотечные процедуры часто используются при разработке других библиотечных процедур. Например, проект для Concatenate может быть:

 

PROCEDURE Concatenate(VAR F1, F2, F3: TEXT);

{Создает F3 из символов F1, за которыми следуют символы из F2}

 

{Включаем PROCEDURE CopyOpen(VAR F1, F2: TEXT);

Копирует строку из F1 в F2 без выполнения RESET или REWRITE, F1 должен быть подготовлен для чтения, а F2 – для записи. Строка прошлого этих файлов может быть непустой}

 

BEGIN {Concatenate}

RESET(F1);

RESET(F2);

REWRITE(F3);

CopyOpen(F1, F3);

CopyOpen(F2, F3)

END {Concatenate}

 

Коллизии идентификаторов.

 

В большинстве случаев не требуется дополнительных определений, чтобы использовать программное исчисление с процедурами с параметрами в CF Pascal. Локальные переменные появляются внутри <блока>, текст которого присоединяется как значение к идентификатору процедуры в состоянии выполнения. Значение процедурного оператора получается из значения идентификатора применением бокс-функции к тексту процедуры. Локальные переменные через функцию VAR … помещаются в состояние выполнения и удаляются с помощью функции VAR …^T аналогично переменным, объявленным в главном блоке.

 

Рассмотрим для примера программу.

 

PROGRAM NoCon(INPUT, OUTPUT);

VAR

Global: CHAR;

 

PROCEDURE HasLocal;

VAR

Local: CHAR;

BEGIN {HasLocal}

Local:= ‘L’

END; {HasLocal}

 

BEGIN {NoCon}

Global:= ‘G’;

HasLocal

END. {NoCon}

 

Состояние выполнения перед выполнением процедурного оператора будет

s = {INPUT ·<x, ††, R>, OUTPUT ·<††, ††, W>, Global·G}

где x – входная строка

 

Значение процедурного оператора HasLocal для состояния S:

 

HasLocal (S) = S(HasLocal) (S) = VAR Local: CHAR; BEGIN Local:= ‘L’ END (S)

= VAR Local: CHAR;^T(Local:= ‘L’(VAR Local: CHAR; (S)))

= VAR Local: CHAR;^T(Local:= ‘L’({INPUT·<x, ††, R>, OUTPUT·<††, ††, W>, Global·G, Local·?}))

= VAR Local: CHAR;^T({INPUT·<x, ††, R>, OUTPUT·<††, ††, W>, Global·G, Local·L})

= {INPUT·<x, ††, R>, OUTPUT·<††, ††, W>, Global·G }

 

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

 

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

 

PROGRAM Confuse(INPUT, OUTPUT);

VAR

MixedUp: CHAR;

 

PROCEDURE HasLocal;

VAR

MixedUp: CHAR;

BEGIN {HasLocal}

MixedUp:= ‘L’

END; {HasLocal}

 

BEGIN {Confuse}

MixedUp:= ‘G’;

HasLocal

END. {Confuse}

 

Эта программа должна иметь точно такое же значение что и предыдущая. Но при вычислении значения процедурного выражения в состояние выполнения, где присутствует пара

<MixedUp·G>

для глобальной переменной.

И должна быть добавлена пара

<MixedUp·L>

для локальной переменной.

Имеем смешение идентификаторов, которые должны храниться отдельно.

 

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

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

Один из способов создания таких идентификаторов – добавлять символ N к имени идентификатора до тех пор, пока существует конфликт имен. В конечном счете, мы получим новый идентификатор, который еще не присутствует в состоянии выполнения, таким образом, коллизия будет разрешена.

 

Формальное определение функции частного значения процедурного оператора для объявления

PROCEDURE P (VAR X: CHAR); VAR Z: CHAR; BEGIN … END

будет

P (Y) (s) = s (P) _{X<-Y, Z<-Z’} (s)

где Z Î domain(s), a Z’ – новый идентификатор

 

Для примера выше, используя схему добавления символа N для создания нового идентификатора, получим

HasLocal(S) = S(HasLocal) (S) = VAR MixedUpN: CHAR; BEGIN MixedUpN:= ‘L’ END (S)

и здесь все работает так, как должно быть.

 

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

 

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

 

PROGRAM WhichWhich (INPUT, OUTPUT);

VAR

Which: CHAR;

 

PROCEDURE Zap

BEGIN {Zap}

Which:= ‘Z’ {Прибъем ее, пока не известно, какую именно?}

END; {Zap}

 

PROCEDURE Invoke

VAR

Which: CHAR;

BEGIN {Invoke}

Which:= ‘B’;

Zap;

WRITE(Which)

END; {Invoke}

 

BEGIN {WhichWhich}

Which:= ‘A’;

Invoke;

WRITELN (Which)

END. {WhichWhich}

 

Здесь ясно, какие переменные используются в выражениях WRITE: локальная переменная, объявленная в Invoke, используется в операторе WRITE и глобальная в WRITELN. Однако, между присвоения и операторами WRITE одна из переменных оказывается прибита (Zapped). Если прибивается локальная переменная, тогда значение программы будет функцией с постоянным значением

W = <†ZA†>

или, если изменяется глобальная переменная

W = <†BZ†>

В трудных случаях, таких как этот, существует способ определить значение без вычисления функции значения программы. Представим, что мы изменили описанным выше способом один из идентификаторов Which. Если меняется локальный, программа продолжает оставаться синтаксически корректной и ее OUTPUT будет †BZ†. Если меняется глобальный идентификатор Which, программа не будет синтаксически корректной, поскольку в Zap будет использоваться необъявленная переменная Which. Следовательно, в Zap используется глобальная переменная Which, которая «прибивается» в нашем случае.

 

Используя модифицированное определение в состоянии выполнения

 

S = {INPUT ·<x, ††, R>, OUTPUT ·<††, ††, W>, Which·A}, которое существует при вызове процедуры Invoke

 

Invoke (S) = S(Invoke) (S) = VAR WhichN: CHAR; BEGIN WhichN:= ‘B’; … END (S)

= VAR WhichN: CHAR^T (BEGIN WhichN:= ‘B’; … END (VAR WhichN: CHAR (S)))

= VAR WhichN: CHAR^T (BEGIN WhichN:= ‘B’; … END

({INPUT ·<x, ††, R>, OUTPUT ·<††, ††, W>, Which·A, WhichN·?}))

= VAR WhichN: CHAR^T (WhichN:= ‘B’; Zap; WRITE(WhichN)

({INPUT ·<x, ††, R>, OUTPUT ·<††, ††, W>, Which·A, WhichN·?}))

= VAR WhichN: CHAR^T (Zap; WRITE(WhichN)

({INPUT ·<x, ††, R>, OUTPUT ·<††, ††, W>, Which·A, WhichN·B}))

= VAR WhichN: CHAR^T (WRITE(WhichN)

({INPUT ·<x, ††, R>, OUTPUT ·<††, ††, W>, Which·Z, WhichN·B}))

= VAR WhichN: CHAR^T ({INPUT ·<x, ††, R>, OUTPUT ·<†B†, ††, W>, Which·Z, WhichN·B})

={INPUT ·<x, ††, R>, OUTPUT ·<†B†, ††, W>, Which·Z}

С этого момента нетрудно будет выполнить окончательное вычисление значения программы:

W = <†BZ†>

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