LexBisonLabs

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ

СРЕДСТВА АВТОМАТИЗАЦИИ ПОСТРОЕНИЯ СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ

Методические указания к выполнению лабораторных работ № 1-2

Санкт-Петербург

2006

2

Составители: А.В.Бржезовский, Т.М.Максимова, А.А.Янкелевич

Рецензент: А.В.Гордеев

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

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

альностям 230105 и 010503.

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

	©	ГОУ ВПО СПбГУАП, 2006
_______________________________________________________________________________
Подписано к печати	Формат 60х84 1/16. Бумага офсетная. Печать офсетная
Усл. печ. л Усл. кр.-отт. 0,00. Уч.- изд. л Тираж экз. Заказ №

________________________________________________________

Редакционно-издательский отдел Отдел электронных публикаций и библиографии библиотеки

Отдел оперативной полиграфии СПбГУАП

190000, Санкт-Петербург, ул. Б. Морская, 67

2

3

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

Сканирование и лексический анализ текстов c применением утилиты FLEX

1. Лексический анализ и регулярные выражения

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

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

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

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

Пусть T - конечный алфавит. Регулярное множество в алфавите T определяется рекурсивно следующим образом:

1){} (пустое множество) - регулярное множество в алфавите T;

2){a} - регулярное множество в алфавите T для каждого a T; 3){е} - регулярное множество в алфавите T (e - пустая цепочка);

4)если P и Q - регулярные множества в алфавите T, то таковы же и множества

-P Q (объединение),

-PQ (конкатенация, т.е. множество {pq}, p P, q Q),

-P* (итерация: P*={e} P PP ...;

-ничто другое не является регулярным множеством в алфавите T.

3

4

Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо {}, либо {e}, либо {a} для некоторого a T, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

Приведенное выше определение регулярного множества одновременно определяет и форму его записи, которую будем называть регулярным выражением. Для сокращенного обозначения выражения PP* будем пользоваться записью P+ и там, где это необходимо, будем использовать скобки. В этой записи наивысшим приоритетом обладает операция *, затем - конкатенация и, наконец, операция , для записи которой иногда будем использовать значок '|'. Так, 0|10* означает (0|(1(0*))).

Кроме того, мы будем использовать запись вида d1 = r1 d2 = r2 ....... dn = rn, где di - различные имена, а каждое ri - регулярное выражение над символами T {d1,d2,...,di-1}, т.е. символами основного алфавита и ранее определенными символами. Таким образом, для любого ri можно построить регулярное выражение над Т, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения.

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

Идентификатор = Буква (Буква|Цифра)*

Буква = {a,b,...,z} Цифра = {0,1,...,9}

Число в десятичной записи - это регулярное выражение Целое = Цифра+ Дробная_часть = . Целое | е

Степень = ( Е ( + | - | е ) Целое ) | е Число = Целое Дробная_часть Степень

Состав набора регулярных выражений зависит от того, какие лексемы ожидается получить на выходе сканера, и, обычно, определяется тем, какого рода синтаксический анализ следует проводить в дальнейшем. Например, для языка basic в качестве лексем могут рассматриваться: десятичное число, идентификатор, ключевое слово IF, ключевое слово THEN и так далее. В то же время, для сканирования и дальнейшей обработки некоего произвольного текста, например, табличной информации в виде ASCII документа, может потребоваться набор лексем, зависящий от того, как и каким образом сканируемая информация будет в дальшейшем использована. Набор лексем может для рассматриваемого примера включать: ключевые слова DATE и AMOUNT, используемые в заголовке таблицы; лексему-разделитель колонок, роль которой играет символ «Табуляция»; лексемуразделитель шапки таблицы от остальной ее части, роль которой играет последовательность символов “=====”; лексему «дата», определяющую дату в формате MM/DD/YYYY; а также лексему - число с фиксированной запятой.

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

2. Структура сканера текстов, создаваемого утилитой flex

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

4

5

Структура сканера c процедурным API приведена на Рис. 2. Структура сканера с объектно-ориентированным API приведена на Рис. 1. Для С++ сканера создаются два файла: lex.yy.cc и FlexLexer.h, последний содержит объявления для обоих классов.

Рис. 1. Классы объектно-ориентированного сканера

Файл “lex.yy.c”

char* yytext; /* тек. слово */

FILE* yyin; /*входной файл*/

FILE* yyout; /* для “Эхо” */

/* сканирующая процедура */ int yylex() {

….код, заданный пользователем….

….код, созданный автоматически…

}

/* обработка конца файла */ int yywrap()

{

…. код, заданный пользователем …

}

/* рестарт сканера с новым файлом */ int yyrestart(FILE* in)

{

…. код, созданный автоматически…

}

Рис. 2. Структура процедурного сканера

5

6

Для процедурного сканера создается один файл, обычно именумеый “lex.yy.c” Глобальные переменные, функции и методы классов имеют специальное значе-

ние. Наиболее важные из них:

yytext - указатель на последнее распознанное сканером слово (строка, ограниченная нулевым байтом). Для C++ сканера роль этой переменной играет метод YYText(). yyin - указатель на дескриптор файла, из которого производится чтение. Пользовательская программа должна инициализировать этот указатель. По умолчанию этим файлом является stdin.

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

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

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

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

3. Файл описания сканера

Для задания сканера создается специальный текстовый файл, который впоследствии обрабатывается утилитой flex для построения исходного программного кода. Файл включает в себя 3 секции: Определения, Правила и Пользовательский код. Последняя из них не является обязательной. Для разделения секций используется строка с символами

%%

Общая структура файла описания:

Определения

%%

Правила

%%

Пользовательский код

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

6

7

Утилита flex выполняет чтение файла и, на основании содержимого секции определений, производит построение размещаемых в выходном файле lex.yy.c (или lex.yy.cc для объектно-ориентированного сканера) внутренних таблиц для распознавания символов. На основе секции правил flex строит также размещаемый в файле lex.yy.c код обработки для каждой встреченной в исходном файле последовательности символов, удовлетворяющей заданному шаблону; а содержимое секции пользовательского кода копирует в выходной файл lex.yy.c без изменений. Таким образом, файл определений изначально содержит некоторые фрагменты кода на C/C++ , которые впоследствии добавляются к коду, создаваемому flex, и вместе образуют пользовательский сканер текстов.

В секциях определений и правил возможно указывать фрагменты (необходимые определения и объявления на языке С/С++), которые также будут попадать в результирующий файл без изменений, по аналогии с содержимым секции пользовательского кода. Это позволяет задать все необходимые с точки зрения С/С++ объявления до их использования в разделе правил. Для выделения таких конструкций используются разделители %{ и %}. Эти символы удаляются flex, а текст между ними помещается в выходной файл с исходным С/С++ кодом без изменений. Например:

%{

#include <stdio>

#define MAX_BUFFER_SIZE 4096 void print_error(int iErrorCode); %}

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

Основным элементом секции определений является объявление регулярного выражения в виде двух компонент:

<имя регулярного выражения> <выражение > , задаваемых в одной строке и разделяемых стандартными разделителями (пробелы, табуляции).

Например, строка:

Digit [0-9]

задает регулярное выражение, определяющее символ - десятичную цифру от 0 до 9. Выражение:

Number Digit ({Digit})*

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

Набор выражений позволяет построить шаблоны, по которым сканер выполняет поиск определенных последовательностей символов во входном тексте.

Секция правил состоит из строк вида: <выражение> <действие> ,

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

{<имя регулярного выражения>} <действие>

Действием является конструкция языка C/C++ или специальные макросы, обрабатываемые flex. Если действие состоит из нескольких операторов, для расположения их на нескольких строках могут использоваться операторные скобки { <действие> }. При задании пустого действия входное слово, удовлятворяющее шаблону, будет просто проигнорировано без дополнительной обработки. Типичным действием при обнаружении

7

8

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

%{

#define LEXEM_NUMBER 1 long iCurrNumLexValue = 0;

%}
%%
{Number}	{

iCurrNumLexValue = atol(yytext); return LEXEM_NUMBER;

}

В соответствии с рассмотренным правилом при обнаружении во входном тексте десятичного числа сканер сохранит значение этого числа в переменной iCurrNumLexValue и вернет код LEXEM_NUMBER как результат вызова yylex(). Вызывающая программа может обработать результаты и вновь вызвать yylex() для получения следующей лексемы.

В правилах можно обращаться к глобальным переменным сканера, например

yytext.

Порядок расположения правил имеет принципиальное значение. Если правило, выделяющее обобщенное множество слов (например, все слова, удовлетворяющие шаблону «идентификатор»), встречается раньше, чем правило, выделяющее конкретное слово (например, “WHILE”) из данного множества, то последнее правило никогда не будет активизировано.

Более полную информацию по структуре файла и доступным функциям можно получить в руководстве по flex.

4.Параметры flex

Всобранном виде flex включает в себя основной запускаемый файл, flex.exe, и, возможно, файл с шаблоном сканера flex.skl. В общем случае для запуска утилиты и получения результирующего С/C++ файла сканера можно воспользоваться следующей командой:

Flex.exe –o<имя результирующего файла> -Sflex.skl <имя файла описания>

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

- генерация C++ сканера “-+”;

- нечувствительность генирируемого сканера к регистру: “-i “;

8

9

- создание сканера, выводящего на stdout отладочные сообщения (при установленной в “1” глобальной переменной yy_flex_debug в коде сканера) : “-d”;

Для полного списка опций следует обратиться к руководству по flex.

Кроме параметров, в командной строке, можно указывать аналогичные значения в разделе определений файла описания сканера, используя синтаксис:

%option <код опции>

Полезные коды опций:

%option c++ %option yylineno %option noyywrap

Последние две опции недоступны через командную строку и могут быть заданы лишь в файле описания. yylineno позволяет включить поддержку функции lineno(). Вызов этой функции в пользовательском коде позволяет получить номер строки, из которой прочитана очередная лексема или в которой возникла ошибка. Опцию noyywrap необходимо указывать при отсутствии пользовательской реализации функции yywrap().

5. Пример описания сканера

В качестве примера, рассмотрим следующий текстовый файл, подлежаший обработке:

Ext 999 7:10 AM , 12/11/2003			Aspect
Page 1
			Users Database
			Default		Default
Ext #	Last Name	First Name	Type	Group	Team
201	TEST	TEST	Agent	20	0
202	TEST	TEST	Agent	21	0
203	TEST	TEST	Agent	23	0

Total Records: 3

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

Описание сканера может иметь следующий вид:

%option noyywrap %option yylineno

%option never-interactive

%{

#include <stdio.h> #include <string> #include "tokens.h"

9

10

std::string tmpstr = "";

%}

ws	[ \t]+
Digit	[0-9]
HexDigit	[0-9a-fA-F]
Number	[0-9]({Digit})*
HexNumber	0x({HexDigit})*
Tab	[\t]
Usk	[\x5F]
At	[\x40]
Dot	[\x2E]
Smc	[\x3A]
Sbra	[\x5B]
Sket	[\x5D]
Bra	[\x28]
Cket	[\x29]
Spc	[\x20]
Pls	[\x2B]
Min	[\x2D]
Sq	[\x27]
Semi	[\x2C]
Num	[#]
Slash	[\x2F]
Escape	[\\]([n]|[\"]|[\\])
AnyStrChr	[^\\"]
AP_USERS	Users
AP_ASPECT	Aspect
AP_DATABASE	Database
AP_PAGE	Page
AP_DEFAULT	Default
AP_PROFILE	Profile
AP_LASTNAME	Last{Spc}Name
AP_FIRSTNAME	First{Spc}Name
AP_TYPE	Type
AP_GROUP	Group
AP_TEAM	Team
AP_AGENT	Agent
AP_EXT	Ext
AP_TOTAL	Total
AP_RECORDS	Records
Id	[a-zA-Z]([a-zA-Z0-9]|[\x5F])*

10