Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214
 Скачать 452.53 Kb.
|
Лабораторная/практическая работа № 8Название работы: «Семантика языков программирования. Типы данных. Виртуальные машины, интерпретирующие псевдокод». Цели работы: изучение семантических свойств объектов транслируемой программы, методов их выявления и использования, типов данных и методов контроля типов, областей видимости переменных, локальных и нелокальных сред ссылок, способов передачи параметров, приобретение навыков разработки элементов виртуальной машины для интерпретируемого языка. Основные теоретические сведения: При реализации виртуальной машины интерпретатора необходимо учитывать множество свойств языка программирования. Базовые типы данных Перечень базовых типов и их свойства, как правило, полностью определяются стандартом языка программирования, хотя некоторые детали могут определяться аппаратной платформой и конкретной реализацией транслятора. Количество базовых типов данных в любом языке программирования обычно очень ограничено. Так, например, в языке С существует всего три базовых типа данных – символьный (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 к данным символьного типа не могут применяться битовые и арифметические операции, а могут только операции присваивания и сравнения. К функции, наоборот, может быть применена операция передачи управления (с предварительным сохранением адреса возврата), но не может применяться ни одна арифметическая, логическая или сравнивающая операция (как уже было сказано, не следует путать операции с функцией как объектом программы и операции со значением, возвращаемым ею в результате вызова). Базовые типы данных определены стандартом языка во всех деталях, т. е. разработчику транслятора заранее известно их внутреннее устройство, множество применимых к ним операций, в том числе операций преобразования в другие базовые типы, преобразования из внешнего во внутреннее представление, и наоборот, из внутреннего во внешнее. Базовыми типами данных могут обладать так называемые простые переменные и константы. Константы бывают именованными и литеральными. Именованные константы с точки зрения решения задач семантического анализа почти полностью эквивалентны переменным. Единственное отличие состоит в том, что к именованной константе неприменима операция присваивания. Способы объявления именованных констант в разных языках различны. Литеральными константами (или просто литералами) называются объекты, не имеющие имени и объявленные просто в виде их значений прямо в тексте инструкции. С литеральными константами связано несколько проблем, которые могут разными способами решаться разработчиками трансляторов: Являются ли несколько текстуально одинаковых литеральных констант, встречающихся в разных точках текста программы, одним объектом времени исполнения, или каждая такая константа есть самостоятельный объект, занимающий собственный элемент памяти? В какой момент времени (на каком этапе трансляции) должно осуществляться отнесение каждой встреченной в тексте программы константы к тому или иному типу данных и соответственно преобразование литерала (текстового представления константы) во внутреннее представление, т. е. значение? Единых ответов на эти вопросы не существует. От того, как разработчик языка отвечает на них, существенно зависят свойства языка, а также характеристики программ на нем. Проиллюстрируем существо этих проблем на небольшом примере. Пусть в программе на языке С встречается такая последовательность операторов, показанная на рис. 8.1. int val; double values[10]; double * pointer; val=1; pointer=values; *pointer=1; pointer+=1; Рис. 8.1. Литеральные константы в языке С В этой последовательности появляются три литеральные константы с идентичным текстовым представлением 1. Казалось бы, после обработки текста лексическим анализатором, обнаружившим три вхождения целочисленной константы 1, транслятор должен каждое из этих вхождений связать с одним и тем же объектом. Однако семантические правила языка С таковы, что в операторе присваивания val=1; должно использоваться целое значение 1, результатом выполнения оператора *pointer=1; в конечном итоге должна быть запись вещественного значения 1.0 (заметим, что внутреннее двоичное представление вещественной единицы может не совпадать с представлением целой единицы) в самый первый элемент массива values, а фактическое значение литеральной константы 1 в строке (7) зависит от реализации транслятора (и от аппаратной платформы) и может оказаться равным 8 или 10. Этот простой пример показывает, что (по крайней мере, в некоторых языках) установление типа данных литеральных констант и формирование внутреннего представления их значений не может выполняться на этапах лексического или синтаксического анализа. Оно должно выполняться семантическим анализатором позднее. Производные типы данных Производные типы конструируются программистом по правилам, определенным стандартом языка. Для разных языков эти правила различаются. В силу того, что возможность и степень удобства конструирования в точности таких типов, которые необходимы для решения каждой конкретной задачи, чрезвычайно важны при программировании, именно средства, предоставляемые языком для этих целей, во многом определяют как потенциальную применимость языка, так и его популярность. В зависимости от того, что понимается под типом данных, существует несколько принципиально различающихся возможностей для определения производных типов (здесь перечислены только некоторые, наиболее часто употребляемые способы). 1. Модификация тех или иных параметров внутреннего устройства базового типа. Например, в языке С существует возможность определения коротких (short) и длинных (long), знаковых (signed) и беззнаковых (unsigned) вариантов обычного целого типа. 2. Образование однородных (содержащих элементы одного и того же типа) массивов требуемых размерности и границ по каждому измерению. Идентификация элементов массива для доступа к их значениям осуществляется с помощью указания целочисленных индексов по каждому измерению. К элементам массивов обычно оказываются применимы в точности те же самые операции, что и к одиночным элементам данных того же самого типа. К массивам в целом обычно оказываются применимыми только передача в качестве аргумента процедуры или функции, возврат в качестве значения функции и (не во всех языках программирования) присваивание. 3. Определение неоднородных совокупностей из данных разного типа. Примеры таких совокупностей – записи (record) в языке Pascal, структуры (struct) в языке С. Идентификация элементов таких совокупностей для доступа к их значениям обычно осуществляется по составному имени, включающему имя совокупности и имя элемента. Перечень операций, применимых к элементам, полностью определяется их типами. К записям (структурам) в целом обычно оказываются применимы такие же операции, что и к массивам (передача в качестве аргументов, возврат в качестве результата и присваивание). 4. Определение процедур/функций. Это объекты, к которым могут применяться операции вызова с передачей им аргументов требуемых типов и/или операции передачи их в качестве аргументов других процедур/функций. С другой точки зрения процедуры/функции можно рассматривать как новые операции, определяемые программистом и применяемые к значениям их аргументов. 5. Объектно-ориентированное программирование. Это развитие способа 4 в сочетании со способом 3 (структуры и записи), которое привело к образованию ряда базовых понятий: классов, их свойств и методов. Свойство экземпляра класса, выглядящее в тексте программы как составное имя элемента данных, реализуется путем создания двух одноименных функций, одна из которых предназначена для извлечения значения свойства (аналогичное понятие – r-value), а другая – для присваивания ему значения (аналог – l-value). В зависимости от того, в каком контексте употребляется имя свойства, транслятор подставляет вместо него вызов либо той, либо другой функции. Методы, более похожие на обычные функции, стали основой для определения и переопределения операций, применяемых к экземплярам классов (например, операции >> и << классов cin и cout, определенных в языке С++ для ввода и вывода данных). 6. Создание указателя на существующий тип данных. Не в каждом языке допускается явное программирование операций с адресами как со значениями. Как уже упоминалось, в языках, не предназначенных для системного программирования, адресная арифметика обычно полностью скрывается от программиста. Если же разрешается образовывать указательные типы данных, как правило, к ним допускается применять только операции присваивания. И только в языках, предназначенных в основном для написания системных программ (например, в языке С), к указательным значениям оказывается возможным применение некоторых арифметических операций (сложение и вычитание с целым значением) и операций сравнения. Для каждого из способов конструирования производных типов данных в разных языках предусматриваются различные моменты связываний атрибутов объектов с самими объектами. Выбор момента выполнения связывания, как уже было отмечено, влияет как на мощность изобразительных средств языка, так и на скорость работы программ, разработанных средствами данного языка. Независимо от того, к какому типу – базовому или производному – относятся объекты программы, для каждой операции с некоторым объектом, обнаруженной в ее тексте, семантический анализатор транслятора должен иметь возможность выявления как внутреннего устройства объекта, так и применимости данной операции к его значению. Это делается на основе явных или неявных объявлений типов объектов программы и обычно называется контролем типов данных. Контроль типов данных объектов программы В различных языках программирования реализован широкий спектр подходов к контролю типов данных. На одном конце спектра находятся такие языки программирования (например, язык Perl), в которых не требуется явно указывать типы используемых в программе объектов (или явное определение типов опционально, как в языке Visual Basic). В этом случае тип объекта может стать известным (определенным) только после первого присваивания ему значения во время исполнения программы. До этого присваивания тип объекта просто не определен. Последующие во времени операции с объектом могут приводить к изменению его типа. Ясно, что в таком случае семантические проверки возможности выполнения операций над значениями объектов могут быть произведены только во время исполнения программы, поскольку типы данных операндов всех или некоторых операций не известны во время трансляции. При интерпретации эти проверки будут выполняться транслятором или виртуальной машиной. Если реализуется компиляция, то семантический анализатор должен встраивать в программу дополнительные действия для проверки возможности исполнения операций над объектами неизвестного типа, построенных по тексту транслируемой программы. Такие действия обычно называются динамическими проверками в отличие от статических проверок, которые выполняются во время трансляции программы. Динамические проверки могут значительно увеличивать время исполнения программы независимо от того, интерпретируется она или компилируется. Необходимо отметить, что этот подход, т.е. потенциальная возможность изменения типов объектов программы «на лету», постоянно подвергается жесткой критике вследствие крайней затруднительности разработки безопасных программ (программ, не содержащих трудно обнаруживаемые ошибки). Тем не менее основанные на таком подходе языки программирования существуют и продолжают развиваться. Другой крайней точкой рассматриваемого спектра подходов к контролю типов данных является так называемая строгая (сильная) типизация. Под строгой типизацией понимается выполнение следующей совокупности требований к программе: для каждого используемого в программе типа должны быть известны множество значений (т. е. внутреннее устройство) и множество применимых к ним операций; каждый объект программы должен иметь однажды определенный и неизменяемый тип; при выполнении любого присваивания значения объекту тип присваиваемого значения должен быть эквивалентен типу объекта; использование значения объекта допускается только в качестве операнда операций, допустимых для данного типа. К строгой типизации стремились разработчики языков Pascal, Ada, Java и ряда других. В случае строгой типизации подавляющая часть полного набора семантических проверок возможности применения операций к объектам может быть выполнена в процессе трансляции программы, т. е. статически. К сожалению, абсолютно все проверки реализовать во время трансляции нельзя, достаточно вспомнить операцию деления на неизвестное транслятору значение, которым при исполнении программы может оказаться ноль. Первичная информация для проверок извлекается семантическим анализатором из операторов объявления данных и сохраняется в таблице идентификаторов в качестве атрибутов объектов. Как часть общего текста программы эти операторы вначале обрабатываются лексическим и синтаксическим анализаторами и могут преобразовываться в постфиксную форму записи. Большое количество языков программирования, в том числе такие популярные (по крайней мере, в свое время), как Algol-60, Fortran, С и многие другие, занимают то или иное промежуточное положение в этом спектре, предоставляя, с одной стороны, полную информацию о типах и возможность (но необязательность в Fortran’е) явного единственного объявления типа каждого объекта в рамках одной программной единицы, а с другой – нарушение двух последних требований строгой типизации. Так, например, в каждом из перечисленных языков допускается возможность присваивания значения одного типа объекту другого типа с подразумеваемым, т. е. неявно выполняемым, преобразованием. В языках Fortran и С существует возможность выполнения операций, не применимых к значениям данного типа за счет неконтролируемой подстановки – присваивания значения объекту другого типа (такие возможности предоставляют объявления common, equivalence в Fortran и union в С). Любое нарушение правил строгой типизации – потенциальная причина появления в программе ошибок, которые иногда чрезвычайно трудно обнаружить. Именно за это языки, не гарантирующие строгую типизацию, часто подвергаются суровой критике. Вместе с тем требования строгой типизации заметно сужают область применения языка программирования. Системные программы, такие как операционные системы и их утилиты, очень трудно разрабатывать, соблюдая абсолютно все требования строгой типизации. Явные объявления типов данных, с одной стороны, позволяют обеспечивать более или менее строгий контроль применимости знаков операций к операндам во время трансляции, с другой – порождают ряд проблем, которые так или иначе должны быть разрешены разработчиками языка программирования и трансляторов для него. Потенциальная возможность неоднократного (намеренного или случайного) объявления типа данных для одного и того же наименования порождает первую проблему: разрешать такую возможность или запрещать ее. Запрет множественных объявлений разных объектов с одним именем в пределах одной транслируемой программы в принципе возможен, но обычно считается слишком жестким ограничением и практически не применяется. В том случае, когда такие объявления разрешаются стандартами языка, ими же должны быть определены правила, позволяющие любое использование наименования в тексте программы отождествить с единственным объектом (либо обнаружить и диагностировать ошибку). Такие правила можно определить на основе понятия ассоциации и использовать их во время трансляции для определения того, к какому именно объекту будет применяться операция во время исполнения программы. Исполнение программы есть последовательное исполнение операций, преобразующих значения своих операндов в значения, которые будут обрабатываться другими операциями. Для любой операции не позже чем к моменту ее фактического исполнения должны быть установлены действительная возможность ее применения к значениям операндов и конкретный способ обработки значений. Для примера вспомним, что складывать целые числа, целое и вещественное, целое и указательное и т. д. нужно по-разному. Выражение a+b должно быть преобразовано в разные машинные команды для различных сочетаний типов данных a и b. Для выявления смысла каждой операции в общем случае нужно выполнить такую последовательность действий: – определить количество операндов (напомним, что одно и то же слово может применяться для разных операций: скажем, знак «–» обычно используется и для обозначения бинарной операции вычитания и для обозначения унарной операции изменения знака числа); – определить тип каждого операнда; – проверить, допустим ли этот тип к данной позиции операнда в операции путем сравнения типов; – на основании результатов всех проверок принять решение, может ли быть выполнена данная операция и если может, то как. Предполагая, что задачи определения количества операндов и их типов решены (первая может считаться тривиальной, а вторая обычно решается путем выборки атрибутов объекта из таблицы идентификаторов, см. раздел 4.8), сосредоточимся на способах решения задачи сравнения типов. Под сравнением будем понимать только установление эквивалентности или неэквивалентности двух типов. Эквивалентность типов данных Для описания типа языковой конструкции будем использовать понятие «выражение типа». Выражение типа, как и любое выражение, имеет вычисляемое значение, которым может являться либо базовый, либо производный тип. В том случае если тип является производным, значение выражения типа должно быть построено с помощью применения оператора, называемого конструктором типа, к другим выражениям типа. Множества базовых типов и конструкторов производных типов зависят от проверяемого языка. В некоторых языках программирования типам могут даваться имена. Например, во фрагменте программы на языке Pascal, представленном на рис. 8.2, идентификатор link объявлен в качестве имени типа ^cell(указатель на ячейку). type link = ^cell; var next : link; last : link; p : ^cell; q, r :^cell; Рис. 8.2. Имена типов в языке Pascal Для реализации последующих операций важно знать, идентичны ли типы переменных next, last, p, q и r? Для реализации правил проверки очень важно иметь точное определение равенства двух типов. Потенциальная неоднозначность возникает с именами выражений типа, которые затем используются в последующих выражениях типа. Ключевой вопрос обычно состоит в том, является ли имя в выражении типа само по себе выражением или сокращением для другого выражения типа. Для обеспечения высокой эффективности работы транслятора требуется использовать такие представления выражений типа, которые позволяют быстро определять, являются ли сравниваемые типы эквивалентными. Представление типов может быть либо именным, либо структурным, либо кодированным. Именное представление и сравнение типов Именная эквивалентность проверяется путем: извлечения текстового представления имени типа из программы или формирования его путем применения конструктора типа; приведения этого представления к стандартному виду (замена возможных сокращений, удаление незначащих пробелов, добавление всех возможных скобок и т.д.); сравнения двух текстовых представлений как обычных строк. При применении этого способа к фрагменту программы на рис. 8.2 будут получены имена выражений типов переменных, приведенные в табл. 8.1.  Таблица 8.1
|