Рис. 1.4. Внешний вид интерфейсной формы для лабораторной работы № 1.
Функция чтения содержимого файла с идентификаторами (procedure TLab1Form. BtnLoadClick) вызывается щелчком по кнопке BtnLoad. Она организована таким образом, что сначала содержимое файла читается в многострочное поле Listldents, а затем все прочитанные идентификаторы записываются в две таблицы идентификаторов. Каждая строка файла считается отдельным идентификатором, пробелы в начале и в конце строки игнорируются. При ошибке размещения идентификатора в одной из таблиц выдается предупреждающее сообщение (например, если будет считано более 223 различных идентификаторов, то рехэширование станет невозможным и будет выдано сообщение об ошибке).
Функция поиска идентификатора (procedure TLab1Form.SearchStr) вызывается однократно щелчком по кнопке BtnSearch (процедура procedure TLab1Form.BtnSearchClick) или многократно щелчком по кнопке BtnAllSearch (процедура procedure TLab1Form. BtnAllSearchClick). Поиск идет сразу в двух таблицах, результаты поиска и накопленная статистическая информация отображаются в соответствующих полях.
Полный текст программного кода модуля интерфейса с пользователем и описание ресурсов пользовательского интерфейса находятся в архиве, располагающемся на веб-сайте издательства, в файлах FormLab1.pas и FormLab1.dfm соответственно.
Полный текст всех программных модулей, реализующих рассмотренный пример для лабораторной работы № 1, можно найти в архиве, располагающемся на вебсайте, в подкаталогах LABS и COMMON (в подкаталог COMMON вынесены те программные модули, исходный текст которых не зависит от входного языка и задания по лабораторной работе). Главным файлом проекта является файл LAB1.DPR в подкаталоге LABS. Кроме того, текст модуля FncTree приведен в листинге П3.1 в приложении 3.
Выводы по проделанной работе
В результате выполнения написанного программного кода для ряда тестовых файлов было установлено, что при заполнении таблицы идентификаторов до 20 % (до 45 идентификаторов) для поиска и размещения идентификатора с использованием рехэширования на основе генератора псевдослучайных чисел в среднем требуется меньшее число сравнений, чем при использовании хэш-адресации в комбинации с бинарным деревом. При заполнении таблицы от 20 % до 40 % (примерно 45–90 идентификаторов) оба метода имеют примерно равные показатели, но при заполнении таблицы более, чем на 40 % (90-223 идентификаторов), эффективность комбинированного метода по сравнению с методом рехэширования резко возрастает. Если на входе имеется более 223 идентификаторов, рехэширование полностью перестает работать.
Таким образом, установлено, что комбинированный метод работоспособен даже при наличии простейшей хэш-функции и дает неплохие результаты (в среднем 3–5 сравнений на входных файлах, содержащих 500–700 идентификаторов), в то время как метод на основе рехэширования для реальной работы требует более сложной хэш-функции с диапазоном значений в несколько тысяч или десятков тысяч.
Лабораторная работа № 2
Проектирование лексического анализатора
Цель работы
Цель работы: изучение основных понятий теории регулярных грамматик, ознакомление с назначением и принципами работы лексических анализаторов (сканеров), получение практических навыков построения сканера на примере заданного простейшего входного языка.
Краткие теоретические сведения
Назначение лексического анализатора
Лексический анализатор (или сканер) – это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
Лексема (лексическая единица языка) – это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка. Лексемами языков программирования являются идентификаторы, константы, ключевые слова языка, знаки операций и т. п. Состав возможных лексем каждого конкретного языка программирования определяется синтаксисом этого языка.
С теоретической точки зрения лексический анализатор не является обязательной, необходимой частью компилятора. Его функции могут выполняться на этапе синтаксического анализа. Однако существует несколько причин, исходя из которых в состав практически всех компиляторов включают лексический анализ. Это следующие причины:
• упрощается работа с текстом исходной программы на этапе синтаксического разбора и сокращается объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и удаляет всю незначащую информацию;
• для выделения в тексте и разбора лексем возможно применять простую, эффективную и хорошо проработанную теоретически технику анализа, в то время как на этапе синтаксического анализа конструкций исходного языка используются достаточно сложные алгоритмы разбора;
• лексический анализатор отделяет сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходной программы, структура которого может варьироваться в зависимости от версии входного языка – при такой конструкции компилятора при переходе от одной версии языка к другой достаточно только перестроить относительно простой лексический анализатор.
Функции, выполняемые лексическим анализатором, и состав лексем, которые он выделяет в тексте исходной программы, могут меняться в зависимости от версии компилятора. В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, знаков операций, разделителей и ключевых (служебных) слов входного языка.
В большинстве компиляторов лексический и синтаксический анализаторы – это взаимосвязанные части. Где провести границу между лексическим и синтаксическим анализом, какие конструкции анализировать сканером, а какие – синтаксическим распознавателем, решает разработчик компилятора. Как правило, любой анализ стремятся выполнить на этапе лексического разбора входной программы, если он может быть там выполнен. Возможности лексического анализатора ограничены по сравнению с синтаксическим анализатором, так как в его основе лежат более простые механизмы. Более подробно о роли лексического анализатора в компиляторе и о его взаимодействии с синтаксическим анализатором можно узнать в [1–4, 7].
Проблема определения границ лексем
В простейшем случае фазы лексического и синтаксического анализа могут выполняться компилятором последовательно. Но для многих языков программирования информации на этапе лексического анализа может быть недостаточно для однозначного определения типа и границ очередной лексемы.
Иллюстрацией такого случая может служить пример оператора программы на языке Фортран, когда по части текста DO 10 I=1… невозможно определить тип оператора (а соответственно, и границы лексем). В случае DO 10 I=1.15 это будет присвоение вещественной переменной DO10I значения константы 1.15 (пробелы в Фортране игнорируются), а в случае DO 10 I=1,15 это цикл с перечислением от 1 до 15 по целочисленной переменной I до метки 10.
Другая иллюстрация из более современного языка программирования C++ – оператор присваивания k=i+++++j;, который имеет только одну верную интерпретацию (если операции разделить пробелами): k = i++ + ++j;.
Если невозможно определить границы лексем, то лексический анализ исходного текста должен выполняться поэтапно. Тогда лексический и синтаксический анализаторы должны функционировать параллельно, поочередно обращаясь друг к другу. Лексический анализатор, найдя очередную лексему, передает ее синтаксическому анализатору, тот пытается выполнить анализ считанной части исходной программы и может либо запросить у лексического анализатора следующую лексему, либо потребовать от него вернуться на несколько шагов назад и попробовать выделить лексемы с другими границами. При этом он может сообщить информацию о том, какую лексему следует ожидать. Более подробно такая схема взаимодействия лексического и синтаксического анализаторов описана в [3, 7].
Параллельная работа лексического и синтаксического анализаторов, очевидно, более сложна в реализации, чем их последовательное выполнение. Кроме того, такой подход требует больше вычислительных ресурсов и в общем случае большего времени на анализ исходной программы, так как допускает возврат назад и повторный анализ уже прочитанной части исходного кода. Тем не менее сложность синтаксиса некоторых языков программирования требует именно такого подхода – рассмотренный ранее пример программы на языке Фортран не может быть проанализирован иначе.
Чтобы избежать параллельной работы лексического и синтаксического анализаторов, разработчики компиляторов и языков программирования часто идут на разумные ограничения синтаксиса входного языка. Например, для языка C++ принято соглашение, что при возникновении проблем с определением границ лексемы всегда выбирается лексема максимально возможной длины.