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

1. Модификация тех или иных параметров внутреннего устройства базового типа. Например, в языке С существует возможность определения коротких (short) и длинных (long), знаковых (signed) и беззнаковых (unsigned) вариантов обычного целого типа.

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

3. Определение неоднородных совокупностей из данных разного типа. Примеры таких совокупностей – записи (record) в языке Pascal, структуры (struct) в языке С. Идентификация элементов таких совокупностей для доступа к их значениям обычно осуществляется по составному имени, включающему имя совокупности и имя элемента. Перечень операций, применимых к элементам, полностью определяется их типами. К записям (структурам) в целом обычно оказываются применимы такие же операции, что и к массивам (передача в качестве аргументов, возврат в качестве результата и присваивание).

4. Определение процедур/функций. Это объекты, к которым могут применяться операции вызова с передачей им аргументов требуемых типов и/или операции передачи их в качестве аргументов других процедур/функций. С другой точки зрения процедуры/функции можно рассматривать как новые операции, определяемые программистом и применяемые к значениям их аргументов.

5. Объектно-ориентированное программирование. Это развитие способа 4 в сочетании со способом 3 (структуры и записи), которое привело к образованию ряда базовых понятий: классов, их свойств и методов. Свойство экземпляра класса, выглядящее в тексте программы как составное имя элемента данных, реализуется путем создания двух одноименных функций, одна из которых предназначена для извлечения значения свойства (аналогичное понятие – r-value), а другая – для присваивания ему значения (аналог – l-value). В зависимости от того, в каком контексте употребляется имя свойства, транслятор подставляет вместо него вызов либо той, либо другой функции. Методы, более похожие на обычные функции

---

, стали основой для определения и переопределения операций, применяемых к экземплярам классов (например, операции >> и << классов cin и cout, определенных в языке С++ для ввода и вывода данных).

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

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

Для каждого из способов конструирования производных типов данных в разных языках предусматриваются различные моменты связываний атрибутов объектов с самими объектами. Выбор момента выполнения связывания, как уже было отмечено, влияет как на мощность изобразительных средств языка, так и на скорость работы программ, разработанных средствами данного языка. Независимо от того, к какому типу – базовому или производному – относятся объекты программы, для каждой операции с некоторым объектом, обнаруженной в ее тексте, семантический анализатор транслятора должен иметь возможность выявления как внутреннего устройства объекта, так и применимости данной операции к его значению. Это делается на основе явных или неявных объявлений типов объектов программы и обычно называется контролем типов данных.

3. 
   Контроль типов данных объектов программы
   

В различных языках программирования реализован широкий спектр подходов к контролю типов данных.

На одном конце спектра находятся такие языки программирования (например, язык Perl), в которых не требуется явно указывать типы используемых в программе объектов (или явное определение типов опционально, как в языке Visual Basic). В этом случае тип объекта может стать известным (определенным) только после первого присваивания ему значения во время исполнения программы. До этого присваивания тип объекта просто не определен. Последующие во времени операции с объектом могут приводить к изменению его типа. Ясно, что в таком случае семантические проверки возможности выполнения операций над значениями объектов могут быть произведены только во время исполнения программы, поскольку типы данных операндов всех или некоторых операций не известны во время трансляции. При интерпретации эти проверки будут выполняться транслятором или виртуальной машиной. Если реализуется компиляция, то семантический анализатор должен встраивать в программу дополнительные действия для проверки возможности исполнения операций над объектами неизвестного типа, построенных по тексту транслируемой программы.

---

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

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

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

К строгой типизации стремились разработчики языков Pascal, Ada, Java и ряда других.

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

Большое количество языков программирования, в том числе такие популярные (по крайней мере, в свое время), как Algol-60, Fortran, С и многие другие, занимают то или иное промежуточное положение в этом спектре, предоставляя, с одной стороны, полную информацию о типах и возможность (но необязательность в Fortran’е) явного единственного объявления типа каждого объекта в рамках одной программной единицы, а с другой – нарушение двух последних требований строгой типизации. Так, например, в каждом из перечисленных языков допускается возможность присваивания значения одного типа объекту другого типа с подразумеваемым, т. е. неявно выполняемым, преобразованием. В языках Fortran и С существует возможность выполнения операций, не применимых к значениям данного типа за счет неконтролируемой подстановки – присваивания значения объекту другого типа (такие возможности предоставляют объявления common, equivalence в Fortran и union в С). Любое нарушение правил строгой типизации – потенциальная причина появления в программе ошибок, которые иногда чрезвычайно трудно обнаружить. Именно за это языки, не гарантирующие строгую типизацию, часто подвергаются суровой критике. Вместе с тем требования строгой типизации заметно сужают область применения языка программирования. Системные программы, такие как операционные системы и их утилиты, очень трудно разрабатывать, соблюдая абсолютно все требования строгой типизации.

---

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

Исполнение программы есть последовательное исполнение операций, преобразующих значения своих операндов в значения, которые будут обрабатываться другими операциями. Для любой операции не позже чем к моменту ее фактического исполнения должны быть установлены действительная возможность ее применения к значениям операндов и конкретный способ обработки значений. Для примера вспомним, что складывать целые числа, целое и вещественное, целое и указательное и т. д. нужно по-разному. Выражение a+b должно быть преобразовано в разные машинные команды для различных сочетаний типов данных a и b. Для выявления смысла каждой операции в общем случае нужно выполнить такую последовательность действий:

– определить количество операндов (напомним, что одно и то же слово может применяться для разных операций: скажем, знак «–» обычно используется и для обозначения бинарной операции вычитания и для обозначения унарной операции изменения знака числа);

– определить тип каждого операнда;

– проверить, допустим ли этот тип к данной позиции операнда в операции путем сравнения типов;

---

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

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

4. 
   Эквивалентность типов данных
   

Для описания типа языковой конструкции будем использовать понятие «выражение типа». Выражение типа, как и любое выражение, имеет вычисляемое значение, которым может являться либо базовый, либо производный тип. В том случае если тип является производным, значение выражения типа должно быть построено с помощью применения оператора, называемого конструктором типа, к другим выражениям типа. Множества базовых типов и конструкторов производных типов зависят от проверяемого языка.

В некоторых языках программирования типам могут даваться имена. Например, во фрагменте программы на языке Pascal, представленном на рис. 8.2, идентификатор link объявлен в качестве имени типа ^cell(указатель на ячейку).

1. 
   type link = ^cell; var next : link;
   
2. 
   last : link;
   
3. 
   p : ^cell; q, r :^cell;
   

Рис. 8.2. Имена типов в языке Pascal
Для реализации последующих операций важно знать, идентичны ли типы переменных next, last, p, q и r? Для реализации правил проверки очень важно иметь точное определение равенства двух типов. Потенциальная неоднозначность возникает с именами выражений типа, которые затем используются в последующих выражениях типа. Ключевой вопрос обычно состоит в том, является ли имя в выражении типа само по себе выражением или сокращением для другого выражения типа.

Для обеспечения высокой эффективности работы транслятора требуется использовать такие представления выражений типа, которые позволяют быстро определять, являются ли сравниваемые типы эквивалентными. Представление типов может быть либо именным, либо структурным, либо кодированным.

• 
  Именное представление и сравнение типов
  

Именная эквивалентность проверяется путем:

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

---