Тестирование процедуры RemoveExtraBlanks.
Для тестирования этой процедуры полезно пометить начало и конец строк, чтобы их легко было видеть. Для этой цели можно использовать символ #.
PROGRAM TestRes(INPUT, OUTPUT)
VAR
Ch: CHAR;
TestIn, TestOut: TEXT;
PROCEDURE RemoveExtraBlanks(VAR FileIn, FileOut: TEXT);
{ копирует слова из FileIn в FileOut, удаляя головные и хвостовые пробелы, а также лишние пробелы между словами }
BEGIN
ASSIGN(TestIn, ‘TestIn.txt’);
ASSIGN(TextOut, ‘TestOut.txt’);
WHILE NOT EOF
{копируем одну строку из INPUT в файл TestIn, с эхом ввода};
RemoveExtraBlanks(TestIn, TestOut);
{Копируем результирующую строку из TestOut в OUTPUT}
END
END
Задание 2. Написать недостающие разделы проекта для программы TestRes. При выводе результата на экран пометить начало и конец входной и выходной строки символом #.
INPUT:
Pack my box with six.
SOLIDPACKED□□
OUTPUT:
Input is: # Pack my box with six.#
Output is: #Pack my box with six.#
Input is: #SOLIDPACKED #
Output is: #SOLIDPACKED#
(15 баллов)
Программа передает каждую входную строку процедуре RemoveExtraBlanks и выводит результат. Описание синтаксиса входной строки в форме Бекуса-Наура для всех возможных входов (правила 1 и 2) дают нам способ выбора тестовых данных. Если мы полагаем, что разделы RemoveExtraBlanks для пропуска пробелов и копирования слов работают корректно, единственное, что должно быть протестировано – это комбинация позиций <слов> и <пробелов> описываемых данными синтаксическими правилами. Согласно этим правилам возможно 4 варианта:
<пробел>
<слово> <пробелы> <список-слов-пробелов> <пробел>
<пробелы> <пробел>
<пробелы> <слово> <проелы> <список-слов-пробелов> <пробел>
Заслуживающие внимания тестовые случаи, за исключением конечного <списка-слов-пробелов> <пробела> такие:
††
†the †
† †
† the †
10.1.5 Анализ процедуры RemoveExtraBlanks
Для того чтобы продемонстрировать, что RemoveExtraBlanks выполняет то, ради чего была спроектирована, ее функция должна быть вычислена. Пролект для части DO внутреннего оператора WHILE такой:
{копируем слово};
FlushBlanks(Ch);
{вставляем пробел, если это не последнее слово}
Соответствующая функция для каждой из этих трех частей может быть записана в виде условного присваивания.
Функция C для копирования слова такая:
C = C1 | C2
где
C1 = ((Ch <> ‘ ‘)
AND (NOT(EOF(FileIn))) AND (FileIn.2 = (x B) & y)
AND (FileIn.3 = R) AND (FileOut.3 = W)
Ch,FileOut.1,FileIn.1, FileIn.2 :=
□,(FileOut.1 Ch) & x,FileIn.1 & (x B),y)
и
C2 = (Ch = ‘ ‘ )
где x – строка не пробельных символов, не содержащая маркера конца строки, y – строка, а B – либо маркер конца строки, либо □. В этом и в следующих условных присваиваниях элементы 3-списков файлов изображаются при помощи индекса, следующего за точкой. Например, FileIn.2 означает FileIn2, второй элемент списка (являющийся строкой будущего). Такая нотация позволяет записывать условные присваивания в комментариях программе, где запись индексов не возможна.
Функция F для FlushBlanks(Ch) такая:
F = (F0 (F1 | F2)) | F3
где
F0 = ((Ch = ‘ ‘) AND (NOT(EOF(FileIn))) AND (FileIn.3 = R)
F1 = (FileIn.2 = b Z & w
Ch, FileIn.1, FileIn.2 := Z, FileIn.1 & b Z, w)
F2 = (FileIn.2 = b /
Ch, FileIn.1, FileIn.2 := □, FileIn.1 & FileIn.2, ††)
F3 = ((Ch <> ‘ ‘) OR (EOF(FileIn)) )
где b - строка из пробелов и маркеров конца строки (возможно, пустая), Z – это символ, отличный от пробела и маркера конца строки, а w – непустая строка символов.
Задание 3. Доказать, что
BEGIN {copy word} … END = C
и
FlushBlanks(Ch) = F
(30 баллов)
Доказательство того, что функция I соответствует условной вставке пробела, следует далее:
I = I1 | I2
I1 = ((NOT(EOF(FileIn))) AND (FileOut.3 = W) AND (FileIn.3 = 3)
FileOut.1 = FileOut.1 □)
I2 = ((EOF(FileIn)) AND (FileIn.3 = R) )
Значение части DO, следовательно, является композицией этих трех функций C◦ F ◦ I. Композиция может быть вычислена с использованием условных трассировочных таблиц. Каждое условие помечается. Имеется два условия для C, три условия для F и два - для I. Всего 12 комбинаций. Каждая таблица помечается условиями, которые она покрывает. Например, (C1, F1, I1) представляет первое условие C, первое условие F и первое условие I. FileIn и FileOut будут сокращенно называться FI и FO, соответственно.
12 случаев:
Случай 1(C1, F1, I1) |
Случай 5 (C1, F3, I1) |
Случай 9 (C2, F2, I1) |
Случай 2(C1, F1, I2) |
Случай 6 (C1, F3, I2) |
Случай 10 (C2, F2, I2) |
Случай 3(C1, F2, I1) |
Случай 7 (C2, F1, I1) |
Случай 11 (C2, F3, I1) |
Случай1 4(C1, F2, I2) |
Случай 8 (C2, F1, I2) |
Случай 12 (C2, F3, I2) |
Случай 1(C1, F1, I1)
Условие |
Ch |
F0.1 |
FI.1 |
FI.2 |
(Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.2 = z B & y) AND (FI.3 = R) AND (FO.3 = W) |
□ |
FO.1 Ch & z |
FI.1 & z B |
y |
(□ = ‘ ‘) AND (NOT(EOF(<FI.1 & z B,y,FI.3>))) AND (FI.3 = R) AND (y = b Z & w) |
Z |
|
FI.1 & z B & b Z |
w |
NOT(EOF(<FI.1 & z & B & b Z, w, FI.3>)) AND (FI.3 = R) AND (FO.3 = W) |
|
FO.1 Ch & z □ |
|
|
Условие такое:
(Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.2 = z B & y) AND (FI.3 = R) AND (FO.3 = W) AND (□ = □)
AND (NOT(EOF(<FI.1 & z B,y,FI.3>)) AND (y = b Z & w)
AND (NOT(EOF(<FI.1 & z & B & b Z, w, FI.3>)))
Несколько частей данного условия эквивалентны TRUE:
Условие |
равно TRUE, т.к. |
□ = □ |
Очевидно |
NOT(EOF(<FI.1 & z B,y,FI.3>)) |
Из-за следующего условия: y = b Z & w, а w – не пусто |
NOT(EOF(<FI.1 & z & B & b Z, w, FI.3>)) |
W не пусто |
Таким образом, выполнив подстановку y, условие уменьшается до:
Условие:
(Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.2 = x B & b Z & w) AND (FI.3 = R) AND (FO.3 = W)
Присваивание:
Ch, FO.1, FI.1, FI.2 := Z, FO.1 Ch & x □, FI.1 & x B & b Z, w
Задание 4. Аналогичным образом напишите условные присваивания для случаев 2 - 12. Покажите, что произойти могут только случаи 1, 4, 6, 7, 10 и 12.
(55 баллов)
Собирая вместе все возможные случаи, композиция трех функций C◦F◦I имеет условия и присваивания:
Случай 1.
Условие: (Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.2 = x B & b Z & w) AND (FI.3 = R) AND (FO.3 = W)
Присваивание: Ch, FO.1, FI.1, FI.2 := Z, FO.1 Ch & x □, FI.1 & x B & b Z, w
Случай 4.
Условие: (Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.2 = x B & b /) AND (FI.3 = R) AND (FO.3 = W)
Присваивание: Ch, FO.1, FI.1, FI.2 := □, FO.1 Ch & x □, FI.1 & x B & b /, ††
Случай 6.
Условие: (Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R) AND (FO.3 = W) AND (FI.2 = x /)
Присваивание: Ch, FO.1, FI.1, FI.2 := □, FO.1 Ch & x, FI.1 & x /, ††
Случай 7.
Условие: (Ch = ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R) AND (FI.2 = b Z & w) AND (FO.3 = W)
Присваивание: Ch, FO.1, FI.1, FI.2 := Z, FO.1 □, FI.1 & b Z, w
Случай 10.
Условие: (Ch = ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R) AND (FI.2 = b /)
Присваивание: Ch, FI.1, FI.2 := □, FI.1 & FI.2, ††
Случай 12.
Условие: (Ch = ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R)
Присваивание:
Игнорируя условия того, что входной файл должен быть открыт для чтения, а выходной – для записи, случаи 1, 4 и 6 происходят когда значении Ch не равно □, а входной файл не закончился, согласно значению FileIn.2, мы имеем следующее:
Случай |
FileIn.2 |
Следующее слово z |
Добавляение к FileOut.1 |
1 |
Z B & b Z & w |
пары <пробел> <слово> |
Ch & z □ |
4 |
Z B & b / |
<пробелы> |
Ch & z |
6 |
Z / |
Маркер конца строки |
Ch & z |
z – это строка непробельных символов, не содаржащая маркер конца строки, B – пробел, либо маркер конца строки, b – строка пробелов или маркеров конца строк, w – это непустая строка, Z- символ, не являющийся пробелом либо маркером конца строки
Случаи 7 и 10 происходят, когда значения Ch равно □, а входной файл не закончился.
Случай |
FileIn.2 |
Следующие <пробелы> b |
Добавляение к FileOut.1 |
7 |
b Z & w |
пары <слово> <пробел> |
Ch & z □ |
10 |
b / |
Маркер конца строки |
Ch & z |
Случай 12 происходит в конце файла. К FileOut ничего не добавляется.
Функция g = C ◦ F ◦ I может быть записана в виде условного присваивания при помощи комбинирования случаев, написанных выше.
g =
((Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R) AND (FO.3 = W)
(FI.2 = z B & b Z & w Ch, FO.1, FI.1, FI.2 := Z, FO.1 Ch & x □, FI.1 & x B & b Z, w) |
(FI.2 = z B & b / Ch, FO.1, FI.1, FI.2 := □,FO.1 Ch & x, FI.1 & x B & b /, ††) |
(FI.2 = z / Ch, FO.1, FI.1, FI.2 :=□, FO.1 Ch & x, FI.1 & x /, ††)) |
((Ch = ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R)
((FI.2 = b Z & w) AND (FO.3 = W) Ch FO.1, FI.1, FI.2 := Z, FO.1 □, FI.1 & b Z, w) |
(FI.2 = b / Ch, FI.1, FI.2 := □, FI.1 & FI.2, ††)) |
((Ch = ‘ ‘) AND (EOF(FI)) AND (FI.3 = R) )
Номера слева идентичны случаям, осуждаемым выше. Эта функция описывает копирование слова из FileIn в FileOut, начинающегося с символа в Ch (в том случае, когда он не равен пробелу); когда Ch является пробелом, единственный пробел добавляется к FileOut за исключение случая, при котором курсор в FileIn указывает на конец файла.
В проекте процедуры RemoveExtraBlanks входной и выходной файлы были описаны с использованием нотации Бекуса-Наура. Строки, описываемые нотацией BNF, могут также быть описаны с использованием формальных строковых операций, как это было сделано в определении функции g. Наличие соответствия между этими двумя описаниями помогает понять, как программа решает задачу. В случае 1, нам показывают, что входная строка имеет вид:
Ch & x B & b Z & w
Подчеркнутая последовательность может быть описана в виде BNF так:
<слово> <пробелы> <не пробел>
где <слово> - это непустая строка непробельных символов, <пробелы> - непустая строка □, а <непробел> - это непробельный символ. B & b могут содержать маркеры конца строки, но они будут сконвертированы в пробелы до того, как будут рассмотрены в Ch)
Выходная строка для случая 1 функции g изменяется путем добавления:
Ch & x □,
что в нотации BNF представляет собой
<слово> <пробел>
В случае 1, функция g конвертирует строку вида:
<слово> <пробелы> <не пробел>,
в строку вида:
<слово> <пробел> <не пробел>.
Аналогичным способом запишем в виде BNF оставшиеся случачаи: