Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 44
Текст из файла (страница 44)
Программисту зтн сведения нужны для того, чтобы писать правильные программы и заранее знать результат выполнения любых операторов программы. Разработчику корректные определения конструкций необходимы для создания правильной реализации языка. В большинстве руководств определение семантики дается в виде обычного текста. Как правило, сначала при помощи какой-либо формальной грамматики (например, НФБ-грамматики) дается определение синтаксиса конструкции, а затем для пояснения семантики приводятся несколько примеров и небольшой пояснительный текст. К сожалению, смысл этого текста часто неоднозначен, так что разные читатели могут понимать его по-разному.
Программист может получить ошибочное представление о том, что именно будет делать написанная им программа при выполнении, а разработчик может реализовать какую-либо языковую конструкцию иначе, чем разработчики других реализаций того же языка. Как и в случае синтаксиса, нужен какой-то метод, позволяющий дать удобочитаемое, точное и лаконичное определение семантики всего языка. Задача определения семантики языка программирования рассматривается теоретиками так же долго, как и задача определения синтаксиса, но в данном случае гораздо труднее найти удовлетворительное решение, Было разработано множество различных методов формального определения семантики. Ниже мы приводим описания некоторых из них, Грамматические модели. Некоторые ранние попытки добавить корректное определение семантики к языку программирования делались путем добавления расширений к НФБ-грамматике, определяющей этот язык.
Дополнительную ин- 4.2. Семантика языка 157 формацию о семантике можно было извлечь из дерева синтаксического разбора. Мы коротко обсудим атрпбутивные грамматики как способ получения этой дополнительной информации. Императивные (операционные) модели. Операционное определение языка программирования дает описание того, как составленные на данном языке и рограммы выполняются на виртуальном компьютере, Обычно виртуальный компьютер определяется как автомат, но гораздо более сложный по сравнению с обычными моделями автоматов, которые используются при изучении синтаксиса и осуществлении синтаксического разбора.
Внутренние состояния этого автома> а соответствуют сосгояниям программы при ее выполнении; это означает, что в состояние автомата входят значения всех переменных, выполняемая программа и различные вспомогательные системные структуры данных. Для определения возможных изменений внутреннего состояния автомата в результате выполнения одного операт<>ра программы используется набор формально определенных операций. Вторая часть определения задает способ трансляции текста программы в исходное состояние автомата. Начиная с этого исходного состояния, автомат в соответствии с определяющими его правилами последовательно переходит к следующим состояниям, пока не достигнет конечного. Такое операционное определение языка программирования может представлять собой достаточно прямую абстракцию возможной фактической реализации языка. С другой стороны, это определение может представлять и более абстрактную модель, которую можно использовать как основу для программно моделируемого интерпретатора языка, но не для фактической реализации В 70-с гг.
была разработана операционная модель языка под названием 1 )еипа Ое/ииг1оп 7апдиаде (>>1>1) — метаязык, предназначенный для описания других языков. В этой модели дерево синтаксического анализа включает в себя также машинный интерпретатор. Состояние вычисления входит в дерево программы, а такжевдерево, описывающее все данные для конкретной машины. Очередной оператор переводит дерево в новос состояние. Аппликативпые модели.
Аппликативное определение языка пытается непосредственно сконструировать определение функции, которую вычисляет каждая программа, написанная на атом языке. Такое определение языка строится как иерархия определений функций, которые вычисляются каждой отдельной программной конструкцией. По аналогии с аппликативными языками, которые обсуждались в первой главе, атот метод определения языка представляет собой аппликативцый подход к моделированию семантики.
В программе любая элементарная операция или операция, определенная программистом, представляет собой некоторую математическую функцию. Структуры управления последовательностью действий могут быть использованы для композиции этих функций в более крупные последовательности, представленные в тексте программы выражениями и операторами.
Линейные последовательности операторов и условное ветвление легко могут быть представлены функциями, составленными из функций, которые соответствуют отдельным компонентам этих конструкций. Цикл обычно представляется посредством рекурсивной функции, составленной из компонентов, вхолящих в тело цикла. В конце концов образуется функциональная модель всей программы. Примерами такого подхода к определс- 158 Глава 4.
Моделирование свойств языка нию семантики являются метод денотационной сел)антики Скотта (Ясогс) и Стрэчи (ЯггасЬеу) и лштод функциональной семантики Миллза (М)Пз). В разделе 4.2.2 вы найдете краткое введение в денотационную семантику. Аксиоматические модели. Данный метод распространяет на программы область применения исчисления предикатов.
Семантику каждой синтаксической конструкции языка можно определить как некий набор аксиом или правил вывода, который можно использовать для вывода результатов выполнения этой конструкции. Чтобы понять смысл всей программы (то есть разобраться, что и как она делает), эти аксиомы и правила вывода следует использовать так же, как при доказательстве обычных математических теорем. В предположении, что значения входных переменных удовлетворяют некоторым ограничениям, аксиомы и правила вывода мо)ут быть использованы для получения (вывода) ограничений на значения других переменных после выполнения каждого оператора программы.
В конце концов, когда программа выполнена, мы получаем доказательство того, что вычисленные результаты удовлетворяют необходимым ограничениям на их значения относнтедьно входных значений. То есть доказано, что выходные данные представляют значения соответствующей функции, вычисленной по значениям входных данных. Примером описанного подхода является метод аксиоматической семантики, разработанный Хвором (Ноаге) (см. раздел 4.2.4). Модели спецификаций.
В модели спецификаций мы описываем отношение между различными функциями, реализующими про)рамму. Пока нам удается показать, что реализация подчиняется этому отношению между любыми двумя функциями, мы можем утверждать, что она коррекгна по отношению к спецификации. Алгебраический тип данных является одним из видов формальной спецификации.
Например, если вы пишете программу, реализующую стеки, то действия раз)) (записать в стек) и рор (прочитать из стека) имеют противодоложное действие в том смысле, что если для некоторого заданного стека 5 выполнить действие рвэ)), а затем немедленно — действие рор, то в итоге получится исходный стек. Это можно сформулировать в виде аксиомы: рар(рвэщ5 х)) - 5 Любая реализация, которая сохраняет это свойство (а также некоторые другие), является корректной реализацией стека. В разделе 4.2.5 мы представим краткий обзор алгебраических типов данных. Формальное определение семантики становится общепринятой частью определения нового языка. Стандартное описание языка Р1./1 включает в себя г'1)1.-подобную нотацию, описываюшую семантику операторов Р1./1, а для языка Ада было разработано определение на основе денотационной семантики.
Тем не менее изучение формальных определений семантики не оказало такого сильного влияния на практическое определение языков, как изучение формальных грамматик — на определение синтаксиса. Ни один из методов определения семантики не оказался полезным ни для пользователя, ни для разработчика языка. Операционные модели достаточно удобны для создания формальной модели реализации и могут быть полезны разработчику, но для пользователя эти модели не имеют большого значения, так как в них слишком много ненужных ему подробностей. Разработчик вряд ли сможет руководствоваться функциональными и денотационными моделями, а для пользователя они, как правило, оказываются слишком сложными, чтобы их можно было 4.2. Семантика языка 159 использовать непосредственно.
Пользователю легче понять аксиоматическне модели, но при попытке составить полное определение языка обычно они становятся чрезвычайно сложными, а для разработчика эти модели и вовсе непригодны. В следующем разделе вы найдете краткое описание атрибутивной грамматики как одной из форм семантической модели языка программирования. В разделе 4 2 мы описываем другие семантические модели. 4.2.1. Атрибутивные грамматики Атрибут Правило Е-+ Е+Т значение (Е~) = значение (Ег) + значение (Т) значение(Е) = значение(Т) значение (Т, ) = значение (Тг) х значение (Р) значение(Т) = значение(Р) значение (Р) = значение числа) значение(Р) = значение(Е) Š— гт Т->Тх Р Т-чР Р-+1 Р -г (Е) Здесь нижние индексы 1 и 2 обозначают соответственно ссылку на первый и второй одинаковые нетерминальные символы в данном правиле.
На рис. 4.3 представлен пример дерева с атрибутами, которос дает значение выражения 2 ч- 4 х (1 ч- 2). Одной из первых попыток разработки семантической модели языка программирования была концепция атрибутивной грамматики, предложенная Лональдом Кнутом [64). Идея заключалась в том, чтобы сопостанить каждому узлу дерева синтаксического разбора данной программы некоторую функцию, задающую семантическое содержание данного узла. Лтрибутивные грамматики создавались путем добавления функпий (атрибутов) к каждому правилу грамматики. Унаслгедованиый атрибут — это функция, которая сопоставляет петерминальные значения в данном узле дерева с нетерминальными значениями, расположенными на более высоком уровне дерева.
Иными словами, функциональное значение для нетерминальных символов, расположенных в правой части любого правила, является функцией нетерминальных символов, расположенных в его левой части. Синтезированный атрибут — это функция, которая соотносит нетерминальные символы, расположенные в левой части правила, со значениями нетерминальных символов, расположенными в правой части правила.
Такие атрибуты передают информацию вверх по дереву (то есть они синтезированы на основе информации, взятой из нижних уровней дерева). Рассмотрим простую грамматику для арифметических выражений: Е-+Т ( ЕчТ Т-+Р)ТхР Р -г 1 ) (Е) Семантику этого языка можно определить посредством набора отношений между нетерминальнымн символами грамматики. Например, значение любого выражения, определяемого этой грамматикой, выводится при помощи следующих функций. Е значение = 14 значение = 4 Т значение = 2 Е Р значение = 3 + 4 значение = 2 Т значение = 4 Р ! 4 значение = 2 Р значение = 1 Р значение = 2 значение = 1 значение = 1 Рис.
4.3. Пример дерева со значениями атрибутов Атрибутивные грамматики можно использовать для передачи семантической информации по синтаксическому дереву. Например, можно с помощью правил объявлений собрать всю информацию об объявлениях и информацию из получившейся таблицы символов передавать вниз по дереву для использования при генерации кода для выражений, Например, для создания множества имен, объявленных в программе, можно добавить следующие атрибуты к нетерминальным символам <бес! > и <бес1ага с1оп>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
