Принципы построения лексических анализаторов

АКАДЕМИЯ УПРАВЛЕНИЯ ПРИ ПРЕЗИДЕНТЕ РЕСПУБЛИКИ БЕЛАРУСЬ ИНСТИТУТ УПРАВЛЕНЧЕСКИХ КАДРОВ ФАКУЛЬТЕТ ИННОВАЦИОННОЙ ПОДГОТОВКИ КАФЕДРА УПРАВЛЕНИЕ ИНФОРМАЦИОННЫМИ РЕСУРСАМИ КОНТРОЛЬНАЯ РАБОТА по дисциплине «Интеллектуальные информационные системы»

на тему «Принципы построения лексических анализаторов»

Минск 2014

СОДЕРЖАНИЕ ВВЕДЕНИЕ ПОНЯТИЕ И ПРИЧИНЫ ИСПОЛЬЗОВАНИЯ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА ПРИНЦИПЫ ПОСТРОЕНИЯ ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ (ПРОГРАММА LEX)

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

Лексический анализатор (англ. lexical analyzer или коротко lexer) — это программа или часть программы, выполняющая лексический анализ. Лексический анализатор обычно работает в две стадии: сканирование и оценка.

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

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

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

По подробнее принцип построения лексического компилятора рассмотрим в данной курсовой работе.

ПОНЯТИЕ И ПРИЧИНЫ ИСПОЛЬЗОВАНИЯ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА Лексический анализатор (или сканер) — это часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы входного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.

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

Причины использования лексических анализаторов:

применение лексического анализатора упрощает работу с текстом исходной программы на этапе синтаксического разбора и сокращает объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и отбрасывает всю незначащую информацию;

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

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

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

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

ПРИНЦИПЫ ПОСТРОЕНИЯ ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ Лексический анализатор имеет дело с такими объектами, как различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык констант и идентификаторов является регулярным — то есть может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы. Следовательно, основой для реализации лексических анализаторов служат регулярные грамматики и конечные автоматы. Существуют правила, с помощью которых для любой регулярной грамматики может быть построен конечный автомат, распознающий цепочки языка, заданного этой грамматикой.

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

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

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

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

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

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

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

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

Пример анализа лексем, представляющих собой целочисленные константы в формате языка С. В соответствии с требованиями языка, такие константы могут быть десятичными, восьмеричными или шестнадцатеричными. Восьмеричной константой считается число, начинающееся с 0 и содержащее цифры от 0 до 7; шестнадцатеричная константа должна начинаться с последовательности символов 0х и может содержать цифры и буквы от, а до f. Остальные числа считаются десятичными (правила их записи напоминать, наверное, не стоит). Константа может начинаться также с одного из знаков + или -, а в конце цифры, обозначающей значение константы, в языке С может следовать буква или две буквы, явно обозначающие ее тип (u, U — unsigned; h, Н —short; l, L — long).

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

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

АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ (ПРОГРАММА LEX)

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

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

Для решения задач построения лексических анализаторов существуют различные программы. Наиболее известной среди них является программа LЕХ.

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

История программы LЕХ тесно связана с историей операционных систем типа UNIХ. Эта программа появилась в составе утилит ОС UNIХ и в настоящее время входит в поставку практически каждой ОС этого типа. Однако сейчас существуют версии программы LЕХ практически для любой ОС, в том числе для широко распространенной М5-DО5.

Поскольку LЕХ появилась в среде ОС UNIХ, то первоначально языком программирования, на котором строились порождаемые ею лексические анализаторы, был язык С. Но со временем появились версии LЕХ, порождающие сканеры и на основе других языков программирования (например, известны версии для языка Раsсаl).

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

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

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

последовательный;

параллельный

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

Работа синтаксического и лексического анализаторов в варианте их последовательного взаимодействия изображена в виде схемы на рис. 1.

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

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

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

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

помещать новую лексему в таблицу лексем;

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

добавлять новую лексему в таблицу идентификаторов;

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

прерывать процесс компиляции.

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

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

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

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

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

Правила трансляции %%

Вспомогательные подпрограммы.

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

[abc] - либо a, либо b, либо c;

[a-z] - диапазон символов;

R* - 0 или более повторений регулярного выражения R;

R+ - 1 или более повторений регулярного выражения R;

R1/R2 — R1, если за ним следует R2;

R1|R2 — либо R1, либо R2;

R? — если есть R, выбрать его;

R$ - выбрать R, если оно последнее в строке;

^R — выбрать R, если оно первое в строке;

[^R] - дополнение к R;

R{n, m} - повторение R от n до m раз;

{имя} - именованное регулярное выражение;

® — группировка.

Правила трансляции LEX программ имеют вид

p₁ { действие₁ }

p₂ { действие₂ }

p_n { действие_n },

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

Третья секция содержит вспомогательные процедуры, необходимые для действий. Эти процедуры могут транслироваться раздельно и загружаться с лексическим анализатором. Лексический анализатор, сгенерированный LEX, взаимодействует с синтаксическим анализатором следующим образом. При вызове его синтаксическим анализатором лексический анализатор посимвольно читает остаток входа, пока не находит самый длинный префикс, который может быть сопоставлен одному из регулярных выражений p_i. Затем он выполняет действие_i. Как правило, действие_i возвращает управление синтаксическому анализатору. Если это не так, т. е. в соответствующем действии нет возврата, то лексический анализатор продолжает поиск лексем до тех, пока действие не вернет управление синтаксическому анализатору. Повторный поиск лексем вплоть до явной передачи управления позволяет лексическому анализатору правильно обрабатывать пробелы и комментарии. Синтаксическому анализатору лексический анализатор возвращает единственное значение — тип лексемы. Для передачи информации о типе лексемы используется глобальная переменная yylval. Текстовое представление выделенной лексемы хранится в переменной yytext, а ее длина в переменной yylen.

ЗАКЛЮЧЕНИЕ

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

Был изучен принцип построения лексического анализатора и автоматизация построения лексического анализатора (LEX).

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Бржезовский А. В., Корсакова Н. В., Фильчаков В. В. Лексический и синтаксический анализ. Формальные языки и грамматики — Л.: ЛИАП, 1990.

Льюис Ф. и др. Теоретические основы построения компиляторов — М.: Мир, 1979.

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции — М.: Мир, 1978, т.1.

Робин Хантер Основные концепции компиляторов — М.: Издательский дом «Вильямс», 2002.

Ахо А, Сети Р., Ульман Д. Компиляторы: принципы, технологии инструменты.: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.:ил. ISBN5−8459−0189−8(рус), ББК 32.973.26.-018.2.75