Итак, полный распознаватель для языка программирования можно построить на основе распознавателя КЗ-языка. Однако известно, что такой распознаватель имеет экспоненциальную зависимость требуемых для выполнения разбора цепочки вычислительных ресурсов от длины входной цепочки. Компилятор, построенный на основе такого распознавателя, будет неэффективным с точки зрения либо скорости работы, либо объема необходимой памяти. Поэтому такие компиляторы практически не используются, а все реально существующие компиляторы на этапе разбора входных цепочек проверяют только синтаксические конструкции входного языка, не учитывая его семантику.
С целью повысить эффективность компиляторов разбор цепочек входного языка выполняется в два этапа: первый — синтаксический разбор на основе распознавателя одного из известных классов КС-языков; второй — семантический анализ входной цепочки.
Для проверки семантической правильности входной программы необходимо иметь всю информацию о найденных лексических единицах языка. Эта информация помещается в таблицу лексем на основе конструкций, найденных синтаксическим распознавателем. Примерами таких конструкциями являются блоки описания констант и идентификаторов (если они предусмотрены семантикой языка) пли операторы, где тот или иной идентификатор встречается впервые (если описание происходит по факту первого использования). Поэтому полный семантический анализ входной программы может быть произведен только после полного завершения её синтаксического разбора.
Таким образом, входными данными для семантического анализа служат:
· таблица идентификаторов;
· результаты разбора синтаксических конструкций входного языка.
Результаты выполнения синтаксического разбора могут быть представлены в одной из форм внутреннего представления программы в компиляторе. Как правило, на этапе семантического анализа используются различные варианты деревьев синтаксического разбора, поскольку семантический анализатор интересует прежде всего структура входной программы.
Семантический анализ обычно выполняется на двух этапах компиляции: на этапе синтаксического разбора и в начале этапа подготовки к генерации кода. В первом случае всякий раз по завершении распознавания определенной синтаксической конструкции входного языка выполняется её семантическая проверка на основе имеющихся в таблице идентификаторов данных (такими конструкциями, как правило, являются процедуры, функции и блоки операторов входного языка). Во втором случае, после завершения всей фазы синтаксического разбора, выполняется полный семантическим анализ программы на основании данных в таблице идентификаторов (сюда попадает, например, поиск неописанных идентификаторов). Иногда семантический анализ выделяют в отдельный этап (фазу) компиляции.
В каждом компиляторе обычно присутствуют оба варианта семантического анализатора.
Семантический анализатор выполняет следующие основные действия:
· проверка соблюдения во входной программе семантических соглашений входного языка;
· дополнение внутреннего представления программы в компиляторе операторами и действиями, неявно предусмотренными семантикой входного языка;
· проверка элементарных семантических (смысловых) норм языков программирования, напрямую не связанных с входным языком.
Проверка соблюдения во входной программе семантических соглашений входного языка заключается в сопоставлении входных цепочек программы с требованиями семантики входного языка программирования. Каждый язык программирования имеет четко заданные и специфицированные семантические соглашения, которые не могут быть проверены на этапе синтаксического разбора. Именно их в первую очередь проверяет семантический анализатор.
Примерами таких соглашении являются следующие требования:
· каждая метка, на которую есть ссылка, должна один раз присутствовать в программе;
· каждый идентификатор должен быть описан один раз, и ни один идентификатор не может быть описан более одного раза (с учетом блочной структуры описаний);
· все операнды в выражениях и операциях должны иметь типы, допустимые для данного выражения или операций;
· типы переменных в выражениях должны быть согласованы между собой;
· при вызове процедур и функций число и типы фактических параметров должны быть согласованы с числом и типами формальных параметров.
Например, если оператор языка Pascal имеет вид
a := b + c:
то с точки зрения синтаксического разбора это будет абсолютно правильный оператор. Однако, мы не можем сказать, является ли этот оператор правильным с точки зрения входного языка (Pasca]), пока не проверим семантические требования для всех входящих в него лексических элементов. Такими элементами здесь являются идентификаторы a, b и с. Не зная, что они собой представляют, мы не можем не только окончательно утверждать правильность приведенного выше оператора, но и понять ого смысл. Фактически необходимо знать описание этих идентификаторов.
В том случае, если хотя бы один из них не описан, имеет мест явная ошибка. Если это числовые переменные и константы, то мы имеем дело с оператором сложения, если же это строковые переменные и константы — с оператором конкатенации строк. Кроме того, идентификатор а, например, ни в коем случае не может быть константой — иначе нарушена семантика оператора присваивания. Также невозможно, чтобы одни из идентификаторов были числами, а другие строками, или, скажем, идентификаторами массивов или структур – такое сочетание аргументов для оператора сложения недопустимо.
Следует также отметить, что от семантических соглашений зависит не только правильность оператора, но и его смысл. Действительно, операции алгебраического сложения и конкатенации строк имеют различный смысл, хотя и обозначаются в рассмотренном примере одним знаком “+”. Следовательно от семантического анализатора зависит также и код результирующей программы.
Если какое-либо из семантических требований входного языка не выполняется, то компилятор выдает сообщение об ошибке и процесс компиляции на этом, как правило, прекращается.
Дополнение внутреннего представления программы операторами и действиями, неявно предусмотренными семантикой входного языка, связано с преобразованием типов операндов в выражениях и при передаче параметров в процедуры и функции.
Если вернуться к рассмотренному выше элементарному оператору языка Pascal:
то можно отметить, что здесь выполняются две операции: одна операция сложения (или конкатенации, в зависимости от типов операндов) и одна операция присвоения результата. Соответствующим образом должен быть порожден и код результирующей программы.
Однако не все так очевидно просто, допустим, что где-то перед рассмотренным оператором мы имеем описание его операндов в виде:
Var
а : real;
b : integer;
c : double;
из этого описания следует, что а — вещественная переменная языка Pascal, b — целочисленная переменная, с — вещественная переменная с двойной точностью. Тогда смысл рассмотренного оператора с точки зрения входной программы существенным образом меняется, поскольку в языке Pascal нельзя напрямую выполнять операции над операндами различных типов. Существуют правила преобразования типов, принятые для данного языка. Кто выполняет эти преобразования?
Это может сделать разработчик программы — но тогда преобразования типов в явном виде будут присутствовать в тексте входной программы (в рассмотренном примере это не так). В другом случае это делает код, порождаемый компилятором, когда преобразования типов в явном виде в тексте программы не присутствуют, но неявно предусмотрены семантическими соглашениями языка. Для этого в составе библиотек функции, доступных компилятору, должны быть функции преобразования типов Вызовы этих функции как раз и будут встроены в текст результирующей программы для удовлетворения семантических соглашении о преобразованиях типов во входном языке, хотя в тексте программы в явном виде они не присутствуют. Чтобы это произошло, эти функции должны быть встроены и во внутреннее представление программы в компиляторе. За это также отвечает семантический анализатор.
С учетом предложенных типов данных, в рассмотренном пример будут не две, а четыре операции: преобразование целочисленной переменной b в формат вещественных чисел с двойной точностью; сложение двух вещественных чисел двойной точностью; преобразование результата в вещественное число с одинарной точностью; присвоение результата переменной c. Количество операций возросло вдвое, причем добавились нетривиальные функции преобразования типов. Преобразование типов — эго только один вариант операций, неявно добавляемых компилятором в код программы на основе семантических соглашении. Другим примером такого рода операций могут служить операции вычисления адреса, когда происходит обращение к элементам сложных структур данных. Существуют и другие варианты такого рода операций.
Таким образом, и здесь действия, выполняемые семантическим анализатором, существенным образом влияют на порождаемый компилятором код результирующей программы.
Проверка элементарных смысловых норм языков программирования, напрямую не снизанных с входным языком, — это сервисная функция, которую предоставляют большинство современных компиляторов. Эта функция обеспечивает проверку компилятором некоторых соглашений, применимых к большинству современных языков программирования, выполнение которых связано со смыслом как всей входной программы и целом, так и отдельных её фрагментов.
Идентификация переменных, типов, процедур, функций и других лексических единиц языков программирования – это установление однозначного соответствия между данными объектами и их именами в тексте исходной программы. Идентификация лексических единиц языка чаще всего выполняется на этапе семантического анализа.
Как правило, большинство языков программирования требуют, чтобы в исходной программе имена лексических единиц не совпадали как между собой, так и с ключевыми словами синтаксических конструкций языка. Однако, чаще всего этого бывает недостаточно, чтобы установить однозначное соотношение между лексическими единицами и их именами, поскольку существуют дополнительные смысловые ограничения, накладываемые языком на употребление эти имен.
Например локальные переменные в большинстве языков программирования имею область видимости, которая ограничивает употребление имени переменной рамками того блока исходной программы, где эта переменная описана. Это значит, что с одной стороны, такая переменная не может быть использована вне пределов своей области видимости. С другой стороны, имя переменной может быть не уникальным, поскольку в двух различных областях видимости допускается существование двух различных переменных с одинаковыми именами. Полный перечень таких ограничений зависит от семантики конкретного языка программирования. Все они четко заданы в описании языка и не могут допускать неоднозначности в толковании, но не могут быть полностью определены на этапе лексического разбора, а потому требуют от компилятора дополнительных действий на этапах синтаксического разбора и семантического анализа. Общая направленность этих действий такова, чтобы дать каждой лексической единице языка уникальное имя в пределах всей исходной программы и потом использовать это имя при синтезе результирующей программы.
Можно дать примерный перечень действий компиляторов для идентификации переменных, констант, функций, процедур и других лексических единиц языка:
· имена локальных переменных дополняются именами тех блоков (функций, процедур), в которых эти переменные описаны;
· имена внутренних переменных и функций модулей исходной программы дополняются именем самих модулей, причем это касается только внутренних имен и не должно происходить, если переменная или функция доступна извне модуля;
· имена процедур и функций, принадлежащих объектам (классам), в объектно-ориентированных языках программирования дополняются наименованием типа объекта (класса), которому они принадлежат;
· имена процедур и функций модифицируются в зависимости от типов их формальных аргументов.
Конечно, это далеко не полный перечень возможных действий компилятора, каждая реализация компилятора может предполагать свои набор действий. То, какие из них будут использоваться и как они будут реализованы на практике, зависит от языка исходной программы и разработчиков компилятора.
Как правило, уникальные имени, которые компилятор присваивает лексическим единицам языка, используются только во внутреннем представлении исходной программы компилятором, и человек, создавший исходную программу, не сталкивается с ними. Но они могут потребоваться пользователю в некоторых случаях – например, при отладке программы, при порождении текста результирующей программы на языке ассемблера или при использовании библиотеки, созданной версией компилятора для одного языка программирования и другом языке (или даже просто в другой версии компилятора). Тогда пользователь должен знать, по каким правилам компилятор порождает уникальные имена для лексических единиц исходной программы.
Во многих современных компиляторах (и обрабатываемых ими входных языках) предусмотрены специальные настройки и ключевые слова, которые позволяют отключить процесс порождения компилятором уникальных имен для лексических единиц языка. Эти слова учтены в специальных синтаксических конструкциях языка (как прилило, это конструкции, содержащие слона export пли external). Если пользователь использует эти средства, то компилятор не применяет механизм порождения уникальных имен для указанных лексических единиц. В этом случае разработчик программы сам отвечает за уникальность имени данной лексической единицы в пределах всей исходной программы или даже в пределах всего проекта, Если требование уникальности не будет выполняться, могут возникнуть синтаксические или семантические ошибки па стадии компиляции либо же другие ошибки на более поздних этапах разработки программного обеспечения. Поскольку наиболее широко используемыми лексическими единицами в различных языках программирования являются, как правило, имена процедур и функций, то этот вопрос, прежде всего, касается именно их.
1. Серебряков – Языки программирования: http://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
Страницы: 1, 2, 3
