Урок 3: Лексический анализатор

Вступление

На втором уроке мы рассмотрели организацию проекта и теперь можем приступать к непосредственно написанию кода лицевой части компилятора. Из классической теории нам известно что лицевая часть состоит из трёх основных стадий, как показано на рисунке: 

-------------               --------------                  -----------                 ----------------
|           |  Лексический  |            |  Синтаксический  | Дерево  |  Семантический  |    Дерево    |
| Программа |    ----->     |   Токены   |      ----->      | разбора |      ----->     | абстрактного |
|           |  анализатор   |            |    анализатор    |         |   анализатор    |  синтаксиса  |
-------------               --------------                  -----------                 ----------------

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

В реальных компиляторах лексический анализатор чаще всего делают без использования сторонних инструментов, однако для упрощения задачи мы воспользуемся так называемым «генератором лексических анализаторов» flex. Этот генератор на основе файла в специальном формате создаёт модуль на языке Си, который непосредственно занимается распознанием лексем в подаваемом файле.

В рамках данного урока нашей задачей будет распознание всех лексем языка X в подаваемом на вход файле и вывод их на экран. При этом следует точно указывать положение лексем в тексте. Также надо учитывать некорректные лексемы. Формат вывода распознанных лексем такой:

Класс токена, "Лексема", Строка, Столбец

Строка и столбец здесь являются положением первого символа лексемы в тексте. Какие лексемы встречаются в нашем языке: IF, ELIF, ELSE, FOR, BREAK, CONTINUE, RETURN, NEW, TRUE, FALSE, INT, CHAR, BOOL, VOID, LOGIC_AND, LOGIC_OR, IS_EQ, IS_NEQ, IS_GEQ, IS_LEQ, CHAR, INTEGER, IDENTIFIER, +, -, *, >, <, !, ;, ,, =, (, ), {, }, [, ], ERROR.

Выполнение

Кратко про flex

Идея генератора лексических анализаторов состоит в следующем: мы пишем шаблон, по которому распознаётся лексема и выполняются действия если мы эту лексему распознали. Шаблоном может быть символ, строка или регулярное выражение. Такие инструменты используются чтобы сократить время на создание собственного распознавателя, и мы воспользуемся этой возможностью.

Структура файла описания flex выглядит примерно следующим образом:

Секция объявлений

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

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

%%

Секция правил

Здесь мы пишем лексему и код на Си, который вызывается при её распознании.
Выглядит это примерно следующим образом:

Шаблон { Код на Си }

%%

Секция кода

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

Файл состоит из трёх секций, разделённых символом %%. В секции объявлений можно добавлять код на языке Си внутри блока, обозначенного символами %{ %}.

Обычно код для flex расположен в файлах с расширениями .l или .ll. Для примера можно создать минимальный файл на flex и выполнить трансляцию в язык Си:

$ cat > src/x-lexer.l
%%
%%

$ flex src/x-lexer.l

$ ls lex.yy.c
lex.yy.c

Сам по себе файл lex.yy.c бесполезен, его можно удалить но любопытствующие могут поизучать его внутренности.

Интеграция модуля в проект

Компиляция модуля

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

-------------          -------------
|           |   flex   |           |
| x-lexer.l |  ----->  | x-lexer.c |
|           |          |           |\   gcc    -------------
-------------          -------------  -------> |           |
                                               |  x_d.out  |
                       -------------  -------> |           |
                       |           |/          -------------
                       |   main.c  |
                       |           |
                       -------------

Выше уже писалось что flex создаёт файл на языке Си. Этот файл будет пересоздаваться каждый раз при пересборке поекта, а в самом создаваемом файле никаких правок мы делать не будем. Для таких файлов создадим отдельный каталог gen (сокращение от generated). Соответственно, команду трансляции следует переписать под работу с этим каталогом:

$ flex --header-file=gen/x-lexer.h -o gen/x-lexer.c src/x-lexer.l

Рассмотри подробнее опции в команде:

Разумеется, мы не будем каждый раз вызывать эту команду руками, а значит нам необходимо добавить её в файл сценария сборки: 

x-lexer.c:
	mkdir -p $(GEN_DIR)
	$(LEX) --header-file=$(GEN_DIR)/x-lexer.h -o $(GEN_DIR)/x-lexer.c $(SRC_DIR)/x-lexer.l

x-lexer.o: x-lexer.c
	$(CC) $(CFLAGS) $(GEN_DIR)/x-lexer.c -I$(GEN_DIR) -o $(OBJ_DIR)/x-lexer.o -c -std=gnu18

Нам пришлось добавить сразу две цели в сценарий сборки. Первая цель - создание модуля из файла x-lexer.l. Вторая цель - непосредственно компиляция этого модуля. Читателю остаётся только дополнить список объектов для вызова компоновщика и указать компилятору что ему необходимо искать заголовочные файлы также и в каталоге $(GEN_DIR). Также стоит обратить внимание на появление опции -std=gnu18. Эта опция связана с тем что flex генерирует файл, не совсем соотвествующий классическому стандарту и в нём появляется функция из расширения GNU.

Взаимодействие модуля с остальным кодом

Мы научились создавать и собирать модуль с распознавателем. Теперь необходимо научиться его вызывать. За вызов распознавателя отвечает функция int yylex(void). Эта функция начинает читать символы входного потока до тех пор пока они не закончатся или до тех пор пока правило шаблона не завершит исполнение. В случае успешного завершения функция вернёт 0. Описание функции находится в файле x-lexer.h, который мы создали в каталоге gen. Теперь попробуем вызвать эту функцию:

#include "x-lexer.h"

int main(void)
{
    return yylex();
}

Прежде чем пересобирать проект, сделаем небольшую магическую вставку в файл лексического анализатора, и целиком наш файл x-lexer.l будет выглядеть так:

/* Эти три директивы говорят flex не генерировать функции input, yyunput и
 * yywrap, которые в данном случае не используются. Они необходимы для
 * подавления предупреждений компилятора */
%option nounput
%option noinput
%option noyywrap

%%

%%

Теперь можно собирать проект и запускать его:

$ ./bin/debug/x_d
test
test

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

Создание правил распознавания

Распознаём любой символ

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

. { printf("UNKNOWN\n"); }

После пересборки и запуска теста на простом входном слове получим следующий результат:

test
UNKNOWN
UNKNOWN
UNKNOWN
UNKNOWN

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

Для того чтобы немного упростить себе жизнь в будущем, прямо сейчас сделаем небольшую обёртку для функции printf под названием printLexeme, и для печати будем использовать только её. Смысл такой замены будет понятен несколькими параграфами ниже. Теперь наш файл x-lexer.l будет выглядеть вот так:

/* Эти три директивы говорят flex не генерировать функции input, yyunput и
 * yywrap, которые в данном случае не используются. Они необходимы для
 * подавления предупреждений компилятора */
%option nounput
%option noinput
%option noyywrap

%{

/**
 * @brief Печать считанной лексемы
 *
 * @param [in] tokName Имя токена, который представляет лексему
 */
static void printLexeme(const char * tokName)
{
    printf("%s\n", tokName);
}

%}

%%

. { printLexeme("UNKNOWN"); }

%%

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

Распознаём ключевые слова

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

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

if { printLexeme("IF"); }

Пересоберём и посмотрим как теперь работает распознаватель:

$ ./a.out
if 3
IF
UNKNOWN
UNKNOWN

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

Использование синонимов

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

INTEGER [0-9]+

%%

{INTEGER} { printLexeme("INTEGER"); }

Распознавание комментариев и строк

Многострочные комментарии и символьные литералы имеют некоторые неприятные особенности. Например, мы могли бы составить одно регулярное выражение для всего многострочного комментария, но при этом нам бы отдельно пришлось разбирать его содержимое для вычисления количества переносов строк и смещения от начала строки закрывающего символа.

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

В секции объявлений мы можем добавить необходимые состояния одним из двух методов, в данном случае сделаем это через исключающее состояние (также существуют включающие состояния):

%x COMMENT

Активировать состояние можно при помощи вызова макроса BEGIN, указав его аргументом название состояния. Соответственно, обработка комментария будет строиться как включение состояния COMMENT при открытии комментария и включении состояния INITIAL при его закрытии:

"/*"          { /* Включаем состояние анализа комментариев */ BEGIN(COMMENT); }
<COMMENT>.    { /* Внутри комментария ничего не делаем */ }
<COMMENT>"*/" { /* Возвращаемся в начальное состояние */ BEGIN(INITIAL); }

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

Отслеживаем положение лексем в тексте

Отслеживание положения во flex производится в полу-автоматическом режиме. Для начала необходимо завести структуру отображающую положение в тексте и её объект:

/**
 * @brief Контейнер для положения символа в тексте
 */
typedef struct
{
    int line;   /*!< @brief Строка */
    int colomn; /*!< @brief Столбец */
} Position_t;

/**
 * @brief Текущая позиция в файле
 */
static Position_t Position = {1, 1};

/**
 * @brief Сдвигаемся на #num строк
 *
 * @param [in] num  Количество строк, на которое сдвигаемся
 */
static void incrLine(int num) {Position.line += num;}

/**
 * @brief Получаем текущую строку в читаемом файле
 *
 * @returns Текущая строка в читаемом файле
 */
static int line(void) {return Position.line;}

/**
 * @brief Сдвигаемся на #num столбцов
 *
 * @param [in] num  Количество столбцов, на которое сдвигаемся
 */
static void incrColomn(int num) {Position.colomn += num;}

/**
 * @brief Получаем текущий столбец в читаемом файле
 *
 * @returns Текущий столбец в читаемом файле
 */
static int colomn(void) {return Position.colomn;}

Теперь объект Position можно использовать для хранения позиции в тексте. Во flex существует специальный макрос YY_USER_ACTION, который вызывается при распознавании любой лексемы. В нём удобней всего вычислять текущее положение. Например так:

#define YY_USER_ACTION { incrColomn(yyleng); }

Переменная yyleng хранит в себе длину считаной лексемы, поэтому в приведённом коде мы каждый раз смещаем положение на эту длину. Можно заметить что в макросе мы выпонляем только смещение по столбцам текста, но игнорируем увеличение номера строки.

Отслеживать строки нам имеет смысл только во время непосредственно распознавания символов перехода:

\n { dropColomn(); incrLine(1);}

Функция dropColomn, как можно догадаться, смещает положение столбца текста в позицию 1.

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

static void printLexeme(const char * tokName)
{
    printf("%s, \"%s\", %d, %d\n",
           tokName,
           yytext,
           line(),
           colomn() - yyleng);
}

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

Считывание из файла

На данный момент наш распознаватель принимает на вход символы из стандартного ввода. Нам было бы удобней подавать первым аргументом читаемый файл. Мы не будем здесь показывать как это сделать в Си - это описано в любом учебнике, и посмотрим только как передать дескриптор открытого файла во flex:

yyrestart(f);   /* Задаём flex файл откуда считывать символы */
res = yylex();  /* Непосредственно запуск лексического анализатора */

Собственно, всё что нужно - это воспользоваться функцией void yyrestart ( FILE *input_file );, которая на вход принимает указатель на открытый файл.

Добавляем тесты

Тесты правильных программ

На предыдущем уроке мы создали каталог для хранения тестов с названием correct. Этот каталог подразумевает что в нём будут храниться правильные программы, которые мы потом будем запускать. Наша текущая задача - создать в этом каталоге некоторое количество тестов, которое позволило бы нам покрывать все правила, написанные в распознавателе.

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

/* Разные типы данных */

void f1(){}

int main()
{
    bool b1 = true, b2 = false;
    int i = 0;
    char c = '!';
    int[10][10] arr;

    f1();

    delete arr;

    return i;
}

Рассмотрим небольшой участок результата запуска распознавателя на примере выше:

VOID, "void", 3, 1
IDENTIFIER, "f1", 3, 6
(, "(", 3, 8
), ")", 3, 9
{, "{", 3, 10
}, "}", 3, 11
INT, "int", 5, 1
IDENTIFIER, "main", 5, 5

Для отслеживания ошибок в ходе работы над проектом необходимо создать эталонную выдачу для теста и при каждом тестировании проверять что выдача текущей версии соответствует эталонной. Поэтому в сценарий тестирования следует добавить ещё одну проверку:

diff -q "$OUTPUT_CORRECT_DIR/$i.sample" "$SAMPLE_CORRECT_DIR/$i.sample"
if [ `echo $?` != 0 ]
then
    RES=4
    echo "ошибка в запуске: diff -q "$OUTPUT_CORRECT_DIR/$i.sample" "$SAMPLE_CORRECT_DIR/$i.sample""
else
    echo "пройден!"
fi

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

Тесты ошибочных программ

После добавления всех тестов мы можем заметить что у нас всё ещё недостаточное покрытие. Это связано с тем что мы не написали тестов ошибочных ситуаций. Эти тесты тоже важны чтобы знать что компилятор не пропускает заведомо ошибочный код и что у него работает система диагностики ошибок.

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

/* Тест на некорректные символы */

ывапвы

??

int main()
{
    return 0;
}

Данный тест содержит явно ошибочные лексемы ывапвы и ??. Хорошим способом выполнения урока было бы распознать их как отдельные лексемы и сделать выдачу как показано в примере:

ERROR, "ывапвы", 3, 1
ERROR, "??", 5, 1
INT, "int", 7, 1
IDENTIFIER, "main", 7, 5
(, "(", 7, 9
), ")", 7, 10
{, "{", 8, 1
RETURN, "return", 9, 5
INTEGER, "0", 9, 12
;, ";", 9, 13
}, "}", 10, 1

Для тестов ошибочных ситуаций мы создадим каталоги tests/in/incorrect/ и tests/out/incorrect/, в которые поместим входные и эталонные данные соответственно. Также нам придётся дописать сценарий тестирования:

# Тестируем неправильные примеры
echo "Тесты ошибочных ситуаций"
mkdir -p $OUTPUT_INCORRECT_DIR
for i in `ls "$INPUT_INCORRECT_DIR"` ;
do
    echo -n "Тест $i: "

    $BIN "$INPUT_INCORRECT_DIR/$i" >& $OUTPUT_INCORRECT_DIR/"$i.sample"
    if [ `echo $?` == 0 ]
    then
    echo "ошибка в запуске: $BIN $INPUT_INCORRECT_DIR/$i"
    RES=5
        continue
    fi

    diff -q "$OUTPUT_INCORRECT_DIR/$i.sample" "$SAMPLE_INCORRECT_DIR/$i.sample"
    if [ `echo $?` != 0 ]
    then
        RES=6
        echo "ошибка в запуске: diff -q "$OUTPUT_INCORRECT_DIR/$i.sample" "$SAMPLE_INCORRECT_DIR/$i.sample""
    else
        echo "пройден!"
    fi
done

Прочие тесты

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

Итог

Итогом этого урока должна получиться программа, принимающая на вход текстовый файл и выводящая на экран все встреченные лексемы:

$ make debug
mkdir -p bin/debug obj/debug
mkdir -p gen
flex --header-file=gen/lexer.h -o gen/lexer.c src/lexer.l
gcc -Wall -Werror -std=gnu18 -g -fsanitize=address gen/lexer.c -Igen -o obj/debug/lexer.o -c -std=gnu18
gcc -Wall -Werror -std=gnu18 -g -fsanitize=address src/main.c -Igen -c -o obj/debug/main.o
gcc -g -fsanitize=address obj/debug/*.o -o bin/debug/x_d

$ ./bin/debug/x_d tests/in/correct/1.1.x
INT, "int", 3, 1
IDENTIFIER, "main", 3, 5
(, "(", 3, 9
), ")", 3, 10
{, "{", 4, 1
RETURN, "return", 5, 5
INTEGER, "0", 5, 12
;, ";", 5, 13
}, "}", 6, 1

При этом мы должны уметь выявлять лексические ошибки и помечать их соответствующим образом:

$ ./bin/debug/x_d tests/in/incorrect/1.1.x
ERROR, "ывапвы", 3, 1
ERROR, "??", 5, 1
INT, "int", 7, 1
IDENTIFIER, "main", 7, 5
(, "(", 7, 9
), ")", 7, 10
{, "{", 8, 1
RETURN, "return", 9, 5
INTEGER, "0", 9, 12
;, ";", 9, 13
}, "}", 10, 1
UNKNOWN, "'", 12, 1

Система тестирования должна покрывать все лексемы и все возможные случаи:

$ make test
...
Тесты верных ситуаций
Тест 1.1.x: пройден!
Тест 1.2.x: пройден!
Тест 1.3.x: пройден!
Тест 1.4.x: пройден!
Тесты ошибочных ситуаций
Тест 1.1.x: пройден!
Тесты передаваемых аргументов

В итоге мы должны выполнить полное покрытие кода тестами. При этом сам lcov работает не очень корректно с flex и никогда не выдаст нам 100% покрытие. Впрочем, если Вашему чувству прекрасного нанесено несмываемое оскорбление, Вы можете поискать способ сделать всё идеальным.

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

Эталонное исполнение традиционно доступно по ссылке.