LexBisonLabs

21

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

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

В рамках лабораторной работы будем рассматривать класс контекстно-свободных грамматик, задаваемых следующими элементами:

Пусть G – грамматика, образуемая следующими элементами:

N – множество нетерминальных символов (понятий языка) , T – множество терминальных символов (лексем),

P – множество продукций (правил вывода) вида A->b , где A – нетерминал а b цепочка, которая может содержать как терминальны так и нетерминальные

символы.

S - стартовый символ из множества N с которого начинается вывод. Предложением языка L(G), заданного граматикой G, называют цепочку лексем

(терминальных символов из множества Т). Цепочка, выведенная из S и содержащая как терминальные, так и нетерминальные символы, называется сентенциальной формой в грамматике G. Для формального языка любое из его предложений может быть выведенно (построено) из стартового символа S на основе правил из P. Таким образом, можно перечислить все предложения языка. Каждый шаг вывода представляет собой замену очередного нетерминального символа в рассматриваемой цепочке на другую цепочку, задаваемую правой частью продукции, содержащей заменяемый нетерминал в левой части. Исходная цепочка для начала вывода любого предложения, как уже упоминалось, состоит из единственного нетерминального символа S.

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

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

Наиболее эффективный программный анализатор может быть построен для LR – грамматик, получивших обозначение из-за того, что в них применяется сканирование входной последовательности слева-направо (L) и применяется правый разбор (R).

Для реализации LR анализаторов часто применяют механизм магазинного автомата. Магазинным автоматом называется набор M = (Q,T,Z,P,q0,F,s0), где Q - множество

21

22

состояний, T - входной алфавит, Z - магазинный алфавит, P - множество правил, q0 - начальное состояние, F - множество заключительных состояний, s0 - начальный магазинный символ.

Правила имеют вид: (q,a,z) -> (q',b) - если автомат находится в состоянии q, текущий входной символ равен a, верхний магазинный символ равен z, то можно прочесть символ a, заменить магазинный символ z цепочкой b и перейти в состояние q'; или (q,{},z) -> (q',b) - если автомат находится в состоянии q и верхний магазинный символ равен z, то можно заменить символ z цепочкой b и перейти в состояние q', не читая входной цепочки.

Практическое применение данной математической модели для синтаксическго анализа основано на использовании стека, в котором по мере работы размещаются прочтенные лексемы и нетерминальные символы, полученные в результате замены по правилам заданного языка. Состоянием автомата является состояние стека. Очередная лексема размещается в стеке (выполняется операция «перенос») после чего выполняется проверка содержимого стека на возможность применить одно из правил (продукций). При обнаружении в стеке последовательности символов, удовлетворяющих правой части некоторой продукции, символы удаляются из стека и заменяются на единственный символ из левой части продукции (выполняется операция «свертка»). Эта операция может быть повторена на новом состоянии стека без чтения следующей лексемы до тех пор, пока в стеке обнаруживаются последовательности, подлежащие замене. Если после исчерпания входных лексем стек автомата пуст – входная последовательность принимается как предложение языка L(G), для распознавания которого создан данный автомат.

2. Построение набора правил для описания формального языка

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

При составлении правил отправной точкой служит набор лексем, которыми оперирует сканер текстов. Они образуют множество терминальных символов. Например, множество может включать ключевые слова IF, THEN ELSE, а также идентификатор (id) и целое число (int) для случая простейшего языка программирования. При необходимости разбора текстовой информации в виде некоторой таблицы данных набор нетерминалов может, например, включать ключевые слова DATE, и AMOUNT, используемые в заголовке таблицы, разделитель «Табуляция» (tab), разделитель шапки таблицы “=====” (eq), дату в формате MM/DD/YYYY (date), число с фиксированной запятой (num) и т.д.

Далее вводятся обобщенные понятия, описывающие некоторые смысловые фрагменты цепочек языка. Например, “Выражение” (Expr), которое для простейшего языка программирования может быть определено: Expr -> id, а также Expr -> int. В данном случае приведены две продукции, описывающие возможные способы образования выражения в языке программирования. Для сокращения записи часто применяют символ | и объединяют продукции, в левых частях которых стоит один и тот же нетерминальный символ, записывая их следующим образом: Expr -> id | int.

Аналогично рассуждая, можно вывести продукцию для понятия «условный оператор» (CondStatment), используя при этом как множество исходных лексем, так и понятий (нетерминалов), выведенных на предыдущем шаге : CondStatment-> IF Expr THEN Expr ELSE Expr. Процесс продолжается вплоть до определения исходного понятия, например «Программа» (Prog) через ранее определенные понятия: Prog-> CondStatment. При со-

22

23

ставлении правил разбора для случая синтаксического анализа табличной информации, могут быть введены следующие понятия: «Элемент таблицы» (Cell) , «Шапка таблицы» (Header), «Строка таблицы» (Row):

Cell->date | num; Row-> Cell tab Cell; Header-> DATE tab AMOUNT eq;

В процессе составления продукций может потребоваться использование рекурсии или пустой продукции. В первом случае результирующая продукция включает имя понятия как в левой части, так и в правой. Например, «Множество строк таблицы» (Rows): Rows -> Row | Rows Row, задает одну или несколько строк. Если требуется также указать факт возможного отсутствия строк в таблице, то правило записывается как: Rows -> |Row | Rows Row с использованием пустой продукции, не содержашей никаких символов (отделенной от других первым разделителем | )

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

Утилита bison предназначена для генерации программного кода синтаксического анализатора на основе заданой грамматики (набора продукций). Утилита создает программный код на языке С/C++, доступный для встраивания в программу на C или С++. Синтаксический анализатор содержится в одном файле исходного кода и имеет процедурный API (программный интерфейс), структура анализатора представлена на Рис. 3. Помимо файла с программным кодом, утилита также может создавать включаемый файл, в котором через директиву #define объявлены коды лексем, описанных как входные в файле с заданной грамматикой. Этот включаемый файл может быть использован для согласования кодировки лексем между анализатором и сканером тестов.

23

24

Файл: analyser_yy.tab.c

/* ссылка на внешнюю int функцию () сканера возвращающую код лексемы*/

#define YYLEX yylex

/*ссылка на внешнюю void-функцию (const char*) для сообщения ошибки

*/

#define YYERROR yyerror

/* переопределяемый тип, int -умолчание */ typedef int YYSTYPE;

/* переменная для значения лексемы */

YYSTYPE yyval;

/* основная функция анализатора */ int yyparse() {

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

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

…обращения к YYLEX …

}

Рис. 3. Структура создаваемого файла анализатора

Утилита bison создает лишь процедурную реализацию синтаксического анализатора, объектная реализация является экспериментальной и содержит большое количество ошибок.

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

здаваемый программный код. Это функции int yylex() и void yyerror (char const* msg).

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

24

25

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

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

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

4. Файл описания синтаксического анализатора

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

%{

Определения программного кода

%}

Настройки bison

%%

Правила

%%

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

Утилита bison выполняет чтение файла и создает исходный программный код анализатора, в который добавляются определения и пользовательский код. Утилита создает реализацию магазинного автомата на основе продукций из раздела правил исходного файла описания. Файл описаний, так же, как и для случая с flex, содержит некоторые фрагменты C/C++ кода. Без изменений эти фрагменты перемещаются в начало результирующего файла из секции определений программного кода и в конец результирующего файла из секции пользовательского кода, если она задана. Это позволяет создать все необходимые описания C/C++ типов или включить требуемые внешние файлы, а также - обеспечить реализацию для всех функций, на которые ссылается создаваемый анализатор.

Секция настроек bison служит для задания списка лексем (множества терминальных символов), которые воспринимаются анализатором, а также определения типов данных, ассоциируемых с указанными лексемами и с вводимыми в рассмотрение позже нетерминальными символами.

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

25

26

на директива %union. Директива действует аналогично выражению union языка C. За ключевым словом в фигурных скобках указываются типы данных и переменные, которые хранят возможные значения, ассоциируемые с лексемами, например:

%union {

char* string;

}

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

%union {

char* string; long number;

}

В этом случае разные лексемы должны быть объявлены с использованием ссылки на разные поля. Директива объявления лексем, позволяющая выполнить такое сопоставление, будет рассмотрена позже.

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

Код синтаксического анализатора содержит глобальную переменную yylval (как указано на Рис. 3), объявленную внешней во включаемом файле со списком кодов лексем. Использование подобного файла в коде сканера текстов из предыдущей лабораторной работы позволяет, например, переписать объявление действия для лексемы AP_USERS для сканера следующим образом:

{AP_USERS} {

yylval.string = strdup(yytext); return AP_USERS_KW;

}

В этом примере лексический анализатор будет передавать в синтаксический анализатор помимо кода лексемы AP_USERS_KW еще и непосредственное значение этой лексемы в виде слова “Users” через глобальную переменную yylval.string. Полученное значение, как будет показано ниже, может быть в дальнейшем использовано в коде действия, связываемого с данной лексемой синтаксическим анализатором. Перечень лексем, ожидаемых анализатором должен быть приведен в секции настроек. Для этого используется директива %token <имя лексемы>, например:

%token AP_USERS_KW

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

26

27

Возможно задание нескольких лексем в одной директиве:

%token AP_ASPECT_KW AP_AGENT_KW AP_USERS_KW AP_DATABASE_KW

Все идентификаторы, объявленные в директивах token, автоматически определяются утилитой bison через директиву #define в результирующем коде анализатора.

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

%token <string> AP_USERS_KW

В приведенном примере с лексемой AP_USERS_KW связывается строковое значение, для хранения которого предварительно объявлено поле в директиве %union. При использовании директивы %union в директиве %token в обязательном порядке должен быть указан тип.

Существует возможность связывания специфического значения с нетерминальным символом, используемым внутри синтаксического анализатора, для чего используется директива %type, аналогичная директиве %token для лексем.

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

<левая часть продукции > : <правая часть продукции> [{действие}] ;

В левой части фигурирует нетерминальный символ, подлежащий определению через набор терминалов и\или нетерминалов в правой части. В дополнение к цепочке, определяющей правую часть продукции, может быть задано действие, выполняемое анализатором в момент применения данного правила – выполнения свертки в стеке. Действие задается в фигурных скобках после цепочки. При отсутствии действия цепочка завершается символом “;”. Если несколько продукций имеют одинаковые левые части, то допускается сокращать их в одно определение, используя символ “|” для разделения различных правых частей. Примеры правил и ассоциируемых с ними действией:

header : AP_USERS_KW AP_DATABASE_KW ;

expr : id | number;

statement : /* empty rule */ | expr

{

std::cout << “Statement detected”<< std::endl; };

conditionalstatement : IF_KW expr THEN_KW expr ELSE_KW expr

{

if ($2)

{

$$ = $4;

std::cout<< $4<< std::endl;

}

else

{

$$ = $6;

27

28

std::cout << $6<< std::endl;

}

};

Действие задается в виде фрагмента программного кода на языке C/C++, в котором возможны ссылки на переменные и типы, объявленные ранее в секции определений программного кода. В коде действия допустимы специальные макроподстановки $$ и $n, где n- число от 1 до количества элементов (терминалов и нетерминалов), использованных в правой части правила, для которого задано действие. Первое из макроопределений позволяет сослаться на результирующее значение нетерминального символа в левой части правила (например, conditionalstatement из приведенного выше примера). Bison в процессе генерации заменяет макроподстановку $$ на переменную, связанную с нетерминалом левой части правила, что позволяет присваивать ей значение. Остальные макроподстановки вида $n служат для доступа к значениям лексем и нетерминалов из правой части правила. Число n определяет порядковый номер элемента, для которого выбирается значение. Если для правила не задано действие, то по умолчанию bison ассоциирует с ним выражение $$ = $1, присваивая таким образом нетерминальному символу значение первого символа из правой части. Данное действие применимо, только если типы нетерминала и первого символа совместимы, иначе значение для нетерминала не определено.

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

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

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

5. Параметры утилиты bison

Для успешного запуска утилиты bison (версия 1.28) на платформе Windows требуется предварительно создать переменную среды окружения BISON_SIMPLE, в которой указать относительный путь из текущего каталога запуска до файла bison.simple, который распространяется вместе с утилитой.

В общем случае для запуска bison можно использовать следующую командную

строку

bison.exe -d -o <имя выходного файла парсера> <имя файла определения>

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

28

29

создаваемым анализатором. Имя этого файла конструируется из имени выходного файла, задаваемого ключом –o, и добавлением расширения “.h”.

Более подробно с опциями запуска bison можно ознакомится в документации на утилиту.

Если вы не установили переменную среды окружения при старте компьютера, то перед запуском bison из командной строки необходимо выполнить команду:

set BISON_SIMPLE = .\bison.simple

В процессе работы утилита печатает сообщения о статусе на консоль.

6. Типичные ошибки при составлении грамматики

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

<файл определения> contains <N> reduce/reduce conflicts. <файл определения> contains <N> shift/reduce conflicts.

Первый тип сообщения сигнализирует о серьезных ошибках «свертка\свертка» которые должны быть обязательно устранены. Сообщения второго рода также сигнализируют о том, что грамматика не является LR(1)-грамматикой, но иногда задать грамматику без подобного рода конфликтов невозможно. Bison предпринимает попытки разрешения такого конфликта, отдавая предпочтение переносу, что в большинстве случаев помогает решить проблему. Однако следует проанализировать причины возникновения конфликтов «перенос\свертка» и попытаться устранить их, изменяя грамматику, или хотя бы свести их количество к минимуму.

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

table	:	/*empty*/
		| row
		| table row ;
row	:	/* empty */
		| cell TAB_CHAR cell;

Данный набор утверждает, что таблица может состоять из одной или нескольких строк или вообще быть пустой, и что строка также может быть пустой. В данном случае пустая строка может быть свернута использованием первого правила для table так же, как и использованием первого правила для row. Решением проблемы может быть отказ от пустого правила для строки:

table	:	/*empty*/
	| row
	| table row ;
row	:	cell TAB_CHAR cell;

29

30

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

table	:	/*empty*/
	| table row ;
row	:	cell TAB_CHAR cell;

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

Еще одним примером возникновения конфликтов «перенос\свертка» является определение неполного условного оператора:

statement : IF expr THEN statement |

IF expr THEN statement ELSE statement ;

В этой ситуации после того, как прочтен неполный оператор If – then, анализатор не в состоянии определить, необходимо ли ему выполнять перенос, записывая следуюшую лексему ELSE в стек, либо сначала выполнить свертку для неполного оператора и продолжать анализ входных лексем. Этот пример наглядно демонстрирует, почему перенос является предпочтительной операцией для анализатора, так как при свертке может получиться синтаксическая ошибка на одиночный ELSE. Для устранения такой ошибки можно переформулировать правила следующим образом:

statement : condstat | uncondstat; condstat : ifthenstat | ifthenelsestat; fullstat : ifthenelsestat | uncondstat;

ifthenelsestat : IF expr THEN fullstat ELSE statement ; ifthenstat : IF expr THEN statement;

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

7. Пример описания синтаксического анализатора

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

Описание синтаксического анализатора приведено ниже:

%{

#include <iostream> #include <stdlib.h>

30