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

Лексический анализ

Вопросы

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

«Я мечтаю жить в Париже, как мой отец.» (мечтаю, как отец, или жить в Париже, как отец?);

«Вывешены списки студентов, которые находились в деканате.» (списки или студенты находились в деканате?);

«Мать велела сыну налить воды себе.» (кому налить воды, сыну или матери?).

2. Что такое синтаксис и семантика языка?

3. В чем отличие компилятора от транслятора?

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

5. Почему компилятор языка Си работает дольше, чем компилятор языка Паскаль?

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

Лексема — это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе дру­гих структурных единиц языка.

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

Каждый класс лексем описывается правилом, называемым шаблоном. Шаблон соответствует каждой строке в наборе-классе лексем. Лексема же представляет собой последовательность символов исходной программы, которая соответствует шаблону. Например, в инструкции Pascal

const e = 2.78;

подстрока pi представляет собой лексему “идентификатор”.

Шаблон-лексема	Пример лексем	Неформальное описание шаблона
const	const	const
relation	<,<=,>,>=,<>,=	< или <= или >или >= или <> или =
num	2.78	Любая числовая константа
id	pi	Буква, за которой следуют буквы и цифры

Рис. 4. Примеры лексем.

Шаблон – правило, описывающее набор лексем, которые могут представлять определенную лексему в исходной программе. Так, шаблон const (рис. 4) представляет собой просто строку const, являющуюся ключевым словом. Шаблон relation – набор всех шести операторов сравнения в Pascal. Для точного описания сложных шаблонов типа id (для идентификатора) и num (для числа) нужно использовать регулярные выражения.

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

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

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

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

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

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

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

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

Основные функции лексического анализатора:

1) исключение из текста исходной про­граммы комментариев;

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

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

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

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

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

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

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

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

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

Рис. 5. Параллельное взаимодействие лексического и синтаксического анализаторов

Дата добавления: 2014-12-27