Системное программное обеспечение

конца. Тем не менее по-прежнему преобладают компьютеры традиционной, «неймановской» архитектуры, которые умеют понимать только машинные команды, поэтому вопрос о создании компиляторов продолжает быть актуальным.

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

Особенности построения и функционирования компиляторов Как уже было сказано ранее, для задания языка программирования

необходимо решить три задачи:

1.определить множество допустимых символов языка;

2.определить множество правильных программ языка;

3.задать смысл для каждой правильной программы.

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

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

2.использовать для проверки смысла некоторую «идеальную машину», которая предназначена для выполнения программ, написанных на данном языке.

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

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

операции — слишком трудоемкая задача. Именно таким переводом занимаются компиляторы для языков программирования.

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

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

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

Например, предложение в программе на языке Pascal вида: i: =0; while i=0 do i =0, может быть легко оценено любой машиной как бессмысленное. Но если в задачу входит обеспечение взаимодействия с другой параллельно выполняемой программой или, например, просто проверка надежности и долговечности процессора или какой-то ячейки памяти, то это же предложение покажется уже не лишенным смысла.

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

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

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

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

Некоторые успехи в процессе проверки осмысленности программ достигнуты в рамках систем автоматизации разработки программного обеспечения (CASE-системы). Их подход основан на проектировании сверху вниз — от описания задачи на языке, понятном человеку, до перевода ее в операторы языка программирования. Но такой подход выходит за рамки возможностей трансляторов, поэтому здесь рассматриваться не будет.

2.Компиляторы в составе систем программирования

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

Логичным завершением этого процесса стало создание систем программирования — программных комплексов, объединяющих в себе кроме непосредственно компиляторов множество связанных с ними компонентов программного обеспечения. Появившись, системы программирования быстро завоевали рынок и ныне в массе своей преобладают на нем. Фактически, в настоящее время обособленные компиляторы — это редкость среди современных программных средств. О том, что представляют собой и как организованы современные системы программирования см. в главе 6 «Современные системы программирования».

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

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

Первыми компиляторами были компиляторы с мнемокодов. Их потомки

— современные компиляторы с языков ассемблера — существуют практически для всех известных вычислительных систем. Они предельно жестко ориентированы на архитектуру. Затем появились компиляторы с таких языков, как FORTRAN, ALGOL-68, PL/1. Они были ориентированы на большие ЭВМ с пакетной обработкой задач. Из вышеперечисленных только FORTRAN, пожалуй, продолжает использоваться по сей день, поскольку имеет огромное количество библиотек различного назначения [5]. Многие языки, родившись, так и не получили широкого распространения — ADA, Modula, Simula известны лишь узкому кругу специалистов. В то же время на рынке программных систем доминируют системы программирования и компиляторы для языков, которым не прочили светлого будущего. В первую очередь, сейчас это С и C++. Первый из них родился вместе с операционными системами типа UNIX, вместе с ними завоевал свое «место под солнцем», а затем перешел под ОС других типов. Второй удачно воплотил в себе пример реализации идей объектно-ориентированного программирования на хорошо зарекомендовавшей себя практической базе1. Ещё можно упомянуть довольно распространенный Pascal, который неожиданно для многих вышел за рамки чисто учебного языка для университетской среды.

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

Литература

Основная:

1.Молчанов А.Ю. Системное программное обеспечение. Учебник для вузов.

— СПб.: Питер, 2003. — 396 с.

2.Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум.- СПб.: Питер, 2005.- 284 с.

3.Юров В.И. Assembler. Учебник для вузов. 2-е издание - СПб.: Питер.- 2004.- 637 с.

4.Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование: Основы построения трансляторов + FD.- М.: КОРОНА принт.- 2004.- 255 с.

5.Фельдман Ф.К. Системное программирование на персональном компьютере.- 2004.- 512

6.Ахо А.,Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.

7.Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. —

СПб.: Питер, 2002. — 734 с.

8.Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002. — 544

Дополнительная:

1.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2001. – Ч. 1. – 96 с.

2.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2002. – Ч. 2. – 96 с.

3.Ф.Льюис, Д. Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979.

4.Л. Бек. Введение в системное программирование. М.,Мир, 1988.

5.В.Е.Котов, В.К.Сабельфельд. Теория схем программ. -М.: Наука, 1978

6.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И.Варшавского. -М.:Наука.

7.Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Наука. 1984.

8.Минский М. Вычисления и автоматы. - М.: Мир.- 1971.

9.Котов В.Е. Сети Петри. - М.: Наука. - 1984.-

10.Ахо А.,Хопкрофт Дж., Ульман Дж.Построение и анализ вычислительных алгоритмов. - М.: Мир. -1979.

11.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. –

М.: Мир, 1984. – 264 с.

Лекция 13 Таблицы идентификаторов.

План

1.Идентификация

1.Идентификация

Идентификация идентификаторов - одна из задач, решение которой необходимо для проверки правильности использования типов.

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

Каждое вхождение идентификатора в программу является либо определяющим, либо использующим. Под определяющим вхождением идентификатора понимается его вхождение в описание, например, int i. Все остальные вхождения являются использующими, например, i = 5 или i+13.

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

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

•создавать узел в синтаксическом дереве для конструкции "описание идентификатора" и запоминать информацию о типе идентификатора в этом узле;

•создать таблицу идентификаторов (IdTab) и в ней запоминать информацию о типе идентификатора. Почему нам может потребоваться новая

таблица? Понятно, что если транслируемая программа может иметь блочную структуру, и/или язык допускает создание и использование перегруженных 1)

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

На самом деле, между перечисленными способами много общего и мы остановимся на обсуждении второго способа.

Структура таблиц

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

struct IdItem
{
ReprInd toRepr;		/* ссылка в ReprTab на представление */
TypeInd toMode;		/* тип идентификатора */
IdInd toId;		/* ссылка на элемент таблицы идентификаторов
}	с таким же значением поля toRepr */
Расширим структуру таблицы внешних представлений следующим
образом:
struct ReprItem
{
HashInd toHash;		/* значение hash-функции для лексемы */
unsigned	short LexClass;		/* лексический класс */
unsigned	short LexMark;		/* лексическая марка */
IdInd toId;		/*ссылка в IdTab на доступное определение
			идентификатора */

}

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

•первая часть алгоритма обрабатывает определяющие вхождения идентификаторов

•вторая часть алгоритма обрабатывает использующие вхождения идентификаторов

Обработка определяющего вхождения идентификатора

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

•Создаем новый элемент таблицы идентификаторов

•В поле toRepr таблицы идентификаторов помещаем rpr .

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

таблицы мы попадаем по прямой ссылке из таблицы представлений.

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

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

Пример

Рассмотрим программу следующей структуры: {int n; …; n++; .. {float n; … n = 3.14; … } …n--; … }

При входе во внешний блок идентификатор n будет занесен в таблицу представлений, кроме того, будет создан элемент таблицы идентификаторов.

После входа во внутренний блок будет добавлен еще один элемент в таблицу идентификаторов, соответствующий идентификатору n .

После выхода из внутреннего блока таблицы будут выглядеть следующим образом.

Конструирование типов Типы языков программирования конструируются из примитивных типов,

таких как boolean , char , integer , real и void , с помощью конструкторов типов. К примитивным типам естественно отнести и тип, который не используется при

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

1.Массивы. Если T - тип, то array (I, T) - тип, обозначающий тип массива с элементами типа T и индексным множеством I . Например, описание языка Pascal:

2.var A: array [1..10] of integer;

связывает выражение над типами array (1..10, T) с A .

3.Произведение. Если T1 и T2 - типы, то их декартово произведение T1

*T2 также является типом.

4.Структуры. Конструктор struct применяется к кортежу пар ( имя поля, тип поля). Например, фрагмент программы на языке Pascal:

5.type row = record

6.address: integer;

7.lexeme: array [1..15] of char

8.end;

9.var table: array [1..13] of row;

Тип row строится из примитивных типов следующим образом: struct ((address*integer) (lexeme*array (1..15, char))).

10.Указатели. Если T - тип, то и pointer (T) - тип, определяющий " указатель на объект типа T". Например, описание языка Pascal:

11.var p: ^row;

определяет переменную p , имеющую тип pointer (row) .

12.Функции. Если T1, T2 - типы, то proc (T1, T2) - тип, определяющий процедуру, типы формальных параметров которой есть T1, а тип результата - T2. Например, функция mod , вычисляющая остаток, имеет тип proc (int *int, int)

,а функция, определенная как

13.function f (a, b: char) : ^integer;

имеет тип proc (char char, pointer (integer)) .

Преобразование типов

Рассмотрим формулу x+i , где x - вещественная переменная, i - целая переменная. Так как представления целых и вещественных чисел в памяти компьютера различны, различные команды используются для целых и вещественных значений, и обычно нет команд, операндами которых являются значения смешанных типов, то компилятор должен преобразовать один из операндов к типу другого.

Описания языков определяют, какие преобразования возможны и необходимы. Если целое значение присваивается вещественной переменной или наоборот, выполняется преобразование к типу получателя присваивания. Хотя преобразование вещественного значения в целое, вообще говоря, некорректно. В формуле обычно выполняется преобразование целого операнда к вещественному типу. Фаза контроля типов вставляет эти операции преобразования в промежуточное представление исходной программы. Например, для формулы x+i после фазы контроля типов будет получено следующее дерево: