3. Семантическая теория программ.

Семантическая теория программы

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

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

1. Лексика, т.е. знаковая система, состоящая из алфавита и множества вспомогательных символов т.е. допустимых символов, используемых в данной системе.

2. Синтаксис, т.е. множества правил построения последовательности допустимых символов. А именно, синтаксис позволяет определить правильно построенные формулы ППФ от случайной последовательности символов, используемых в этом языке.

3. Семантика – это взаимно однозначное соответствие между допустимыми последовательностями символов языка и смыслами, придаваемыми этим последовательностям в данном языке.

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

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

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

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

В отношении семантики успехи математической лингвистики гораздо скромнее в этом отношении большое значение имеет знаменитая теорема Райса (Никакое нетривиальное свойство функции не является алгоритмически разрешимым, т.е. по описанию алгоритма нельзя ничего узнать о свойствах вычисляемой функции [нетривиальное св-во – «функция принаджлежит классу С, где С – непустой класс, и существуют ф-ии не принадлежащие С), которая накладывает известное ограничение на семантику языков программирования.

Исследования алфавита

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

Или считается, что алфавит В является расширением алфавита А.

Если в естественном языке совокупность символов называется словом, то в языках программирования совокупности символов алфавита называется более нейтральным термином – строки.

И любую строку можно записать как а1, а2, …, аn.

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

Заметим, что лямбда не является символом алфавита, а специально введена для возможности использования пустой строки.

По аналогии с лингвистикой, иногда удобно строки иногда называть словами, множество всех строк над алфавитом А называется замыканием А и обозначают, как A*. A * = A’U A^2 U…A^n В том случае, когда мы не делаем ограничений на число символов в слове:

А* = А^0 U … U A^n, n – бесконечность.

Основная операция над строками – конкатенация. Формально, она может быть определена, как результат слияния 2х строк.

Если строки состоят из повторяющихся букв, то в математической лингвистике принято сокращенное обозначение: пустая строка: a^0; aa=a^2; abaaa=aba^3.

Традиционно программы для ЭВМ записываются в виде строк символов на некотором языке программирования.

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

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

Механизм проверки правильности цепочек символов необходим трансляторам.

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

Если принадлежит, то транслятор переводит её в машинный код, иначе – сообщает программисту о предполагаемых ошибках. Как правило, предполагаемые ошибки – это отличия анализируемой цепочки от некой ближайшей к ней правильной цепочке.