Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 32

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 26 27 28 29 30 31 < 32 > 33 34 35 36 37 38 .. 316 >> Следующая

86
ГЛАВА 2. ССП
§ 2.3. АБСТРАКТНОЕ И КОНКРЕТНОЕ ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ
2.3.1. Абстрактное представление
Обычное текстовое представление программы имеет синтаксическую структуру, в которой каждая структурная единица — языковая конструкция — является строкой, вводимой из некоторого нетерминального символа грамматики языка. Грамматика, таким образом, задает конкретные синтаксические правила построения программы как строки символов и, вместе с тем, определяет, какие структурные элементы могут быть выделены в правильном тексте программы, который естественно считать конкретным представлением программ і. Здесь нет речи о вычислительном аспекте программ, ко-торй появляется тогда, когда грамматическое, или, что то е, конкретно-синтаксическое определение языка дополняется заданием модели вчисле-ний.
Действия абстрактного вычислителя определяются на структурном представлении программы.
о но описвать вчисления на структуре, которая непосредственно задается грамматикой языка: для кадой грамматической (конкре но-син ак-сической) конструкции определяется, какие действия абстрактный вычислитель должен осуществить с ее составляющими, т. е. с сыновними вершинами в дереве конструкции. Эти составляющие, являясь также конструкциями программ , в сво очередь, иницииру т соответствуие вчисления над составляими их конструкциями. днако такое использование конкретной синтаксической структуры не совсем адекватно, в частности, по следуим причинам.
a) Есть элемента, вообще никаким действиям не соответствующие и необ-ходиме только для обеспечения представления программы в виде текста: слу ебне слова, не несуие операционной нагрузки, комментарии и др.
b) Программы, записанные по-разному, но очевидным образом эквивалентные с точки зрения эффекта вычислений, да т разну конкретну синтаксическую структуру (см. пример).
Пример 2.3.1. Три оператора
X = a * b + c * d; X = (a * b) + (c * d); X = ((a * b) + (c * d));
2.3. ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ
87
и подобные им содерательно полность эквивалентны, тогда как с точки зрения текстового представления различны.
В то же время, приведенные выше фрагменты не эквивалентны следую-ему:
X = a * (b + c) * d;
Конец примера 2.3.1.
Таким образом, нужна структура синтаксических понятий, которая соответствует некоторому поняти эквивалентности программ. т выбранного конкретного понятия эквивалентности зависит вбор структурного представления синтаксиса, используемого для задания абстрактного вычислителя, которое называется абстрактно-синтаксическим представлением.
Возмо ен и другой, чае всего применяемый на практике, ход. место явного задания вчислительной эквивалентности зада т понятие синтаксической эквивалентности, которое очевиднм образом согласуется с функциональной эквивалентность . Так, например, предло ения, перечисленные в примере 2.3.1, могут описываться следующим понятием синтаксической эквивалентности: скобки вокруг подвыра ений, связанных операцией более всокого приоритета, чем операция, примененная к их результату, могут опускаться. В данном смысле присваивание рассматривается так е как операция, имеая более высокий приоритет, чем лбая из арифметических операций.
Еще одна возможность, открываемая переходом к абстрактно-синтаксическим определениям, мо ет быть усмотрена, если м определим, например, эквивалентность подвыра ений для сло ения и умно ения
A + B о B + A.
Здесь абстрактная эквивалентность враает не просто соглаение об опускании скобок, а свойство самой операции. пт показывает, что далье ассоциативности и коммутативности в абстрактном синтаксисе двигаться весьма опасно.
Рассмотрим, в частности, предельнй случай: если считать эквивалент-нми все программы, которе на одних и тех е входных даннх приводят к получению одних и тех же выходных данных (функциональная эквивалент -ность программ), то данное понятие является просто алгоритмически неразрешимым, и использовать его для определения абстрактного синтаксиса абсурдно.
88
2.
ля понимания суности вчислений и отделения ее от конкретно-синтаксических деталей ниже приводится ряд иллюстраций, которые показывают, как можно определять вычисления в языке программирования на основе абстрактно-синтаксических структур.
Пример 2.3.2. [Соответствие конкретного и абстрактного] В качестве развития приведенных примеров эквивалентных и неэквивалентных фрагментов программ на рис. 2.2 вверху приведены две (неэквивалентные!) абстрактно-синтаксические структур арифметических выра ений и их текстовые представления. ля вра ений, получаихся дописванием линих скобок, деревья абстрактно-синтаксических представлений будут в точности те же самые. Другой вариант абстрактно-синтаксической структуры для выра-ений мо ет бть предло ен, если допустить переменное число ветвей у вершин дерева (см. третий вариант на рис. 2.2, приводится дерево только для первого фрагмента, поскольку для второго оно совпадает с преддуим вариантом). Здесь уже используются конкретные знания о свойствах сложения: его ассоциативность.
Следуий пример иллстрирует вызов функции:
Предыдущая << 1 .. 26 27 28 29 30 31 < 32 > 33 34 35 36 37 38 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100