Инфраструктура для тестирования лексического и синтаксического анализатора

Были реализованы генераторы тестовых файлов для лексических и синтаксических анализаторов:

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

  2. Генератор для синтаксических анализаторов. Результатом его работы являются файлы с заданным количеством функций. Функции имеют:

    1. сигнатуру с случайными именами, именами переменных и типами;

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

В данной работе рассматриваются лексический и синтаксический генераторы – flex и bison, соответственно.

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

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

На вход генераторы принимают правила выделения лексем, а на выходе даёт код анализатора, в виде функции на языке Си. Общая структура для описания генераторов:

  1. блок определений – содержит стартовые значения и определения;

  2. блок правил – выражения и соответствующие им действия;

  3. блок кода на С – пользовательский код.

Определения и правила описываются при помощи одного из вариантов расширенной формы Бекуса-Наура.

Пример описания лексического генератора (flex) для целых чисел и чисел с плавающей точкой:

Блок определений
Нетерминальные символы(идентификаторы) Выражение

DIGIT

IntegerLiteral

FloatLiteral

[0-9]

{DIGIT}+

{DIGIT}+"."{DIGIT}*
Блок правил
Правило Обработчик

{IntegerLiteral}

{FloatLiteral}

int int_literal = atoi(yytext); printf("%d\n“, int_literal);

float fl_literal = atof(yytext); printf("%f\n“, fl_literal);
Блок пользовательского кода

void main(int argc, char **argv)

{

++argv, --argc;

if ( argc > 0 )

yyin = fopen( argv[0], "r" );

else

yyin = stdin;

yylex();

}

Пример описания синтаксического генератора (bison) для целых чисел и чисел с плавающей точкой:

Блок определений
Лексемы

%token INTEGER_LITERAL FLOAT_LITERAL // ожидаемые токены

%start input // Входное правило для анализатора
Блок правил
Правило Обработчик

%%

input: /* empty */

|

integer_literal input

|

float_literal input;

integer_literal: INTEGER_LITERAL

float_literal: FLOAT_LITERAL

// Входное правило для анализатора

{printf("Current int: %d\n", $1);}

{printf("Current float: %f\n", fsum);}

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

Назад