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

Причины использования лексических анализаторов. Язык констант и идентификаторов. Основные программы, существующие для решения задач построения лексических анализаторов. История программы LЕХ, принцип ее работы и правила трансляции, секция объявлений.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
АКАДЕМИЯ УПРАВЛЕНИЯ ПРИ ПРЕЗИДЕНТЕ РЕСПУБЛИКИ
КАФЕДРА УПРАВЛЕНИЕ ИНФОРМАЦИОННЫМИ РЕСУРСАМИ
по дисциплине «Интеллектуальные информационные системы»
на тему «Принципы построения лексических анализаторов»
ПОНЯТИЕ И ПРИЧИНЫ ИСПОЛЬЗОВАНИЯ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА
ПРИНЦИПЫ ПОСТРОЕНИЯ ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ
АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ (ПРОГРАММА 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-программа состоит из трех частей: лексический анализатор идентификатор трансляция
Секция объявлений включает объявления переменных, констант и определения регулярных выражений. При определении регулярных выражений могут использоваться следующие конструкции:
R* - 0 или более повторений регулярного выражения R;
R+ - 1 или более повторений регулярного выражения R;
R1/R2 - R1, если за ним следует R2;
R$ - выбрать R, если оно последнее в строке;
^R - выбрать R, если оно первое в строке;
R{n,m} - повторение R от n до m раз;
{имя} - именованное регулярное выражение;
Правила трансляции LEX программ имеют вид
где каждое 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
Измерение S–параметров с помощью рефлектометров. Анализаторы цепей СВЧ. Принцип работы импульсного рефлектометра. Измерители комплексных коэффициентов передачи и отражения. Особенности применения рефлектометров. Методы калибровки измерителя S–параметров. дипломная работа [1,1 M], добавлен 21.09.2012
Скалярные анализаторы цепей (ВАЦ) как база для создания гетеродинных векторных анализаторов: разница в устройстве. Достоинства и недостатки гетеродинных ВАЦ. Упрощенная схема гомодинных векторных анализаторов цепей. Классификация методов измерения. реферат [61,9 K], добавлен 23.01.2009
Исследование технологии построения систем передачи со спектральным уплотнением оптических каналов WDM/DWDM. Характеристика основных принципов работы анализаторов оптического спектра. Организация тестирования параметров линейных сигналов систем WDM/DWDM. презентация [1,6 M], добавлен 05.02.2011
Общие сведения о сетевых анализаторах, особенности их применения. Виды и анализ конвергентных (мультисервисных) сетей. Обратная сторона использования и сущность анализаторов сетевых протоколов. Принцип действия и работа системы мониторинга безопасности. курсовая работа [3,5 M], добавлен 01.03.2013
Исследование принципа работы схемы сумматора структуры адреса, основных электрических параметров микросхем. Изучение последовательности операций параметрического контроля. Обзор алгоритма интерполяции по методу цифровых дифференциальных анализаторов. курсовая работа [3,5 M], добавлен 22.05.2012
Рассмотрение системы аварийного расхолаживания высокого и низкого давлений, назначения, принципа работы борного регулирования. Изучение устройства составных частей анализатора, пульта измерительного базового, концентратометров НАР 12М, УНО-60М-01. дипломная работа [2,9 M], добавлен 25.03.2010
Методика построения программной модели. Обобщенная структурная схема ВС. Моделирование работы абонента и работы буферной памяти. Разработка программы сбора статистики и управляющей программы имитационной модели. Методика реализации событийной модели. курс лекций [190,1 K], добавлен 24.06.2009
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Принципы построения лексических анализаторов контрольная работа. Коммуникации, связь, цифровые приборы и радиоэлектроника.
Организация Труда Темы Рефератов
Реферат по теме Мир глазами Исаака Ньютона: пространство и время
Реферат: Вирусная диарея крупного рогатого скота. Скачать бесплатно и без регистрации
Реферат На Тему Рынок Медикаментов
Реферат: Государственная молодежная политика сущность, проблемы, способы реализации
Дипломная работа: Халькогеніди свинцю і сполуки на їх основі
Реферат По Географии 5 Класс География Сегодня
Реферат На Тему Понятие Предупреждения Преступления
Курсовая работа по теме Расчет гидравлической системы строительно-дорожных машин
Реферат Автоматизация Водоохладительных Установки Типа Ув 10
Адгезия Флюса При Сварке Жаропрочных Сплавов Реферат
Сочинение По Картине Степанова Лоси 2
Определение интервалов притока и поглощения с помощью дебитомеров
Сочинение Мир Где Нет Музыки
Дипломная работа по теме Проект ділянки нової залізниці
Курсовая работа: Формы реализии уголовной ответственности
Курсовая работа по теме Влияние внешних факторов на функционирование организации
Сочинения Делу Время
Реферат: Бухгалтерский учет на ООО "Санаторий". Скачать бесплатно и без регистрации
Курсовая работа по теме Задачи и содержание аудита маркетинга
Особенности современной научной картины мира - Биология и естествознание реферат
Создание опорной межевой сети. Инженерно-геодезические работы при межевании земель - Геология, гидрология и геодезия курсовая работа
Наука хозяйственного права - Государство и право контрольная работа