Эта книга является логическим продолжением и дополнением учебника «Системное программное обеспечение»,^[1] вышедшего в свет в 2003 году. Главной целевой аудиторией книги «Системное программное обеспечение» были студенты технических вузов, обучающиеся по специальности «Вычислительные машины, комплексы, системы и сети» и родственным с ней направлениям, поэтому материал книги был подобран исходя из требований стандарта этой специальности для курса «Системное программное обеспечение». Программа этого курса предусматривает практические занятия в виде лабораторных работ, а также выполнение курсовой работы по итогам курса. Поэтому автор посчитал разумным добавить к сухим теоретическим выкладкам необходимый живой практический материал, проиллюстрированный конкретными примерами реализации.
   Некоторая часть материала, касающаяся базовых теоретических основ, в этой книге перекликается с уже опубликованным материалом книги «Системное программное обеспечение». Но автор посчитал необходимым кратко привести здесь только те теоретические выкладки, без которых невозможно построить логическое изложение материала. Подразумевается, что читатели уже знакомы с основами курса «Системное программное обеспечение», поэтому в соответствующих местах всегда даются ссылки на литературу – в основном на базовые книги курса [1–3, 7], а также на книги по курсу «Операционные системы» [3, 5, 6]. Поскольку оба курса («Системное программное обеспечение» и «Операционные системы») тесно взаимосвязаны, читателям этой книги необходимо знать их основы, чтобы понять и практически применять изложенный в книге материал (совсем недавно, в старой редакции образовательного стандарта, оба этих курса составляли единое целое [3]).
   Книга может оказаться полезной не только студентам, но и специалистам, чья деятельность напрямую связана с созданием средств обработки текстов и структурированных текстовых команд. Некоторые практические приемы, описанные в книге и проиллюстрированные в примерах программного кода, будут полезны не только тем, кто создает или изучает трансляторы, компиляторы или любые другие распознаватели для формальных языков, но и вообще всем разработчикам программного обеспечения.
   Для понимания практических примеров необходимо знание языка программирования Object Pascal и хотя бы общее представление о системе программирования Delphi, а также знание языка ассемблера процессоров типа Intel 80x86. В ряде случаев для сравнения и понимания примеров синтаксических конструкций рекомендуется знать язык программирования C. Соответствующие сведения можно почерпнуть в дополнительной литературе, приведенной в конце книги [13, 23–25, 28, 31, 32, 37, 39, 41, 44].
   Все практические примеры созданы автором в системе программирования Delphi 5 на языке Object Pascal с использованием примитивных классов из библиотеки VCL. Но автор приложил все усилия, чтобы они не были привязаны ни к версии системы программирования, ни к особенностям исходного языка. Поэтому желающие без проблем могут перенести их под любую версию Delphi, а при необходимости переписать, например на C++, для чего требуются только самые элементарные знания языка.
   Программный код, приводимый в примерах, ни в коей мере не претендует на высокую эффективность. При его создании автор в первую очередь думал об иллюстративности кода, о его способности наглядно отражать те теоретические посылки, которые есть в книге. И тем не менее использованные методы и приемы, по мнению автора, могут служить не только примером реализации элементов компилятора, но и иллюстрацией хорошего стиля программирования – но пусть об этом лучше судят сами читатели. Возможности дальнейшего совершенствования кода чаще всего специально заложены в примерах, а в тексте книги указано, в чем эти возможности заключаются. При проведении занятий преподаватели могут использовать эти моменты для дополнительных заданий по теме книги.
   Структура книги проста: она содержит описания четырех лабораторных работ и одной курсовой работы. Каждая лабораторная работа снабжена краткими теоретическими выкладками, имеет перечень вариантов заданий, рекомендации по выполнению и оформлению результатов работы, а также пример выполнения. В каждой лабораторной работе автор обращает внимание на основные сложности, связанные с ее выполнением, а также на возможные типичные ошибки и недочеты, дает рекомендации по возможностям программной реализации, отличным от кода, приводимого в примерах.
   Все лабораторные работы связаны с реализацией составных частей компилятора. Первая работа посвящена организации таблиц идентификаторов, вторая – созданию лексического анализатора, третья – созданию синтаксического анализатора и четвертая – генерации и оптимизации результирующего кода. Работы имеют разную сложность выполнения: по мнению автора, первые две работы элементарно просты, третья – более сложная и, наконец, четвертая имеет максимальную сложность. Это следует учитывать преподавателям при планировании выполнения работ и обучающимся при их выполнении. Кроме того, все четыре работы взаимосвязаны – каждая последующая работа использует материал предыдущей, поэтому для обучающихся желательно иметь один номер варианта на выполнение всех работ (взаимосвязь работ и преимущества такого подхода наглядно проиллюстрированы в примерах их выполнения).
   Курсовая работа предусматривает создание простейшего компилятора для заданного входного языка. Она основана на том же теоретическом материале, что и лабораторные работы, но требует комплексного подхода к освоению материала и к выполнению задания. Кроме того, в курсовой работе обучающимся предоставляется большая самостоятельность в выборе методов и приемов реализации задания, чем в лабораторных работах.
   Практическая направленность данной книги требует использования значительного объема программного кода для реализации и иллюстрации выполняемых примеров в лабораторных работах и курсовой работе. К сожалению, из-за ограничений по объему нет возможности включить весь программный код в книгу. Поэтому автор счел необходимым привести в книге только программный код, связанный с курсовой работой (часть которого используется также и в лабораторных работах). Остальной программный код можно найти на веб-сайте издательства «Питер».
   Приводимый в книге практический материал не претендует на полноту охвата всего курса «Системное программное обеспечение». Автор считает необходимым дополнить его работами по программированию параллельных взаимодействующих процессов [3, 5], а также методами разработки программного обеспечения в распределенных системах (по технологиям построения систем «клиент-сервер» и многоуровневой архитектуре [7]). Автор надеется, что ему удастся в ближайшее время подготовить соответствующий материал.

   При выполнении семантического анализа, генерации кода и оптимизации результирующей программы компилятор должен оперировать характеристиками основных элементов исходной программы – переменных, констант, функций и других лексических единиц входного языка. Эти характеристики могут быть получены компилятором на этапе синтаксического анализа входной программы (чаще всего при анализе структуры блоков описаний переменных и констант), а также дополнены на этапе подготовки к генерации кода (например при распределении памяти).
   Набор характеристик, соответствующий каждому элементу исходной программы, зависит от типа этого элемента, от его смысла (семантики) и, соответственно, от той роли, которую он исполняет в исходной и результирующей программах. В каждом конкретном случае этот набор характеристик может быть свой в зависимости от синтаксиса и семантики входного языка, от архитектуры целевой вычислительной системы и от структуры компилятора. Но есть типовые характеристики, которые чаще всего присущи тем или иным элементам исходной программы. Например для переменной – это ее тип и адрес ячейки памяти, для константы – ее значение, для функции – количество и типы формальных аргументов, тип возвращаемого результата, адрес вызова кода функции. Более подробную информацию о характеристиках элементов исходной программы, их анализе и использовании можно найти в [1, 3, 7].
   Главной характеристикой любого элемента исходной программы является его имя. Именно с именами переменных, констант, функций и других элементов входного языка оперирует разработчик программы – поэтому и компилятор должен уметь анализировать эти элементы по их именам.
   Имя каждого элемента должно быть уникальным. Многие современные языки программирования допускают совпадения (неуникальность) имен переменных и функций в зависимости от их области видимости и других условий исходной программы. В этом случае уникальность имен должен обеспечивать сам компилятор – о том, как решается эта проблема, можно узнать в [1–3, 7], здесь же будем считать, что имена элементов исходной программы всегда являются уникальными.
   Таким образом, задача компилятора заключается в том, чтобы хранить некоторую информацию, связанную с каждым элементом исходной программы, и иметь доступ к этой информации по имени элемента. Для решения этой задачи компилятор организует специальные хранилища данных, называемые таблицами идентификаторов, или таблицами символов. Таблица идентификаторов состоит из набора полей данных (записей), каждое из которых может соответствовать одному элементу исходной программы. Запись содержит всю необходимую компилятору информацию о данном элементе и может пополняться по мере работы компилятора. Количество записей зависит от способа организации таблицы идентификаторов, но в любом случае их не может быть меньше, чем элементов в исходной программе. В принципе, компилятор может работать не с одной, а с несколькими таблицами идентификаторов – их количество и структура зависят от реализации компилятора [1, 2].

   Компилятор пополняет записи в таблице идентификаторов по мере анализа исходной программы и обнаружения в ней новых элементов, требующих размещения в таблице. Поиск информации в таблице выполняется всякий раз, когда компилятору необходимы сведения о том или ином элементе программы. Причем следует заметить, что поиск элемента в таблице будет выполняться компилятором существенно чаще, чем помещение в нее новых элементов. Так происходит потому, что описания новых элементов в исходной программе, как правило, встречаются гораздо реже, чем эти элементы используются. Кроме того, каждому добавлению элемента в таблицу идентификаторов в любом случае будет предшествовать операция поиска – чтобы убедиться, что такого элемента в таблице нет.
   На каждую операцию поиска элемента в таблице компилятор будет затрачивать время, и поскольку количество элементов в исходной программе велико (от единиц до сотен тысяч в зависимости от объема программы), это время будет существенно влиять на общее время компиляции. Поэтому таблицы идентификаторов должны быть организованы таким образом, чтобы компилятор имел возможность максимально быстро выполнять поиск нужной ему записи таблицы по имени элемента, с которым связана эта запись.
   Можно выделить следующие способы организации таблиц идентификаторов:
   • простые и упорядоченные списки;
   • бинарное дерево;
   • хэш-адресация с рехэшированием;
   • хэш-адресация по методу цепочек;
   • комбинация хэш-адресации со списком или бинарным деревом.
   Далее будет дано краткое описание всех вышеперечисленных способов организации таблиц идентификаторов. Более подробную информацию можно найти в [3, 7].

   В простейшем случае таблица идентификаторов представляет собой линейный неупорядоченный список, или массив, каждая ячейка которого содержит данные о соответствующем элементе таблицы. Размещение новых элементов в такой таблице выполняется путем записи информации в очередную ячейку массива или списка по мере обнаружения новых элементов в исходной программе.
   Поиск нужного элемента в таблице будет в этом случае выполняться путем последовательного перебора всех элементов и сравнения их имени с именем искомого элемента, пока не будет найден элемент с таким же именем. Тогда если за единицу времени принять время, затрачиваемое компилятором на сравнение двух строк (в современных вычислительных системах такое сравнение чаще всего выполняется одной командой), то для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений.
   Время, требуемое на добавление нового элемента в таблицу (T_д), не зависит от числа элементов в таблице (N). Но если N велико, то поиск потребует значительных затрат времени. Время поиска (T_п) в такой таблице можно оценить как T_п = O(N). Поскольку именно поиск в таблице идентификаторов является наиболее часто выполняемой компилятором операцией, такой способ организации таблиц идентификаторов является неэффективным. Он применим только для самых простых компиляторов, работающих с небольшими программами.
   Поиск может быть выполнен более эффективно, если элементы таблицы отсортированы (упорядочены) естественным образом. Поскольку поиск осуществляется по имени, наиболее естественным решением будет расположить элементы таблицы в прямом или обратном алфавитном порядке. Эффективным методом поиска в упорядоченном списке из N элементов является бинарный, или логарифмический, поиск.
   Алгоритм логарифмического поиска заключается в следующем: искомый символ сравнивается с элементом (N + 1)/2 в середине таблицы; если этот элемент не является искомым, то мы должны просмотреть только блок элементов, пронумерованных от 1 до (N + 1)/2 – 1, или блок элементов от (N + 1)/2 + 1 до N в зависимости от того, меньше или больше искомый элемент того, с которым его сравнили. Затем процесс повторяется над нужным блоком в два раза меньшего размера. Так продолжается до тех пор, пока либо искомый элемент не будет найден, либо алгоритм не дойдет до очередного блока, содержащего один или два элемента (с которыми можно выполнить прямое сравнение искомого элемента).
   Так как на каждом шаге число элементов, которые могут содержать искомый элемент, сокращается в два раза, максимальное число сравнений равно 1 + log₂ N. Тогда время поиска элемента в таблице идентификаторов можно оценить как T_п = O(log₂ N). Для сравнения: при N = 128 бинарный поиск требует самое большее 8 сравнений, а поиск в неупорядоченной таблице – в среднем 64 сравнения. Метод называют «бинарным поиском», поскольку на каждом шаге объем рассматриваемой информации сокращается в два раза, а «логарифмическим» – поскольку время, затрачиваемое на поиск нужного элемента в массиве, имеет логарифмическую зависимость от общего количества элементов в нем.
   Недостатком логарифмического поиска является требование упорядочивания таблицы идентификаторов. Так как массив информации, в котором выполняется поиск, должен быть упорядочен, время его заполнения уже будет зависеть от числа элементов в массиве. Таблица идентификаторов зачастую просматривается компилятором еще до того, как она заполнена, поэтому требуется, чтобы условие упорядоченности выполнялось на всех этапах обращения к ней. Следовательно, для построения такой таблицы можно пользоваться только алгоритмом прямого упорядоченного включения элементов.
   Если пользоваться стандартными алгоритмами, применяемыми для организации упорядоченных массивов данных, то среднее время, необходимое на помещение всех элементов в таблицу, можно оценить следующим образом:
   Здесь k – некоторый коэффициент, отражающий соотношение между временами, затрачиваемыми компьютером на выполнение операции сравнения и операции переноса данных.
   При организации логарифмического поиска в таблице идентификаторов обеспечивается существенное сокращение времени поиска нужного элемента за счет увеличения времени на помещение нового элемента в таблицу. Поскольку добавление новых элементов в таблицу идентификаторов происходит существенно реже, чем обращение к ним, этот метод следует признать более эффективным, чем метод организации неупорядоченной таблицы. Однако в реальных компиляторах этот метод непосредственно также не используется, поскольку существуют более эффективные методы.

   Можно сократить время поиска искомого элемента в таблице идентификаторов, не увеличивая значительно время, необходимое на ее заполнение. Для этого надо отказаться от организации таблицы в виде непрерывного массива данных.
   Существует метод построения таблиц, при котором таблица имеет форму бинарного дерева. Каждый узел дерева представляет собой элемент таблицы, причем корневым узлом становится первый элемент, встреченный компилятором при заполнении таблицы. Дерево называется бинарным, так как каждая вершина в нем может иметь не более двух ветвей. Для определенности будем называть две ветви «правая» и «левая».
   Рассмотрим алгоритм заполнения бинарного дерева. Будем считать, что алгоритм работает с потоком входных данных, содержащим идентификаторы. Первый идентификатор, как уже было сказано, помещается в вершину дерева. Все дальнейшие идентификаторы попадают в дерево по следующему алгоритму:
   1. Выбрать очередной идентификатор из входного потока данных. Если очередного идентификатора нет, то построение дерева закончено.
   2. Сделать текущим узлом дерева корневую вершину.
   3. Сравнить имя очередного идентификатора с именем идентификатора, содержащегося в текущем узле дерева.
   4. Если имя очередного идентификатора меньше, то перейти к шагу 5, если равно – прекратить выполнение алгоритма (двух одинаковых идентификаторов быть не должно!), иначе – перейти к шагу 7.
   5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе – перейти к шагу 6.
   6. Создать новую вершину, поместить в нее информацию об очередном идентификаторе, сделать эту новую вершину левой вершиной текущего узла и вернуться к шагу 1.
   7. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе – перейти к шагу 8.
   8. Создать новую вершину, поместить в нее информацию об очередном идентификаторе, сделать эту новую вершину правой вершиной текущего узла и вернуться к шагу 1.
   Рассмотрим в качестве примера последовательность идентификаторов Ga, D1, М22, Е, А12, ВС, F. На рис. 1.1 проиллюстрирован весь процесс построения бинарного дерева для этой последовательности идентификаторов.
   Рис. 1.1. Заполнение бинарного дерева для последовательности идентификаторов.
 
   Поиск элемента в дереве выполняется по алгоритму, схожему с алгоритмом заполнения дерева:
   1. Сделать текущим узлом дерева корневую вершину.
   2. Сравнить имя искомого идентификатора с именем идентификатора, содержащимся в текущем узле дерева.
   3. Если имена совпадают, то искомый идентификатор найден, алгоритм завершается, иначе надо перейти к шагу 4.
   4. Если имя очередного идентификатора меньше, то перейти к шагу 5, иначе – перейти к шагу 6.
   5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе – искомый идентификатор не найден, алгоритм завершается.
   6. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе – искомый идентификатор не найден, алгоритм завершается.
   Для данного метода число требуемых сравнений и форма получившегося дерева зависят от того порядка, в котором поступают идентификаторы. Например, если в рассмотренном выше примере вместо последовательности идентификаторов Ga, D1, М22, Е, А12, ВС, F взять последовательность А12, ВС, D1, Е, F, Ga, М22, то дерево выродится в упорядоченный однонаправленный связный список. Эта особенность является недостатком данного метода организации таблиц идентификаторов. Другими недостатками метода являются: необходимость хранить две дополнительные ссылки на левую и правую ветви в каждом элементе дерева и работа с динамическим выделением памяти при построении дерева.
   Если предположить, что последовательность идентификаторов в исходной программе является статистически неупорядоченной (что в целом соответствует действительности), то можно считать, что построенное бинарное дерево будет невырожденным. Тогда среднее время на заполнение дерева (Т_д) и на поиск элемента в нем (Т_п) можно оценить следующим образом [3, 7]:
   Несмотря на указанные недостатки, метод бинарного дерева является довольно удачным механизмом для организации таблиц идентификаторов. Он нашел свое применение в ряде компиляторов. Иногда компиляторы строят несколько различных деревьев для идентификаторов разных типов и разной длины [1, 2, 3, 7].

   В реальных исходных программах количество идентификаторов столь велико, что даже логарифмическую зависимость времени поиска от их числа нельзя признать удовлетворительной. Необходимы более эффективные методы поиска информации в таблице идентификаторов. Лучших результатов можно достичь, если применить методы, связанные с использованием хэш-функций и хэш-адресации.
   Хэш-функцией F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z:
   Сам термин «хэш-функция» происходит от английского термина «hash function» (hash – «мешать», «смешивать», «путать»).
   Множество допустимых входных элементов R называется областью определения хэш-функции. Множеством значений хэш-функции F называется подмножество М из множества целых неотрицательных чисел Z:
   содержащее все возможные значения, возвращаемые функцией F:
 
   Процесс отображения области определения хэш-функции на множество значений называется хэшированием.
   При работе с таблицей идентификаторов хэш-функция должна выполнять отображение имен идентификаторов на множество целых неотрицательных чисел. Областью определения хэш-функции будет множество всех возможных имен идентификаторов.
   Хэш-адресация заключается в использовании значения, возвращаемого хэш-функцией, в качестве адреса ячейки из некоторого массива данных. Тогда размер массива данных должен соответствовать области значений используемой хэш-функции. Следовательно, в реальном компиляторе область значений хэш-функции никак не должна превышать размер доступного адресного пространства компьютера.
   Метод организации таблиц идентификаторов, основанный на использовании хэш-адресации, заключается в помещении каждого элемента таблицы в ячейку, адрес которой возвращает хэш-функция, вычисленная для этого элемента. Тогда в идеальном случае для помещения любого элемента в таблицу идентификаторов достаточно только вычислить его хэш-функцию и обратиться к нужной ячейке массива данных. Для поиска элемента в таблице также необходимо вычислить хэш-функцию для искомого элемента и проверить, не является ли заданная ею ячейка массива пустой (если она не пуста – элемент найден, если пуста – не найден). Первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми.
   Этот метод весьма эффективен, поскольку как время размещения элемента в таблице, так и время его поиска определяются только временем, затрачиваемым на вычисление хэш-функции, которое в общем случае несопоставимо меньше времени, необходимого для многократных сравнений элементов таблицы.