Назад

Купить и читать книгу за 133 руб.

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

Системное программное обеспечение. Лабораторный практикум

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


Алексей Юрьевич Молчанов Системное программное обеспечение. Лабораторный практикум

Введение

   Эта книга является логическим продолжением и дополнением учебника «Системное программное обеспечение»,[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]). Автор надеется, что ему удастся в ближайшее время подготовить соответствующий материал.

От издательства

   Ваши замечания, предложения и вопросы отправляйте по адресу электронной почты comp@piter.com (издательство «Питер», компьютерная редакция).
   Мы будем рады узнать ваше мнение!
   Подробную информацию о наших книгах вы найдете на веб-сайте издательства: http://www.piter.com.

Лабораторная работа № 1
Организация таблиц идентификаторов

Цель работы

   Цель работы: изучить основные методы организации таблиц идентификаторов, получить представление о преимуществах и недостатках, присущих различным методам организации таблиц идентификаторов.
   Для выполнения лабораторной работы требуется написать программу, которая получает на входе набор идентификаторов, организует таблицы идентификаторов с помощью заданных методов, позволяет осуществить многократный поиск произвольного идентификатора в таблицах и сравнить эффективность методов организации таблиц. Список идентификаторов считать заданным в виде текстового файла. Длина идентификаторов ограничена 32 символами.

Краткие теоретические сведения

Назначение таблиц идентификаторов

   При выполнении семантического анализа, генерации кода и оптимизации результирующей программы компилятор должен оперировать характеристиками основных элементов исходной программы – переменных, констант, функций и других лексических единиц входного языка. Эти характеристики могут быть получены компилятором на этапе синтаксического анализа входной программы (чаще всего при анализе структуры блоков описаний переменных и констант), а также дополнены на этапе подготовки к генерации кода (например при распределении памяти).
   Набор характеристик, соответствующий каждому элементу исходной программы, зависит от типа этого элемента, от его смысла (семантики) и, соответственно, от той роли, которую он исполняет в исходной и результирующей программах. В каждом конкретном случае этот набор характеристик может быть свой в зависимости от синтаксиса и семантики входного языка, от архитектуры целевой вычислительной системы и от структуры компилятора. Но есть типовые характеристики, которые чаще всего присущи тем или иным элементам исходной программы. Например для переменной – это ее тип и адрес ячейки памяти, для константы – ее значение, для функции – количество и типы формальных аргументов, тип возвращаемого результата, адрес вызова кода функции. Более подробную информацию о характеристиках элементов исходной программы, их анализе и использовании можно найти в [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 + log2 N. Тогда время поиска элемента в таблице идентификаторов можно оценить как Tп = O(log2 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:

   Процесс отображения области определения хэш-функции на множество значений называется хэшированием.
   При работе с таблицей идентификаторов хэш-функция должна выполнять отображение имен идентификаторов на множество целых неотрицательных чисел. Областью определения хэш-функции будет множество всех возможных имен идентификаторов.
   Хэш-адресация заключается в использовании значения, возвращаемого хэш-функцией, в качестве адреса ячейки из некоторого массива данных. Тогда размер массива данных должен соответствовать области значений используемой хэш-функции. Следовательно, в реальном компиляторе область значений хэш-функции никак не должна превышать размер доступного адресного пространства компьютера.
   Метод организации таблиц идентификаторов, основанный на использовании хэш-адресации, заключается в помещении каждого элемента таблицы в ячейку, адрес которой возвращает хэш-функция, вычисленная для этого элемента. Тогда в идеальном случае для помещения любого элемента в таблицу идентификаторов достаточно только вычислить его хэш-функцию и обратиться к нужной ячейке массива данных. Для поиска элемента в таблице также необходимо вычислить хэш-функцию для искомого элемента и проверить, не является ли заданная ею ячейка массива пустой (если она не пуста – элемент найден, если пуста – не найден). Первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми.
   Этот метод весьма эффективен, поскольку как время размещения элемента в таблице, так и время его поиска определяются только временем, затрачиваемым на вычисление хэш-функции, которое в общем случае несопоставимо меньше времени, необходимого для многократных сравнений элементов таблицы.
   Метод имеет два очевидных недостатка. Первый из них – неэффективное использование объема памяти под таблицу идентификаторов: размер массива для ее хранения должен соответствовать всей области значений хэш-функции, в то время как реально хранимых в таблице идентификаторов может быть существенно меньше. Второй недостаток – необходимость соответствующего разумного выбора хэш-функции. Этот недостаток является настолько существенным, что не позволяет непосредственно использовать хэш-адресацию для организации таблиц идентификаторов.
   Проблема выбора хэш-функции не имеет универсального решения. Хэширование обычно происходит за счет выполнения над цепочкой символов некоторых простых арифметических и логических операций. Самой простой хэш-функцией для символа является код внутреннего представления в компьютере литеры символа. Эту хэш-функцию можно использовать и для цепочки символов, выбирая первый символ в цепочке.
   Очевидно, что такая примитивная хэш-функция будет неудовлетворительной: при ее использовании возникнет проблема – двум различным идентификаторам, начинающимся с одной и той же буквы, будет соответствовать одно и то же значение хэш-функции. Тогда при хэш-адресации в одну и ту же ячейку таблицы идентификаторов должны быть помещены два различных идентификатора, что явно невозможно. Такая ситуация, когда двум или более идентификаторам соответствует одно и то же значение хэш-функции, называется коллизией.
   Естественно, что хэш-функция, допускающая коллизии, не может быть использована для хэш-адресации в таблице идентификаторов. Причем достаточно получить хотя бы один случай коллизии на всем множестве идентификаторов, чтобы такой хэш-функцией нельзя было пользоваться. Но возможно ли построить хэш-функцию, которая бы полностью исключала возникновение коллизий?
   Для полного исключения коллизий хэш-функция должна быть взаимно однозначной: каждому элементу из области определения хэш-функции должно соответствовать одно значение из ее множества значений, и наоборот – каждому значению из множества значений этой функции должен соответствовать только один элемент из ее области определения. Тогда любым двум произвольным элементам из области определения хэш-функции будут всегда соответствовать два различных ее значения. Теоретически для идентификаторов такую хэш-функцию построить можно, так как и область определения хэш-функции (все возможные имена идентификаторов), и область ее значений (целые неотрицательные числа) являются бесконечными счетными множествами, поэтому можно организовать взаимно однозначное отображение одного множества на другое.
   Но на практике существует ограничение, делающее создание взаимно однозначной хэш-функции для идентификаторов невозможным. Дело в том, что в реальности область значений любой хэш-функции ограничена размером доступного адресного пространства компьютера. Множество адресов любого компьютера с традиционной архитектурой может быть велико, но всегда конечно, то есть ограничено. Организовать взаимно однозначное отображение бесконечного множества на конечное даже теоретически невозможно. Можно, конечно, учесть, что длина принимаемой во внимание части имени идентификатора в реальных компиляторах на практике также ограничена – обычно она лежит в пределах от 32 до 128 символов (то есть и область определения хэш-функции конечна). Но и тогда количество элементов в конечном множестве, составляющем область определения хэш-функции, будет превышать их количество в конечном множестве области ее значений (количество всех возможных идентификаторов больше количества допустимых адресов в современных компьютерах). Таким образом, создать взаимно однозначную хэш-функцию на практике невозможно. Следовательно, невозможно избежать возникновения коллизий.
   Поэтому нельзя организовать таблицу идентификаторов непосредственно на основе одной только хэш-адресации. Но существуют методы, позволяющие использовать хэш-функции для организации таблиц идентификаторов даже при наличии коллизий.

Хэш-адресация с рехэшированием

   Для решения проблемы коллизии можно использовать много способов. Одним из них является метод рехэширования (или расстановки). Согласно этому методу, если для элемента А адрес n0 = h(A), вычисленный с помощью хэш-функции h, указывает на уже занятую ячейку, то необходимо вычислить значение функции n1 = h1(A) и проверить занятость ячейки по адресу п1. Если и она занята, то вычисляется значение h2(A), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hi(А) не совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет – выдается информация об ошибке размещения идентификатора в таблице.
   Тогда поиск элемента А в таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму:
   1. Вычислить значение хэш-функции n = h(A) для искомого элемента А.
   2. Если ячейка по адресу п пустая, то элемент не найден, алгоритм завершен, иначе необходимо сравнить имя элемента в ячейке n с именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= 1 и перейти к шагу 3.
   3. Вычислить ni = hi(A). Если ячейка по адресу ni пустая или n = ni, то элемент не найден и алгоритм завершен, иначе – сравнить имя элемента в ячейке ni с именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= i + 1 и повторить шаг 3.
   Алгоритмы размещения и поиска элемента схожи по выполняемым операциям. Поэтому они будут иметь одинаковые оценки времени, необходимого для их выполнения.
   При такой организации таблиц идентификаторов в случае возникновения коллизии алгоритм помещает элементы в пустые ячейки таблицы, выбирая их определенным образом. При этом элементы могут попадать в ячейки с адресами, которые потом будут совпадать со значениями хэш-функции, что приведет к возникновению новых, дополнительных коллизий. Таким образом, количество операций, необходимых для поиска или размещения в таблице элемента, зависит от заполненности таблицы.
   Для организации таблицы идентификаторов по методу рехэширования необходимо определить все хэш-функции hi для всех i. Чаще всего функции hi определяют как некоторые модификации хэш-функции h. Например, самым простым методом вычисления функции hi(A) является ее организация в виде hi(A) = (h(A) + pi) mod Nm, где pi – некоторое вычисляемое целое число, а Nm – максимальное значение из области значений хэш-функции h. В свою очередь, самым простым подходом здесь будет положить pi = i. Тогда получаем формулу hi(A) = (h(A) + i) mod Nm. В этом случае при совпадении значений хэш-функции для каких-либо элементов поиск свободной ячейки в таблице начинается последовательно от текущей позиции, заданной хэш-функцией h(A).
   Этот способ нельзя признать особенно удачным: при совпадении хэш-адресов элементы в таблице начинают группироваться вокруг них, что увеличивает число необходимых сравнений при поиске и размещении. Но даже такой примитивный метод рехэширования является достаточно эффективным средством организации таблиц идентификаторов при неполном заполнении таблицы.
   Среднее время на помещение одного элемента в таблицу и на поиск элемента в таблице можно снизить, если применить более совершенный метод рехэширования. Одним из таких методов является использование в качестве pi для функции hi(A) = (h(A) + pi) mod Nm последовательности псевдослучайных целых чисел p1, p2, …, pk. При хорошем выборе генератора псевдослучайных чисел длина последовательности k = Nm.
   Существуют и другие методы организации функций рехэширования hi(A), основанные на квадратичных вычислениях или, например, на вычислении произведения по формуле: hi(A) = (h(A)N·i) mod N'm, где N'm – ближайшее простое число, меньшее Nm. В целом рехэширование позволяет добиться неплохих результатов для эффективного поиска элемента в таблице (лучших, чем бинарный поиск и бинарное дерево), но эффективность метода сильно зависит от заполненности таблицы идентификаторов и качества используемой хэш-функции – чем реже возникают коллизии, тем выше эффективность метода. Требование неполного заполнения таблицы ведет к неэффективному использованию объема доступной памяти.
   Оценки времени размещения и поиска элемента в таблицах идентификаторов при использовании различных методов рехэширования можно найти в [1, 3, 7].

Хэш-адресация с использованием метода цепочек

   Неполное заполнение таблицы идентификаторов при применении рехэширования ведет к неэффективному использованию всего объема памяти, доступного компилятору. Причем объем неиспользуемой памяти будет тем выше, чем больше информации хранится для каждого идентификатора. Этого недостатка можно избежать, если дополнить таблицу идентификаторов некоторой промежуточной хэш-таблицей.
   В ячейках хэш-таблицы может храниться либо пустое значение, либо значение указателя на некоторую область памяти из основной таблицы идентификаторов. Тогда хэш-функция вычисляет адрес, по которому происходит обращение сначала к хэш-таблице, а потом уже через нее по найденному адресу – к самой таблице идентификаторов. Если соответствующая ячейка таблицы идентификаторов пуста, то ячейка хэш-таблицы будет содержать пустое значение. Тогда вовсе не обязательно иметь в самой таблице идентификаторов ячейку для каждого возможного значения хэш-функции – таблицу можно сделать динамической, так чтобы ее объем рос по мере заполнения (первоначально таблица идентификаторов не содержит ни одной ячейки, а все ячейки хэш-таблицы имеют пустое значение).
   Такой подход позволяет добиться двух положительных результатов: во-первых, нет необходимости заполнять пустыми значениями таблицу идентификаторов – это можно сделать только для хэш-таблицы; во-вторых, каждому идентификатору будет соответствовать строго одна ячейка в таблице идентификаторов. Пустые ячейки в таком случае будут только в хэш-таблице, и объем неиспользуемой памяти не будет зависеть от объема информации, хранимой для каждого идентификатора, – для каждого значения хэш-функции будет расходоваться только память, необходимая для хранения одного указателя на основную таблицу идентификаторов.
   На основе этой схемы можно реализовать еще один способ организации таблиц идентификаторов с помощью хэш-функции, называемый методом цепочек. В этом случае в таблицу идентификаторов для каждого элемента добавляется еще одно поле, в котором может содержаться ссылка на любой элемент таблицы. Первоначально это поле всегда пустое (никуда не указывает). Также необходимо иметь одну специальную переменную, которая всегда указывает на первую свободную ячейку основной таблицы идентификаторов (первоначально она указывает на начало таблицы).
   Метод цепочек работает по следующему алгоритму:
   1. Во все ячейки хэш-таблицы поместить пустое значение, таблица идентификаторов пуста, переменная FreePtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов.
   2. Вычислить значение хэш-функции n для нового элемента A. Если ячейка хэш-таблицы по адресу n пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе перейти к шагу 3.
   3. Выбрать из хэш-таблицы адрес ячейки таблицы идентификаторов m и перейти к шагу 4.
   4. Для ячейки таблицы идентификаторов по адресу m проверить значение поля ссылки. Если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5; иначе выбрать из поля ссылки новый адрес m и повторить шаг 4.
   5. Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента A (поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки. Если больше нет идентификаторов, которые надо поместить в таблицу, то выполнение алгоритма закончено, иначе перейти к шагу 2.
   Поиск элемента в таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму:
   1. Вычислить значение хэш-функции n для искомого элемента A. Если ячейка хэш-таблицы по адресу n пустая, то элемент не найден и алгоритм завершен, иначе выбрать из хэш-таблицы адрес ячейки таблицы идентификаторов m.
   2. Сравнить имя элемента в ячейке таблицы идентификаторов по адресу m с именем искомого элемента A. Если они совпадают, то искомый элемент найден и алгоритм завершен, иначе перейти к шагу 3.
   3. Проверить значение поля ссылки в ячейке таблицы идентификаторов по адресу m. Если оно пустое, то искомый элемент не найден и алгоритм завершен; иначе выбрать из поля ссылки адрес m и перейти к шагу 2.
   При такой организации таблиц идентификаторов в случае возникновения коллизии алгоритм помещает элементы в ячейки таблицы, связывая их друг с другом последовательно через поле ссылки. При этом элементы не могут попадать в ячейки с адресами, которые потом будут совпадать со значениями хэш-функции. Таким образом, дополнительные коллизии не возникают. В итоге в таблице возникают своеобразные цепочки связанных элементов, откуда и происходит название данного метода – «метод цепочек».
   На рис. 1.2 проиллюстрировано заполнение хэш-таблицы и таблицы идентификаторов для ряда идентификаторов: A1, A2, A3, A4, A5 при условии, что h(A1) = h(A2) = h(A5) = n1; h(A3) = n2; h(A4) = n4. После размещения в таблице для поиска идентификатора A1 потребуется одно сравнение, для A2 – два сравнения, для A3 – одно сравнение, для A4 – одно сравнение и для A5 – три сравнения (попробуйте сравнить эти данные с результатами, полученными с использованием простого рехэширования для тех же идентификаторов).
   Метод цепочек является очень эффективным средством организации таблиц идентификаторов. Среднее время на размещение одного элемента и на поиск элемента в таблице для него зависит только от среднего числа коллизий, возникающих при вычислении хэш-функции. Накладные расходы памяти, связанные с необходимостью иметь одно дополнительное поле указателя в таблице идентификаторов на каждый ее элемент, можно признать вполне оправданными, так как возникает экономия используемой памяти за счет промежуточной хэш-таблицы. Этот метод позволяет более экономно использовать память, но требует организации работы с динамическими массивами данных.
   Рис. 1.2. Заполнение таблицы идентификаторов при использовании метода цепочек.

Комбинированные способы построения таблиц идентификаторов

   Кроме рехэширования и метода цепочек можно использовать комбинированные методы для организации таблиц идентификаторов с помощью хэш-адресации. В этом случае для исключения коллизий хэш-адресация сочетается с одним из ранее рассмотренных методов – простым списком, упорядоченным списком или бинарным деревом, который используется как дополнительный метод упорядочивания идентификаторов, для которых возникают коллизии. Причем, поскольку при качественном выборе хэш-функции количество коллизий обычно невелико (единицы или десятки случаев), даже простой список может быть вполне удовлетворительным решением при использовании комбинированного метода.
   При таком подходе возможны два варианта: в первом случае, как и для метода цепочек, в таблице идентификаторов организуется специальное дополнительное поле ссылки. Но в отличие от метода цепочек оно имеет несколько иное значение: при отсутствии коллизий для выборки информации из таблицы используется хэш-функция, поле ссылки остается пустым. Если же возникает коллизия, то через поле ссылки организуется поиск идентификаторов, для которых значения хэш-функции совпадают – это поле должно указывать на структуру данных для дополнительного метода: начало списка, первый элемент динамического массива или корневой элемент дерева.
   Во втором случае используется хэш-таблица, аналогичная хэш-таблице для метода цепочек. Если по данному адресу хэш-функции идентификатор отсутствует, то ячейка хэш-таблицы пустая. Когда появляется идентификатор с данным значением хэш-функции, то создается соответствующая структура для дополнительного метода, в хэш-таблицу записывается ссылка на эту структуру, а идентификатор помещается в созданную структуру по правилам выбранного дополнительного метода.
   В первом варианте при отсутствии коллизий поиск выполняется быстрее, но второй вариант предпочтительнее, так как за счет использования промежуточной хэш-таблицы обеспечивается более эффективное использование памяти.
   Как и для метода цепочек, для комбинированных методов время размещения и время поиска элемента в таблице идентификаторов зависит только от среднего числа коллизий, возникающих при вычислении хэш-функции. Накладные расходы памяти при использовании промежуточной хэш-таблицы минимальны.
   Очевидно, что если в качестве дополнительного метода использовать простой список, то получится алгоритм, полностью аналогичный методу цепочек. Если же использовать упорядоченный список или бинарное дерево, то метод цепочек и комбинированные методы будут иметь примерно равную эффективность при незначительном числе коллизий (единичные случаи), но с ростом количества коллизий эффективность комбинированных методов по сравнению с методом цепочек будет возрастать.
   Недостатком комбинированных методов является более сложная организация алгоритмов поиска и размещения идентификаторов, необходимость работы с динамически распределяемыми областями памяти, а также бóльшие затраты времени на размещение нового элемента в таблице идентификаторов по сравнению с методом цепочек.
   То, какой конкретно метод применяется в компиляторе для организации таблиц идентификаторов, зависит от реализации компилятора. Один и тот же компилятор может иметь даже несколько разных таблиц идентификаторов, организованных на основе различных методов. Как правило, применяются комбинированные методы.
   Создание эффективной хэш-функции – это отдельная задача разработчиков компиляторов, и полученные результаты, как правило, держатся в секрете. Хорошая хэш-функция распределяет поступающие на ее вход идентификаторы равномерно на все имеющиеся в распоряжении адреса, чтобы свести к минимуму количество коллизий. В настоящее время существует множество хэш-функций, но, как было показано выше, идеального хэширования достичь невозможно.
   Хэш-адресация – это метод, который применяется не только для организации таблиц идентификаторов в компиляторах. Данный метод нашел свое применение и в операционных системах, и в системах управления базами данных [5, 6, 11].

Требования к выполнению работы

Порядок выполнения работы

   Во всех вариантах задания требуется разработать программу, которая может обеспечить сравнение двух способов организации таблицы идентификаторов с помощью хэш-адресации. Для сравнения предлагаются способы, основанные на использовании рехэширования или комбинированных методов. Программа должна считывать идентификаторы из входного файла, размещать их в таблицах с помощью заданных методов и выполнять поиск указанных идентификаторов по требованию пользователя. В процессе размещения и поиска идентификаторов в таблицах программа должна подсчитывать среднее число выполненных операций сравнения для сопоставления эффективности используемых методов.
   Для организации таблиц предлагается использовать простейшую хэш-функцию, которую разработчик программы должен выбрать самостоятельно. Хэш-функция должна обеспечивать работу не менее чем с 200 идентификаторами, допустимая длина идентификатора должна быть не менее 32 символов. Запрещается использовать в работе хэш-функции, взятые из примера выполнения работы.
   Лабораторная работа должна выполняться в следующем порядке:
   1. Получить вариант задания у преподавателя.
   2. Выбрать и описать хэш-функцию.
   3. Описать структуры данных, используемые для заданных методов организации таблиц идентификаторов.
   4. Подготовить и защитить отчет.
   5. Написать и отладить программу на ЭВМ.
   6. Сдать работающую программу преподавателю.

Требования к оформлению отчета

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

Основные контрольные вопросы

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

Варианты заданий

   В табл. 1.1 перечислены методы организации таблиц идентификаторов, используемые в заданиях.
Таблица 1.1. Методы организации таблиц идентификаторов

   В табл. 1.2 даны варианты заданий на основе методов организации таблиц идентификаторов, перечисленных в табл. 1.1.
Таблица 1.2. Варианты заданий

Пример выполнения работы

Задание для примера

   В качестве примера выполнения лабораторной работы возьмем сопоставление двух методов: хэш-адресации с рехэшированием на основе псевдослучайных чисел и комбинации хэш-адресации с бинарным деревом. Если обратиться к приведенной выше табл. 1.1, то такой вариант задания будет соответствовать комбинации методов 2 и 7 (в табл. 1.2 среди вариантов заданий такая комбинация отсутствует).

Выбор и описание хэш-функции

   Для хэш-адресации с рехэшированием в качестве хэш-функции возьмем функцию, которая будет получать на входе строку, а в результате выдавать сумму кодов первого, среднего и последнего элементов строки. Причем если строка содержит менее трех символов, то один и тот же символ будет взят и в качестве первого, и в качестве среднего, и в качестве последнего.
   Будем считать, что прописные и строчные буквы в идентификаторах различны.[2] В качестве кодов символов возьмем коды таблицы ASCII, которая используется в вычислительных системах на базе ОС типа Microsoft Windows. Тогда, если положить, что строка из области определения хэш-функции содержит только цифры и буквы английского алфавита, то минимальным значением хэш-функции будет сумма трех кодов цифры «0», а максимальным значением – сумма трех кодов литеры «z».
   Таким образом, область значений выбранной хэш-функции в терминах языка Object Pascal может быть описана как:
   (Ord(0 )+Ord(0 )+Ord(0 ))..(Ord('z')+Ord('z')+Ord('z'))

   Диапазон области значений составляет 223 элемента, что удовлетворяет требованиям задания (не менее 200 элементов). Длина входных идентификаторов в данном случае ничем не ограничена. Для удобства пользования опишем две константы, задающие границы области значений хэш-функции:
   HASH_MIN = Ord(0 )+Ord(0 )+Ord(0 );
   HASH_MAX = Ord('z')+Ord('z')+Ord('z').

   Сама хэш-функция без учета рехэширования будет вычислять следующее выражение:
   Ord(sName[1]) + Ord(sName[(Length(sName)+1) div 2]) + Ord(sName[Length(sName);
   здесь sName – это входная строка (аргумент хэш-функции).

   Для рехэширования возьмем простейший генератор последовательности псевдослучайных чисел, построенный на основе формулы F = i-H1 mod Н2, где Н1 и Н2 – простые числа, выбранные таким образом, чтобы H1 было в диапазоне от Н2/2 до Н2. Причем, чтобы этот генератор выдавал максимально длинную последовательность во всем диапазоне от HASH_MIN до HASH_MAX, Н2 должно быть максимально близко к величине HASH_MAX – HASН_МIN + 1. В данном случае диапазон содержит 223 элемента, и поскольку 223 – простое число, то возьмем Н2 = 223 (если бы размер диапазона не был простым числом, то в качестве Н2 нужно было бы взять ближайшее к нему меньшее простое число). В качестве H1 возьмем 127: H1 = 127.
   Опишем соответствующие константы:
   REHASH1 = 127;
   REHASH2 = 223;

   Тогда хэш-функция с учетом рехэширования будет иметь следующий вид:
   function VarHash(const sName: string; iNum: integer):longint;
   begin
   Result:=(Ord(sName[1])+Ord(sName[(Length(sName)+1) div 2])
   + Ord(sName[Length(sName)]) – HASH_MIN
   + iNum*REHASH1 mod REHASH2)
   mod (HASH_MAX-HASH_MIN+1) + HASH_MIN;
   if Result < HASH_MIN then Result:= HASH_MIN;
   end;
   Входные параметры этой функции: sName – имя хэшируемого идентификатора, iNum – индекс рехэшированиея (если iNum = 0, то рехэширование отсутствует). Строка проверки величины результата (Result < HASH_MIN) добавлена, чтобы исключить ошибки в тех случаях, когда на вход функции подается строка, содержащая символы вне диапазона 0 ..'z' (поскольку контроль входных идентификаторов отсутствует, это имеет смысл).
   Для комбинации хэш-адресации и бинарного дерева можно использовать более простую хэш-функцию – сумму кодов первого и среднего символов входной строки. Диапазон значений такой хэш-функции в терминах языка Object Pascal будет выглядеть так:
   (Ord(0 )+Ord(0 ))..(Ord('z')+Ord('z'))
   Этот диапазон содержит менее 200 элементов, однако функция будет удовлетворять требованиям задания, так как в комбинации с бинарным деревом она будет обеспечивать обработку неограниченного количества идентификаторов (максимальное количество идентификаторов будет ограничено только объемом доступной оперативной памяти компьютера).
   Без применения рехэширования эта хэш-функция будет выглядеть значительно проще, чем описанная выше хэш-функция с учетом рехэширования:
   function VarHash(const sName: string): longint;
   begin
   Result:=(Ord(sName[1])+Ord(sName[(Length(sName)+1) div 2])
   – HASH_MIN) mod (HASH_MAX-HASH_MIN+1) + HASH_MIN;
   if Result < HASH_MIN then Result:= HASH_MIN;
   end.

Описание структур данных таблиц идентификаторов

   В первую очередь необходимо описать структуру данных, которая будет использована для хранения информации об идентификаторах в таблицах идентификаторов. Для обеих таблиц (с рехэшированием на основе генератора псевдослучайных чисел и в комбинации с бинарным деревом) будем использовать одну и ту же структуру. В этом случае в таблицах будут храниться неиспользуемые данные, но программный код будет проще. В качестве учебного примера такой подход оправдан.
   Структура данных таблицы идентификаторов (назовем ее TVarInfo) должна содержать в обязательном порядке поле имени идентификатора (поле sName: string), а также поля дополнительной информации об идентификаторе по усмотрению разработчиков компилятора. В лабораторной работе не предусмотрено хранение какой-либо дополнительной информации об идентификаторах, поэтому в качестве иллюстрации информационного поля включим в структуру TVarInfo дополнительную информационную структуру TAddVarInfo (поле pInfo: TAddVarInfo).
   Поскольку в языке Object Pascal для полей и переменных, описанных как class, хранятся только ссылки на соответствующую структуру, такой подход не приведет к значительным расходам памяти, но позволит в будущем хранить любую информацию, связанную с идентификатором, в отдельной структуре данных (поскольку предполагается использовать создаваемые программные модули в последующих лабораторных работах). В данном случае другой подход невозможен, так как заранее не известно, какие данные необходимо будет хранить в таблицах идентификаторов. Но разработчик реального компилятора, как правило, знает, какую информацию требуется хранить, и может использовать другой подход – непосредственно включить все необходимые поля в структуру данных таблицы идентификаторов (в данном случае – в структуру TVarInfo) без использования промежуточных структур данных и ссылок.
   Первый подход, реализованный в данном примере, обеспечивает более экономное использование оперативной памяти, но является более сложным и требует работы с динамическими структурами, второй подход более прост в реализации, но менее экономно использует память. Какой из двух подходов выбрать, решает разработчик компилятора в каждом конкретном случае (второй подход будет проиллюстрирован позже в примере к лабораторной работе № 4).
   Для работы со структурой данных TVarInfo потребуются следующие функции:
   • функции создания структуры данных и освобождения занимаемой памяти – реализованы как constructor Create и destructor Destroy;
   • функции доступа к дополнительной информации – в данной реализации это procedure SetInfo и procedure ClearInfo.
   Эти функции будут общими для таблицы идентификаторов с рехэшированием и для комбинированной таблицы идентификаторов.
   Однако для комбинированной таблицы идентификаторов в структуру данных TVarInfo потребуется также включить дополнительные поля данных и функции, обеспечивающие организацию бинарного дерева:
   • ссылки на левую («меньшую») и правую («большую») ветвь дерева – реализованы как поля данных minEl, maxEl: TVarInfo;
   • функции добавления элемента в дерево – function AddElCnt и function AddElem;
   • функции поиска элемента в дереве – function FindElCnt и function FindElem;
   • функция очистки информационных полей во всем дереве – procedure ClearAllInfo;
   • функция вывода содержимого бинарного дерева в одну строку (для получения списка всех идентификаторов) – function GetElList.
   Функции поиска и размещения элемента в дереве реализованы в двух экземплярах, так как одна из них выполняет подсчет количества сравнений, а другая – нет.
   Поскольку на функции и процедуры не расходуется оперативная память, в результате получилось, что при использовании одной и той же структуры данных для разных таблиц идентификаторов в таблице с рехэшированием будет расходоваться неиспользуемая память только на хранение двух лишних ссылок (minEl и maxEl).
   Полностью вся структура данных TVarInfo и связанные с ней процедуры и функции описаны в программном модуле TblElem. Полный текст этого программного модуля приведен в листинге П3.1 в приложении 3.
   Надо обратить внимание на один важный момент в реализации функции поиска идентификатора в дереве (function TVarInfo.FindElCnt). Если выполнять сравнение двух строк (в данном случае – имени искомого идентификатора sN и имени идентификатора в текущем узле дерева sName) с помощью стандартных методов сравнения строк языка Object Pascal, то фрагмент программного кода выглядел бы примерно так:
   if sN < sName then
   begin
   …
   end
   else
   if sN > sName then
   begin
   …
   end
   else…
   В этом фрагменте сравнение строк выполняется дважды: сначала проверяется отношение «меньше» (sN < sName), а потом – «больше» (sN > sName). И хотя в программном коде явно это не указано, для каждого из этих операторов будет вызвана библиотечная функция сравнения строк (то есть операция сравнения может выполниться дважды!). Чтобы этого избежать, в реализации предложенной в примере выполняется явный вызов функции сравнения строк, а потом обрабатывается полученный результат:
   i:= StrComp(PChar(sN), PChar(sName));
   if i < 0 then
   begin
   …
   end
   else
   if i > 0 then
   begin
   …
   end
   else…
   В таком варианте дважды может быть выполнено только сравнение целого числа с нулем, а сравнение строк всегда выполняется только один раз, что существенно увеличивает эффективность процедуры поиска.

Организация таблиц идентификаторов

   Таблицы идентификаторов реализованы в виде статических массивов размером HASH_MIN..HASH_MAX, элементами которых являются структуры данных типа TVarInfo. В языке Object Pascal, как было сказано выше, для структур таких типов хранятся ссылки. Поэтому для обозначения пустых ячеек в таблицах идентификаторов будет использоваться пустая ссылка – nil.
   Поскольку в памяти хранятся ссылки, описанные массивы будут играть роль хэш-таблиц, ссылки из которых указывают непосредственно на информацию в таблицах идентификаторов.
   На рис. 1.3 показаны условные схемы, наглядно иллюстрирующие организацию таблиц идентификаторов. Схема 1 иллюстрирует таблицу идентификаторов с рехэшированием на основе генератора псевдослучайных чисел, схема 2 – таблицу идентификаторов на основе комбинации хэш-адресации с бинарным деревом. Ячейки с надписью «nil» соответствуют незаполненным ячейкам хэш-таблицы.
   Рис. 1.3. Схемы организации таблиц идентификаторов.

   Для каждой таблицы идентификаторов реализованы следующие функции:
   • функции начальной инициализации хэш-таблицы – InitTreeVar и InitHashVar;
   • функции освобождения памяти хэш-таблицы – ClearTreeVar и ClearHashVar;
   • функции удаления дополнительной информации в таблице – ClearTreeInfo и ClearHashInfo;
   • функции добавления элемента в таблицу идентификаторов – AddTreeVar и AddHashVar;
   • функции поиска элемента в таблице идентификаторов – GetTreeVar и GetHashVar;
   • функции, возвращающие количество выполненных операций сравнения при размещении или поиске элемента в таблице – GetTreeCount и GetHashCount.
   Алгоритмы поиска и размещения идентификаторов для двух данных методов организации таблиц были описаны выше в разделе «Краткие теоретические сведения», поэтому приводить их здесь повторно нет смысла. Они реализованы в виде четырех перечисленных выше функций (AddTreeVar и AddHashVar – для размещения элемента; GetTreeVar и GetHashVar – для поиска элемента). Функции поиска и размещения элементов в таблице в качестве результата возвращают ссылку на элемент таблицы (структура которого описана в модуле TblElem) в случае успешного выполнения и нулевую ссылку – в противном случае.
   Надо отметить, что функции размещения идентификатора в таблице организованы таким образом, что если на момент помещения нового идентификатора в таблице уже есть идентификатор с таким же именем, то функция не добавляет новый идентификатор в таблицу, а возвращает в качестве результата ссылку на ранее помещенный в таблицу идентификатор. Таким образом, в таблице не может быть двух и более идентификаторов с одинаковым именем. При этом наличие одинаковых идентификаторов во входном файле не воспринимается как ошибка – это допустимо, так как в задании не предусмотрено ограничение на наличие совпадающих имен идентификаторов.
   Все перечисленные функции описаны в двух программных модулях: FncHash – для таблицы идентификаторов, построенной на основе рехэширования с использованием генератора псевдослучайных чисел, и FncTree – для таблицы идентификаторов, построенной на основе комбинации хэш-адресации и бинарного дерева. Кроме массивов данных для организации таблиц идентификаторов и функций работы с ними эти модули содержат также описание переменных, используемых для подсчета количества выполненных операций сравнения при размещении и поиске идентификатора в таблицах.
   Полные тексты обоих модулей (FncHash и FncTree) можно найти на веб-сайте издательства, в файлах FncHash.pas и FncTree.pas. Кроме того, текст модуля FncTree приведен в листинге П3.2 в приложении 3.
   Хочется обратить внимание на то, что в разделах инициализации (initialization) обоих модулей вызывается функция начального заполнения таблицы идентификаторов, а в разделах завершения (finalization) обоих модулей – функция освобождения памяти. Это гарантирует корректную работу модулей при любом порядке вызова остальных функций, поскольку Object Pascal сам обеспечивает своевременный вызов программного кода в разделах инициализации и завершения модулей.

Текст программы

   Кроме перечисленных выше модулей необходим еще модуль, обеспечивающий интерфейс с пользователем. Этот модуль (FormLab1) реализует графическое окно TLab1Form на основе класса TForm библиотеки VCL. Он обеспечивает интерфейс средствами Graphical User Interface (GUI) в ОС типа Windows на основе стандартных органов управления из системных библиотек данной ОС. Кроме программного кода (файл FormLab1.pas) модуль включает в себя описание ресурсов пользовательского интерфейса (файл FormLab1.dfm). Более подробно принципы организации пользовательского интерфейса на основе GUI и работа систем программирования с ресурсами интерфейса описаны в [3, 5, 6, 7].
   Кроме описания интерфейсной формы и ее органов управления модуль FormLab1 содержит три переменные (iCountNum, iCountHash, iCountTree), служащие для накопления статистических результатов по мере выполнения размещения и поиска идентификаторов в таблицах, а также функцию (procedure ViewStatistic) для отображения накопленной статистической информации на экране.
   Интерфейсная форма, описанная в модуле, содержит следующие основные органы управления:
   • поле ввода имени файла (EditFile), кнопка выбора имени файла из каталогов файловой системы (BtnFile), кнопка чтения файла (BtnLoad);
   • многострочное поле для отображения прочитанного файла (Listldents);
   • поле ввода имени искомого идентификатора (EditSearch);
   • кнопка для поиска введенного идентификатора (BtnSearch) – этой кнопкой однократно вызывается процедура поиска (procedure SearchStr);
   • кнопка автоматического поиска всех идентификаторов (BtnAllSearch) – этой кнопкой процедура поиска идентификатора (procedure SearchStr) вызывается циклически для всех считанных из файла идентификаторов (для всех, перечисленных в поле Listldents);
   • кнопка сброса накопленной статистической информации (BtnReset);
   • поля для отображения статистической информации;
   • кнопка завершения работы с программой (BtnExit).
   Внешний вид этой формы приведен на рис. 1.4.
   Рис. 1.4. Внешний вид интерфейсной формы для лабораторной работы № 1.

   Функция чтения содержимого файла с идентификаторами (procedure TLab1Form. BtnLoadClick) вызывается щелчком по кнопке BtnLoad. Она организована таким образом, что сначала содержимое файла читается в многострочное поле Listldents, а затем все прочитанные идентификаторы записываются в две таблицы идентификаторов. Каждая строка файла считается отдельным идентификатором, пробелы в начале и в конце строки игнорируются. При ошибке размещения идентификатора в одной из таблиц выдается предупреждающее сообщение (например, если будет считано более 223 различных идентификаторов, то рехэширование станет невозможным и будет выдано сообщение об ошибке).
   Функция поиска идентификатора (procedure TLab1Form.SearchStr) вызывается однократно щелчком по кнопке BtnSearch (процедура procedure TLab1Form.BtnSearchClick) или многократно щелчком по кнопке BtnAllSearch (процедура procedure TLab1Form. BtnAllSearchClick). Поиск идет сразу в двух таблицах, результаты поиска и накопленная статистическая информация отображаются в соответствующих полях.
   Полный текст программного кода модуля интерфейса с пользователем и описание ресурсов пользовательского интерфейса находятся в архиве, располагающемся на веб-сайте издательства, в файлах FormLab1.pas и FormLab1.dfm соответственно.
   Полный текст всех программных модулей, реализующих рассмотренный пример для лабораторной работы № 1, можно найти в архиве, располагающемся на вебсайте, в подкаталогах LABS и COMMON (в подкаталог COMMON вынесены те программные модули, исходный текст которых не зависит от входного языка и задания по лабораторной работе). Главным файлом проекта является файл LAB1.DPR в подкаталоге LABS. Кроме того, текст модуля FncTree приведен в листинге П3.1 в приложении 3.

Выводы по проделанной работе

   В результате выполнения написанного программного кода для ряда тестовых файлов было установлено, что при заполнении таблицы идентификаторов до 20 % (до 45 идентификаторов) для поиска и размещения идентификатора с использованием рехэширования на основе генератора псевдослучайных чисел в среднем требуется меньшее число сравнений, чем при использовании хэш-адресации в комбинации с бинарным деревом. При заполнении таблицы от 20 % до 40 % (примерно 45–90 идентификаторов) оба метода имеют примерно равные показатели, но при заполнении таблицы более, чем на 40 % (90-223 идентификаторов), эффективность комбинированного метода по сравнению с методом рехэширования резко возрастает. Если на входе имеется более 223 идентификаторов, рехэширование полностью перестает работать.
   Таким образом, установлено, что комбинированный метод работоспособен даже при наличии простейшей хэш-функции и дает неплохие результаты (в среднем 3–5 сравнений на входных файлах, содержащих 500–700 идентификаторов), в то время как метод на основе рехэширования для реальной работы требует более сложной хэш-функции с диапазоном значений в несколько тысяч или десятков тысяч.

Лабораторная работа № 2
Проектирование лексического анализатора

Цель работы

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

Краткие теоретические сведения

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

   Лексический анализатор (или сканер) – это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
   Лексема (лексическая единица языка) – это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка. Лексемами языков программирования являются идентификаторы, константы, ключевые слова языка, знаки операций и т. п. Состав возможных лексем каждого конкретного языка программирования определяется синтаксисом этого языка.
   С теоретической точки зрения лексический анализатор не является обязательной, необходимой частью компилятора. Его функции могут выполняться на этапе синтаксического анализа. Однако существует несколько причин, исходя из которых в состав практически всех компиляторов включают лексический анализ. Это следующие причины:
   • упрощается работа с текстом исходной программы на этапе синтаксического разбора и сокращается объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и удаляет всю незначащую информацию;
   • для выделения в тексте и разбора лексем возможно применять простую, эффективную и хорошо проработанную теоретически технику анализа, в то время как на этапе синтаксического анализа конструкций исходного языка используются достаточно сложные алгоритмы разбора;
   • лексический анализатор отделяет сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходной программы, структура которого может варьироваться в зависимости от версии входного языка – при такой конструкции компилятора при переходе от одной версии языка к другой достаточно только перестроить относительно простой лексический анализатор.
   Функции, выполняемые лексическим анализатором, и состав лексем, которые он выделяет в тексте исходной программы, могут меняться в зависимости от версии компилятора. В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, знаков операций, разделителей и ключевых (служебных) слов входного языка.
   В большинстве компиляторов лексический и синтаксический анализаторы – это взаимосвязанные части. Где провести границу между лексическим и синтаксическим анализом, какие конструкции анализировать сканером, а какие – синтаксическим распознавателем, решает разработчик компилятора. Как правило, любой анализ стремятся выполнить на этапе лексического разбора входной программы, если он может быть там выполнен. Возможности лексического анализатора ограничены по сравнению с синтаксическим анализатором, так как в его основе лежат более простые механизмы. Более подробно о роли лексического анализатора в компиляторе и о его взаимодействии с синтаксическим анализатором можно узнать в [1–4, 7].

Проблема определения границ лексем

   В простейшем случае фазы лексического и синтаксического анализа могут выполняться компилятором последовательно. Но для многих языков программирования информации на этапе лексического анализа может быть недостаточно для однозначного определения типа и границ очередной лексемы.
   Иллюстрацией такого случая может служить пример оператора программы на языке Фортран, когда по части текста DO 10 I=1… невозможно определить тип оператора (а соответственно, и границы лексем). В случае DO 10 I=1.15 это будет присвоение вещественной переменной DO10I значения константы 1.15 (пробелы в Фортране игнорируются), а в случае DO 10 I=1,15 это цикл с перечислением от 1 до 15 по целочисленной переменной I до метки 10.
   Другая иллюстрация из более современного языка программирования C++ – оператор присваивания k=i+++++j;, который имеет только одну верную интерпретацию (если операции разделить пробелами): k = i++ + ++j;.
   Если невозможно определить границы лексем, то лексический анализ исходного текста должен выполняться поэтапно. Тогда лексический и синтаксический анализаторы должны функционировать параллельно, поочередно обращаясь друг к другу. Лексический анализатор, найдя очередную лексему, передает ее синтаксическому анализатору, тот пытается выполнить анализ считанной части исходной программы и может либо запросить у лексического анализатора следующую лексему, либо потребовать от него вернуться на несколько шагов назад и попробовать выделить лексемы с другими границами. При этом он может сообщить информацию о том, какую лексему следует ожидать. Более подробно такая схема взаимодействия лексического и синтаксического анализаторов описана в [3, 7].
   Параллельная работа лексического и синтаксического анализаторов, очевидно, более сложна в реализации, чем их последовательное выполнение. Кроме того, такой подход требует больше вычислительных ресурсов и в общем случае большего времени на анализ исходной программы, так как допускает возврат назад и повторный анализ уже прочитанной части исходного кода. Тем не менее сложность синтаксиса некоторых языков программирования требует именно такого подхода – рассмотренный ранее пример программы на языке Фортран не может быть проанализирован иначе.
   Чтобы избежать параллельной работы лексического и синтаксического анализаторов, разработчики компиляторов и языков программирования часто идут на разумные ограничения синтаксиса входного языка. Например, для языка C++ принято соглашение, что при возникновении проблем с определением границ лексемы всегда выбирается лексема максимально возможной длины.
   В рассмотренном выше примере для оператора k=i+++++j; это приведет к тому, что при чтении четвертого знака + из двух вариантов лексем (+ – знак сложения в C++, а ++ – оператор инкремента) лексический анализатор выберет самую длинную – ++ (оператор инкремента) – и в целом весь оператор будет разобран как k = i++ ++ +j; (знаки операций разделены пробелами), что неверно, так как семантика языка C++ запрещает два оператора инкремента подряд. Конечно, неверный анализ операторов, аналогичных приведенному в примере (желающие могут убедиться в этом на любом доступном компиляторе языка C++), – незначительная плата за увеличение эффективности работы компилятора и не ограничивает возможности языка (тот же самый оператор может быть записан в виде k=i++ + ++j;, что исключит любые неоднозначности в его анализе). Однако таким же путем для языка Фортран пойти нельзя – разница между оператором присваивания и оператором цикла слишком велика, чтобы ею можно было пренебречь.
   В дальнейшем будем исходить из предположения, что все лексемы могут быть однозначно выделены сканером на этапе лексического анализа. Для всех современных языков программирования это действительно так, поскольку их синтаксис разрабатывался с учетом возможностей компиляторов.

Таблица лексем и содержащаяся в ней информация

   Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем с учетом характеристик каждой лексемы. Этот перечень лексем можно представить в виде таблицы, называемой таблицей лексем. Каждой лексеме в таблице лексем соответствует некий уникальный условный код, зависящий от типа лексемы, и дополнительная служебная информация. Таблица лексем в каждой строке должна содержать информацию о виде лексемы, ее типе и, возможно, значении. Обычно структуры данных, служащие для организации такой таблицы, имеют два поля: первое – тип лексемы, второе – указатель на информацию о лексеме.
   Кроме того, информация о некоторых типах лексем, найденных в исходной программе, должна помещаться в таблицу идентификаторов (или в одну из таблиц идентификаторов, если компилятор предусматривает различные таблицы идентификаторов для различных типов лексем).
   Внимание!
   Не следует путать таблицу лексем и таблицу идентификаторов – это две принципиально разные таблицы, обрабатываемые лексическим анализатором.
   Таблица лексем фактически содержит весь текст исходной программы, обработанный лексическим анализатором. В нее входят все возможные типы лексем, кроме того, любая лексема может встречаться в ней любое количество раз. Таблица идентификаторов содержит только определенные типы лексем – идентификаторы и константы. В нее не попадают такие лексемы, как ключевые (служебные) слова входного языка, знаки операций и разделители. Кроме того, каждая лексема (идентификатор или константа) может встречаться в таблице идентификаторов только один раз. Также можно отметить, что лексемы в таблице лексем обязательно располагаются в том же порядке, что и в исходной программе (порядок лексем в ней не меняется), а в таблице идентификаторов лексемы располагаются в любом порядке так, чтобы обеспечить удобство поиска.
   В качестве примера можно рассмотреть некоторый фрагмент исходного кода на языке Object Pascal и соответствующую ему таблицу лексем, представленную в табл. 2.1:
   …
   begin
   for i:=1 to N do
   fg:= fg * 0.5
   …
Таблица 2.1. Лексемы фрагмента программы на языке Pascal
   Поле «значение» в табл. 2.1 подразумевает некое кодовое значение, которое будет помещено в итоговую таблицу лексем в результате работы лексического анализатора. Конечно, значения, которые записаны в примере, являются условными. Конкретные коды выбираются разработчиками при реализации компилятора. Важно отметить также, что устанавливается связь таблицы лексем с таблицей идентификаторов (в примере это отражено некоторым индексом, следующим после идентификатора за знаком «:», а в реальном компиляторе определяется его реализацией).

Построение лексических анализаторов (сканеров)

   Лексический анализатор имеет дело с такими объектами, как различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык описания констант и идентификаторов в большинстве случаев является регулярным, то есть может быть описан с помощью регулярных грамматик [1–4, 7]. Распознавателями для регулярных языков являются конечные автоматы (КА). Существуют правила, с помощью которых для любой регулярной грамматики может быть построен КА, распознающий цепочки языка, заданного этой грамматикой.
   Более подробно о построении КА на основе грамматик для регулярных языков можно узнать в [3, 7, 26].
   Любой КА может быть задан с помощью пяти параметров: M(Q,Σ,δ,q0,F),
   где:
   Q – конечное множество состояний автомата;
   Σ – конечное множество допустимых входных символов (входной алфавит КА);
   δ – заданное отображение множества Q·Σ во множество подмножеств P(Q)δ: Q·Σ → P(Q) (иногда δ называют функцией переходов автомата);
   – начальное состояние автомата;
   – множество заключительных состояний автомата.

   Другим способом описания КА является граф переходов – графическое представление множества состояний и функции переходов КА. Граф переходов КА – это нагруженный однонаправленный граф, в котором вершины представляют состояния КА, дуги отображают переходы из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют функции перехода КА. Если функция перехода КА предусматривает переход из состояния q в q' по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q'.
   Недетерминированный КА неудобен для анализа цепочек, так как в нем могут встречаться состояния, допускающие неоднозначность, то есть такие, из которых выходит две или более дуги, помеченные одним и тем же символом. Очевидно, что программирование работы такого КА – нетривиальная задача. Для простого программирования функционирования КА M(Q,Σ,δ,q0,F) он должен быть детерминированным – в каждом из возможных состояний этого КА для любого входного символа функция перехода должна содержать не более одного состояния:
   Доказано, что любой недетерминированный КА может быть преобразован в детерминированный КА так, чтобы их языки совпадали [3, 7, 26] (говорят, что эти КА эквивалентны).
   Кроме преобразования в детерминированный КА любой КА может быть минимизирован – для него может быть построен эквивалентный ему детерминированный КА с минимально возможным количеством состояний. Алгоритмы преобразования КА в детерминированный КА и минимизации КА подробно описаны в [3, 7, 26].
   Можно написать функцию, отражающую функционирование любого детерминированного КА. Чтобы запрограммировать такую функцию, достаточно иметь переменную, которая бы отображала текущее состояние КА, а переходы из одного состояния в другое на основе символов входной цепочки могут быть построены с помощью операторов выбора. Работа функции должна продолжаться до тех пор, пока не будет достигнут конец входной цепочки. Для вычисления результата функции необходимо по ее завершении проанализировать состояние КА. Если это одно из конечных состояний, то функция выполнена успешно и входная цепочка принимается, если нет, то входная цепочка не принадлежит заданному языку.
   Однако в общем случае задача лексического анализатора шире, чем просто проверка цепочки символов лексемы на соответствие ее входному языку. Он должен правильно определить конец лексемы (об этом было сказано выше) и выполнить те или иные действия по запоминанию распознанной лексемы (занесение ее в таблицу лексем). Набор выполняемых действий определяется реализацией компилятора. Обычно эти действия выполняются сразу же при обнаружении конца распознаваемой лексемы.
   Во входном тексте лексемы не ограничены специальными символами. Определение границ лексем – это выделение тех строк в общем потоке входных символов, для которых надо выполнять распознавание. Если границы лексем всегда определяются (а выше было принято именно такое соглашение), то их можно определить по заданным терминальным символам и по символам начала следующей лексемы. Терминальные символы – это пробелы, знаки операций, символы комментариев, а также разделители (запятые, точки с запятой и др.). Набор таких терминальных символов может варьироваться в зависимости от входного языка. Важно отметить, что знаки операций сами также являются лексемами и необходимо не пропустить их при распознавании текста.
   Таким образом, алгоритм работы простейшего сканера можно описать так:
   • просматривается входной поток символов программы на исходном языке до обнаружения очередного символа, ограничивающего лексему;
   • для выбранной части входного потока выполняется функция распознавания лексемы;
   • при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу;
   • при неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера: либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).
   Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.

Требования к выполнению работы

Порядок выполнения работы

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

Требования к оформлению отчета

   Отчет должен содержать следующие разделы:
   • Задание по лабораторной работе.
   • Описание КС-грамматики входного языка в форме Бэкуса—Наура.
   • Описание алгоритма работы сканера или граф переходов КА для распознавания цепочек (в соответствии с вариантом задания).
   • Текст программы (оформляется после выполнения программы на ЭВМ).
   • Выводы по проделанной работе.

Основные контрольные вопросы

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

Варианты заданий

   1. Входной язык содержит арифметические выражения, разделенные символом; (точка с запятой). Арифметические выражения состоят из идентификаторов, десятичных чисел с плавающей точкой (в обычной и логарифмической форме), знака присваивания (:=), знаков операций +, —, *, / и круглых скобок.
   2. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, констант true и false, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.
   3. Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой (в обычной и логарифмической форме), знак присваивания (:=).
   4. Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой (в обычной и логарифмической форме), знак присваивания (:=).
   5. Входной язык содержит арифметические выражения, разделенные символом; (точка с запятой). Арифметические выражения состоят из идентификаторов, римских чисел, знака присваивания (:=), знаков операций +, —, *, / и круглых скобок.
   6. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, констант 0 и 1, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.
   7. Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).
   8. Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).
   9. Входной язык содержит арифметические выражения, разделенные символом; (точка с запятой). Арифметические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций +, —, *, / и круглых скобок.
   10. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.
   11. Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присваивания (:=).
   12. Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присваивания (:=).
   13. Входной язык содержит арифметические выражения, разделенные символом; (точка с запятой). Арифметические выражения состоят из идентификаторов, символьных констант (один символ в одинарных кавычках), знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.
   14. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, символьных констант Т и 'F', знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.
   15. Входной язык содержит операторы условия типа if… then… else и if… then, разделенные символом; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, строковые константы (последовательность символов в двойных кавычках), знак присваивания (:=).
   16. Входной язык содержит операторы цикла типа for (…;…;…) do, разделенные символом; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, строковые константы (последовательность символов в двойных кавычках), знак присваивания (:=).
   Примечание.
   • Римскими числами считать последовательности заглавных латинских букв X, V и I;
   • шестнадцатеричными числами считать последовательность цифр и символов «а», «Ь», «с», «d, „е“ и „f“, начинающуюся с цифры (например: 89, 45ас9, 0abc4);
   • задание по лабораторной работе № 2 взаимосвязано с заданием по лабораторной работе № 3, для уточнения состава входного языка можно посмотреть грамматику, заданную в работе № 3 по соответствующему варианту.

Пример выполнения работы

Задание для примера

   В качестве задания для примера возьмем входной язык, который содержит набор условных операторов условия типа if… then… else и if… then, разделенных символом; (точка с запятой). Эти операторы в качестве условия содержат логические выражения, построенные с помощью операций or, xor и and, операндами которых являются идентификаторы и целые десятичные константы без знака. В исполнительной части эти операторы содержат или оператор присваивания переменной логического выражения (:=), или другой условный оператор.
   Комментарий будет организован в виде последовательности символов, начинающейся с открывающей фигурной скобки ({) и заканчивающейся закрывающей фигурной скобкой (}). Комментарий может содержать любые алфавитно-цифровые символы, в том числе и символы национальных алфавитов.

Грамматика входного языка

   Описанный выше входной язык может быть построен с помощью КС-грамматики G({if,then,else,a,=,or,xor,and,(,),},{S,F,E,D,C},P,S) с правилами Р:
   S → F;
   F → if E then T else F | if E then F | a:= E
   T → if E then T else T | a:= E
   E → E or D | E xor D | D
   D → D and С | С
   С → a | (E)
   Описание грамматики построено в форме Бэкуса—Наура. Жирным шрифтом в грамматике и в правилах выделены терминальные символы.
   Выбранный в качестве примера язык и задающая его грамматика не совпадают ни с одним из предложенных выше вариантов. С другой стороны, на этом примере можно проиллюстрировать многие особенности построения лексического, а впоследствии – и синтаксического распознавателя, присущие различным вариантам. Он содержит как условные операторы, связанные с передачей управления в то или иное место исходной программы, так и линейные операции в форме вычисления логических выражений. Поэтому данный пример выбран в качестве иллюстрации для лабораторной работы № 2, а позже будет использоваться также в лабораторных работах № 3 и 4.

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

   Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются:
   • шесть ключевых слов языка (if, then, else, or, xor и and);
   • разделители: открывающая и закрывающая круглые скобки, точка с запятой;
   • знак операции присваивания;
   • идентификаторы;
   • целые десятичные константы без знака.
   Кроме перечисленных лексем распознаватель должен уметь определять и исключать из входного текста комментарии, принцип построения которых описан выше. Для выделения комментариев ключевыми символами должны быть открывающая и закрывающая фигурные скобки.
   Для перечисленных типов лексем и комментария можно построить регулярную грамматику, а затем на ее основе создать КА. Однако построенная таким образом грамматика, с одной стороны, будет элементарно простой, с другой стороны – громоздкой и малоинформативной. Поэтому можно пойти путем построения КА непосредственно по описанию лексем. Для этого не хватает только описания идентификаторов и целых десятичных констант без знака:
   • идентификатор – это произвольная последовательность малых и прописных букв латинского алфавита (от А до Z и от а до z), цифр (от 0 до 9) и знака подчеркивания (_), начинающаяся с буквы или со знака подчеркивания;
   • целое десятичное число без знака – это произвольная последовательность цифр (от 0 до 9), начинающаяся с любой цифры.
   Границами лексем для данного распознавателя будут служить пробел, знак табуляции, знаки перевода строки и возврата каретки, а также круглые скобки, открывающая фигурная скобка, точка с запятой и знак двоеточия. При этом следует помнить, что круглые скобки и точка с запятой сами по себе являются лексемами, открывающая фигурная скобка начинает комментарий, а знак двоеточия, являясь границей лексемы, в то же время является и началом другой лексемы – операции присваивания.
   В данном языке лексический анализатор всегда может однозначно определить границы лексемы, поэтому нет необходимости в его взаимодействии с синтаксическим анализатором и другими элементами компилятора.
   Рис. 2.1. Фрагмент графа переходов КА для распознавания всех лексем, кроме ключевых слов.

   Полный граф переходов КА будет очень громоздким и неудобным для просмотра, поэтому проиллюстрируем его несколькими фрагментами. На рис. 2.1 изображен фрагмент графа переходов КА, отвечающий за распознавание разделителей, комментариев, знака присваивания, переменных и констант (всех лексем входного языка, кроме ключевых слов).
   На рис. 2.2 изображен фрагмент графа переходов КА, отвечающий за распознавание ключевых слов if и then (этот фрагмент имеет ссылки на состояния, изображенные на рис. 2.1). Аналогичные фрагменты можно построить и для других ключевых слов.
   Рис. 2.2. Фрагмент графа переходов КА для ключевых слов if и then.

   На фрагментах графа переходов КА, изображенных на рис. 2.1 и 2.2, приняты следующие обозначения:
   • А– любой алфавитно-цифровой символ;
   • А(*) – любой алфавитно-цифровой символ, кроме перечисленных в скобках;
   • П– любой незначащий символ (пробел, знак табуляции, перевод строки, возврат каретки);
   • Б– любая буква английского алфавита (прописная или строчная) или символ подчеркивания (_);
   • Б(*) – любая буква английского алфавита (прописная или строчная) или символ подчеркивания (_), кроме перечисленных в скобках;
   • Ц– любая цифра от 0 до 9;
   • F – функция обработки таблицы лексем, вызываемая при переходе КА из одного состояния в другое. Обозначения ее аргументов:
   – v – переменная, запомненная при работе КА;
   – d – константа, запомненная при работе КА;
   – a – текущий входной символ КА.
   С учетом этих обозначений, полностью КА можно описать следующим образом:
   M(Q,Σ,δ,q0,F):
   Q = {H, C, G, V, D, I1, I2, T1, T2, T3, T4, E1, E2, E3, E4, O1, O2, X1, X2, X3, A1, A2, A3, F}
   Σ = А (все допустимые алфавитно-цифровые символы);
   q 0 = H;
   F = {F}.
   Функция переходов (δ) для этого КА приведена в приложении 2.
   Из начального состояния КА литеры «i», «t», «e», «o», «x» и «a» ведут в начало цепочек состояний, каждая из которых соответствует ключевому слову:
   • состояния I1, I2 – ключевому слову if;
   • состояния T1, T2, T3, T4 – ключевому слову then;
   • состояния E1, E2, E3, E4 – ключевому слову else;
   • состояния O1, O2 – ключевому слову or;
   • состояния X1, X2, X3 – ключевому слову xor;
   • состояния A1, A2, A3 – ключевому слову and.
   Остальные литеры ведут к состоянию, соответствующему переменной (идентификатору), – V. Если в какой-то из цепочек встречается литера, не соответствующая ключевому слову, или цифра, то КА также переходит в состояние V, а если встречается граница лексемы – запоминает уже прочитанную часть ключевого слова как переменную (чтобы правильно выделять такие идентификаторы, как «i» или «els», которые совпадают с началом ключевых слов).
   Цифры ведут в состояние, соответствующее входной константе, – D. Открывающая фигурная скобка ведет в состояние C, которое соответствует обнаружению комментария – из этого состояния КА выходит, только если получит на вход закрывающую фигурную скобку. Еще одно состояние – G – соответствует лексеме «знак присваивания». В него КА переходит, получив на вход двоеточие, и ожидает в этом состоянии символа «равенство».
   Состояние H – начальное состояние КА, а состояние F – его конечное состояние. Поскольку КА работает с непрерывным потоком лексем, перейдя в конечное состояние, он тут же должен возвращаться в начальное, чтобы распознавать очередную лексему. Поэтому в моделирующей программе эти два состояния можно объединить.
   На графе и при описании функции переходов не обозначено состояние «ошибка», чтобы не загромождать и без того сложный граф и функцию. В это состояние КА переходит всегда, когда получает на вход символ, по которому нет переходов из текущего состояния.
   Функция F, которой помечены дуги КА на графе и переходы в функции переходов, соответствует выполнению записи данных в таблицу лексем. Аргументы функции зависят от текущего состояния КА. В реализации программы, моделирующей функционирование КА, этой функции должны соответствовать несколько функций, вызываемые в зависимости от текущего состояния и входного символа.
   Надо отметить, что для корректной записи переменных и констант в таблицу лексем КА должен запоминать соответствующие им цепочки символов. Проще всего это делать, запоминая позицию считывающей головки КА всякий раз, когда он находится в состоянии H.
   Можно заметить, что функция переходов КА получилась довольно громоздкой, хотя и простой по своей сути (для всех ключевых слов она работает однотипно). В реализации функционирования КА проще было бы не выделять отдельные состояния для ключевых слов, а переходить всегда по обнаружению буквы на входе КА в состояние V. Тогда проверку того, является ли считанная строка ключевым словом или же идентификатором, можно было бы выполнять на момент ее записи в таблицу лексем с помощью стандартных операций сравнения строк. Граф переходов КА в таком варианте был бы намного компактнее – он выглядел бы точно так же, как фрагмент, представленный на рис. 2.1. Его можно назвать «сокращенным» графом переходов КА (или «сокращенным КА»).
   Но следует отметить, что, несмотря на большую наглядность и простоту реализации, сокращенный КА будет менее эффективным, поскольку в момент записи лексемы в таблицу он должен будет выполнять ее сравнение со всеми известными ключевыми словами (в данном случае надо определять шесть ключевых слов – следовательно, будет выполняться шесть сравнений строк). То есть такой КА будет повторно просматривать уже прочитанную часть входной цепочки, да еще и несколько раз! И хотя в явном виде в реализации сокращенного КА эта операция не присутствует, она все равно будет выполняться в вызове библиотечной функции сравнения строк.
   Итак, хотя сокращенный КА меньше по количеству состояний и проще в реализации, он является менее эффективным, чем полный КА, построенный на анализе всех входных лексем. Тем не менее оба варианта реализации КА обеспечивают построение требуемого лексического анализатора. Какой из них выбрать, решает разработчик компилятора.

Реализация лексического анализатора

Разбиение на модули
   Модули, реализующие лексический анализатор, разделены на две группы:
   • модули, программный код которых не зависит от входного языка;
   • модули, программный код которых зависит от входного языка.
   В первую группу входят модули:
   • LexElem – описывает структуру данных элемента таблицы лексем;
   • FormLab2 – описывает интерфейс с пользователем.
   Во вторую группу входят модули:
   • LexType – описывает типы входных лексем, связанные с ними наименования и текстовую информацию;
   • LexAuto – реализует функционирование КА.
   Такое разбиение на модули позволяет использовать те же самые структуры данных для организации лексического распознавателя при изменении входного языка.
   Кроме этих модулей для реализации лабораторной работы № 2 используются также программные модули (TblElem и FncTree), позволяющие работать с комбинированной таблицей идентификаторов, которые были созданы при выполнении лабораторной работы № 1. Эти два модуля, очевидно, также не зависят от входного языка.
   Кратко опишем содержание программных модулей, используемых для организации лексического анализатора.
Модуль типов лексем
   Модуль LexType в детальных комментариях не нуждается. В нем перечислены все допустимые типы лексем (тип данных TLexType), каждой из которых соответствует наименование и обозначение лексемы. Вывод наименований лексем обеспечивает функция LexTypeName, а вывод обозначений – функция LexTypeInfo. Следует отметить, что кроме перечисленных в задании лексем используется еще одна дополнительная информационная лексема (LEXSTART), обозначающая конец строки.
   Модуль LexElem описывает структуры данных элемента таблицы лексем (TLexem) и самой таблицы лексем (TLexList), а также все, что с ними связано.
Модуль структур данных таблицы идентификаторов
   Структура данных таблицы лексем содержит информацию о лексеме (поле LexInfo). В этом поле содержится тип лексемы (LexType), а также следующие данные:
   • VarInfo – ссылку на элемент таблицы идентификаторов для лексем типа «переменная»;
   • ConstVal – целочисленное значение для лексем типа «константа»;
   • szInfo – произвольная строка для информационной лексемы.
   Для лексем других типов не требуется никакой дополнительной информации.
   Следует отметить, что для лексем типа «переменная» хранится именно ссылка на таблицу идентификаторов, а не имя переменной. Именно для этого в данной лабораторной работе используются модули из лабораторной работы № 1. Для самого лексического анализатора не имеет значения, что хранить в таблице лексем – ссылку на таблицу идентификаторов со всей информацией о переменной или же только имя переменной. Но реализация лексического анализатора, при которой хранится именно ссылка на таблицу идентификаторов, чрезвычайно удобна для дальнейшей обработки данных, что будет очевидно в последующих работах (лабораторных работах № 3 и № 4). Поскольку лексический анализатор интересен не сам по себе, а в составе компилятора, такой подход принципиально важен.
   Кроме этого в структуре данных элемента таблицы лексем хранится информация о позиции лексемы в тексте входной программы:
   • iStr – номер строки, где встретилась лексема;
   • iPos – позиция лексемы в строке;
   • iAllP – позиция лексемы относительно начала входного файла.
   Эта информация будет полезна, в частности, при информировании пользователя об ошибках.
   Кроме этих данных структура содержит также:
   • четыре конструктора для создания лексем четырех разных типов:
   – CreateVar – для создания лексем типа «переменная»;
   – CreateConst – для создания лексем типа «константа»;
   – CreateInfo – для создания информационных лексем;
   – CreateKey – для создания лексем других типов;
   • деструктор Destroy для освобождения памяти, занятой лексемой (важен для информационных лексем);
   • свойства и функции для доступа к информации о лексеме.
   Хранить в структуре строку самой лексемы нет никакой необходимости (для переменных строка хранится в таблице идентификаторов, для других типов лексем она просто не нужна).
   Сама таблица лексем (тип данных TLexList) построена на основе динамического массива TList из библиотеки VCL (модуль Classes) системы программирования Delphi 5.
   Динамический массив типа TList обеспечивает все функции и данные, необходимые для хранения в памяти произвольного количества лексем (максимальное количество лексем ограничено только объемом доступной оперативной памяти). Для таблицы лексем TLexList дополнительно реализованы функции очистки таблицы, которые освобождают память, занятую лексемами, при их удалении из таблицы (функция Clear и деструктор Destroy), а также функция GetLexem и свойство Lexem, обеспечивающие удобный доступ к любой лексеме в таблице по ее индексу (порядковому номеру).
Модуль моделирования работы КА
   Модуль LexAuto, моделирующий работу КА, на основе которого построен лексический распознаватель, – самый значительный по объему программного кода. Однако по содержанию программного кода он предельно прост. Этот модуль обеспечивает функционирование полного КА, фрагменты графа переходов которого были изображены на рис. 2.1 и 2.2, а функция переходов была построена выше.
   Главной составляющей этого программного модуля является функция МакеLexList, которая непосредственно моделирует работу КА. На вход функции подается входная программа в виде списка строк (формальный параметр listFile) и таблица лексем, куда должны помещаться найденные лексемы (формальный параметр listLex). Результатом работы функции является 0, если лексический анализ выполнен без ошибок, а если ошибка обнаружена – номер строки в исходном файле, в которой она присутствует. Для более подробной информации об обнаруженной ошибке функция создает информационную лексему и помещает ее в конец таблицы лексем. Сама информационная лексема кроме текстовой информации об ошибке содержит еще дополнительную информацию о ее местонахождении в исходной программе (смещение от начала файла и длина ошибочной лексемы).
   В типе данных TAutoPos перечислены все возможные состояния КА. Перечень состояний полностью соответствует функции переходов КА.
   Реализация функции MakeLexList, несмотря на большой объем программного кода, предельно проста. Она построена на основе двух вложенных циклов (первый – по строкам входного списка, второй – по символам в текущей строке), внутри которых находятся два уровня вложенных оператора выбора типа case – типичный подход к моделированию функционирования КА. Внешний оператор case выполняется по всем возможным состояниям автомата, а case второго уровня – по допустимым входным символам в каждом состоянии.
   Можно обратить внимание на шесть вспомогательных функций:
   • AddVarToList – добавление лексемы типа «переменная» в таблицу лексем;
   • AddVarKeyToList – добавление лексем типа «переменная» и типа «разделитель» в таблицу лексем;
   • AddConstToList – добавление лексемы типа «константа» в таблицу лексем;
   • AddConstKeyToList – добавление лексем типа «константа» и типа «разделитель» в таблицу лексем;
   • AddKeyToList – добавление лексемы типа «ключевое слово» или «разделитель» в таблицу лексем;
   • Add2KeysToList – добавление лексем типа «ключевое слово» и «разделитель» в таблицу лексем подряд.
   Эти функции, по сути, являются реализацией функции, которая на графе переходов КА была обозначена F.
   Еще две вспомогательные функции служат для упрощения кода. Они выполняют часто повторяющиеся действия в состояниях автомата, которые связаны со средними символами ключевых слов (в функции переходов эти состояния обозначены T2, T3, E2, E3, X2 и A2) и завершающими символами ключевых слов (в функции переходов эти состояния обозначены I2, T4, E4, O2, X3 и A3).
   Построенный лексический анализатор обнаруживает три типа ошибок:
   • неверный символ в лексеме (например, сочетания «2a» или «:6» будут признаны неверными символами в лексемах);
   • незакрытый комментарий (присутствует открывающая фигурная скобка, но отсутствует соответствующая ей закрывающая);
   • незавершенная лексема (в данном входном языке это может быть только символ «:» в конце входной программы, который будет воспринят как начало незавершенной лексемы «:=»).
   Остальные ошибки входного языка должен обнаруживать синтаксический анализатор.
   В качестве еще одной особенности реализации можно отметить, что переход с одной строки входного списка на другую должен восприниматься как граница текущей лексемы, так как одна лексема не может быть разбита на две строки – именно это и реализовано в конце цикла по символам текущей строки.

Текст программы распознавателя

   Кроме перечисленных выше модулей необходим еще модуль, обеспечивающий интерфейс с пользователем. Как и в лабораторной работе № 1, этот модуль (FormLab2) реализует графическое окно TLab2Form на основе класса TForm библиотеки VCL и включает в себя две составляющие:
   • файл программного кода (файл FormLab2.pas);
   • файл описания ресурсов пользовательского интерфейса (файл FormLab2.dfm).
   Кроме описания интерфейсной формы и ее органов управления модуль FormLab2 содержит переменную (listLex), в которую записывается ссылка на таблицу лексем.
   Интерфейсная форма, описанная в модуле, содержит следующие основные органы управления:
   • многостраничную вкладку (PageControll) с двумя закладками (SheetFile и SheetLexems) под названиями «Исходный файл» и «Таблица лексем» соответственно;
   • на закладке SheetFilе:
   – поле ввода имени файла (EditFile), кнопка выбора имени файла из каталогов файловой системы (BtnFile), кнопка чтения файла (BtnLoad);
   – многострочное поле для отображения прочитанного файла (Listldents);
   • на закладке SheetLexems:
   – сетка (GridLex) с тремя колонками для отображения данных о прочитанных лексемах;
   • кнопка завершения работы с программой (BtnExit).
   Внешний вид двух закладок этой формы приведен на рис. 2.3 и 2.4.
   Рис. 2.3. Внешний вид первой закладки интерфейсной формы для лабораторной работы № 2.

   Рис. 2.4. Внешний вид второй закладки интерфейсной формы для лабораторной работы № 2.

   Чтение содержимого входного файла организовано точно так же, как в лабораторной работе № 1.
   После чтения файла создается таблица лексем (ссылка на нее запоминается в переменной listLex) и вызывается функция MakeLexList, результат работы которой помещается во временную переменную iErr.
   Если обнаружена ошибка, пользователю выдается сообщение об этом и указатель в списке строк позиционируется на место, где обнаружена ошибка.
   Если ошибок не обнаружено, то на основании считанной таблицы лексем listLex заполняется сетка GridLex, которая очень удобна для наглядного представления таблицы лексем:
   • первая колонка – порядковый номер лексемы;
   • вторая колонка – тип лексемы (ее внешний вид);
   • третья колонка – информация о лексеме.
   Полный текст программного кода модуля интерфейса с пользователем приведен в листинге П2.4 в приложении 2, а описание ресурсов пользовательского интерфейса – в листинге П2.5 в приложении 2.
   Полный текст всех программных модулей, реализующих рассмотренный пример для лабораторной работы № 2, приведен в приложении 2.

Выводы по проделанной работе

   В результате лабораторной работы № 2 построен лексический анализатор на основе конечного автомата. Построенный лексический анализатор позволяет выделять в тексте исходной программы лексемы следующих типов:
   • ключевые слова (if, then, else, or, xor и and);
   • идентификаторы (при этом в именах идентификаторов различаются строчные и прописные английские буквы);
   • знак операции присваивания;
   • целые десятичные константы без знака;
   • разделители (круглые скобки и точка с запятой).
   Лексический анализатор игнорирует в тексте входной программы пробелы, знаки табуляции и переводы строки, а также комментарии, выделенные фигурными скобками.
   В случае обнаружения неверной лексемы (например числа, содержащего букву), незакрытого комментария или незавершенной лексемы (такой лексемой может быть только символ «:») лексический анализатор выдает сообщение об ошибке и прекращает дальнейший анализ. При наличии нескольких неверных лексем анализатор обнаруживает только первую из них.
   Результатом выполнения лексического анализа является структура данных, которая представляет таблицу лексем. Построенный лексический анализатор предназначен для подготовки данных, необходимых для выполнения следующих лабораторных работ, связанных с синтаксическим анализом и генерацией кода.

Лабораторная работа № 3
Построение простейшего дерева вывода

Цель работы

   Цель работы: изучение основных понятий теории грамматик простого и операторного предшествования, ознакомление с алгоритмами синтаксического анализа (разбора) для некоторых классов КС-грамматик, получение практических навыков создания простейшего синтаксического анализатора для заданной грамматики операторного предшествования.

Краткие теоретические сведения

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

   По иерархии грамматик Хомского выделяют четыре основные группы языков (и описывающих их грамматик) [1, 3, 4, 7]. При этом наибольший интерес представляют регулярные и контекстно-свободные (КС) грамматики и языки. Они используются при описании синтаксиса языков программирования. С помощью регулярных грамматик можно описать лексемы языка – идентификаторы, константы, служебные слова и прочие. На основе КС-грамматик строятся более крупные синтаксические конструкции: описания типов и переменных, арифметические и логические выражения, управляющие операторы и, наконец, полностью вся программа на входном языке.
   Входные цепочки регулярных языков распознаются с помощью конечных автоматов (КА). Они лежат в основе сканеров, выполняющих лексический анализ и выделение слов в тексте программы на входном языке. Результатом работы сканера является преобразование исходной программы в список или таблицу лексем. Дальнейшую ее обработку выполняет другая часть компилятора – синтаксический анализатор. Его работа основана на использовании правил КС-грамматики, описывающих конструкции исходного языка.
   Синтаксический анализатор (синтаксический разборщик) – это часть компилятора, которая отвечает за выявление и проверку синтаксических конструкций входного языка. В задачу синтаксического анализатора входит:
   • найти и выделить синтаксические конструкции в тексте исходной программы;
   • установить тип и проверить правильность каждой синтаксической конструкции;
   • представить синтаксические конструкции в виде, удобном для дальнейшей генерации текста результирующей программы.
   Синтаксический анализатор – это основная часть компилятора на этапе анализа. Без выполнения синтаксического разбора работа компилятора бессмысленна, в то время как лексический разбор, в принципе, не является обязательной фазой компиляции. Все задачи по проверке синтаксиса входного языка могут быть решены на этапе синтаксического разбора. Лексический анализатор только позволяет избавить сложный по структуре синтаксический анализатор от решения примитивных задач по выявлению и запоминанию лексем исходной программы.
   Выходом лексического анализатора является таблица лексем. Эта таблица образует вход синтаксического анализатора, который исследует только один компонент каждой лексемы – ее тип. Остальная информация о лексемах используется на более поздних фазах компиляции при семантическом анализе, подготовке к генерации и генерации кода результирующей программы.
   Синтаксический анализатор воспринимает выход лексического анализатора и разбирает его в соответствии с грамматикой входного языка. Однако в грамматике входного языка программирования обычно не уточняется, какие конструкции следует считать лексемами. Примерами конструкций, которые обычно распознаются во время лексического анализа, служат ключевые слова, константы и идентификаторы. Но эти же конструкции могут распознаваться и синтаксическим анализатором. На практике не существует жесткого правила, определяющего, какие конструкции должны распознаваться на лексическом уровне, а какие надо оставлять синтаксическому анализатору. Обычно это определяет разработчик компилятора исходя из технологических аспектов программирования, а также синтаксиса и семантики входного языка. Принципы взаимодействия лексического и синтаксического анализаторов были рассмотрены в лабораторной работе № 2.
   В основе синтаксического анализатора лежит распознаватель текста исходной программы, построенный на основе грамматики входного языка. Как правило, синтаксические конструкции языков программирования могут быть описаны с помощью КС-грамматик; реже встречаются языки, которые могут быть описаны с помощью регулярных грамматик.
   Главную роль в том, как функционирует синтаксический анализатор и какой алгоритм лежит в его основе, играют принципы построения распознавателей для КС-языков. Без применения этих принципов невозможно выполнить эффективный синтаксический разбор предложений входного языка.

Проблема распознавания цепочек КС-языков

   Взаимодействие лексического и синтаксического анализаторов рассматривалось в предыдущей лабораторной работе, здесь же будут рассмотрены алгоритмы, лежащие в основе синтаксического анализа. Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода. Одним из способов такого представления является дерево синтаксического разбора.
   Основой для построения распознавателей КС-языков являются автоматы с магазинной памятью – МП-автоматы – односторонние недетерминированные распознаватели с линейно-ограниченной магазинной памятью (полная классификация распознавателей приведена в [1, 4, 3, 7]). Поэтому важно рассмотреть, как функционирует МП-автомат и как для КС-языков решается задача разбора – построение распознавателя языка на основе заданной грамматики. Далее рассмотрены технические аспекты, связанные с реализацией синтаксических анализаторов.
   МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и нетерминальные символы грамматики языка). Переход МП-автомата из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.
   При выполнении перехода МП-автомата из одной конфигурации в другую из стека удаляются верхние символы, соответствующие условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при которых входной символ игнорируется (и тем самым он будет входным символом при следующем переходе). Эти переходы называются ^-переходами. Если при окончании цепочки автомат находится в одном из заданных конечных состояний, а стек пуст, цепочка считается принятой (после окончания цепочки могут быть сделаны Х-переходы). Иначе цепочка символов не принимается.
   МП-автомат называется недетерминированным, если при одной и той же его конфигурации возможен более чем один переход. В противном случае (если из любой конфигурации МП-автомата по любому входному символу возможно не более одного перехода в следующую конфигурацию) МП-автомат считается детерминированным (ДМП-автоматом). ДМП-автоматы задают класс детерминированных КС-языков, для которых существуют однозначные КС-грамматики. Именно этот класс языков лежит в основе синтаксических конструкций всех языков программирования, так как любая синтаксическая конструкция языка программирования должна допускать только однозначную трактовку [1–4, 7].
   По произвольной КС-грамматике
   всегда можно построить недетерминированный МП-автомат, который допускает цепочки языка, заданного этой грамматикой [1–3, 7]. А на основе этого МП-автомата можно создать распознаватель для заданного языка.
   Однако при алгоритмической реализации функционирования такого распознавателя могут возникнуть проблемы. Дело в том, что построенный МП-автомат будет, как правило, недетерминированным, а для МП-автоматов, в отличие от обычных КА, не существует алгоритма, который позволял бы преобразовать произвольный МП-автомат в ДМП-автомат. Поэтому программирование функционирования МП-автомата – нетривиальная задача. Если моделировать его функционирование по шагам с перебором всех возможных состояний, то может оказаться, что построенный для тривиального МП-автомата алгоритм никогда не завершится на конечной входной цепочке символов при определенных условиях. Примеры таких МП-автоматов можно найти в [1, 3, 7].
   Поэтому для построения распознавателя для языка, заданного КС-грамматикой, рекомендуется воспользоваться соответствующим математическим аппаратом и одним из существующих алгоритмов.

Виды распознавателей для КС-языков

   Существуют несложные преобразования КС-грамматик, выполнение которых гарантирует, что построенный на основе преобразованной грамматики МП-автомат можно будет промоделировать за конечное время на основе конечных вычислительных ресурсов. Описание сути и алгоритмов этих преобразований можно найти в [1, 3, 7].
   Эти преобразования позволяют строить два основных типа простейших распознавателей:
   • распознаватель с подбором альтернатив;
   • распознаватель на основе алгоритма «сдвиг-свертка».
   Работу распознавателя с подбором альтернатив можно неформально описать следующим образом: если на верхушке стека МП-автомата находится нетерминальный символ A, то его можно заменить на цепочку символов а при условии, что в грамматике языка есть правило A → а, не сдвигая при этом считывающую головку автомата (этот шаг работы называется «подбор альтернативы»); если же на верхушке стека находится терминальный символ a, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется «выброс»). Данный МП-автомат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида A → а, тогда функция δ(q,λ,A) будет содержать более одного следующего состояния – у МП-автомата будет несколько альтернатив.
   Решение о том, выполнять ли на каждом шаге работы МП-автомата выброс или подбор альтернативы, принимается однозначно. Моделирующий алгоритм должен обеспечивать выбор одной из возможных альтернатив и хранение информации о том, какие альтернативы на каком шаге уже были выбраны, чтобы иметь возможность вернуться к этому шагу и подобрать другие альтернативы.
   Распознаватель с подбором альтернатив является нисходящим распознавателем: он читает входную цепочку символов слева направо и строит левосторонний вывод. Название «нисходящий» дано ему потому, что дерево вывода в этом случае следует строить сверху вниз, от корня к концевым вершинам («листьям»).[3]
   

notes

Примечания

1

   Молчанов А. Ю. Системное программное обеспечение: Учебник для вузов. – СПб.: Питер, 2003. – 396 с.

2

   Программные модули, реализующие таблицы символов, построены таким образом, что в зависимости от условий компиляции они могут либо различать, либо не различать прописные и строчные буквы. Условие компиляции реализовано через макрокоманды компилятора Delphi 5 в функции Upper в модуле TblElem (листинг П3.1, приложение 3). О принципах, на основе которых выполняются макрокоманды и условная компиляция, можно подробно узнать в [7, 13, 23, 25, 28, 32].

3

   В отличие от обычных деревьев, корень у синтаксического дерева вывода находится вверху, а листья – внизу.
Купить и читать книгу за 133 руб.

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