Синтаксис и семантика CF Pascal

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

Выполнение программ предполагает дополнительный набор проблем, которыми мы можем быть озадачены. Как долго она будет выполняться? Не произойдет ли аварийного завершения? Какие строки были выполнены и сколько раз? Какие ресурсы (память, файловое пространство, пропускная способность сети, производительность процессора) требуются для выполнения этой программы? Ответы на эти вопросы зависят от входных данных использованных при выполнении программы. Поведение программы зачастую различается для разных входных данных и чтобы сделать заключение о ее поведении, требуется исчерпывающий набор тестовых запусков с разными входными данными, которые могут дать представление о разных аспектах выполнения программы.

Нотация Бекуса-Наура (BNF) предоставляет нам точный способ описания синтаксиса CF Pascal. Вместе с контекстными правилами, синтаксические правила BNF описывают все возможности для разработки программ на CF Pascal.

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

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

Семантическое значение для данной CF Pascal программы будет математическое отношение или функция, упорядоченный набор пар, который определяет соответствие между одним набором данных (INPUT) и другим набором данных (OUTPUT). Значением программы будет трансформация данных, описанная следующим соответствием: данным значениям в INPUT соответствуют значения в OUTPUT полученные при выполнении этой программы на Паскаль-машине.

СЕМАНТИКА CF PASCAL.

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

Знать значение программы – значит быть способным определить выход программы для любого заданного входа. Если для некоторого X на входе программа выдает Y на выходе, то такая пара формирует часть значения функции. Множество всех пар X,Y для которых программа выполняется корректно, является полным значением программы.

Если какие-то входные данные X₀ вызывают аварийное завершение или бесконечное выполнение, то X₀ н принадлежит значению программы.

Для некоторых программ значения выражаются довольно просто.

PROGRAM Copy (INPUT, OUTPUT);

{Writes first character in INPUT to OUTPUT}

VAR

Ch: CHAR;

BEGIN

READ(Ch);

WRITELN(Ch);

END.

Значение этой программы содержит пары, такие что входная строка не пуста (содержит символы или маркеры конца строки) а выходная строка содержит первый символ входной. Если первый символ входной строки является маркером конца строки, то выходная строка будет содержать символ пробела и такие пары также принадлежат значению программы.

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

Строки символов.

Строки символов – математические объекты, , имеющие имена, над ними определены операции и отношения.

Новые идеи: строка символов, символьный литерал, строковый литерал, пустая строка, конкатенация, композиция, декомпозиция, подсписок.

Строковый литерал (или просто строка) - последовательность символов, чье начало и конец помечены специальным символом – маркером строки.

Строка, не имеющая символов, 0-строка, называется пустой строкой. Примеры строк:

†† - 0-строка

†□† - 1-строка

†string† - 6-строка

†□string□† - 8-строка

Символьные литералы мы помечаем горизонтальным штрихом над символом, например S для изображения пробелов используем специальный символ □.

Строковые и символьные литералы не одно и то же, их не нужно путать. 1-строка не то же самое, что символ, который в ней размещается. Например, □ – символ, †□† - 1-строка.

Строковым литералам удобно присваивать имена, например: S = †string†. Строка может иметь несколько имен, но одно имя использовать для нескольких строк некорректно. Имена лучше всего использовать для именования не каких-то определенных строк, а тех, значение которых мы можем предположить.

CF Pascal предлагает три операции для манипулирования строками:

Оператор CF Pascal	Строковая операция
WRITE(‘ABC’)	Конкатенация
WRITE(Ch)	Композиция
READ(Ch)	Декомпозиция

Эти операции над строками образуют базис для работы со строками как математическими объектами.

Конкатенация строк.

Выходные данные программы обычно представляют собой строку символов, создаваемую выполнением операторов WRITE. Оператор WRITE, где <список вывода> является <строкой символов>, помещает новую строку вслед за текущими данными в OUTPUT.

Операция конкатенации в CF Pascal задается оператором WRITE и заключается в помещении строки символов в OUTPUT. Конкатенацией двух строк является третья строка, полученная присоединением второй строки к первой. Например:

C= †character†

S= †string†

C&S=†characterstring†

S&C=†stringcharacter†

S&S=†stringstring†

Для пустой строки справедливо следующее тождество:

† † & S = S & † † = S

Операция конкатенации является бинарной (два операнда, оба - строки), инфиксной (символ операции помещается между операндами), ассоциативной ((C&B)&S = C&(B&S)) и не является коммутативной(S&C ¹ C & S).

Подстроки.

Строки W = †WRITE(Any, ‘string’)† и строка S = †string† имеют некоторое отношение, а именно символы встречаются внутри W. Говорят, что строка S является подстрокой W.

Строка P является подстрокой Q, если и только если существует строки X и Y, такие что

Q= X & P & Y

В случае с S и W мы можем записать

W = †WRITE(Any, ‘† & S & †’)†

Где согласно определению подстроки

X = †WRITE(Any, ‘†

Y = †’)†

Или для строки T = †tring†

S = †s† & T

T- подстрока S и согласно определению подстроки

X = †s†

Y = ††

или

S = †s† & T & ††

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

Композиция строк.

Оператор WRITE может выполнять другую операцию, присоединяя значение переменной типа CHAR к строке, которая является текущим значением OUTPUT. Это операция композиции, обозначаемая знаком Ñ. Композиция строки и символа – добавление символа к концу строки.

†strin† Ñ g = †string†

Композиция обеспечивает нам способ превращения символа в строку

† † Ñ g = †g†

Это общее тождество, связывающее символ и 1-строку содержащую этот символ.

Композиция с пустой строкой настолько полезна, что пустую строку принято опускать и получается унарная префиксная версия композиции:

Ñ g = †g†

Аналогично конкатенации операция композиции является бинарной(первый операнд – строка, второй - символ), инфиксной, ассоциативной и не является коммутативной.

Следующие варианты недопустимы для композиции

Вариант	Причина
a Ñ b	Первый операнд – символ
Ñ †x†	Операнд 1-строка, а не символ
N Ñ ††	Оба операнда выбраны неверно

Декомпозиция строк.

Если оператор WRITE реализует конкатенацию и композицию строк, то оператор READ выполняет разбиение строк. При каждом выполнении оператора READ с одной переменной строка символов в INPUT разделяется на две части. Первый символ в INPUT становится значением символьной переменной, которая используется в выражении READ, а оставшиеся символы становятся текущей строкой для ввода.

Строковые операции голова (head) и хвост (tail) точно описывают то, что происходит при выполнении выражения READ. Глова (Θ) и хвост (Λ) – унарные префиксные операции, определенные на непустых строках.

Θ S – первый символ в строке S

Λ S – подстрока S полученная удалением первого символа

Например для:

S = †string†

T = †tring†

Θ S = s

Λ S = †tring† = T

Θ T = t

Λ T = †ring†

Поскольку хвост строки – строка, он может служить предметом дальнейшей декомпозиции, например:

Θ (Λ T) = r

Λ(Λ T) = †ing†

Λ (Λ(Λ T)) = †ng†

Θ (Λ (Λ(Λ T))) = n

К-й символ строки может быть извлечен К-1 операциями хвост, к результату которых применена операция голова.

Следует выделить следующие моменты:

1. Операции голова и хвост не определены на пустых строках
2. Результат операции голова – символ, операции хвост – строка.

Поскольку голова строки – символ, мы можем превратить его в строку с помощью композиции, далее с помощью конкатенации с хвостом получим исходную строку.

Θ †string† = s

Λ †string† = †tring†

Ñ(Θ †string†) = †s†

(Ñ(Θ †string†)) & (Λ †string†) = †s† & †tring† = †string†

Этот пример описывает фундаментальное тождество, связывающее операции конкатенации, композиции и декомпозиции, а именно: для любой непустой строки S справедливо следующее:

(Ñ(Θ S)) & (Λ S) = S

Следующая таблица обобщает наши знания о строковых операциях.

Операция	Символ	Пример
конкатенация	&	†me† & †you† = †meyou†
композиция	Ñ	†plural†Ñs = †plurals†
символ в 1-строку	Ñ	Ñv = †v†
голова	Θ	Θ†feet† = f
хвост	Λ	Λ†rattle† = †attle†

Списковые структуры.

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

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

Например, для строки

†this is a list example†

список литералов

<†th†, †is †, †is †, †a †, †list example†>

предлагает нам вариант нарезки данной строки. Выражение Pascal произведет один и тот же OUTPUT, если будет использована данная строка или список, полученный в результате ее разбиения на подстроки.

WRITE(‘this is a list example’);

WRITE(‘th’, ‘is ‘, ‘is ‘, ‘a ‘, ‘list example’);

Спискам, как и строкам, могут быть присвоены имена, например:

L = <†th†, †is †, †is †, †a †, †list example†>

M = <†this is a list example†>

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

Если элемент x находится в списке K, мы обозначаем факт как принадлежности списку как

x Î K, если список K не имеет ни одного вхождения объекта x, мы говорим, x Ï K.

Например, †is † Î L, но †is † Ï M.

Список L содержит пять подстрок, которые могут быть обозначены следующим образом:

L₁ = †th†

L₂ = †is †

L₃ = †is †

L₄ = †a †

L₅ = †list example†

В то время M как содержит только одну строку

M₁ = †this is a list example†

Мы будем использовать индексы для именования элементов списков, используя 1 для обозначения первого элемента и т.д. L можно назвать 5-список, M - 1-список. Список без элементов, 0-список, называется пустым списком и обозначается <>. Необходимо отличать список, содержащий в себе одну строку, от этой строки. Например, M – 1-список с первым и единственным элементом M₁ и

M = <M₁>, но M ¹ M₁

Также необходимо иметь ввиду, что

<††> ¹ <>

потому что <††> это 1-спиоск, первый элемент которого пустая строка, а <> - 0-список и первый элемент там отсутствует.

Элементами списков могут быть не только строки, но и символы и другие списки. Например, список

C = <c, h, a, r, a, c, t, e, r>

Является списком символов и это не то же самое, что строка †character†

Следующий список является списком списков

<M, M> = <<†this is a list example†>, <†this is a list example†>>

где элементами 2-списка являются 1-списки М, рассмотренные выше.

Список может иметь элементы различных видов, например

Q = <A, <A>, †A†>

Содержит элементы, которые являются соответственно символом, списком и строкой.

Элемент данного списка Q₂ содержит единственный элемент – символ A.

(Q₂)₁ = A

Списковые операции.

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

Конкатенацией & двух списков является третий список, полученный присоединением второго к первому. Элементы списка L & M это элементы списка L, дополненные элементами списка M, следующими непосредственно за последним элементом L.

Композиция Ñ для списков означает присоединение элемента в конец списка. Элементы списка L Ñ x, это элементы списка L, дополненные x, следующим непосредственно за последним элементом L.

В декомпозиции результатом операции голова Θ является первый элемент в списке, если таковой имеется. Результатом операции хвост Λ является список, полученный из исходного исключением первого элемента. Операции голова и хвост не определены на пустых списках.

Подсписки определяются аналогично строкам через операцию конкатенации. L является подсписком M, если и только если существуют списки X и Y, такие что

M = X & L & Y

Следующая таблица обобщает наши знания о списковых операциях.

Операция	Символ	Пример
Конкатенация	&	<A> & <A, B> = <A, A, B> <†12†, <A>> & <X> = <†12†, <A>, X>
Композиция	Ñ	<A> Ñ B = <A, B> <A> Ñ <> = <A, <>> <A> Ñ †† = <A, ††> <> Ñ V = <V> <> Ñ <††> = <<††>>
Голова	Θ	Θ<X, <X>> = X
Хвост	Λ	Λ<X, <X>> = <<X>>

Хотя для обозначения порядка элементов в списке используются целые числа, концепция списка не нуждается в натуральных числах. Концепция порядка в последовательности проще и намного примитивнее, чем концепция натуральных чисел. Чтобы определить, какой из двух элементов k и m предшествуют в списке Q сформируем последовательность

Θ Q, Θ(Λ Q), Θ(Λ (Λ Q)), …

и определим, где какой из элементов появляется первым k или m.