Реферат: Семантический анализатор

ОГЛАВЛЕНИЕ

Место компилятора впрограммном обеспечении. 3

Основные принципыработы синтаксического анализатора. 6

Дерево разбора.Преобразование дерева разбора в дерево операций. 8

Автоматизацияпостроения синтаксических анализаторов (программа YACC) 10

Назначениесемантического анализа. 12

Этапы семантическогоанализа. 13

Идентификациялексических единиц языков программирования. 16

Список использованныхисточников. 19


Место компилятора в программном обеспечении

Компиляторысоставляют существенную часть программного обеспечения ЭВМ. Это связано с тем,что языки высокого уровня стали основным средством разработки программ. Толькоочень незначительная часть программного обеспечения, требующая особойэффективности, программируется с помощью ассемблеров. В настоящее времяраспространено довольно много языков программирования. Наряду с традиционнымиязыками, такими, как Фортран, широкое распространение получили так называемые«универсальные» языки (Паскаль, Си, Модула-2, Ада и другие), а также некоторыеспециализированные (например, язык обработки списочных структур Лисп). Крометого, большое распространение получили языки, связанные с узкими предметнымиобластями, такие, как входные языки пакетов прикладных программ.

Для некоторыхязыков имеется довольно много реализаций. Например, реализаций Паскаля,Модулы-2 или Си для ЭВМ типа IBM PC на рынке десятки.

С другойстороны, постоянно растущая потребность в новых компиляторах связана с бурнымразвитием архитектур ЭВМ. Это развитие идет по различным направлениям.Совершенствуются старые архитектуры как в концептуальном отношении, так и поотдельным, конкретным линиям. Это можно проиллюстрировать на примеремикропроцессора Intel-80X86. Последовательные версии этого микропроцессора8086, 80186, 80286, 80386, 80486, 80586 отличаются не только техническимихарактеристиками, но и, что более важно, новыми возможностями и, значит,изменением (расширением) системы команд. Естественно, это требует новыхкомпиляторов (или модификации старых). То же можно сказать о микропроцессорахMotorola 68010, 68020, 68030, 68040.

В рамкахтрадиционных последовательных машин возникает большое число различныхнаправлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такиеведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин сRISC-архитектурами. Естественно, для каждой новой системы команд требуетсяполный набор новых компиляторов с распространенных языков.

Наконец,бурно развиваются различные параллельные архитектуры. Среди них отметимвекторные, многопроцессорные, с широким командным словом (вариантом которыхявляются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ спараллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и другие), черезрабочие станции (например, IBM RS/6000) и кончая персональными (например, наоснове микропроцессора I-860). Естественно, для каждой из машин создаются новыекомпиляторы для многих языков программирования. Здесь необходимо такжеотметить, что новые архитектуры требуют разработки совершенно новых подходов ксозданию компиляторов, так что наряду с собственно разработкой компиляторовведется и большая научная работа по созданию новых методов трансляции.

/>

На фазелексического анализа входная программа, представляющая собой поток литер,разбивается на лексемы — слова в соответствии с определениями языка. Основнымиформализмами, лежащим в основе реализации лексических анализаторов, являютсяконечные автоматы и регулярные выражения. Лексический анализатор может работатьв двух основных режимах: либо как подпрограмма, вызываемая синтаксическиманализатором для получения очередной лексемы, либо как полный проход,результатом которого является файл лексем.

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

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

Основнаязадача синтаксического анализа — разбор структуры программы. Как правило, подструктурой понимается дерево, соответствующее разбору в контекстно-свободнойграмматике языка. В настоящее время чаще всего используется либо LL(1)-анализ(и его вариант — рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0),SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручномпрограммировании синтаксического анализатора, LR(1) — при использовании системавтоматического построения синтаксических анализаторов.

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

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

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

Затемпрограмма может быть переведена во внутреннее представление. Это делается дляцелей оптимизации и/или удобства генерации кода. Еще одной целью преобразованияпрограммы во внутреннее представление является желание иметь переносимыйкомпилятор. Тогда только последняя фаза (генерация кода) являетсямашинно-зависимой. В качестве внутреннего представления может использоватьсяпрефиксная или постфиксная запись, ориентированный граф, тройки, четверки идругие.

Фазоптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимыеи машинно-независимые, локальные и глобальные. Часть машинно-зависимойоптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытаетсяпринять во внимание структуру всей программы, локальная — только небольших еефрагментов. Глобальная оптимизация основывается на глобальном потоковоманализе, который выполняется на графе программы и представляет по существупреобразование этого графа. При этом могут учитываться такие свойствапрограммы, как межпроцедурный анализ, межмодульный анализ, анализ областейжизни переменных и т.д.

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

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

Основные принципы работы синтаксическогоанализатора

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

В основе синтаксического анализатора лежитраспознаватель текста входной программы на основе грамматики входного языка.Как правило, синтаксические конструкции языков программирования могут бытьописаны с помощью КС-грамматик, реже встречаются языки, которые, могут бытьописаны с помощью регулярных грамматик. Чаще всего регулярные грамматикиприменимы к языкам ассемблера, а языки высокого уровня построены па основесинтаксиса КС-языков. Распознаватель дает ответ на вопрос о том, принадлежитили нет цепочка входных символов заданному языку. Однако, как и в случаелексического анализа, задача синтаксического разбора не ограничишься толькопроверкой принадлежности цепочки заданному языку. Необходимо выполнить всеперечисленные выше задачи, которые должен решить синтаксический анализатор. В такомварианте анализатор уже не является разновидностью МП-автомата — его функцииможно трактовать шире. Синтаксический анализатор должен иметь некий выходнойязык, с помощью которого он передает следующим фазам компиляции не толькоинформацию о найденных и разобранных синтаксических структурах. В таком случаеон уже является преобразователем с магазинной памятью — МП-преобразователем.Синтаксический разбор — это основная часть компилятора на этапе анализа. Безвыполнения синтаксического разбора работа компилятора бессмысленна, в то времякак лексический разбор в принципе является необязательной фазой. Все задачи попроверке синтаксиса входного языка могут быть решены на этапе синтаксическогоразбора. Сканер только позволяет избавить сложный по структуре синтаксическийанализатор от решения примитивных задач по выявлению и запоминанию лексем исходнойпрограммы.

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

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

Дерево разбора.Преобразование дерева разбора в дерево операций

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

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

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

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

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

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

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

Алгоритм преобразования дерева семантическогоразбора и дерево операции можно представить следующим образом.

Шаг 1. Если в дереве больше несодержится узлов, помеченных нетерминальными символами, то выполнение алгоритмазавершено; иначе — перейти к шагу 2

Шаг. 2. Выбрать крайний левыйузел дерена, помеченный нетерминальным символом грамматики и сделать еготекущим. Перейти к шагу 3.

Шаг 3. Если текущий узел имееттолько один нижележащий узел, то текущий узел необходимо удалить из дерена, асвязанный с ним узел присоединить к узлу вышележащего уровня (исключить издерена цепочку) и вернуться к шагу 1; иначе – перейти к шагу 4.

Шаг 4. Если текущий узел имеет нижележащий узел (листдерева), помеченный терминальным символом, который не несет семантическойнагрузки, тогда этот лист нужно удалить из дерева и вернуться к шагу 3; иначе —перейти к шагу 5.

Шаг 5. Если текущий узел имеет один нижележащий узел (листдерева), помеченный терминальным символом, обозначающим знак операции, аостальные узлы помечены как операнды, то лист, помеченный знаком операции, надоудалить из дерева, текущий узел пометить этим знаком операции и перейти к шагу1; иначе — перейти к шагу 6.

Шаг 6. Если среди нижележащихузлов для текущего узла есть узлы, помеченные нетерминальными символами грамматики,то необходимо выбрать крайний левый среди этих узлов, сделать его текущим умоми перейти к шагу 3: иначе — выполнение алгоритма завершено.

Автоматизация построениясинтаксических анализаторов (программа YACC)

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

Автоматизированное построение синтаксическиханализаторов может быть выполнено с помощью программы YACC. Программа YACC (Yet Another Compiler Compiler) предназначена дляпостроения синтаксического анализатора контекстно-свободного языка.Анализируемый язык описывается с помощью грамматики к пиле, близком формеБэкуса— Наура (нормальная форма Бэкуса—Наура — НФБН). Результатом работы YACC является исходный текстпрограммы синтаксического анализатора. Анализатор, который порождается YACC, реализует восходящий LALR(l) распознаватель.

Как ипрограмма LEX, служащая дли автоматизации построении лексических анализаторов,программа YACC тесно связана с историей операционных систем типа UNIX. Эта программа входит впоставку многих версий ОС UNIX или Linux. Поэтому чаще всего результатом работы YACC является исходный текстсинтаксического распознавателя на языке С, Однако существуют версии YACC, выполняющиеся подуправлением ОС, отличных от UNIX, и порождающие исходный код на других языкахпрограммирования (например, Pascal). Принцип работы YACC похож на принцип работы LEX: на вход поступает файл,содержащий описание грамматики заданного КС-языка, а на выходе получаем текстпрограммы синтаксического распознавателя, который, естественно, можно дополнятьи редактировать, как и любую другую программу на заданном языкепрограммирования.

Исходная грамматика для YACC состоит из трех секций,разделенных символом %%, — секции описаний, секции правил, в которой описываетсяграмматика, и секции программ, содержимое которой просто копируется в выходной файл.Например, ниже приведено описание простейшей грамматики для YACC, которая соответствуетграмматике арифметических выражений:

%token a

%start e

%

e: e ‘+‘ m | e ‘-‘ m | m

m: m ‘*’ t | m ‘/’ t | t

a: a | ‘(’ e ‘)’ :

%%

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

Грамматика, записана обычным образом —идентификаторы обозначают терминальные и нетерминальные символы; символьныеконстанты типа '+' и '-' считаются терминальными символами. Символы :, |,;принадлежат к метаязыку YACC и читаются согласно НФБН «есть по определению»,«или» и «конец правила» соответственно.

В отличие от LEX, который всегда способенсостроить лексический распознаватель, если входной файл содержит правильноерегулярное выражение, YACC не всегда может построить распознаватель, дажеесли входной язык задан правильной КС-грамматикой. Ведь заданная грамматикаможет и не принадлежать к классу LALR(l). В этом случае YACC выдаст сообщение об ошибке (наличиинеразрешимого LALR(t)конфликта в грамматике) при построении синтаксического анализатора. Тогдапользователь должен либо преобразовать грамматику, либо задать YACC некоторые дополнительныеправила, которые могут облегчить построение анализатора. Например, YACC позволяет указать правила,явно задающие приоритет операций и порядок их выполнения (слева направо илисправа налево).

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

Назначение семантическогоанализа

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

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

С целью повысить эффективность компиляторов разборцепочек входного языка выполняется в два этапа: первый — синтаксический разборна основе распознавателя одного из известных классов КС-языков; второй —семантический анализ входной цепочки.

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

Таким образом, входными данными для семантическогоанализа служат:

·         таблицаидентификаторов;

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

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

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

В каждом компиляторе обычно присутствуют оба вариантасемантического анализатора.

Этапы семантического анализа

Семантический анализатор выполняет следующиеосновные действия:

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

·         дополнениевнутреннего представления программы в компиляторе операторами и действиями,неявно предусмотренными семантикой входного языка;

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

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

Примерами таких соглашении являются следующиетребования:

·         каждаяметка, на которую есть ссылка, должна один раз присутствовать в программе;

·         каждыйидентификатор должен быть описан один раз, и ни один идентификатор не можетбыть описан более одного раза (с учетом блочной структуры описаний);

·         всеоперанды в выражениях и операциях должны иметь типы, допустимые для данноговыражения или операций;

·         типыпеременных в выражениях должны быть согласованы между собой;

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

Например, если оператор языка Pascal имеет вид

a := b + c:

то с точки зрения синтаксического разбора этобудет абсолютно правильный оператор. Однако, мы не можем сказать, является лиэтот оператор правильным с точки зрения входного языка (Pasca]), пока не проверимсемантические требования для всех входящих в него лексических элементов. Такимиэлементами здесь являются идентификаторы a, b и с. Не зная, что онисобой представляют, мы не можем не только окончательно утверждать правильностьприведенного выше оператора, но и понять ого смысл. Фактически необходимо знатьописание этих идентификаторов.

В том случае, если хотя бы один из них не описан,имеет мест явная ошибка. Если это числовые переменные и константы, то мы имеемдело с оператором сложения, если же это строковые переменные и константы — соператором конкатенации строк. Кроме того, идентификатор а, например, ни в коемслучае не может быть константой — иначе нарушена семантика оператораприсваивания. Также невозможно, чтобы одни из идентификаторов были числами, адругие строками, или, скажем, идентификаторами массивов или структур – такоесочетание  аргументов для оператора сложения недопустимо.

Следует также отметить, что от семантическихсоглашений зависит не только правильность оператора, но и его смысл.Действительно, операции алгебраического сложения и конкатенации строк имеютразличный смысл, хотя и обозначаются в рассмотренном примере одним знаком “+”.Следовательно от семантического анализатора зависит также и код результирующейпрограммы.

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

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

Если вернуться к рассмотренному вышеэлементарному оператору языка Pascal:

a := b + c:

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

Однако не все так очевидно просто, допустим, чтогде-то перед рассмотренным оператором мы имеем описание его операндов в виде:

Var

  а: real;

  b: integer;

  c: double;

из этого описания следует, что а — вещественнаяпеременная языка Pascal, b — целочисленная переменная, с — вещественная переменная с двойнойточностью. Тогда смысл рассмотренного оператора с точки зрения входнойпрограммы существенным образом меняется, поскольку в языке Pascal нельзя напрямуювыполнять операции над операндами различных типов. Существуют правилапреобразования типов, принятые для данного языка. Кто выполняет этипреобразования?

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

С учетом предложенных типов данных, врассмотренном пример будут не две, а четыре операции: преобразованиецелочисленной переменной b в формат вещественных чисел с двойной точностью; сложениедвух вещественных чисел двойной точностью; преобразование результата ввещественное число с одинарной точностью; присвоение результата переменной c. Количество операцийвозросло вдвое, причем добавились нетривиальные функции преобразования типов. Преобразованиетипов — эго только один вариант операций, неявно добавляемых компилятором в кодпрограммы на основе семантических соглашении. Другим примером такого рода операциймогут служить операции вычисления адреса, когда происходит обращение кэлементам сложных структур данных. Существуют и другие варианты такого рода операций.

Таким образом, и здесь действия, выполняемыесемантическим анализатором, существенным образом влияют на порождаемыйкомпиляторомкод результирующей программы.

Проверка элементарных смысловых норм языковпрограммирования, напрямую не снизанных с входным языком, — это сервисная функция,которую предоставляют большинство современных компиляторов. Эта функцияобеспечивает проверку компилятором некоторых соглашений, применимых кбольшинству современных языков программирования, выполнение которых связано со смысломкак всей входной программы и целом, так и отдельных её фрагментов.

Идентификация лексическихединиц языков программирования

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

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

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

Можно дать примерный перечень действийкомпиляторов для идентификации переменных, констант, функций, процедур и другихлексических единиц языка:

·         именалокальных переменных дополняются именами тех блоков  (функций, процедур), вкоторых эти переменные описаны;

·         именавнутренних переменных и функций модулей исходной программы дополняются именемсамих модулей, причем это касается только внутренних имен и не должнопроисходить, если переменная или функция доступна извне модуля;

·         именапроцедур и функций, принадлежащих объектам (классам), вобъектно-ориентированных языках программирования дополняются наименованием типаобъекта (класса), которому они принадлежат;

·         именапроцедур и функций модифицируются в зависимости от типов их формальныхаргументов.

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

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

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


Список использованныхисточников

1.       Серебряков –Языки программирования: infonet.cherepovets.ru/citforum/programming/theory/serebryakov

2.       Свободнаяэнциклопедия – Википедияhttp://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D1%81%D0%BB%D1%8F%D1%82%D0%BE%D1%80

еще рефераты
Еще работы по информатике, программированию