УЗБЕКСКОЕ АГЕНТСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

 

 

 

 

 

 

 

 

 

 

 

Методическое пособие для лабораторных занятий

По предмету

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

 

 

 

Ташкент 2008.

Л.Т. Марышева, А.Эргашев «Системное программное обеспечение»

 

 

 

    Данное методическое пособие предназначено для студентов специальности информационные технологии изучающих предмет «Системное программное обеспечение».

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

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

 

 

Темы

часы

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

4

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

4

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

4

Лабораторная работа №4  Генерация и оптимизация объектного кода

4

Всего

16

 

                  

 

 

 

   Рецензенты:

 

 

Краткое содержание

Введение......................................................................................................................................... 10

Лабораторная работа № 1

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

Лабораторная работа № 2

Проектирование лексического анализатора   ....................................................................... 39

Лабораторная работа № 3

Построение простейшего дерева вывода............................................................................... 60

Лабораторная работа № 4

Генерация и оптимизация объектного кода.......................................................................... 95

Курсовая работа   ...................................................................................................................... 133

Приложение 1

Функция переходов конечного автомата

для лабораторной работы № 2  .............................................................................................. 181

Приложение 2

Функция переходов конечного автомата

для курсовой работы................................................................................................................. 184

Приложение 3

Тексты программных модулей для курсовой работы..................................................... 190

Приложение 4

Примеры входных и результирующих файлов

для курсовой работы................................................................................................................. 268

Литература    .............................................................................................................................. 279

Алфавитный указатель……………………………………………………………..282

 

Содержание

Введение ................................................................................................... 10

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

ЛАБОРАТОРНАЯ РАБОТА № 1

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

Цель работы   ............................................................................................................................ 13

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

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

Принципы организации таблиц идентификаторов    ...................................................... 14

Простейшие методы построения таблиц

идентификаторов............................................................................................................ 15

Построение таблиц идентификаторов по методу

бинарного дерева   ........................................................................................................ 17

Хэш-функции и хэш-адресация......................................................................................... 19

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

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

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

идентификаторов............................................................................................................ 25

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

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

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

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

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

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

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

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

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

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

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

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

ЛАБОРАТОРНАЯ РАБОТА № 2

Проектирование лексического анализатора   ........................................ 39

Цель работы   ..................................................... ,.................................................................... 39

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

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

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

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

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

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

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

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

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

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

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

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

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

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

входного языка............................................................................................................... 49

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

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

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

ЛАБОРАТОРНАЯ РАБОТА № 3

Построение простейшего дерева вывода .............................................. 60

Цель работы   ............................................................................................................................ 60

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

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

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

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

Построение синтаксического анализатора   .................................................................... 65

Грамматики предшествования   ....................................................................................... 69

Алгоритм «сдвиг-свертка» для грамматик операторного
предшествования........................................................................................................... 74

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

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

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

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

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

Варианты исходных грамматик......................................................................................... 78

Исходные грамматики и типы допустимых лексем   ....................................................... 79

Примечание    .................................................................................................................... 80

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

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

Построение матрицы операторного предшествования   ............................................... 81

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

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

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

ЛАБОРАТОРНАЯ РАБОТА № 4

Генерация и оптимизация объектного кода .......................................... 95

Цель работы   ........................................................................................................................... 95

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

Общие принципы генерации кода..................................................................................... 95

Синтаксически управляемый перевод............................................................................. 97

Способы внутреннего представления программ............................................................ 99

Многоадресный коде неявно именуемым результатом (триады)  .... 100

Схемы СУ-перевода   ..................................................................................................... 101

Общие принципы оптимизации кода.............................................................................. 103

Принципы оптимизации линейных участков   .............................................................. 107

Свертка объектного кода   ............................................................................................. 107

Исключение лишних операций....................................................................................... 110

Общий алгоритм генерации и оптимизации объектного кода...................................... 112

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

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

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

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

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

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

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

Построение схем СУ-перевода  ..................................................................................... 115

Пример генерации списка триад.................................................................................... 118

Реализация генератора списка триад............................................................................. 120

Текст программы генератора списка триад   ............................................................... 128

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

Курсовая работа  .................................................................................... 133

Цель работы   ............................................................................................ ,.......................... 133

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

Требования к содержанию пояснительной записки   .......................................................... 135

Задание на курсовую работу   .............................................................................................. 136

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

Порядок оценки результатов работы   ............................................................................... 140

Рекомендации по выполнению работы................................................................................. 142

Пример выполнения курсовой работы   ............................................................................. 143

Задание для примера выполнения работы  ................................................................... 144

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

Описание выбранного способа организации

таблицы идентификаторов.......................................................................................... 146

Описание лексического анализатора........................................................................... . 146

Описание синтаксического анализатора......................................................................... 150

Внутреннее представление программы и генерация кода   ........................................ 158

Описание используемого метода оптимизации    .......................................................... 171

Текст программы компилятора...................................................................................... 173

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

ПРИЛОЖЕНИЕ 1

Функция переходов конечного автомата

для лабораторной работы № 2 .............................................................. isi

ПРИЛОЖЕНИЕ 2

Функция переходов конечного автомата

для курсовой работы............................................................................... ^

ПРИЛОЖЕНИЕ 3

Тексты программных модулей для курсовой работы .. 19С

Модуль структуры данных для таблицы идентификаторов  ............................................ 19(

Модуль таблицы идентификаторов на основе хэш-адресации

в комбинации с бинарным деревом.................................................................................... 19J

Модуль описания всех типов лексем    ......................................................................... 19{

Модуль описания структуры элементов таблицы лексем   ....................................... 20(

Модуль заполнения таблицы лексем по исходному

тексту программы   ..................................................................................................... 20С

Модуль описания матрицы предшествования и правил

исходной грамматики................................................................................................... 211

Модуль описания структур данных синтаксического анализатора

и реализации алгоритма «сдвиг-свертка»   ...................................................................... 21 f

Модуль описания допустимых типов триад................................................................. 22!

Модуль вычисления значений триад при свертке

объектного кода........................................................................................................... 22'

Модуль описания структур данных триад.......................................................................... 22!

Модуль, реализующий алгоритмы оптимизации списков триад....................................... 23

Модуль создания списка триад на основе дерева разбора......................................... 23'

Модуль построения ассемблерного кода по списку триад   ...................................... 24<

Модуль интерфейса с пользователем........................................................................... 25!

ПРИЛОЖЕНИЕ 4

Примеры входных и результирующих файлов

для курсовой работы   ............................................................................ 26

Пример 1. Вычисление факториала   ................................................................................... 26

Пример 2. Иллюстрация работы функций оптимизации  .................................................. 27

Литература .............................................................................................. 27

Основная литература   .......................................................................................................... 27

Дополнительная литература   ............................................................................................... 27

Алфавитный указатель...................................................................................................... 28

Введение

Эта книга является логическим продолжением и дополнением учебника «Си­стемное программное обеспечение»1, вышедшего в свет в 2003 году. Главной це­левой аудиторией книги «Системное программное обеспечение» были студенты технических вузов, обучающиеся по специальности «Вычислительные машины, комплексы, системы и сети» и родственным с ней направлениям, поэтому мате­риал книги был подобран исходя из требований стандарта этой специальности для курса «Системное программное обеспечение». Программа этого курса пре­дусматривает практические занятия в виде лабораторных работ, а'также выпол­нение курсовой работы по итогам курса. Поэтому автор посчитал разумным доба­вить к сухим теоретическим выкладкам необходимый живой практический мате­риал, проиллюстрированный конкретными примерами реализации. Некоторая часть материала, касающаяся базовых теоретических основ, в этой книге перекликается с уже опубликованным материалом книги «Системное про­граммное обеспечение». Но автор посчитал необходимым кратко привести здесь только те теоретические выкладки, без которых невозможно построить логиче­ское изложение материала. Подразумевается, что читатели уже знакомы с осно­вами курса «Системное программное обеспечение», поэтому в соответствующих местах всегда даются ссылки на литературу — в основном на базовые книги курса [1-3, 7], а также на книги по курсу «Операционные системы» [3, 5, 6]. Поскольку оба курса («Системное программное обеспечение» и «Операционные системы») тесно взаимосвязаны, читателям этой книги необходимо знать их основы, чтобы понять и практически применять изложенный в книге материал (совсем недавно, в старой редакции образовательного стандарта, оба этих курса составляли единое целое [3]).

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

Для понимания практических примеров необходимо знание языка программиро­вания Object Pascal и хотя бы общее представление о системе программирования Delphi, а также знание языка ассемблера процессоров типа Intel 80x86. В ряде слу­чаев для сравнения и понимания примеров синтаксических конструкций реко­мендуется знать язык программирования С. Соответствующие сведения можно почерпнуть в дополнительной литературе, приведенной в конце книги [13, 23-25,28,31,32,37,39,41,44].

Все практические примеры созданы автором в системе программирования Delphi 5 на языке Object Pascal с использованием примитивных классов из библиотеки VCL. Но автор приложил все усилия, чтобы они не были привязаны ни к версии системы программирования, ни к особенностям исходного языка. Поэтому жела­ющие без проблем могут перенести их под любую версию Delphi, а при необходи­мости переписать, например па C++, для чего требуются только самые элемен­тарные знания языка.

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

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

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

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

Приводимый в книге практический материал не претендует на полноту охвата всего курса «Системное программное обеспечение». Автор считает необходимым дополнить его работами по программированию параллельных взаимодействую­щих процессов [3, 5], а также методами разработки программного обеспечения в распределенных системах (по технологиям построения систем «клиент-сервер» и многоуровневой архитектуре [7]). Автор надеется, что ему удастся в ближай­шее время подготовить соответствующий материал.

ЛАБОРАТОРНАЯ РАБОТА № 1

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

Цель работы

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

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

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

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

Набор характеристик, соответствующий каждому элементу исходной программы, зависит от типа этого элемента, от его смысла (семантики) и, соответственно, от той роли, которую он исполняет в исходной и результирующей программах. В каж­дом конкретном случае этот набор характеристик может быть свой в зависимости от синтаксиса и семантики входного языка, от архитектуры целевой вычислитель­ной системы и от структуры компилятора. Но есть типовые характеристики, ко­торые чаще всего присущи тем или иным элементам исходной программы. На­пример для переменной — это ее тип и адрес ячейки памяти, для константы — ее значение, для функции — количество и типы формальных аргументов, тип воз­вращаемого результата, адрес вызова кода функции. Более подробную информа­цию о характеристиках элементов исходной программы, их анализе и использо­вании можно найти в [1, 3, 7].

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

Имя каждого элемента должно быть уникальным. Многие современные языки программирования допускают совпадения (не уникальность) имен переменных и функций в зависимости от их области видимости и других условий исходной программы. В этом случае уникальность имен должен обеспечивать сам компи­лятор — о том, как решается эта проблема, можно узнать в [1-3, 7], здесь же бу­дем считать, что имена элементов исходной программы всегда являются уникаль­ными.

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

Принципы организации таблиц идентификаторов

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

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

□     простые и упорядоченные списки;

□     бинарное дерево;

а  хэш-адресация с рехэшированием; Q   хэш-адресация по методу цепочек;

□   комбинация хэш-адресации со списком или бинарным деревом.

Далее будет дано краткое описание всех вышеперечисленных способов органи­зации таблиц идентификаторов. Более подробную информацию можно найти в [3,7].

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

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

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

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

Алгоритм логарифмического поиска заключается в следующем: искомый символ сравнивается с элементом (N+ 1)/2 в середине таблицы; если этот элемент не является искомым, то мы должны просмотреть только блок элементов, пронуме­рованных от 1 до (JV + 1)/2 - 1, или блок элементов от (N + 1)/2 + 1 до JVb зависи­мости от того, меньше или больше искомый элемент того, с которым его сравни­ли. Затем процесс повторяется над нужным блоком в два раза меньшего размера. Так продолжается до тех пор, пока либо искомый элемент не будет найден, либо алгоритм не дойдет до очередного блока, содержащего один или два элемента (с которыми можно выполнить прямое сравнение искомого элемента).

Так как на каждом шаге число элементов, которые могут содержать искомый элемент, сокращается в два раза, максимальное число сравнений равно 1 + log2 N. Тогда время поиска элемента в таблице идентификаторов можно оценить как ТП = 0(log2 N). Для сравнения: при N = 128 бинарный поиск требует самое боль­шее 8 сравнений, а поиск в неупорядоченной таблице — в среднем 64 сравне­ния. Метод называют «бинарным поиском», поскольку на каждом шаге объем рассматриваемой информации сокращается в два раза, а «логарифмическим» — поскольку время, затрачиваемое на поиск нужного элемента в массиве, имеет логарифмическую зависимость от общего количества элементов в нем. Недостатком логарифмического поиска является требование упорядочивания таблицы идентификаторов. Так как массив информации, в котором выполняется поиск, должен быть упорядочен, время его заполнения уже будет зависеть от чис­ла элементов в массиве. Таблица идентификаторов зачастую просматривается компилятором еще до того, как она заполнена, поэтому требуется, чтобы условие упорядоченности выполнялось на всех этапах обращения к ней. Следовательно, для построения такой таблицы можно пользоваться только алгоритмом прямого упорядоченного включения элементов.

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

Гд = 0(Nlog2 N) + k-O(N).

Здесь k — некоторый коэффициент, отражающий соотношение между времена­ми, затрачиваемыми компьютером на выполнение операции сравнения и опера­ции переноса данных.

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

Построение таблиц идентификаторов по методу бинарного дерева

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

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

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

1.            Выбрать очередной идентификатор из входного потока данных. Если очеред­ного идентификатора нет, то построение дерева закончено.

2.            Сделать текущим узлом дерева корневую вершину.

3.            Сравнить имя очередного идентификатора с именем идентификатора, содер­жащегося в текущем узле дерева.

4.            Если имя очередного идентификатора меньше, то перейти к шагу 5, если рав­но — прекратить выполнение алгоритма (двух одинаковых идентификаторов быть не должно!), иначе — перейти к шагу 7.

5.            Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе — перейти к шагу 6.

6.            Создать новую вершину, поместить в нее информацию об очередном иденти­фикаторе, сделать эту новую вершину левой вершиной текущего узла и вер­нуться к шагу 1.

7.            Если у текущего узла существует правая вершина, то сделать ее текущим уз­лом и вернуться к шагу 3, иначе — перейти к шагу 8.

8.            Создать новую вершину, поместить в нее информацию об очередном иденти­фикаторе, сделать эту новую вершину правой вершиной текущего узла и вер— v-нуться к шагу 1.

Рассмотрим в качестве примера последовательность идф^фидатрдов, G*,, Щ, W22; КЫЙ
Е, А12, ВС, F. На рис. 1.1 проиллюстрирован весь процесс тюстшщ^Я^ЩЩЩтцЦх,,,!уг­
рева для этой последовательности идентификаторов.                                   '  '    г Tii'Hl^e&e

Рис. 1.1. Заполнение бинарного дерева для последовательности идентификаторов

Ga, D1, М22, Е, А12, ВС, F

Поиск элемента в дереве выполняется по алгоритму, схожему с алгоритмом за­полнения дерева:

1.            Сделать текущим узлом дерева корневую вершину.

2.            Сравнить имя искомого идентификатора с именем идентификатора, содержа­щимся в текущем узле дерева.

3.            Если имена совпадают, то искомый идентификатор найден, алгоритм завер­шается, иначе надо перейти к шагу 4.

4.            Если имя очередного идентификатора меньше, то перейти к шагу 5, иначе — перейти к шагу 6.

5.            Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе — искомый идентификатор не найден, алгоритм завершается.

6.            Если у текущего узла существует правая вершина, то сделать ее текущим уз­лом и вернуться к шагу 2, иначе — искомый идентификатор не найден, алго­ритм завершается.

Для данного метода число требуемых сравнений и форма получившегося дерева зависят от того порядка, в котором поступают идентификаторы. Например, если в рассмотренном выше примере вместо последовательности идентификаторов Ga, D1, М22, Е, А12, ВС, F взять последовательность А12, ВС, Dl, E, F, Ga, M22, то дерево выродит­ся в упорядоченный однонаправленный связный список. Эта особенность являет­ся недостатком данного метода организации таблиц идентификаторов. Другими недостатками метода являются: необходимость хранить две дополнительные ссыл­ки на левую и правую ветви в каждом элементе дерева и работа с динамическим выделением памяти при построении дерева.

Если предположить, что последовательность идентификаторов в исходной про­грамме является статистически неупорядоченной (что в целом соответствует дей­ствительности), то можно считать, что построенное бинарное дерево будет невы­рожденным. Тогда среднее время на заполнение дерева (Т') и на поиск элемента в нем (Ти) можно оценить следующим образом [3, 7]:

Гл = A/-0(log2JV);

r„ = 0(log2iV).

Несмотря на указанные недостатки, метод бинарного дерева является довольно удачным механизмом для организации таблиц идентификаторов. Он нашел свое применение в ряде компиляторов. Иногда компиляторы строят несколько различ­ных деревьев для идентификаторов разных типов и разной длины [1, 2, 3, 7].

Хэш-функции и хэш-адресация

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

Хэш-функцией F называется некоторое отображение множества входных элемен­тов R на множество целых неотрицательных чисел Z: F(r) = n,re R, n e Z. Сам тер­мин «хэш-функция» происходит от английского термина «hash function» (hash — «мешать», «смешивать», «путать»).

Множество допустимых входных элементов R называется областью определе­ния хэш-функции. Множеством значений хэш-функции F называется подмно­жество М из множества целых неотрицательных чисел Z: М с Z, содержащее все возможные значения, возвращаемые функцией F: VrlR: F(r) е М и Mm е М: Зге R: F(r) = m. Процесс отображения области определения хэш-функции на множество значений называется хэшированием.

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

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

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

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

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

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

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

Для решения проблемы коллизии можно использовать много способов. Одним из них является метод рехэширования (или расстановки). Согласно этому методу, если для элемента А адрес п0 = h(A), вычисленный с помощью хэш-функции h, указывает па уже занятую ячейку, то необходимо вычислить значение функции п\ = ЬХ(А) и проверить занятость ячейки по адресу пх. Если и она занята, то вы­числяется значение h2(A), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h:(A) не совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет — выдается информация об ошибке размещения идентификатора в таблице. Тогда поиск элемента А в таблице идентификаторов, организованной таким об­разом, будет выполняться по следующему алгоритму:

1.            Вычислить значение хэш-функции п = h(A) для искомого элемента А.

Если ячейка по адресу п пустая, то элемент не найден, алгоритм завершен, иначе необходимо сравнить имя элемента в ячейке п с именем искомого элемента Л. Если они совпадают, то элемент найден и алгоритм завершен, иначе i := 1 и перейти к шагу 3. 3. Вычислить п. = h;(A). Если ячейка по адресу и. пустая или п = я., то элемент не найден и алгоритм завершен, иначе — сравнить имя элемента в ячейке п. с име­нем искомого элемента Л. Если они совпадают, то элемент найден и алгоритм завершен, иначе i := i + 1 и повторить шаг3.

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

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

Для организации таблицы идентификаторов по методу рехэширования необходи­мо определить все хэш-функции hi для всех г. Чаще всего функции ht определяют как некоторые модификации хэш-функции h. Например, самым простым методом вычисления функции hs(A) является ее организация в виде /г,.(Л) = (h(A) + р;) mod JVm, гдер; — некоторое вычисляемое целое число, а Nm — максимальное значе­ние из области значений хэш-функции h. В свою очередь, самым простым подхо­дом здесь будет положить;?, = i. Тогда получаем формулу /г,(Л) = (h(A) + i) mod Nm. В этом случае при совпадении значений хэш-функции для каких-либо элементов поиск свободной ячейки в таблице начинается последовательно от текущей по­зиции, заданной хэш-функцией h(A).

Этот способ нельзя признать особенно удачным: при совпадении хэш-адресов элементы в таблице начинают группироваться вокруг них, что увеличивает чис­ло необходимых сравнений при поиске и размещении. Но даже такой примитив­ный метод рехэширования является достаточно эффективным средством органи­зации таблиц идентификаторов при неполном заполнении таблицы. Среднее время на помещение одного элемента в таблицу и на поиск элемента в таблице можно снизить, если применить более совершенный метод рехэширо­вания. Одним из таких методов является использование в качестве р. для функ­ции /г;(Л) = (h(A) + p) mod Nm последовательности псевдослучайных целых чи­сел pvpit ...,рк. При хорошем выборе генератора псевдослучайных чисел длина последовательности k - Nm.

Существуют и другие методы организации функций рехэширования ht(A), осно­ванные на квадратичных вычислениях или, например, на вычислении произведе­ния по формуле: /г,(Л) = (h(A)N-i) mod N'm, тц,еЫ'т — ближайшее простое число, мень­шее Nm. В целом рехэширование позволяет добиться неплохих результатов для эф­фективного поиска элемента в таблице (лучших, чем бинарный поиск и бинарное дерево), но эффективность метода сильно зависит от заполненности таблицы иден­тификаторов и качества используемой хэш-фуикции — чем реже возникают коллизии, тем выше эффективность метода. Требование неполного заполнения табли­цы ведет к неэффективному использованию объема доступной памяти.

Оценки времени размещения и поиска элемента в таблицах идентификаторов при использовании различных методов рехэширования можно найти в [1, 3, 7].

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

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

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

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

1. Во все ячейки хэш-таблицы поместить пустое значение, таблица идентифика­торов пуста, переменная FreePtr (указатель первой свободной ячейки) указы­вает на начало таблицы идентификаторов.

2.            Вычислить значение хэш-функции п для нового элемента А. Если ячейка хэш-таблицы по адресу п пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе перейти к шагу 3.

3.            Выбрать из хэш-таблицы адрес ячейки таблицы идентификаторов т и перей­ти к шагу 4.

4.            Для ячейки таблицы идентификаторов по адресу т проверить значение поля ссылки. Если оно пустое, то записать в него адрес из переменной FreePtr и пе­рейти к шагу 5; иначе выбрать из поля ссылки новый адрес т и повторить шаг 4.

5.            Добавить в таблицу идентификаторов новую ячейку, записать в нее информа- ' цию для элемента Л (поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки. Если больше нет идентифи­каторов, которые надо поместить в таблицу, то выполнение алгоритма закон­чено, иначе перейти к шагу 2.

Поиск элемента в таблице идентификаторов, организованной таким образом, бу­дет выполняться по следующему алгоритму:

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

2.           Сравнить имя элемента в ячейке таблицы идентификаторов по адресу т с име­нем искомого элемента А. Если они совпадают, то искомый элемент найден и алгоритм завершен, иначе перейти к шагу 3.

3.           Проверить значение поля ссылки в ячейке таблицы идентификаторов по ад­ресу т. Если оно пустое, то искомый элемент не найден и алгоритм завершен; иначе выбрать из поля ссылки адрес т и перейти к шагу 2.

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

На рис. 1.2 проиллюстрировано заполнение хэш-таблицы и таблицы идентифи-каторов для ряда идентификаторов: AvA2iAyA4,A5 при условии, что А(Л,) = h(A2) = = h(A5) = щ, /г(Л3) = п2; h(A4) = nA. После размещения в таблице для поиска иден­тификатора А, потребуется одно сравнение, для А2 — два сравнения, для А3 — одно сравнение, для Л4 — одно сравнение и для А5 — три сравнения (попробуйте срав­нить эти данные с результатами, полученными с использованием простого рехэ-ширования для тех же идентификаторов).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

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

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

Хэш-адресация — это метод, который применяется не только для организации таблиц идентификаторов в компиляторах. Данный метод нашел свое применение и в операционных системах, и в системах управления базами данных [5, 6, 11].

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

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

Для организации таблиц предлагается использовать простейшую хэш-функцию, которую разработчик программы должен выбрать самостоятельно. Хэш-функция должна обеспечивать работу не менее чем с 200 идентификаторами, допустимая длина идентификатора должна быть не менее 32 символов. Запрещается исполь­зовать в работе хэш-функции, взятые из примера выполнения работы.

Лабораторная работа должна выполняться в следующем порядке:

1.            Получить вариант задания у преподавателя.

2.            Выбрать и описать хэш-функцию.

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

4.            Подготовить и защитить отчет.

5.            Написать и отладить программу на ЭВМ.

6.            Сдать работающую программу преподавателю.

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

Отчет по лабораторной работе должен содержать следующие разделы:

□     задание по лабораторной работе;

□     описание выбранной хэш-функции;

□     схемы организации таблиц идентификаторов (в соответствии с вариантом за­дания);

□     описание алгоритмов поиска в таблицах идентификаторов (в соответствии с ва­риантом задания);

□     текст программы (оформляется после выполнения программы на ЭВМ);

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

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

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

а Что такое таблица символов и для чего она предназначена? Какая информа­ция может храниться в таблице символов?

□     Какие цели преследуются при организации таблицы символов?

□     Какими характеристиками могут обладать лексические элементы исходной программы? Какие характеристики являются обязательными?

□     Какие существуют способы организации таблиц символов?

□     В чем заключается алгоритм логарифмического поиска? Какие преимущества он дает по сравнению с простым перебором и какие он имеет недостатки?

□     Расскажите о древовидной организации таблиц идентификаторов. В чем ее преимущества и недостатки?

□  Что такое хэш-функции и для чего они используются? В чем суть хэш-адресации?
а  Что такое коллизия? Почему она происходит? Можно ли полностью избежать

коллизий?

Q  Что такое рехэширование? Какие методы рехэширования существуют?

а Расскажите о преимуществах и недостатках организации таблиц идентифика­торов с помощью хэш-адресации и рехэширования.

□  В чем заключается метод цепочек?

□     Расскажите о преимуществах и недостатках организации таблиц идентифика­торов с помощью хэш-адресации и метода цепочек.

□     Как могут быть скомбинированы различные методы организации хеш-таблиц?

□     Расскажите о преимуществах и недостатках организации таблиц идентифика­торов с помощью комбинированных методов.

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

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

Таблица 1.1. Методы организации таблиц идентификаторов
№   метода               Способ разрешения коллизий

1                                                Простое рехэширование

2                                                Рехэширование с использованием псевдослучайных чисел

Ч"»  y/'-'.v- ■,-,--------------------------------------------------------------- :------------------------------------------

**>**-*w^*~^—-........................................................................................................        --  -■■■ ■  '-■.. ..     ■■■.J-.a^,-.      ...   -.и|  ' .

№   метода

Способ разрешения коллизий

Рехэширование с помощью произведения Метод цепочек Простой список Упорядоченный список Бинарное дерево

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

Таблица 1.2. Варианты заданий

Второй метод организации таблицы

№   варианта

Первый метод организации таблицы

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

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

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

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

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

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

HASHJ-1IN = Ord('0')+0rd('0')+0rdC' 0'); HASH^MAX = OrdCz'VordCz'HOrdCz').

Сама хэш-функция без учета рехэширования будет вычислять следующее выра­жение:

Ord(sName[l]) + Ord(sName[(hength(sName)+l) div 2]) + Ord(sName[Length(sName)] здесь sName — это входная строка (аргумент хэш-функции). Для рехэширования возьмем простейший генератор последовательности псевдо­случайных чисел, построенный на основе формулы F= г'Я, mod Я2, где Я, и Я2 — простые числа, выбранные таким образом, чтобы Я, было в диапазоне от Я2/2 до Я2. Причем, чтобы этот генератор выдавал максимально длинную последователь­ность во всем диапазоне от HASHMIN до HASH_MAX, Я2 должно быть максимально близ­ко к величине Н ASH_MAX - Н ASH_M IN + 1. В данном случае диапазон содержит 223 эле­мента, и поскольку 223 — простое число, то возьмем Я, = 223 (если бы размер диа­пазона не был простым числом, то в качестве Я, нужно было бы взять ближайшее к нему меньшее простое число). В качестве Я, возьмем 127: Я, = 127. Опишем соответствующие константы:

REHASH1 = 127; REHASH2 = 223;

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

Тогда хэш-функция с учетом рехэширования будет иметь следующий вид:

function VarHashtconst sName;string;  iNum:integer);longint: begin Result:=(Ord(sName[l])+Ord(sName[(hength(sName)+l) div 2]) + Ord(sName[tength(sName)]) - HASH_MIN + iNum*REHASHl mod REHASH2) mod (HASH_MAX-HASH_MIN+1) + HASH_MIN; if Result <HASH_MIN then Result := HASHJIIN; end;

Входные параметры этой функции: sName — имя хэшируемого идентификатора, iNum— индекс рехэшированиея (если iNum = 0, то рехэширование отсутствует);. Строка проверки величины результата (Resul t < HASHMIN) добавлена, чтобы исклю­чить ошибки в тех случаях, когда на вход функции подается строка, содержащая символы вне диапазона ' 0'..' z' (поскольку контроль входных идентификаторов отсутствует, это имеет смысл).

Для комбинации хэш-адресации и бинарного дерева можно использовать более простую хэш-функцию — сумму кодов первого и среднего символов входной стро>,'. ки. Диапазон значений такой хэш-функции в терминах языка Object Pascal будет выглядеть так:

(Ord(,0')+0rd(,0,))..(0rd('z,)+0rd('z,:>)

Этот диапазон содержит менее 200 элементов, однако функция будет удовлетзо^;1 рять требованиям задания, так как в комбинации с бинарным деревом она будет обеспечивать обработку неограниченного количества идентификаторов (макси­мальное количество идентификаторов будет ограничено только объемом доступ^.:' ной оперативной памяти компьютера).

Без применения рехэширования эта хэш-функция будет выглядеть значительно проще, чем описанная выше хэш-функция с учетом рехэширования:

function VarHash(const sName: string): longint: begin

Result:=(Ord(sName[l])+Ord(sName[(hength(sName)+l) div 2]) - HASH_MIN) mod (HASH_MAX-HASH_MIN+1) + HASH_MIN;

if Result < HASH_MIN then Result := HASH_MIN; end.

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

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

Структура данных таблицы идентификаторов (назовем ее TVarlnfo) должна со­держать в обязательном порядке поле имени идентификатора (поле sName: string), а также поля дополнительной информации об идентификаторе по усмотрению разработчиков компилятора. В лабораторной работе не предусмотрено хранение какой-либо дополнительной информации об идентификаторах, поэтому в каче­стве иллюстрации информационного поля включим в структуру TVarlnfo допол­нительную информационную структуру TAddVarlnfo (поле plnfo: TAddVarlnfo). Поскольку в языке Object Pascal для полей и переменных, описанных как cl ass, хранятся только ссылки на соответствующую структуру, такой подход не приве­дет к значительным расходам памяти, но позволит в будущем хранить любую ин­формацию, связанную с идентификатором, в отдельной структуре данных (по­скольку предполагается использовать создаваемые программные модули в по­следующих лабораторных работах). В данном случае другой подход невозможен, так как заранее не известно, какие данные необходимо будет хранить в таблицах идентификаторов. Но разработчик реального компилятора, как правило, знает, какую информацию требуется хранить, и может использовать другой подход — непосредственно включить все необходимые поля в структуру данных таблицы идентификаторов (в данном случае — в структуру TVarlnfo) без использования промежуточных структур данных и ссылок.

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

□     функции создания структуры данных и освобождения занимаемой памяти — реализованы как constructor Create и destructor Destroy;

□     функции доступа к дополнительной информации — в данной реализации это procedure Setlnfo и procedure Clearlnfo.

Эти функции будут общими для таблицы идентификаторов с рехэшированием и для комбинированной таблицы Идентификаторов.

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

□   ссылки на левую («меньшую») и правую («большую») ветвь дерева — реали­
зованы как поля данных minEl, maxEl: TVarlnfo;

U   функции добавления элемента в дерево — function AddElCnt и function AddElem;

□     функции поиска элемента в дереве — function FindElCnt и function FindElem;

□     функция очистки информационных полей во всем дереве — procedure Cl earAl 1 Info;

а   функция вывода содержимого бинарного дерева в одну строку (для получе­ния списка всех идентификаторов) — function GetElList.

Функции поиска и размещения элемента в дереве реализованы в двух экземплярах, так как одна из них выполняет подсчет количества сравнений, а другая — нет. Поскольку на функции и процедуры не расходуется оперативная память, в резуль­тате получилось, что при использовании одной и той же структуры данных для разных таблиц идентификаторов в таблице с рехэшированием будет расходоваться неиспользуемая память только на хранение двух лишних ссылок (minEl и maxEl). Полностью вся структура данных TVarlnfo и связанные с ней процедуры и функ­ции описаны в программном модуле TblElem. Полный текст этого программного модуля приведен в листинге П3.1 в приложении 3.

Надо обратить внимание на один важный момент в реализации функции поиска идентификатора в дереве (function TVarlnfo.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

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

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

Таблицы идентификаторов реализованы в виде статических массивов размером HASHMIN.. HASH_MAX, элементами которых являются структуры данных типа TVar Info. В языке Object Pascal, как было сказано выше, для структур таких типов хранят­ся ссылки. Поэтому для обозначения пустых ячеек в таблицах идентификаторов будет использоваться пустая ссылка — nil.

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

На рис. 1.3 показаны условные схемы, наглядно иллюстрирующие организацию таблиц идентификаторов. Схема 1 иллюстрирует таблицу идентификаторов с ре-хэшированием на основе генератора псевдослучайных чисел, схема 2 — таблицу идентификаторов на основе комбинации хэш-адресации с бинарным деревом. Ячейки с надписью «nil» соответствуют незаполненным ячейкам хэш-таблицы.

Схема 1

 

Ai

 

 

 

Ai

nil

•—

Схема 2

 

 

Ak

nil

nil

nil

 

Н2(А|) = Н2(Ак),Л>Ак; Н2(А)) = Н2(Л).А)>А|

Поля ссылок в элементах таблицы не используются, а потому не имеют значения

 

ЬЦ и Н2 - соответствующие хэш-функции Рис. 1.3. Схемы организации таблиц идентификаторов Для каждой таблицы идентификаторов реализованы следующие функции:

 

-      функции начальной инициализации хэш-таблицы — InitTreeVar и InitHashVar;

- функции освобождения памяти хэш-таблицы — ClearTreeVar и ClearHashVar;

  - функции удаления дополнительной информации в таблице — ClearTreelnfo и ClearHashlnfo;

  - функции добавления элемента в таблицу идентификаторов — AddTreeVar и Add-Ha$hVar;

  -   функции поиска элемента в таблице идентификаторов — GetTreeVar и GetHashVar;

-   функции, возвращающие количество выполненных операций сравнения при

размещении или поиске элемента в таблице — GetTreeCount и GetHashCount.

Алгоритмы поиска и размещения идентификаторов для двух данных методов орга­низации таблиц были описаны выше в разделе «Краткие теоретические сведения», поэтому приводить их здесь повторно нет смысла. Они реализованы в виде четы­рех перечисленных выше функций (AddTreeVar и AddHashVar — для размещения эле­мента; GetTreeVar и GetHashVar — для поиска элемента). Функции поиска и разме­щения элементов в таблице в качестве результата возвращают ссылку на элемент таблицы (структура которого описана в модуле TblElem) в случае успешного вы­полнения и нулевую ссылку — в противном случае.

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

Все перечисленные функции описаны в двух программных модулях: FncHash — для таблицы идентификаторов, построенной на оенбве рехэширования с использова­нием генератора псевдослучайных чисел, и FncTree — для таблицы идентификато­ров, построенной на основе комбинации хэш-адресации и бинарного дерева. Кроме массивов данных для организации таблиц идентификаторов и функций работы с н и-ми эти модули содержат также описание переменных, используемых для подсчета количества выполненных операций сравнения при размещении и поиске иденти­фикатора в таблицах.

Полные тексты обоих модулей (FncHash и FncTree) можно найти на веб-сайте из­дательства, в файлах FncHash.pas и FncTree.pas. Кроме того, текст модуля FncTree приведен в листинге П3.2 в приложении 3.

Хочется обратить внимание на то, что в разделах инициализации (initialization) обоих модулей вызывается функция начального заполнения таблицы идентифи­каторов, а в разделах завершения (final ization) обоих модулей — функция осво­бождения памяти. Это гарантирует корректную работу модулей при любом по­рядке вызова остальных функций, поскольку Object Pascal сам обеспечивает свое­временный вызов программного кода в разделах инициализации и завершения модулей.

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

Кроме перечисленных выше модулей необходим еще модуль, обеспечивающий интерфейс с пользователем. Этот модуль (FormLabl) реализует графическое окно TLablForm на основе класса TForm библиотеки VCL. Он обеспечивает интерфейс

средствами Graphical User Interface (GUI) в ОС типа Windows на основе стан­дартных органов управления из системных библиотек данной ОС. Кроме про­граммного кода (файл FormLabl.pas) модуль включает в себя описание ресурсов пользовательского интерфейса (файл FormLabl.dfm). Более подробно принципы организации пользовательского интерфейса на основе GUI и работа систем про­граммирования с ресурсами интерфейса описаны в [3, 5, 6, 7]. Кроме описания интерфейсной формы и ее органов управления модуль FormLabl содержит три переменные (iCountNum, iCountHash, iCountTree), служащие для накоп­ления статистических результатов по мере выполнения размещения и поиска идентификаторов в таблицах, а также функцию (procedure ViewStati stiс) для ото­бражения накопленной статистической информации на экране. Интерфейсная форма, описанная в модуле, содержит следующие основные орга­ны управления:

□     поле ввода имени файла (EditFi Ie), кнопка выбора имени файла из каталогов файловой системы (BtnFile), кнопка чтения файла (BtnLoad);

□     многострочное поле для отображения прочитанного файла (Li stldents);

□     поле ввода имени искомого идентификатора (EditSearch);

□     кнопка для поиска введенного идентификатора (BtnSearch) — этой кнопкой однократно вызывается процедура поиска (procedure SearchStr);

□     кнопка автоматического поиска всех идентификаторов (BtnAllSearch) — этой кнопкой процедура поиска идентификатора (procedure SearchStr) вызывается циклически для всех считанных из файла идентификаторов (для всех, пере­численных в поле Li stldents);

Q  кнопка сброса накопленной статистической информации (BtnReset);

Q  поля для отображения статистической информации;

□   кнопка завершения работы с программой (BtnExit).

Внешний вид этой формы приведен на рис. 1.4.

Функция чтения содержимого файла с идентификаторами (procedure TLablForm. BtnLoadCl i ck) вызывается щелчком по кнопке BtnLoad. Она организована таким об­разом, что сначала содержимое файла читается в многострочное поле Li stldents, а затем все прочитанные идентификаторы записываются в две таблицы иденти­фикаторов. Каждая строка файла считается отдельным идентификатором, пробе­лы в начале и в конце строки игнорируются. При ошибке размещения идентифи­катора в одной из таблиц выдается предупреждающее сообщение (например, еслг будет считано более 223 различных идентификаторов, то рехэширование станс невозможным и будет выдано сообщение об ошибке).

Функция поиска идентификатора (procedure TLablForm.SearchStr) вызывается од нократно щелчком по кнопке BtnSearch (процедура procedure TLablForm. BtnSearchCl ick или многократно щелчком по кнопке BtnAll Search (процедура procedure TLablForm BtnAllSearchClick). Поиск идет сразу в двух таблицах, результаты поиска и накоп ленная статистическая информация отображаются в соответствующих полях. :; И сходные данные':;

stall

end

bbadsh

Еыорать Файл

sdfasd

ZXCV

агрчзитьФаил  s

czxv

sdag

asdv

ж идентификатора-'

asd

asdgfasdgter

afsdgfsdhhgjhjk

dsthghnxcvnxcv

В сего поиск: 1841

Найти все Копичестео выполнявшихся операций поиска иденти

'им'.......... mm.V.iMn.i.r.iu;  i.fil.........................................................................                                                          .......................

Бинарное дерево-~

Сравнений 15 Всего сравнений: 2

"Рехэширование ~....... -

Идентификатор найдег Сравнений: 13 Всего сравнений: 184

В среднем сравнений: 1.02              В средне

зыаОД из программы

Рис. 1.4. Внешний вид интерфейсной формы для лабораторной работы № 1

Полный текст программного кода модуля интерфейса с пользователем и описа­ние ресурсов пользовательского интерфейса находятся в архиве, располагаю­щемся на веб-сайте издательства, в файлах FormLabl.pas и FormLabl.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 1=1... невозможно определить тип оператора (а соответственно, и границы лексем). В случае DO 10 1=1.15 это будет присвоение вещественной переменной D010I значения константы 1.15 (пробелы з Фортране игнорируются), а в случае DO 10 1=1,15 это цикл с перечислением от 1 до 15 по целочисленной переменной I до метки 10.

Другая иллюстрация из более современного языка программирования C++ — опе­ратор присваивания k=i+++++j;, который имеет только одну верную интерпрета­цию (если операции разделить пробелами): k = i++ + ++j;.

Если невозможно определить границы лексем, то лексический анализ исходного текста должен выполняться поэтапно. Тогда лексический и синтаксический ана­лизаторы должны функционировать параллельно, поочередно обращаясь друг к другу. Лексический анализатор, найдя очередную лексему, передает ее синтак­сическому анализатору, тот пытается выполнить анализ считанной части исход­ной программы и может либо запросить у лексического анализатора следующую лексему, либо потребовать от него вернуться на несколько шагов назад и попро­бовать выделить лексемы с другими границами. При этом он может сообщить ин­формацию о том, какую лексему следует ожидать. Более подробно такая схема взаимодействия лексического и синтаксического анализаторов описана в [3, 7].

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

Чтобы избежать параллельной работы лексического и синтаксического анализа­торов, разработчики компиляторов и языков программирования часто идут на разумные ограничения синтаксиса входного языка. Например, для языка С^ принято соглашение, что при возникновении проблем с определением границ лек семы всегда выбирается лексема максимально возможной длины. В рассмотренном выше примере для оператора 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

 

Лексема

Тип лексемы

 

Значение

begin

Ключевое слово

 

х,

for

Ключевое слово

 

Х2

i

Идентификатор

 

i : 1

■

Знак присваивания

 

s,

1

Целочисленная константа

1

to

Ключевое слово

1

Х3

N

Идентификатор

 

N : 2

do

Ключевое слово

 

х4

fg

Идентификатор

 

fg :3

:=

Знак присваивания

 

S,

fg

Идентификатор

 

Fg : 3

*

Знак арифметической

операции

А,

0.5

Вещественная константа

0.5

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

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

Лексический анализатор имеет дело с такими объектами, как различного рода кон­станты и идентификаторы (к последним относятся и ключевые слова). Язык опи­сания констант и идентификаторов в большинстве случаев является регулярным, то есть может быть описан с помощью регулярных грамматик [1-4,7]. Распознава­телями для регулярных языков являются конечные автоматы (КА). Существуют правила, с помощью которых для любой регулярной грамматики может быть пост­роен КА, распознающий цепочки языка, заданного этой грамматикой. Более подробно о построении КА на основе грамматик для регулярных языков можно узнать в [3, 7, 26].

Любой КА может быть задан с помощью пяти параметров: M(Q,E,8,g(l,F), где:

Q. — конечное множество состояний автомата;

£ — конечное множество допустимых входных символов (входной алфавит КА); 8 — заданное отображение множества Q-E во множество подмножеств P(Q) 8: Q-E —> P(Q) (иногда 8 называют функцией переходов автомата);

q0 e Q, — начальное состояние автомата;

F с Q — множество заключительных состояний автомата.

Другим способом описания КА является граф переходов — графическое представ­ление множества состояний и функции переходов КА. Граф переходов КА — это нагруженный однонаправленный граф, в котором вершины представляют состо­яния КА, дуги отображают переходы из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют функции перехода КА. Если функция пе­рехода КА предусматривает переход из состояния q в q 'по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по ко­торым происходит переход из q в q'.

Недетерминированный КА неудобен для анализа цепочек, так как в нем могут встречаться состояния, допускающие неоднозначность, то есть такие, из которых выходит две или более дуги, помеченные одним и тем же символом. Очевидно, что программирование работы такого КА — нетривиальная задача. Для простого программирования функционирования КА M(Q,£,8//(),F) он должен быть детер­минированным — в каждом из возможных состояний этого КА для любого вход­ного символа функция перехода должна содержать не более одного состояния: ValV, VglQj либо b{a,q) = {г} г е Q, либо b(a,q) = 0.

Доказано, что любой недетерминированный КА может быть преобразован в де­терминированный КА так, чтобы их языки совпадали [3, 7, 26] (говорят, что эти К А эквивалентны).

Кроме преобразования в детерминированный КА любой КА может быть миними­зирован — для него может быть построен эквивалентный ему детерминированный КАс минимально возможным количеством состояний. Алгоритмы преобразования КА в детерминированный КА и минимизации КА подробно описаны в [3, 7, 26].

Можно написать функцию, отражающую функционирование любого детермини­рованного КА. Чтобы запрограммировать такую функцию, достаточно иметь пе­ременную, которая бы отображала текущее состояние КА, а переходы из одного состояния в другое на основе символов входной цепочки могут быть построены с помощью операторов выбора. Работа функции должна продолжаться до тех пор, пока не будет достигнут конец входной цепочки. Для вычисления результата функ­ции необходимо по ее завершении проанализировать состояние КА. Если это одно из конечных состояний, то функция выполнена успешно и входная цепочка при­нимается, если нет, то входная цепочка не принадлежит заданному языку.

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

Во входном тексте лексемы не ограничены специальными символами. Определе­ние границ лексем — это выделение тех строк в общем потоке входных символов,

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

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

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

Q при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу;

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

Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.

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

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

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

Лабораторная работа должна выполняться в следующем порядке:

1.            Получить вариант задания у преподавателя.

2.            Построить описание КА, лежащего в основе лексического анализатора (в виде набора множеств и функции переходов или в виде графа переходов).

Подготовить и защитить отчет.

4.            Написать и отладить программу на ЭВМ.

5.            Сдать работающую программу преподавателю.

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

Отчет должен содержать следующие разделы:

Q   Задание по лабораторной работе.

□      Описание КС-грамматики входного языка в форме Бэкуса—Наура.

□      Описание алгоритма работы сканера или граф переходов КА для распознава­ния цепочек (в соответствии с вариантом задания).

□      Текст программы (оформляется после выполнения программы на ЭВМ).

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

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

□      Что такое трансляция, компиляция, транслятор, компилятор?

□      Из каких процессов состоит компиляция? Расскажите об общей структуре компилятора.

□      Какую роль выполняет лексический анализ в процессе компиляции?

□      Что такое лексема? Расскажите, какие типы лексем существуют в языках про­граммирования.

а   Как могут быть связаны между собой лексический и синтаксический анализ?

□   Какие проблемы могут возникать при определении границ лексем в процессе
лексического анализа? Как решаются эти проблемы?

□   Что такое таблица лексем? Какая информация хранится в таблице лексем?
Q   В чем разница между таблицей лексем и таблицей идентификаторов?

□      Что такое грамматика? Дайте определения грамматики. Как выглядит описа­ние грамматики в форме Бэкуса—Наура.

□      Какие классы грамматик существуют? Что такое регулярные грамматики?

□      Что такое конечный автомат? Дайте определение детерминированного и не­детерминированного конечных автоматов.

□      Опишите алгоритм преобразования недетерминированного конечного автомата в детерминированный.

□      Какие проблемы необходимо решить при построении сканера на основе ко­нечного автомата?

□      Объясните общий алгоритм функционирования лексического анализатора.

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

1.   Входной язык содержит арифметические выражения, разделенные символом ; (точка с запятой). Арифметические выражения состоят, из идентификаторов,

десятичных чисел с плавающей точкой (в обычной и логарифмической фор­ме), знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

2.            Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, констант true и false, знака присваивания (:=), знаков операций or, not, and, not и круглых скобок.

3.            Входной язык содержит операторы условия типа if ... then ... else и if... then,

разделенные символом ; (точка с запятой). Операторы условия содержат иден­тификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой (в обычной и логарифмической форме), знак присваивания (:=).

4.            Входной язык содержит операторы цикла типа for (...; ...; ...) do, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой (в обычной и логарифмической форме), знак присваивания (:-).

5.            Входной язык содержит арифметические выражения, разделенные символом ; (точка с запятой). Арифметические выражения состоят из идентификаторов, римских чисел, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

6.            Входной язык содержит логические выражения, разделенные символом ; (точ­ка с запятой). Логические выражения состоят из идентификаторов, констант О и 1, знака присваивания (: = ), знаков операций or, not, and, not и круглых скобок.

7.            Входной язык содержит операторы условия типа if... then ... else и if... then, разделенные символом ; (точка с запятой). Операторы условия содержат иден­тификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).

8.            Входной язык содержит операторы цикла типа for (...; ...; ...) do, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).

9.            Входной язык содержит арифметические выражения, разделенные символом ; (точка с запятой). Арифметические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

10. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, шестнадца­теричных чисел, знака присваивания (:=), знаков операций or, not, 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, «e» n«f», начинающуюся с цифры (например: 89, 45ас9, 0abc4);

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

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

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

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

Описанный выше входной язык может быть построен с помощью КС-граммати­ки G({if,then,else,a,:=,or, not, and,(,),;},{5,J-'',£',L),C},P,5) с правилами Р:

5->F;

F->if fthen Telse F| if E then F| a := E

T —> if E then Telse T| a := E

E->EorD\ExorD\D

D -> D and С | С

C~>a\ (£)

Описание грамматики построено в форме Бэкуса—Наура. Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

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

Описание конечного автомата

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

Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются:

-     шесть ключевых слов языка (if, then, else, or, xor и and);

-    разделители: открывающая и закрывающая круглые скобки, точка с запятой;

-    знак операции присваивания;

-     идентификаторы;

-    целые десятичные константы без знака.

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

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

-     идентификатор — это произвольная последовательность малых и прописных
букв латинского алфавита (от А до Z и от а до г), цифр (от 0 до 9) и знака
подчеркивания (_), начинающаяся с буквы или со знака подчеркивания;

-   целое десятичное число без знака — это произвольная последовательность цифр

(от 0 до 9), начинающаяся с любой цифры. Границами лексем для данного распознавателя будут служить пробел, знак табу­ляции, знаки перевода строки и возврата каретки, а также круглые скобки, откры­вающая фигурная скобка, точка с запятой и знак двоеточия. При этом следует помнить, что круглые скобки и точка с запятой сами по себе являются лексема­ми, открывающая фигурная скобка начинает комментарий, а знак двоеточия, яв­ляясь границей лексемы, в то же время является и началом другой лексемы — опе­рации присваивания.

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

П

(.): IF (а)

Рис. 2.1. Фрагмент графа переходов КА для распознавания всех лексем, кроме ключевых слов

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

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

Рис. 2.2. Фрагмент графа переходов К А для ключевых слов if и then

На фрагментах графа переходов КА, изображенных на рис. 2.1 и 2.2, приняты сле­дующие обозначения:        *

□   А — любой алфавитно-цифровой символ;

□   А(*) — любой алфавитно-цифровой символ, кроме перечисленных в скобках;

□      П — любой незначащий символ (пробел, знак табуляции, перевод строки, воз­врат каретки);

□      Б — любая буква английского алфавита (прописная или строчная) или сим­вол подчеркивания(_);

 □   Б(*) — любая буква английского алфавита (прописная или строчная) или сим­вол подчеркивания (_), кроме перечисленных в скобках;

 □  Ц — любая цифра от 0 до 9;

 □   F — функция обработки таблицы лексем, вызываемая при переходе КА из од­ного состояния в другое. Обозначения ее аргументов:

■     v — переменная, запомненная при работе КА; ш   d — константа, запомненная при работе КА;

■     а — текущий входной символ КА.

С учетом этих обозначений, полностью КА можно описать следующим образом:

M(Q,£,8,<70,F):

Q= {Н, С, G, V, D, II, 12, Т1, Т2, ТЗ, Т4, Е1, Е2, ЕЗ, Е4, 01, 02, XI, Х2, ХЗ, Al, A2,

A3, J}

£ = А (все допустимые алфавитно-цифровые символы);

<?о= н;

F = {F).

Функция переходов (8) для этого КА приведена в приложении 2.

Из начального состояния КА литеры «i», «t», «e», «о», «х» и «а» ведут в начало

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

□   состояния II, 12 — ключевому слову if;

□   состояния Т1, Т2, ТЗ, Т4 — ключевому слову then;

□     состояния Е1, Е2, ЕЗ, Е4 — ключевому слову else;

□     состояния 01, 02 — ключевому слову or;

□     состояния XI, Х2, ХЗ — ключевому слову хог;

□     состояния Al, A2, A3 — ключевому слову and.

Остальные литеры ведут к состоянию, соответствующему переменной (иденти­фикатору), — V. Если в какой-то из цепочек встречается литера, не соответству­ющая ключевому слову, или цифра, то К А также переходит в состояние V, а если встречается граница лексемы — запоминает уже прочитанную часть ключевого слова как переменную (чтобы правильно выделять такие идентификаторы, как «1» или «els», которые совпадают с началом ключевых слов). Цифры ведут в состояние, соответствующее входной константе, — D. Открываю­щая фигурная скобка ведет в состояние С, которое соответствует обнаружению комментария — из этого состояния КА выходит, только если получит на вход зак­рывающую фигурную скобку. Еще одно состояние — G — соответствует лексеме «знак присваивания». В него КА переходит, получив на вход двоеточие, и ожидает в этом состоянии символа «равенство».

Состояние Н — начальное состояние КА, а состояние F — его конечное состоя­ние. Поскольку КА работает с непрерывным потоком лексем, перейдя в конечное состояние, он тут же должен возвращаться в начальное, чтобы распознавать оче­редную лексему. Поэтому в моделирующей программе эти два состояния можно объединить.

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

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

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

Можно заметить, что функция переходов КА получилась довольно громоздкой, хотя и простой по своей сути (для всех ключевых слов она работает однотипно). В реализации функционирования КА проще было бы не выделять отдельные со­стояния для ключевых слов, а переходить всегда по обнаружению буквы на входе КА в состояние V. Тогда проверку того, является ли считанная строка ключевым словом или же идентификатором, можно было бы выполнять на момент ее записи в таблицу лексем с помощью стандартных операций сравнения строк. Граф пере­ходов КА в таком варианте был бы намного компактнее — он выглядел бы точно так же, как фрагмент, представленный на рис. 2.1. Его можно назвать «сокращен­ным» графом переходов К А (или «сокращенным КА»).

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

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

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

Разбиение на модули

Модули, реализующие лексический анализатор, разделены на две группы:

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

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

В первую группу входят модули:

□   LexEl em — описывает структуру данных элемента таблицы лексем;

□    Forml_ab2 — описывает интерфейс с пользователем.

Во вторую группу входят модули:

□   LexType - описывает типы входных лексем, связанные с ними наименования и текстовую информацию;

□    LexAuto — реализует функционирование КА.

Такое разбиение на модули позволяет использовать те же самые структуры данных для организации лексического распознавателя при изменении входного языка. Кроме этих модулей для реализации лабораторной работы № 2 используются так­же программные модули (TblElem и FncTree), позволяющие работать с комбиниро­ванной таблицей идентификаторов, которые были созданы при выполнении ла­бораторной работы № 1. Эти два модуля, очевидно, также не зависят от входного языка.

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

Модуль типов лексем

Модуль LexType в детальных комментариях не нуждается. В нем перечислены все допустимые типы лексем (тип данных TLexType), каждой из которых соответствует наименование и обозначение лексемы. Вывод наименований лексем обеспечивает функция LexTypeName, а вывод обозначений — функция LexTypelnfo. Следует отме­тить, что кроме перечисленных в задании лексем используется еще одна дополни­тельная информационная лексема (LEXSTART), обозначающая конец строки. Модуль LexEl em описывает структуры данных элемента таблицы лексем (TLexem) и самой таблицы лексем (TLexList), а также все, что с ними связано.

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

Структура данных таблицы лексем содержит информацию о лексеме (поле Lexlnfo). В этом поле содержится тип лексемы (LexType), а также следующие данные:

 □   Varlnfo — ссылку на элемент таблицы идентификаторов для лексем типа «пе­ременная»; Q   ConstVal — целочисленное значение для лексем типа «константа»; □   szlnfo — произвольная строка для информационной лексемы. Для лексем других типов не требуется никакой дополнительной информации. Следует отметить, что для лексем типа «переменная» хранится именно ссылка на таблицу идентификаторов, а не имя переменной. Именно для этого в данной ла­бораторной работе используются модули из лабораторной работы № 1. Для само­го лексического анализатора не имеет значения, что хранить в таблице лексем — ссылку на таблицу идентификаторов со всей информацией о переменной или же

только имя переменной. Но реализация лексического анализатора, при которой хранится именно ссылка на таблицу идентификаторов, чрезвычайно удобна для дальнейшей обработки данных, что будет очевидно в последующих работах (ла­бораторных работах № 3 и № 4). Поскольку лексический анализатор интересен не сам по себе, а в составе компилятора, такой подход принципиально важен.

Кроме этого в структуре данных элемента таблицы лексем хранится информация' о позиции лексемы в тексте входной программы:

О   iStr — номер строки, где встретилась лексема;

a   iPos — позиция лексемы в строке;

а   iA11Р — позиция лексемы относительно начала входного файла.

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

Кроме этих данных структура содержит также:

Q   четыре конструктора для создания лексем четырех разных типов:

■      CreateVar — для создания лексем типа «переменная»;

■      CreateConst — для создания лексем типа «константа»;

■      Createlnfo — для создания информационных лексем;

■      CreateKey — для создания лексем других типов;

 

□     деструктор Destroy для освобождения памяти, занятой лексемой (важен для информационных лексем);

□     свойства и функции для доступа к информации о лексеме.

Хранить в структуре строку самой лексемы нет никакой необходимости (для пе­ременных строка хранится в таблице идентификаторов, для других типов лексем она просто не нужна).

Сама таблица лексем (тип данных TLexList) построена на основе динамического массива TList из библиотеки VCL (модуль Classes) системы программирования Delphi 5.

Динамический массив типа TList обеспечивает все функции и данные, необходи­мые для хранения в памяти произвольного количества лексем (максимальное ко­личество лексем ограничено только объемом доступной оперативной памяти). Для таблицы лексем TLexList дополнительно реализованы функции очистки таблицы, которые освобождают память, занятую лексемами, при их удалении из таблицы (функция Clear и деструктор Destroy), а также функция GetLexem и свойство Lexem, обеспечивающие удобный доступ к любой лексеме в таблице по се индексу (по­рядковому номеру).

Модуль моделирования работы КА

Модуль LexAuto, моделирующий работу КА, на основе которого построен лекси­ческий распознаватель, — самый значительный по объему программного кода. Однако по содержанию программного кода он предельно прост. Этот модуль обеспечивает функционирование полного КА, фрагменты графа переходов которого были изображены на рис. 2.1 и 2.2, а функция переходов была построена выше. Главной составляющей этого программного модуля является функция Маке-LexList, которая непосредственно моделирует работу КА. На вход функции по­дается входная программа в виде списка строк (формальный параметр 1istFile) и таблица лексем, куда должны помещаться найденные лексемы (формальный параметр listLex). Результатом работы функции является 0, если лексический анализ выполнен без ошибок, а если ошибка обнаружена — номер строки в ис­ходном файле, в которой она присутствует. Для более подробной информации об обнаруженной ошибке функция создает информационную лексему и поме­щает ее в конец таблицы лексем. Сама информационная лексема кроме тексто­вой информации об ошибке содержит еще дополнительную информацию о ее местонахождении в исходной программе (смещение от начала файла и длина ошибочной лексемы).

В типе данных TAutoPos перечислены все возможные состояния КА. Перечень со­стояний полностью соответствует функции переходов КА.

Реализация функции MakeLexLi st, несмотря на большой объем программного кода, предельно проста. Она построена на основе двух вложенных циклов (первый — по строкам входного списка, второй — по символам в текущей.строке), внутри которых находятся два уровня вложенных оператора выбора типа case — типич­ный подход к моделированию функционирования КА. Внешний оператор case выполняется по всем возможным состояниям автомата, a case второго уровня — по допустимым входным символам в каждом состоянии.

Можно обратить внимание на шесть вспомогательных функций:

□   AddVarToList — добавление лексемы типа «переменная» в таблицу лексем;

Q  AddVarKeyToLi st — добавление лексем типа «переменная» и типа «разделитель» в таблицу лексем;

□     AddConstToList — добавление лексемы типа «константа» в таблицу лексем;

□     AddConstKeyToLi st — добавление лексем типа «константа» и типа «разделитель» в таблицу лексем;

□     AddKeyToLi st — добавление лексемы типа «ключевое слово» или «разделитель» в таблицу лексем;

□     Add2KeysToList — добавление лексем типа «ключевое слово» и «разделитель» в таблицу лексем подряд.

Эти функции, по сути, являются реализацией функции, которая на графе перехо­дов КА была обозначена F.

Еще две вспомогательные функции служат для упрощения кода. Они выполняют часто повторяющиеся действия в состояниях автомата, которые связаны со сред­ними символами ключевых слов (в функции переходов эти состояния обозначе­ны Т2, ТЗ, Е2, ЕЗ, Х2 и А2) и завершающими символами ключевых слов (в функ­ции переходов эти состояния обозначены 12, Т4, Е4, 02, ХЗ и A3).

Построенный лексический анализатор обнаруживает три типа ошибок:

□     неверный символ в лексеме (например, сочетания «2а» или «:6» будут призна­ны неверными символами в лексемах);

□     незакрытый комментарий (присутствует открывающая фигурная скобка, но отсутствует соответствующая ей закрывающая);

а незавершенная лексема (в данном входном' языке это может быть только сим­вол «:» в конце входной программы, который будет воспринят как начало не­завершенной лексемы «:=»).

Остальные ошибки входного языка должен обнаруживать синтаксический ана­лизатор.

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

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

Кроме перечисленных выше модулей необходим еще модуль, обеспечивающий интерфейс с пользователем. Как и в лабораторной работе № 1, этот модуль (Form-Lab2) реализует графическое окно TLab2Form на основе класса TForm библиотеки VCL и включает в себя две составляющие:.

□     файл программного кода (файл FormLab2.pas);

□     файл описания ресурсов пользовательского интерфейса (файл FormLab2.dfm).

Кроме описания интерфейсной формы и ее органов управления модуль FormLab2 содержит переменную (1 i stLex), в которую записывается ссылка на таблицу лек­сем.

Интерфейсная форма, описанная в модуле, содержит следующие основные орга­ны управления:

□     многостраничную вкладку (PageControll) с двумя закладками (SheetFile и Sheetlexems) под названиями «Исходный файл» и «Таблица лексем» соответ­ственно;

□     на закладке SheetFi 1 е:

 

■     поле ввода имени файла (EditFile), кнопка выбора имени файла из катало­гов файловой системы (BtnFile), кнопка чтения файла (BtnLoad);

■     многострочное поле для отображения прочитанного файла (Li stldents);

□    на закладке SheetLexems:

■   сетка (GridLex) с тремя колонками для отображения данных о прочитанных
лексемах;

□    кнопка завершения работы с программой (BtnExit).

 

Лабораторная работа h»2

Исходный Файл .Табода лексем.

: сводные данные

закладки интерфейсной формы для лабораторной работы № 2

h?j

Лабораторная работа тг

Таблша лек£вм 1

 

1      j Ключевое слово

2       i Переменная

3       I Ключевое слово

 

 

4

; Константа

22

5

: Ключевое слово

ithen

6 7

\ Ключевое слово

• s*

j Переменная

ia

 

I Ключевое слово

;and

10 11

; Ключевое слово Переменная

■then

JJJ

 

 

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

 

Чтение содержимого входного файла организовано точно так же, как в лабора­торной работе № 1.

После чтения файла создается таблица лексем (ссылка на нее запоминается в пе­ременной 1 istLex) и вызывается функция MakeLexList, результат работы которой помещается во временную переменную пЕгг.

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

Если ошибок не обнаружено, то на основании считанной таблицы лексем 1 istLex заполняется сетка GridLex, которая очень удобна для наглядного представления таблицы лексем:

□      первая колонка — порядковый помер лексемы;

□      вторая колонка — тип лексемы (ее внешний вид); Q   третья колонка — информация о лексеме.

Полный текст программного кода модуля интерфейса с пользователем приведен в листинге П2.4 в приложении 2, а описание ресурсов пользовательского интер­фейса — в листинге П2.5 в приложении 2.

Полный текст всех программных модулей, реализующих рассмотренный пример для лабораторной работы № 2, приведен в приложении 2.

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

В результате лабораторной работы № 2 построен лексический анализатор на ос­нове конечного автомата. Построенный лексический анализатор позволяет выде­лять в тексте исходной программы лексемы следующих типов:

Q   ключевые слова (if, then, else, or, xor и and);

□     идентификаторы (при этом в именах идентификаторов различаются строчные и прописные английские буквы);

□     знак операции присваивания;

□     целые десятичные константы без знака;

□     разделители (круглые скобки и точка с запятой).

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

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

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

 

ЛАБОРАТОРНАЯ РАБОТА № 3

Построение простейшего дерева вывода

Цель работы

Цель работы изучение основных понятий теории грамматик простого и опера-?„Z™—*, ознакомление с алгоритмами «*™£^_ за (разбора) для некоторых классов КС-грамматик, получение практических на Z^fcZlZ простейшего синтаксического анализатора для заданной грамматики операторного предшествования.

Краткие теоретические сведения Назначение синтаксического анализатора

По иерархии грамматик Хомского выделяют четыре основные JW™™»» (и описывающих их грамматик) [1, 3, 4, 7]. При этом наибольший интерес представляют регулярные и контекстно-свободные (КС) грамматики и ™^Ohh ис­пользуются при описании синтаксиса языков программирования. С помощью регулярных грамматик можно описать лексемы языка - идентификаторы, константы служебные слова и прочие. На основе КС-грамматик строятся более крупные синтаксические конструкции: описания типов и переменных, арифметические и логические выражения, управляющие операторы и, наконец, полностью вся программа на входном языке.

Входные цепочки регулярных языков распознаются с помощью конечных авто­матов (КА). Они лежат в основе сканеров, выполняющих лексический анализ и выделение слов в тексте программы на входном языке. Результатом работы ска­нера является преобразование исходной программы в список или таблицу лек­сем. Дальнейшую ее обработку выполняет другая часть компилятора — синтак­сический анализатор. Его работа основана на использовании правил КС-грамма­тики, описывающих конструкции исходного языка.

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

□  найти и выделить синтаксические конструкции в тексте исходной программы;

□  установить тип и проверить правильность каждой синтаксической конструк­ции;

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

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

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

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

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

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

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

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

Основой для построения распознавателей КС-языков являются автоматы с мага­зинной памятью — МП-автоматы — односторонние недетерминированные распо­знаватели с линейно-ограниченной магазинной памятью (полная классификация распознавателей приведена в [1, 4, 3, 7]). Поэтому важно рассмотреть, как функ­ционирует МП-автомат и как для КС-языков решается задача разбора — постро­ение распознавателя языка на основе заданной грамматики. Далее рассмотрены технические аспекты, связанные с реализацией синтаксических анализаторов.

МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и не­терминальные символы грамматики языка). Переход МП-автомата из одного со­стояния в другое зависит не только от входного символа, но и от одного или не­скольких верхних символов стека. Таким образом, конфигурация автомата опре­деляется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.

При выполнении перехода МП-автомата из одной конфигурации в другую из стека удаляются верхние символы, соответствующие условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становит­ся верхушкой стека. Допускаются переходы, при которых входной символ игно­рируется (и тем самым он будет входным символом при следующем переходе). Эти переходы называются ^.-переходами. Если при окончании цепочки автомат находится в одном из заданных конечных состояний, а стек пуст, цепочка счита­ется принятой (после окончания цепочки могут быть сделаны А-переходы). Ина­че цепочка символов не принимается.

МП-автомат называется недетерминированным., если при одной и той же его кон­фигурации возможен более чем один переход. В противном случае (если из любой конфигурации МП-автомата по любому входному символу возможно не более од­ного перехода в следующую конфигурацию) МП-автомат считается детерминиро­ванным (ДМП-автоматом). ДМП-автоматы задают класс детерминированных КС-языков, для которых существуют однозначные КС-грамматики. Именно этот класс языков лежит в основе синтаксических конструкций всех языков программйрова ния, так как любая синтаксическая конструкция языка программирования должна допускать только однозначную трактовку [1-4, 7].

По произвольной КС-грамматике G(VN,VT,P,5), V = VTuVN всегда можно по­строить недетерминированный МП-автомат, который допускает цепочки языка, заданного этой грамматикой [1-3, 7]. А на основе этого МП-автомата можно со­здать распознаватель для заданного языка.

Однако при алгоритмической реализации функционирования такого распозна­вателя могут возникнуть проблемы. Дело в том, что построенный МП-автомат будет, как правило, недетерминированным, а для МП-автоматов, в отличие от обычных КА, не существует алгоритма, который позволял бы преобразовать про­извольный МП-автомат в ДМП-автомат. Поэтому программирование функцио­нирования МП-автомата — нетривиальная задача. Если моделировать его функ­ционирование по шагам с перебором всех возможных состояний, то может ока­заться, что построенный для тривиального МП-автомата алгоритм никогда не завершится на конечной входной цепочке символов при определенных условиях. Примеры таких МП-автоматов можно найти в [1, 3, 7].

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

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

Существуют несложные преобразования КС-грамматик, выполнение которых гарантирует, что построенный на основе преобразованной грамматики МП-авто­мат можно будет промоделировать за конечное время на основе конечных вычис­лительных ресурсов. Описание сути и алгоритмов этих преобразований можно найти в [1, 3, 7].

Эти преобразования позволяют строить два основных типа простейших распо­знавателей:

□     распознаватель с подбором альтернатив;

□     распознаватель на основе алгоритма «сдвиг-свертка».

Работу распознавателя с подбором альтернатив можно неформально описать сле­дующим образом: если на верхушке стека МП-автомата находится нетерминаль­ный символ А, то его можно заменить на цепочку символов а при условии, что в грамматике языка есть правило А —> а, не сдвигая при этом считывающую го­ловку автомата (этот шаг работы называется «подбор альтернативы»); если же на верхушке стека находится терминальный символ а, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передви­нуть считывающую головку на одну позицию вправо (этот шаг работы называет­ся «выброс»). Данный МП-автомат может быть недетерминированным, посколь­ку при подборе альтернативы в грамматике языка может оказаться более одного правила вида Л -^ а, тогда функция 8(<уД,Л) будет содержать более одного следу­ющего состояния — у МП-автомата будет несколько альтернатив.

Решение о том, выполнять ли на каждом шаге работы МП-автомата выброс или подбор альтернативы, принимается однозначно. Моделирующий алгоритм дол­жен обеспечивать выбор одной из возможных альтернатив и хранение информа­ции о том, какие альтернативы на каком шаге уже были выбраны, чтобы иметь возможность вернуться к этому шагу и подобрать другие альтернативы. Распознаватель с подбором альтернатив является нисходящим распознавателем: он читает входную цепочку символов слева направо и строит левосторонний вы­вод. Название «нисходящий» дано ему потому, что дерево вывода в этом случае следует строить сверху вниз, от корня к концевым вершинам («листьям»)1. Работу распознавателя на основе алгоритма «сдвиг-свертка» можно описать так: если на верхушке стека МП-автомата находится цепочка символов у, то ее можно заменить на нетерминальный символ А при условии, что в грамматике языка су­ществует правило вида Л —> у, не сдвигая при этом считывающую головку автома­та (этот шаг работы называется «свертка»); с другой стороны, если считывающая головка автомата обозревает некоторый символ входной цепочки а, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо (этот шаг работы называется «сдвиг» или «перенос»).

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

Q  что необходимо выполнять: сдвиг или свертку;

□      если выполнять свертку, то какую цепочку у выбрать для поиска правил (це­почка у должна встречаться в правой части правил грамматики);

□      какое правило выбрать для свертки, если окажется, что существует несколько правил вида А —> у (несколько правил с одинаковой правой частью).

Для моделирования работы этого расширенного МП-автомата надо на каждом шаге запоминать все предпринятые действия, чтобы иметь возможность вернуться к уже сделанному шагу и выполнить эти же действия по-другому. Этот процесс дол­жен повторяться до тех пор, пока не будут перебраны все возможные варианты. Распознаватель на основе алгоритма «сдвиг-свертка» является восходящим рас­познавателем: он читает входную цепочку символов слева направо и строит пра­восторонний вывод. Название «восходящий» дано ему потому, что дерево вывода в этом случае следует строить снизу вверх, от концевых вершин к корню. Функционирование обоих рассмотренных распознавателей реализуется достаточ­но простыми алгоритмами, которые можно найти в [3, 7]. Однако оба они имеют один существенный недостаток — время их функционирования экспоненциаль­но зависит от длины входной цепочки п = |а|, что недопустимо для компиляторов, где длина входных программ составляет от десятков до сотен тысяч символов. Так происходит потому, что оба алгоритма выполняют разбор входной цепочки символов методом простого перебора, подбирая правила грамматики произвольным образом, а в случае неудачи возвращаются к уже прочитанной части вход­ной цепочки и пытаются подобрать другие правила.

Существуют более эффективные табличные распознаватели, построенные на осно­ве алгоритмов Эрли и Кока—Янгера—Касами [1,3]. Они обеспечивают полиноми­альную зависимость времени функционирования от длины входной цепочки (я3 для произвольного МП-автомата и п2 для ДМП-автомата). Это самые эффек­тивные из универсальных распознавателей для КС-языков. Но и полиномиальную зависимость времени разбора от длины входной цепочки нельзя признать удовлет­ворительной.

Лучших универсальных распознавателей не существует. Однако среди всего типа КС-языков существует множество классов и подклассов языков, для которых можно построить распознаватели, имеющие линейную зависимость времени функ­ционирования от длины входной цепочки символов. Такие распознаватели назы­вают линейными распознавателями КС-языков!

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

Среди всего множества можно выделить следующие наиболее часто используе­мые распознаватели:

□     распознаватели на основе рекурсивного спуска (модификация алгоритма с под­бором альтернатив);

□     распознаватели на основе 11(1)- и 11(£)-грамматик (модификация алгоритма с подбором альтернатив);

□     распознаватели на основе LR(0)- и 1й(1)-грамматик (модификация алгорит­ма «сдвиг-свертка»);    • ,-,   Г'

□     распознаватели на основе SLR(l)- и 1Л1Л(1)-грамматик (модификация алго­ритма «сдвиг-свертка»);

□     распознаватели на основе грамматик предшествования (модификация алго­ритма «сдвиг-свертка»).

Алгоритмы функционирования всех перечисленных и ряда других линейных рас­познавателей описаны в [1-4, 7J.

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

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

Но, как и в случае лексического анализа, задача синтаксического анализа не огра­ничивается только проверкой принадлежности цепочки заданному языку. Необ­ходимо оформить найденные синтаксические конструкции для дальнейшей гене-; рации текста результирующей программы. Синтаксический анализатор должен! иметь некий выходной язык, с помощью которого он передает следующим фазам компиляции информацию о найденных и разобранных синтаксических структу­рах. В таком случае он уже является не разновидностью МП-автомата, а преобра­зователем с магазинной памятью — МП-преобразователем [1, 2, 7]. Вопросы, связанные с представлением информации, являющейся результатом работы синтаксического анализатора, и с порождением на основе этой информа­ции текста результирующей программы, рассмотрены в лабораторной работе № 4, поэтому здесь на них останавливаться не будем.

Построение синтаксического анализатора — это более творческий процесс, чем' построение лексического анализатора. Этот процесс не всегда может быть пол­ностью формализован.

Имея грамматику входного языка, разработчик синтаксического анализатора дол­жен в первую очередь выполнить ряд формальных преобразований над этой грам­матикой, облегчающих построение распознавателя. После этого он должен про­верить, относится ли полученная грамматика к одному из известных классов КС-языков, для которых существуют линейные распознаватели. Если такой класс найден, можно строить распознаватель (если найдено несколько классов, следует выбрать тот, для которого построение распознавателя проще либо построенный распознаватель будет обладать лучшими характеристиками). Если же такой класс КС-языков найти не удалось, то разработчик должен попытаться выполнить над грамматикой некоторые преобразования, чтобы привести ее к одному из извест­ных классов. Эти преобразования не могут быть описаны формально, и в каждом конкретном случае разработчик должен попытаться найти их сам (иногда преоб­разования имеет смысл искать даже в том случае, когда грамматика подпадает под; одни из известных классов КС-языков, с целью найти другой класс, для которого можно построить лучший по характеристикам распознаватель). Сложностей с построением синтаксических анализаторов не существовало бы, если, бы для КС-грамматик были разрешимы проблемы преобразования и эквивалент­ности. Но поскольку в общем случае это не так, то одним классом КС-грамматик,' для которого существуют линейные распознаватели, ограничиться не удается. По этой причине для всех классов КС-грамматик существует принципиально важное ограничение: в общем случае невозможно преобразовать произвольную КС-грамматику к виду, требуемому данным классом КС-грамматик, либо же дока­зать, что такого преобразования не существует. То, что проблема неразрешима в об­щем случае, не говорит о том, что она не решается в каждом конкретном частном случае, и зачастую удается найти такие преобразования. И чем шире набор классов КС-грамматик с линейными распознавателями, тем проще их искать. Только, когда в результате всех этих действий не удалось найти соответствующий класс КС-языков, разработчик вынужден строить универсальный распознаватель. Характеристики такого распознавателя будут существенно хуже, чем у линейного распознавателя: в лучшем случае удается достичь квадратичной зависимости вре­мени работы распознавателя от длины входной цепочки. Такое бывает редко, по­этому все современные компиляторы построены на основе линейных распознава­телем! (иначе время их работы было бы недопустимо велико).

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

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

11а вопрос о том, какой распознаватель — нисходящий пли восходящий — выбрать для построения синтаксического анализатора, пет однозначного ответа. Эту про­блему необходимо решать, опираясь на некую дополнительную информацию о том, как будут использованы пли каким образом будут обработаны результаты работы распознавателя. Более подробно обсуждение этого вопроса можно найти в [1, 7].

СОВЕТ----------------------------------------------------------------------------------------------------------------

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

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

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

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

1.            Выполнить простейшие преобразования над заданной КС-грамматикой.

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

Суть принципа такого разбора поясняет рис. 3.1. На нем изображена входная це­почка символов ауР5 в тот момент, когда выполняется свертка цепочки у. Символ а является последним символом подцепочки а, а символ b — первым символом подцепочки р\ Тогда, если в грамматике удастся установить непротиворечивые отношения предшествования, то в процессе выполнения разбора по алгоритму «сдвиг-свертка» можно всегда выполнять сдвиг до тех пор, пока между символом на верхушке стека и текущим символом входной цепочки существует отношение <. или =-. А как только между этими символами будет обнаружено отношение >,. сразу надо выполнять свертку. Причем для выполнения свертки из стека надо выбирать все символы, связанные отношением =■. Все различные правила в грам­матике предшествования должны иметь различные правые части — это гаранти­рует непротиворечивость выбора правила при выполнении свертки.

 

a

а

Рис. 3.1. Отношения между символами входной цепочки в грамматике предшествования

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

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

□  простого предшествования;

□  расширенного предшествования;
□  слабого предшествования;

□     смешанной стратегии предшествования;

□     операторного предшествования.

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

Матрицу операторного предшествования КС-грамматики можно построить, опи­раясь непосредственно на определения отношений предшествования [1, 3, 7], но проще и удобнее воспользоваться двумя дополнительными типами множеств — множествами крайних левых и крайних правых символов, а также множествами крайних левых терминальных и крайних правых терминальных символов для всех нетерминальных символов грамматики.

Если имеется КС-грамматика G(VT,VN,P,5), V = VT и VN, то множества край­них левых и крайних правых символов определяются следующим образом:

Q  L([7) = {Г | 3 U=> *Tz) — множество крайних левых символов относительно нетерминального символа U;

□  R(£Z) = {Т\ 3 [/=> *zT) — множество крайних правых символов относительно
нетерминального символа U,

где U — заданный нетерминальный символ (U e VN), Г — любой символ грамма­тики (Гg V),az — произвольная цепочка символов (ze V*, цепочка z может быть и пустой цепочкой).

Множества крайних левых и крайних правых терминальных символов определя­ются следующим образом:

□  L(([/) = [t | 3 f/=> *tz или 3 U=> *Ctz) — множество крайних левых терминаль­ных символов относительно нетерминального символа U;

Q  R,( U) = {t 13 U => *zt или 3 U => *ztC} — множество крайних правых терминаль­ных символов относительно нетерминального символа U,

где t— терминальный. символ (£е VT), U и С— нетерминальные символы ([/, С е VN), a z — произвольная цепочка символов (z e V*, цепочка может быть и пу­стой цепочкой).

Множества L(U) nR(U) могут быть построены для каждого нетерминального символа U e VN по очень простому алгоритму:

1. Для каждого нетерминального символа U ищем все правила, содержащие U в левой части. Во множество L(f/) включаем самый левый символ из правой части правил, а во множество R(£7) — самый правый символ из правой части (то есть во множество L(C/) записываем все символы, с которых начинаются правила для символа U, а во множество R(LT) — символы, которыми эти пра­вила заканчиваются). Если в правой части правила для символа U имеется только один символ, то он должен быть записан в оба множества — Ц[/) iiR(tT).

Для каждого нетерминального символа U выполняем следующее преобразо­вание: если множество L(U) содержит нетерминальные символы грамматики £/', U", ..., то его надо дополнить символами, входящими в соответствующие множества L(Lf), L(£/")... и не входящими в Ц(/)- Ту же операцию надо вы­полнить для R(f/). Фактически, если какой-то символ ГУ' входит в одно из мно­жеств для символа U, то надо объединить множества для V и U, а результат записать во множество для символа U.

 

Алгоритм «сдвиг-свертка» для грамматик операторного предшествования

Алгоритм «сдвиг-свертка» для грамматики операторного предшествования вы­полняется МП-автоматом с одним состоянием. Для моделирования его работы необходима входная цепочка символов и стек символов, в котором автомат мо­жет обращаться не только к самому верхнему символу, но и к некоторой цепочке символов на вершине стека.

Этот алгоритм для заданной КС-грамматики G(VT,VN,P,5) при наличии постро­енной матрицы предшествования можно описать следующим образом:

1.           Поместить в верхушку стека символ 1м («начало строки»), считывающую го­ловку МП-автомата поместить в начало входной цепочки (текущим входным символом становится первый символ входной цепочки). В конец входной це­почки надо дописать символ _LK («конец строки»).

2.           В стеке ищется самый верхний терминальный символ s; (если на вершине сте­ка лежат нетерминальные символы, они игнорируются и берется первый тер­минальный символ, находящийся под ними), при этом сам символ s. остается в стеке. Из входной цепочки берется текущий символ ai (справа от считываю­щей головки МП-автомата).

3.           Если символ s. — это символ начала строки (Х„), а символ а. — символ конца строки (1к), то алгоритм завершен, входная цепочка символов разобрана.

4.           В матрице предшествования ищется клетка на пересечении строки, помечен-' ной символом s., и столбца, помеченного символом ai (выполняется сравнение текущего входного символа и терминального символа на верхушке стека).

5.           Если клетка, найденная на шаге 3, пустая, то значит, входная строка символов не принимается МП-автоматом, алгоритм прерывается и выдает сообщение об; ошибке.

6.           Если клетка, найденная на шаге 3, содержит символ «=•» («составляет основу») или «<•» («предшествует»), то необходимо выполнить перенос (сдвиг). При выполнении переноса текущий входной символ а. помещается на верхушку сте­ка, считывающая головка МП-автомата во входной цепочке символов сдвигаётся на одну позицию вправо (после чего текущим входным символом становится, следующий символ ai + v i := i+ 1). После этого надо вернуться к шагу 2.

7.           Если клетка, найденная на шаге 3, содержит символ «•>» («следует»), то необходимо произвести свертку. Для выполнения свертки из стека выбираются все! терминальные символы, связанные отношением «=•» («составляет основу»)}! начиная от вершины стека, а также все нетерминальные символы, лежащие в стеке рядом с ними. Эти символы вынимаются из стека и собираются в ней почку у (если в стеке нет символов, связанных отношением «=■», то из него! вынимается один самый верхний терминальный символ и лежащие рядом с ним нетерминальные символы).

Во всем множестве правил Р грамматики G(VT,VN,P,S) ищется правило, у ко­торого правая часть совпадает с цепочкой у (по условиям грамматик предшествования все правые части правил должны быть различны, поэтому может быть найдено или одно такое правило, или ни одного). Если правило найдено, то в стек помещается нетерминальный символ из левой части правила, иначе, если правило не найдено, это значит, что входная строка символов не прини­мается МП-автоматом, алгоритм прерывается и выдает сообщение об ошибке. Следует отметить, что при выполнении свертки считывающая головка авто­мата не сдвигается и текущий входной символ at остается неизменным. После выполнения свертки необходимо вернуться к шагу 2.

После завершения алгоритма решение о принятии цепочки зависит от содержи­мого стека. Автомат принимает цепочку, если в результате завершения алгорит­ма он находится в состоянии, когда в стеке находятся начальный символ грамма­тики 5 и символ ±н. Выполнение алгоритма может быть прервано, если на одном из его шагов возникнет ошибка. Тогда входная цепочка не принимается. Алгоритм «сдвиг-свертка» для грамматики операторного предшествования игно­рирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Это преобразование заключается в том, что все нетерминальные симво­лы в правилах грамматики заменяются на один нетерминальный символ (чаще всего — целевой символ грамматики).

Построенная в результате такого преобразования грамматика называется остовной грамматикой, а само преобразование — основным преобразованием [1, 7]. Остовное преобразование не ведет к созданию эквивалентной грамматики и вы­полняется только для упрощения работы алгоритма (который при выборе правил все равно игнорирует нетерминальные символы) после построения матрицы пред­шествования. Полученная в результате остовного преобразования грамматика может не являться однозначной, но все необходимые данные о порядке примене­ния правил содержатся в матрице предшествования и распознаватель остается детерминированным. Поэтому остовное преобразование может выполняться без потерь информации только после построения матрицы предшествования. При этом также необходимо следить, чтобы в грамматике не возникло неоднозначно­стей из-за одинаковых правых частей правил, которые могут появиться в остовной грамматике. Вывод, полученный при разборе на основе остовной граммати­ки, называют результатом остовного разбора, или остовным выводом. По результатам остовного разбора можно построить соответствующий ему вывод На основе правил исходной грамматики. Однако эта задача не представляет прак­тического интереса, поскольку остовной вывод отличается от вывода на основе Исходной грамматики только тем, что в нем отсутствуют шаги, связанные с при­менением цепных правил, и не учитываются типы нетерминальных символов. Для Компиляторов же распознавание цепочек входного языка заключается не в на­хождении того или иного вывода, а в выявлении основных синтаксических кон­струкций исходной программы с целью построения на их основе цепочек языка Результирующей программы. В этом смысле типы нетерминальных символов И Цепные правила не несут никакой полезной информации, а напротив, только Усложняют обработку цепочки вывода. Поэтому для реального компилятора нахождение остовного вывода является даже более полезным, чем нахождение вывода на основе исходной грамматики. Найденный остовной вывод в дальней­ших преобразованиях уже не нуждается1.

В общем виде последовательность построения распознавателя для КС-граммати­ки операторного предшествования G(VT,VN,P,5) можно описать следующим об­разом:

1 На основе множества правил грамматики Р построить множества крайних ле­вых и крайних правых символов для всех нетерминальных символов грамма­тики Uе. VN: L(U) и R(U).

2.            На основе множества правил грамматики Р и построенных на шаге 1 множеств L(U) и R(£/) построить множества крайних левых и крайних правых терми­нальных символов для всех нетерминальных символов грамматики Ue VN: L,(£/)hR,(£/).

3.            На основе построенных па шаге 2 множеств ht(U) и R,([/) для всех терминаль­ных символов грамматики а е VT заполняется матрица операторного предше­ствования.

4.            Исходная грамматика G(VT,VN,P,5) преобразуется в остовную грамматику G'(VT,{5},P,S) с одним нетерминальным символом.

5.            На основе построенной матрицы предшествования и остовной грамматики | строится распознаватель па базе алгоритма «сдвиг-свертка» для грамматик операторного предшествования.

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

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

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

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

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

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

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

1.           Получить вариант задания у преподавателя.

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

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

4.           Подготовить и защитить отчет.

5.           Написать и отладить программу на ЭВМ.

6.           Сдать работающую программу преподавателю.

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

Отчет должен содержать следующие разделы:

□      Задание по лабораторной работе.

□      Краткое изложение цели работы.

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

□     Множества крайних правых и крайних левых символов с указанием шагов построения.

□     Множества крайних правых и крайних левых терминальных символов.

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

□   Пример выполнения разбора простейшего предложения входного языка.

□   Текст программы (оформляется после выполнения программы на ЭВМ).

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

□  Какую роль выполняет синтаксический анализ в процессе компиляции?

□     Какие проблемы возникают при построении синтаксического анализатора и как они могут быть решены?

□     Какие типы грамматик существуют? Что такое КС-грамматики? Расскажите об их использовании в компиляторе.

□ Какие типы распознавателей для КС-грамматик существуют? Расскажите о не­достатках и преимуществах различных типов распознавателей.

□     Поясните правила построения дерева вывода грамматики.

□     Что такое грамматики простого предшествования?

□ Как вычисляются отношения предшествования для грамматик простого пред­шествования ?

□   Что такое грамматика операторного предшествования ?

□   Как вычисляются отношения для грамматик операторного предшествования ?

□  Расскажите о задаче разбора. Что такое распознаватель языка?
□  Расскажите об общих принципах работы распознавателя языка.

□   Что такое перенос, свертка? Для чего необходим алгоритм «перенос-свертка»?

□     Расскажите, как работает алгоритм «перенос-свертка» в общем случае (с воз­вратами).

□     Как работает алгоритм «перенос-свертка» без возвратов (объясните на своем примере)?

Варианты заданий Варианты исходных грамматик

Далее приведены варианты грамматик. Во всех вариантах символ S является на­чальным символом грамматики; S, F, Ти £ обозначают нетерминальные символы.

Терминальные символы выделены жирным шрифтом. Вместо символа а должны
подставляться лексемы.                          i

1.   5-^a:=F;

F-+F+T\T

Т^Т-Е\ TIE\E E-*{F)\-{F)\a

2.  5^a:=F;

F -> F or T | F xor T | T

T->TsmdE\E £ -»(F) I not (F) | a

3.  5->F;

F -» if E then T else F\iiE then F | a := a

T -$> if E then T else T | a := a E —> a<a | a>a | a=a

4.  S^F;

F -> for (T) do F | a := a

T-^F;E;F\;E;F\F;E;\;E; E —> a<a | a>a | a=a

Исходные грамматики и типы допустимых лексем

Ниже в табл. 3.1 приведены номера заданий. Для каждого задания указана соот­ветствующая ему грамматика и типы допустимых лексем.

Таблица 3.1. Номера заданий для выполнения лабораторной работы

      №   варианта    Допустимые лексемы входного языка грамматики

1         1                          Идентификаторы, десятичные числа с плавающей точкой

2         2                          Идентификаторы, константы true и false

3         3                          Идентификаторы, десятичные числа с плавающей точкой

4         4                          Идентификаторы, десятичные числа с плавающей точкой

5         1                          Идентификаторы, римские числа

6         2                          Идентификаторы, константы 0 и 1

7         3                          Идентификаторы, римские числа

№   варианта    Допустимые лексемы входного языка грамматики

8         4                          Идентификаторы, римские числа

9         1                          Идентификаторы, шестнадцатеричные числа

 

10                       2                         Идентификаторы, шестнадцатеричные числа

11                       3                      '   Идентификаторы, шестнадцатеричные числа

12                       4                         Идентификаторы, шестнадцатеричные числа

13                       1                         Идентификаторы, символьные константы (в одинарных кавычках)

14           2                         Идентификаторы, символьные константы Т и'F'

15                       3                         Идентификаторы, строковые константы (в двойных кавычках) 16

4                           Идентификаторы, строковые константы (в двойных кавычках)

примечание-

римскими числами считать последовательности больших латинских букв X, V и I. Шестнадцатеричными числами считать последовательность цифр и символов «а», «Ь», «с», «d», «е» и «f», начинающуюся с цифры (например: 89, 45ас9, 0abc4). Для выполнения работы рекомендуется использовать лексический анализатор, построен­ный в ходе выполнения лабораторной работы № 2.

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

Для выполнения лабораторной работы возьмем тот же самый язык, который был использован для выполнения лабораторной работы № 2.

Этот язык может быть задан, например, с помощью следующей КС-грамматики G({if,then,else,a,:=,or,xor,and,(,),;},{5,jF,£',D,Q,P,5) с правилами Р:

S->-F;

F—»if E then T else F | if E then F \ a := E T-^ if Ethen Telse Г| a := E E^EorD\ExorD\D D -» D and С | С C-*a|(£)

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

Построение матрицы операторного предшествования

Построение множеств крайних правых и крайних левых символов

Построение множеств крайних левых и крайних правых символов выполним со­гласно описанному ранее алгоритму.

На первом шаге возьмем все крайние левые и крайние правые символы из правил грамматики G. Получим множества, представленные в табл. 3.2.

Таблица 3.2. Множества крайних левых и крайних правых символов. Шаг 1

Символ U                L(U)                              R(U)

S                               F                                    ;

F                               if, a                               F, E

T                               if, a                               T; E

E                               E, D                               D

D                              D, С                              С

С                              а, (                                a, )

Из табл. 3.2 видно, что множества L(f/) для символов S, E, D, а также множества R([/) для символов F, T, E, D содержат другие нетерминальные символы, а потому должны быть дополнены. Например, L(5) должно быть дополнено L(F), так как символ F входит в L(5): Fe L(5), a R(f) должно быть дополнено R(-E), так как символ Е входит в R(F): E e R(F).

Выполним необходимые дополнения и получим множества, представленные в табл. 3.3.

Таблица 3.3. Множества крайних левых и крайних правых символов. Шаг 2

Символ U                L(U)                              R(U)

S                              F, if, a                                   ,     ;

F  -                            if, a                                 F, E, D

T                               if, a                                T, E, D

E                               E, D, С                               D, С

D                             D, C, a, (                            C, a, )

С                            a, (                                            a,)

Практически все множества в табл. 3.3 изменились по сравнению с табл. 3.2 (кро­ме множеств для символа С), а значит, построение не закончено. Продолжим до­полнять множества. Получим множества, представленные в табл. 3.4.

В табл. 3.4 по сравнению с табл. 3.3 изменились множества для символов F,TvlE — построение не закончено. Продолжим дополнять множества. Получим множества, представленные в таблице.

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

Таблица 3.4. Множества крайних левых и крайних правых символов. Шаг 3

Символ U                  MU)       ___________ *W_

F, if, a

if, a                               F, E, D, С

if, а                               Т, Е, D, С

Е                                Е, D, С, а, (                  D,C, а, )

D, С, а, (                       с-а.)

а,

D

С                               а>(

Таблица 3.5. Множества крайних левых и крайних правых символов. Шаг 4 (результат)

Символ U

L(U)                              R<U>

 

s

F, if, a

;

F

if, a

F, E, D, С a, )

т

if, a

T, E, D, C, a, )

E

E, D, C, a, (

D, С a, )

D

D, С, а, (

C, a, )

С

a, (

a,)

В табл. 3.5 по сравнению с табл. 3.4 изменились только множества R(U) для сим­волов F и Г — построение не закончено. Продолжим дополнять множества. Но если выполнить еще один шаг (шаг 5), то можно убедиться, что множества уже больше не изменятся (чтобы не создавать еще одну лишнюю таблицу, этот шаг здесь выполнять не будем). Таким образом, множества, представленные в табл. 3.5, являются результатом построения множеств крайних левых и крайних правых символов грамматики G.

Построение множеств крайних правых и крайних левых терминальных символов

Построение множеств крайних левых и крайних правых терминальных символов также выполним согласно описанному выше алгоритму.

На первом шаге возьмем все крайние левые и крайние правые терминальные символы из правил грамматики G. Получим множества, представленные в табл. 3.6.8■

 

 Таблица 3.6. Множества крайних левых и крайних правых терминальных символов. Шаг 1

Символ U                Lt(U)                            Bt(U)

if a                                else, then,

if, a                               else' :=

or, xor                          or, xor

and                               and

S

F T E D

 

 

 

Дополним множества, представленные в табл. 3.6, на основании ранее построенных множеств крайних левых и крайних правых символов, представленных в табл. 3.5. Например, L,(£) должно быть дополнено Lf(D) и Ц(С), так как символы D и С вхо­дят в L(F): D, С е L(E), a R,(F) должно быть дополнено R,(E), R,(D) и R,(C), так как символы Е, D и С входят в R(F): E,D, Ce R(F).

Получим итоговые множества крайних левых и крайних правых терминальных символов, которые представлены в табл. 3.7.

Таблица 3.7. Множества крайних левых и крайних правых терминальных симво­лов. Результат

Символ U                 Lt(U)                             Rt(U)

if, a, ;

if, a

if, a

or, xor, and, a, (

and, a, (

а, (

else, then, :=, or, xor, and, a, ) else, := , or, xor, and, a, ) or, xor, and, a, ) and, a, ) a,)

 

 

Теперь все готово для заполнения матрицы операторного предшествования.

Заполнение матрицы предшествования

Для заполнения матрицы операторного предшествования необходимы множе­ства крайних левых и крайних правых терминальных символов, представлен­ные в табл. 3.7, и правила исходной грамматики G.

Заполнение таблицы рассмотрим на примере лексем or и (. Символ or не стоит рядом с другими терминальными символами в правилах грам­матики. Поэтому знак «=•» («составляет основу») для него не используется.

Символ or стоит слева от нетерминального символа D в правиле Е —> Е or D. В мно­жество L,(D) входят символы and, а и (. Поэтому в строке матрицы, помеченной символом or, ставим знак «<•» («предшествует») в клетках на пересечении со стол­бцами, помеченными символами and, а и (.

Кроме того, символ or стоит справа от нетерминального символа Е в том же пра­виле Е—» Eor D. В множество R,(£) входят символы or, xor, and, а и ). Поэтому в столбце матрицы, помеченном символом or, ставим знак «•>» («следует») в клет­ках на пересечении со строками, помеченными символами or, xor, and, а и ).

Больше ни в каких правилах символ or не встречается, поэтому заполнение мат­рицы для него закончено.

Символ ( стоит рядом с терминальным символом ) в правиле С —> (Е) (между ними должно быть не более одного нетерминального символа — в данном случае один символ Е). Поэтому в строке матрицы, помеченной символом (, ставим знак «=■» («составляет основу») на пересечении со столбцом, помеченным символом ). Символ ( также стоит слева от нетерминального символа Е в том же правиле С —> (Е). В множество L,(£) входят символы or, not, and, а и (. Поэтому в строке матрицы, помеченной символом (, ставим знак «<•» («предшествует») в клетках на пересечении со столбцами, помеченными символами or, not, and, а и (. Больше ни в каких правилах символ ( не встречается, поэтому заполнение матри­цы для него закончено.

Повторяя описанные выше действия по заполнению матрицы для всех терминаль­ных символов грамматики G, получим матрицу операторного предшествования. Останется только заполнить строку, соответствующую символу ±и («начало стро­ки»), и столбец, соответствующий символу 1к («конец строки»). Начальным символом грамматики G является символ 5, поэтому для заполнения строки, помеченной 1н, возьмем множество L,(5). В это множество входят симво­лы if, а и ;. Поэтому в строке матрицы, помеченной символом ±п, ставим знак «<•» («предшествует») в клетках на пересечении со столбцами, помеченными сим­волами а и ;.

Аналогично, для заполнения столбца, помеченного _1_к, возьмем множество R,(S). В это множество входит только один символ — ;. Поэтому в столбце матрицы, помеченном символом 1к, ставим знак «•>» («следует») в клетке на пересечении со строкой, помеченной символом ;.

В итоге получим заполненную матрицу операторного предшествования, которая представлена в табл. 3.8.

 

iаолица о.

Символы

U.    [VIC

11 ^»ll_l,.

if

then

else

A

or

xor

and

(

)

1K

;

 

 

 

 

<.

<•

<•

<.

<■

 

■>

if

 

 

 

 

 

 

 

 

 

 

 

then

■>

<•

 

=-

<■

 

 

 

 

 

 

else

.>

<.

 

■>

<•

;.                 .>

.>

•>

 

•>

 

а

■>

 

> 

■>

 

<;.

<.

<.

<•

 

 

■ =

•>

 

.>

<•

 

 

 

 

 

 

 

or

.>

 

■>

.>

<•

■>

■>

<.

<•

.>

 

xor

■>

 

•>

.>

<•

> 

•>

<•

<■

.>

 

and

•>

 

.>

•>

<■

• >

•>

.>

<■

•>

 

(

 

 

 

 

<•

<■

<■ •>

.>

<■

> 

 

)

.>

 

•>

.>

 

 

 

 

 

 

 

1к

<•

<■

 

 

<■

 

 

 

 

 

 

Теперь на основе исходной грамматики G можно построить остовную граммати­ку G'({if,then,else,a,:=,or,not,and,(,),;},{Е},Р',Е) с правилами Р':

Е —> Е; — правило 1;

Е —»if E then E else E | if E then Е \ а := Е — правила 2, 3 и 4;

Е —> if E then £ else Е \ а := Е — правила 5 и 6;

Е —> Е or Е | Е not E\E— правила 7, 8 и 9;

Е —> Е and Е \ Е — правила 10 и 11; £—> а | (Е) — правила 12 и 13.

Жирным шрифтом в грамматике и в правилах выделены терминальные символы. Всего имеем 13 правил грамматики. Причем правила 2 и 5, а также правила 4 и 6 в остовной грамматике неразличимы, а правила 9 и 11 не имеют смысла (как было уже сказано, цепные правила в остовных грамматиках теряют смысл). То, что две пары правил стали неразличимы, не имеет значения, так как по смыслу (семантике входного языка) эти две пары правил обозначают одно и то же (правила 2 и 5 соот­ветствуют полному условному оператору, а правила 9 и 11 — оператору присваи­вания). Поэтому в дереве синтаксического разбора нет необходимости их разли­чать. Следовательно, синтаксический распознаватель может пользоваться остов­ной грамматикой G'.

Примеры выполнения разбора предложений входного языка

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

Рассматриваемый МП-автомат имеет только одно состояние. Тогда для иллюст­рации работы МП-автомата будем записывать каждую его конфигурацию в виде трех составляющих {а|(3|у}, где:

□     а — непрочитанная часть входной цепочки;

□     (3 — содержимое стека МП-автомата;

Q у- последовательность номеров примененных правил.

В начальном состоянии вся входная цепочка не прочитана, стек автомата содер­жит только лексему типа «начало строки», последовательность номеров правил пуста.

Для удобства чтения стек МП-автомата будем заполнять в порядке справа нале­во, тогда находящимся на верхушке стека будет считаться крайний правый сим­вол в цепочке (3.

Пример 1

Возьмем входную цепочку «if a or b and с then a := 1 not с;».

После выполнения лексического анализа, если все лексемы типа «идентификатор» и «константа» обозначить как «а», получим цепочку: «if a or a and a then a := a not a;». Рассмотрим процесс синтаксического анализа этой входной цепочки. Шаги функ­ционирования МП-автомата будем обозначать символом « + >>. Символом « + п» будем обозначать шаги, на которых выполняется сдвиг (перенос), символом « _=_ с» — шаги, на которых выполняется свертка.

{if a or a and a then а := a xor a;±J±JX} ■*■ м {a or a and a then a := a xor ajlJi^iflX} * „ {or a and a then a := а xor a;ij±„if a\k} + с {or a and а then a := а xor a;lj±nif £|12} + м {a and я then а := а xor a;±J±ltif £orjl2} + н {and a then а := a xor ajljj^if £ or я|12} + c {and a then a := a xor ajJ-J_Lnif £ or £|12 12} -{a then я := a xor a;lJlMif £ or £ and|l2 12} - „ {then a := a xor ajljl^if £ or £ and a|12 12} -s- c {then a := я xor a;±J±Hif £ or £ and £|12 12 12} + c {then a ■« a xor a;ljl„if £ or £jl2 12 12 10} + ,. {then a := a xor a;±J±„if £jl2 12 12 10 7} * „ {a := a xor a;±K|±Hif £then|12 12 12 10 7} + „ {:= a xor fl;ljlHif£then я|12 12 12 10 7} + „ {a xor a;±J±Hif£ then a:-|12 12 12 10 7} +n {xor a;±J±„if £ then a:- я|12 12 12 10 7} * c {xor a;ljl„if £then a := £|12 12 12 10 7 12} + „ {a;±J±Mif £ then a::- £xor|12 12 12 10 7 12} + м {;l,Jl„if£ then a:-E xor a|12 12 12 107 12} +c {;ljl„if £then a := £xor £jl2 12 12 10 7 12} -c {;ljl„if £then a := E|12 12 12 10 7 12 12 8} + c {;ll± if £ then £11212 12 10 7 12 12 8 4} + . {;ljl„£|12 12 12 10 7 12 12 8 4 3} + „ {1K|1„£;|12 12 12 10 7 12 12 8 4 3} + c

{±j£±J12 12 12 10 7 12 12 8 4 3 1} — разбор закончен, МП-автомат перешел в ко­нечную конфигурацию, цепочка принята.

В результате получим последовательность правил: 12 12 12 10 7 12 12 8 4 3 1. Этой |
последовательности правил будет соответствовать цепочка вывода на основе ос- |
товной грамматики С:                                                                                                                            j

£=>, £; =>3 if £ then £; =>4 if £ then a := £; =>8 if £ then я := £ xor £; =>)2 if £ then а := £ xor a; j
=>l2 if £ then а := a xor a; =>7 if £ or £ then a := a xor я; =>J0 if £ or £ and £ then a := a xor a; j
=>,2 if £ or £ and a then a := a xor a; =>i2 if £ or a and a then а := a xor a;

=>)2 if я or a and а >
then а := a xor а;                                                                                                                                               '

Стоит обратить внимание, что, так как данный МП-автомат строит правосторон­ний вывод, в цепочке вывода на каждом шаге правило всегда применяется тс край­нему правому нетерминальному символу в цепочке.

Дерево синтаксического разбора, соответствующее данной входной цепочке, при­ведено на рис. 3.2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 3.2. Дерево синтаксического разбора входной цепочки «if a or a and a then a := a xor a;»

Пример 2

Возьмем входную цепочку «if (a or b then a := 25;»..

После выполнения лексического анализа, если все лексемы типа «идентифика­тор» и «константа» обозначить как «а», получим цепочку: «if (a or a then a := а». Рассмотрим процесс синтаксического анализа этой входной цепочки: {if (a or a then a := a;J_J±jX} + {(a or a then a := e;lK[±ltif|A,} + п [a or a then a := e;!j-L if(|A.} -*■ „ {or a then а := a;±JJ_Hif(a|A} + с {orathene:=fl;±J±i(if(E|l2} *n {a then a :=