Работа со строками слов (стр. 2 )

  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 s B) & y)

  AND (FileIn.3 = R) AND (FileOut.3 = W) ’

  Ch, FileOut.1,FileIn.1, FileIn.2 :=

  □,(FileOut.1 s Ch) & x, FileIn.1 & (x s 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 s Z & w ’

  Ch, FileIn.1, FileIn.2 := Z, FileIn.1 & b s Z, w)

F2 = (FileIn.2 = b s / ’

  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 s □)

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 s B & y) AND (FI.3 = R) AND (FO.3 = W)	□	FO.1 s Ch & z	FI.1 & z s B	y
(□ = ‘ ‘) AND (NOT(EOF(<FI.1 & z s B, y,FI.3>))) AND (FI.3 = R) AND (y = b s Z & w)	Z	FI.1 & z s B & b s Z	w
NOT(EOF(<FI.1 & z & B & b s Z, w, FI.3>)) AND (FI.3 = R) AND (FO.3 = W)	FO.1 s Ch & z s □

Условие такое:

(Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.2 = z s B & y) AND (FI.3 = R) AND (FO.3 = W) AND (□ = □)

AND (NOT(EOF(<FI.1 & z s B, y,FI.3>)) AND (y = b s Z & w)

AND (NOT(EOF(<FI.1 & z & B & b s Z, w, FI.3>)))

Несколько частей данного условия эквивалентны TRUE:

Условие	равно TRUE, т. к.
□ = □	Очевидно
NOT(EOF(<FI.1 & z s B, y,FI.3>))	Из-за следующего условия: y = b s Z & w, а w – не пусто
NOT(EOF(<FI.1 & z & B & b s Z, w, FI.3>))	W не пусто

Таким образом, выполнив подстановку y, условие уменьшается до:

Условие:

(Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.2 = x s B & b s Z & w) AND (FI.3 = R) AND (FO.3 = W)

Присваивание:

Ch, FO.1, FI.1, FI.2 := Z, FO.1 s Ch & x s □, FI.1 & x s B & b s 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 s B & b s Z & w) AND (FI.3 = R) AND (FO.3 = W)

Присваивание: Ch, FO.1, FI.1, FI.2 := Z, FO.1 s Ch & x s □, FI.1 & x s B & b s Z, w

Случай 4.

Условие: (Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.2 = x s B & b s /) AND (FI.3 = R) AND (FO.3 = W)

Присваивание: Ch, FO.1, FI.1, FI.2 := □, FO.1 s Ch & x s □, FI.1 & x s B & b s /, ††

Случай 6.

Условие: (Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R) AND (FO.3 = W) AND (FI.2 = x s /)

Присваивание: Ch, FO.1, FI.1, FI.2 := □, FO.1 s Ch & x, FI.1 & x s /, ††

Случай 7.

Условие: (Ch = ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R) AND (FI.2 = b s Z & w) AND (FO.3 = W)

Присваивание: Ch, FO.1, FI.1, FI.2 := Z, FO.1 s □, FI.1 & b s Z, w

Случай 10.

Условие: (Ch = ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R) AND (FI.2 = b s /)

Присваивание: 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 s B & b s Z & w	пары <пробел> <слово>	s Ch & z s □
4	Z s B & b s /	<пробелы>	s Ch & z
6	Z s /	Маркер конца строки	s Ch & z

z – это строка непробельных символов, не содаржащая маркер конца строки, B – пробел, либо маркер конца строки, b – строка пробелов или маркеров конца строк, w – это непустая строка, Z - символ, не являющийся пробелом либо маркером конца строки

Случаи 7 и 10 происходят, когда значения Ch равно □, а входной файл не закончился.

Случай	FileIn.2	Следующие <пробелы> b	Добавляение к FileOut.1
7	b s Z & w	пары <слово> <пробел>	s Ch & z s □
10	b s /	Маркер конца строки	s Ch & z

Случай 12 происходит в конце файла. К FileOut ничего не добавляется.

Функция g = C ◦ F ◦ I может быть записана в виде условного присваивания при помощи комбинирования случаев, написанных выше.

g =

((Ch <> ‘ ‘) AND (NOT(EOF(FI))) AND (FI.3 = R) AND (FO.3 = W) ’