Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 40
Текст из файла (страница 40)
Используется для запоминания типа (целого или действительною), Глава 3. Описание синтаксиса и самантикн ожидаемого от выражения, и определяемого типом переменной, стоящей в левой части оператора присваивания. Полностью атрибутивная грамматика показана в листинге З.б. 1. Синтаксическое правило: <присвоить> -з <переменная> := <выражение> Семантическое правило: <выражение>.ожидаемый тип <в <переменная>.фактический тип 2.
Синтаксическое правило: <выражение> -> <переменная>[2] <переменная>[3] Семантическое правило: <выражение>.фактический тип <- 11 (<переменная>[2].фактический тип = 'г.), апс((<переменная>[3].фактический тип = 1пг) г(теп 1пг еХае геа1 епс( 1Г Предикат: <выражение>. фактический тип <выражение>.ожидаемьвч тип 3. Синтаксическое правило: <выражение> -+ <переменная> Семантическое правило: <выражение>. фактический тип +- <переменная>.фактический тип Предикат: <выражение>.фактический тип <выражение>.
ожидаемый тип 4. Синтаксическое правило: <переменная> -+ й(В(С 5. Семантическое правило: <переменная>.фактический тип епоиск(<переменная>.строка) Функция поиска ищет имя данной переменной в таблице идентификаторов и возвращает тип переменной. Пример дерева синтаксического анализа предложения й: = й + В, порождаемого грамматикой, описанной в листинге З.б, показан на рис. 3.7. Как и в самой грамматике, после повторяющихся меток узлов дерева добавлены числа в скобках, так что ни них можно ссылаться однозначно.
14У 3.5. Атрибутивные грамматики <прнсвонть> ннов> (3] <пере А А в Рис. 3. 7. Дерево синтаксического инопизи предло>гения А: = А е В 3.5.6. Вычисление значений атрибутов Рассмотрим теперь процесс заполнения дерева синтаксического анализа атрибутами. Если все атрибуты унаслелованные.
то этот процесс может полностью происходить в нисхоляшем порядке, от корня к листьям. Если же все атрибуты синтезированные. то процесс полностью протекает в восходящем порядке, от листьев к корню. Поскольку рассматриваемая грамматика солержит и синтезированные. и унаслелованные атрибуты, вы пкление значений не может происходить в каком-то одном направлении. Ниже описано вычисление атрибутов в том порядке, в котором они люгут вычисляться.
В общем случае опрелеленне такого порядка вычисления значений атрибутов в обшем случае является сложной задачей, требуюшей создания графа зависимостей для прослеживания всех связей между атрибутами. 1. <переменная>.фактический тип <- поиск(й] (Правило 4) 2. <вь:саженке>.ожидаемый тип < — <переменная>. фактический тип ,'Поавиго 1) 3. <переменная>(2].фактический тип <- поиск[й) (Правило 4) <переменная>(3].фактический тип < — поиск(В) (Правило 4) 4. <вьсажение>.фактический тип < — целый или действительный (Правило 2) 5. <выражение>. ожидаемый тк.. <- <выражение>.
фактический тип или )4О7ИР(й или ЛОЖЬ (Полнило 2) Дерево, приведенное на рис. 3.8, показывает процесс заполнения значениями атрибутов дерева, приведенного на рис. 3.7. Сплошные линии использованы для изображения дерева синтаксического анализа, пунлгирные — процесса вычисления значений атрибутов. Дерево. изображенное на рис. 3.9, показывает окончательные значения атрибутов всех узлов дерева.
В данном примере тип переменной й определен действительным. а переменной  — целым. Глава 3. Описание синтаксиса и семантики влить> <вырвхвние> <фвкки ческий тип> <фапичесилй тип> реыеннвя > 13),ч' еннвя> !2! Л <пере А А В Рис. 3.8. Процесс запазнелия дерева атрибуллашл <прнсвсить> ый тип =действительный мп кнй тип = пей<тли>ел>ныл 1ип нилл> йй Флккическив тип Фвктический илп = <пе селин ип действительный мп А В Рис.
3.9. Подлостью описанное дерево снтлаксического ана>нза 3.5.7. Оценка 3.5. Атрибутивныв грамматики Атрибутнвные грамматики использовались: для полного описания синтаксиса и статической семантики языков программирования (чйлаг!. ! 979); в качестве формазьного определения языка для создания систем генерании компиляторов 1гаггоы<, 1982); как основа для некоторых синтаксически управляемых систем редактирования (Те)гей>аап апд Керл, 1981; г)вйег ег а1, 1984). Помимо этого, атрибутивные грамматики применяются в системах обработки текстов на естественных языках. Одним из основных нелостатков атрибутивной грамматики для описания всего синтаксиса и статической семантики реального современного языка программирования является ее сложность и громоздкость. Большое число атрибутов и грамматических правил, требуемое для полного описания языка программирования, значительно затрудняет написание и чтение подобной грамматики.
Более того, вычисление значений атрибутов большого дерева синтаксического анализа дорого обходится. С другой стороны. менее формальные атрибутивные грамматики представляют собой мощный и широко используемый инструмент для разработчиков компиляторов, которых больше интересует создание компилятора. чем формализм грамматики. 3.6. Описание смысла программ: динамическая семантика Перейдем к сложной задаче описания динамической семантики (дупавк зевапйсз), или смысла, выражений, операторов и программных единиц. Благодаря мощи и естественности формы записи описание синтаксиса является относительно простым лелом.
С другой стороны, лля динамической семантики еше не изобрели общепринятой формы записи. В данном разделе кратко описаны несколько разработанных метолов. Термин сжнишника будет означать динамическую семантику; статическую семантику мы булем называть полностью. Существует несколько причин, по которым следует заниматься описанием семантики. Во-первых.
программисты должны точно знать, что именно делают операторы языка. Однако зачастую они узнают это, читая неточные и неполные англоязычные объяснения в руковолствах по языку. Разработчики компиляторов также обычно опрелеляют семантику языков, лля которых они создают компиляторы, руководствуясь описаниями на английском языке. Все эти неформальные описания заменяют сложные формальные описания семантики. Цель исследований очевидна — найти семантический формализм, который мог бы использоваться программистами и разработчиками компиляторов.
Было пролелано несколько экспериментальных работ по автоматическому порождению компиляторов языков программирования непосредственно из их семантических описаний. В заключение отметим, что показательство корректности программ опирается на некоторое формальное описание семантики языка. 3.6.1. Операционная семантика Операиионная семантика (орегабопа1 зевапбсз), сводится к описанию смысла программы посредством выполнения ее операторов на машине, реальной или виртуально1ь Смысл оператора определяется изменениями, произошедшими в состоянии машины после выполнения данного оператора.
Для того чтооы разобраться в этой концепции, рассмотрим команду на машинном языке. Пусть состояние компьютера — это значения всех его регистров и ячеек памяти, в том числе коды условий н регистры состояний. Если просто записать состояние компьютера, выполнить команду, смысл которой нужно определить, а затем изучить новое состояние машины, то семантика этой команлы станет понятной: она представляется изменением в состоянии компьютера, вызванным выполнением этой команды. 3.6.1.1. Основной процесс Описание операнионной семантики операторов языков программирования высокого уровня требует созлания реального или виртуального компьютера.
В главе 1 говорилось, что аппаратное обеспечение компьютера является чистым интерпретатором его машинного языка. Чистый интерпретатор любого языка программирования может быть создан с помощью программных средств, которые становятся виртуальным компьютером для данного языка. Семантику языка высокого уровня можно описать, используя чистый ин- 150 Глава 3. Описание синтаксиса и семантики Оперецконнак оенанткка ехгр 1оор: Дй ехрг2 = О дока оцс Оператор капка С гок (ехрг1г ехрг2; ехргЗ)( ехргЗ; дока 1осо оцг: Человек, читающий подобное описание.
является "виртуальным компьютером" и предполагается способным правильно "выполнить" команды описания и распознать эффект такого "выполнения". В качестве примера низкоуровневого языка, который можно применять лля операционной семантики, рассмотрим следующий список операторов, соответствующих простым управляющим операторам типичного языка программирования: 1аепг : чаг 1аепс := 1аепс + 1 даепс := 1аепс -1 дево 1аЬе1 дг' чаг ге1ор чаг дока 1аЬе1 Здесь ге1ор — одни из операторов отношений из набора (=, <», , <, >=, < ~, 1аепг — идентификатор, а чаг — нлентифнкатор или константа.
Все эти операторы просты и легки лля понимания и реализации. З.б. Описание смысла программ: динамическая семантика терпретатор данного языка. При таком подходе, правла, существуют лве проблемы. Вопервых, сложность и индивидуальные особенности аппаратного обеспечения компьютера и операционной системы, используемых для запуска чистого интерпретатора. затрудняют понимание происходящих действий.
Во-вторых. выполненное таким образом семантическое определение будет доступно только для люлей с абсолютно идентичной конфигурацией компьютера. Этих проблем можно избежать. заменив реальный компьютер виртуальным компьютером низкого уровня, реализованным с помощью программного моделирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
