Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

5. 
   Требования к содержанию отчета.
   

Отчет должен содержать:

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

6. 
   Контрольные вопросы
   

1. 
   В чем состоят функции контроля структуры программы?
   
2. 
   Перечислите известные Вам способы представления типов данных.
   
3. 
   Что такое тетрада?
   
4. 
   Опишите этапы алгоритма преобразования постфиксной записи в последовательность тетрад.
   
5. 
   Перечислите известные Вам способы образования производных типов данных.
   

---

Лабораторная/практическая работа № 8

1. 
   Название работы: «Семантика языков программирования. Типы данных. Виртуальные машины, интерпретирующие псевдокод».
   
2. 
   Цели работы: изучение семантических свойств объектов транслируемой программы, методов их выявления и использования, типов данных и методов контроля типов, областей видимости переменных, локальных и нелокальных сред ссылок, способов передачи параметров, приобретение навыков разработки элементов виртуальной машины для интерпретируемого языка.
   
3. 
   Основные теоретические сведения:
   

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

1. 
   Базовые типы данных
   

Перечень базовых типов и их свойства, как правило, полностью определяются стандартом языка программирования, хотя некоторые детали могут определяться аппаратной платформой и конкретной реализацией транслятора. Количество базовых типов данных в любом языке программирования обычно очень ограничено. Так, например, в языке С существует всего три базовых типа данных – символьный (char), целый (int) и вещественный (float). Для целого типа определены три разновидности, не обязательно различающиеся по диапазону значений: короткий (short), обычный и длинный (long), для вещественного – две разновидности: обычный и двойной точности (double). Кроме того, символьные и целые значения могут быть либо знаковыми (signed, по умолчанию), либо беззнаковыми (unsigned).

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

Под типом элемента данных принято понимать:

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

Большинство деталей внутреннего устройства данных (за исключением диапазона значений) обычно скрывается от программистов. Для построения транслятора (и понимания принципов его работы), наоборот, очень важны детали внутреннего строения данных. Именно с ними имеют дело процессы семантического анализа, генерации объектного кода и его оптимизации.

---

Внутреннее устройство объектов может быть как очень простым, так и чрезвычайно сложным. Например, объект символьного типа в языке С мож но считать одним из простейших. Внутреннее представление значения такого объекта занимает минимальный адресуемый участок памяти – один байт. Диапазон значений внутреннего представления – от 0 до 255 (в десятичной системе счисления). В операциях символьное значение рассматривается как целое число без знака.

Другой пример – функция в языке С. Функция есть программная единица, возвращающая значение некоторого типа (на данный момент будем считать, что функция возвращает значение одного из базовых типов). Имя функции может быть использовано в выражении, следовательно, она является объектом программы. Каждая конкретная функция имеет свой собственный уникальный тип, внутреннее устройство которого в самых общих чертах можно описать следующим образом.

Функция – это как минимум одна область последовательно расположенных элементов памяти, содержащая исполняемые команды и отдельно расположенные области памяти для хранения адресов связи с другими функциями, значений аргументов, значений локальных переменных, значения результата. Имена функций (с фактическими аргументами) могут быть использованы в выражениях таким образом, что может возникнуть впечатление, будто к ним (функциям) применимы арифметические или иные операции. На самом деле эти операции применяются к значениям, возвращаемым объектом типа «функция». К самим же функциям, как к объектам, применима только операция вызова, т. е. операция передачи управления.

Информация о внутреннем устройстве объектов программы нужна транслятору для определения того, как именно должны использоваться значения объектов. Пусть, например, имеется выражение x + y.

Вычисление значения этого выражения может протекать по-разному не только для разных сочетаний типов данных в одном языке программирования, но и в том случае, если типы данных объектов x и y одинаковы, но это выражение появляется в программах на разных языках программирования. Например, если объекты x и y имеют символьный тип, то в программе на языке С/С++ будет выполняться арифметическое сложение численных эквивалентов текущих значений символов с образованием целого значения в качестве результата, а в программе на языке Object Pascal – конкатенация этих символов с образованием значения типа «массив символов» или «строка». Таким образом, результатом вычисления выражения

---

'0'+'A' в программе на языке С будет целое беззнаковое число 113 (которое можно рассматривать и как символ 'q'), а в программе на языке Object Pascal – строка "0A" (последовательность из двух символов '0' и 'A').

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

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

Константы бывают именованными и литеральными.

Именованные константы с точки зрения решения задач семантического анализа почти полностью эквивалентны переменным. Единственное отличие состоит в том, что к именованной константе неприменима операция присваивания. Способы объявления именованных констант в разных языках различны.

Литеральными константами (или просто литералами) называются объекты, не имеющие имени и объявленные просто в виде их значений прямо в тексте инструкции.

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

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

---

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

1. 
   int val;
   
2. 
   double values[10];
   
3. 
   double * pointer;
   
4. 
   val=1;
   
5. 
   pointer=values;
   
6. 
   *pointer=1;
   
7. 
   pointer+=1;
   

Рис. 8.1. Литеральные константы в языке С

В этой последовательности появляются три литеральные константы с идентичным текстовым представлением 1. Казалось бы, после обработки текста лексическим анализатором, обнаружившим три вхождения целочисленной константы 1, транслятор должен каждое из этих вхождений связать с одним и тем же объектом.

Однако семантические правила языка С таковы, что в операторе присваивания

4. 
   val=1;
   

должно использоваться целое значение 1, результатом выполнения оператора

4. 
   *pointer=1;
   

в конечном итоге должна быть запись вещественного значения 1.0 (заметим, что внутреннее двоичное представление вещественной единицы может не совпадать с представлением целой единицы) в самый первый элемент массива values, а фактическое значение литеральной константы 1 в строке (7) зависит от реализации транслятора (и от аппаратной платформы) и может оказаться равным 8 или 10.

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

2. 
   Производные типы данных
   

Производные типы конструируются программистом по правилам, определенным стандартом языка. Для разных языков эти правила различаются.

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

---