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

Пример к статье доступен на github

Перед чтением этой статьи рекомендуется ознакомиться со статьёй об особенностях языка C

Опции командной строки

Философия UNIX гласит: пишите программы, которые делают что-то одно и делают это хорошо.

GNU flex является утилитой командной строки, построенной по принципам UNIX-систем. Утилита принимает множество опций командной строки, в том числе --help и --version. Примеры вывода при запуске с этими опциями:

>flex --version

flex 2.6.0

>flex --help

Использование: flex [ПАРАМЕТРЫ] [ФАЙЛ]…

Generates programs that perform pattern-matching on text.

Table Compression:

-Ca, --align trade off larger tables for better memory alignment

-Ce, --ecs construct equivalence classes

-Cf do not compress tables; use -f representation

-CF do not compress tables; use -F representation

-Cm, --meta-ecs construct meta-equivalence classes

-Cr, --read use read() instead of stdio for scanner input

-f, --full generate fast, large scanner. Same as -Cfr

-F, --fast use alternate table representation. Same as -CFr

-Cem default compression (same as --ecs --meta-ecs)

Debugging:

-d, --debug enable debug mode in scanner

-b, --backup write backing-up information to lex.backup

-p, --perf-report write performance report to stderr

-s, --nodefault suppress default rule to ECHO unmatched text

-T, --trace flex should run in trace mode

-w, --nowarn do not generate warnings

-v, --verbose write summary of scanner statistics to stdout

--hex use hexadecimal numbers instead of octal in debug outputs

Files:

-o, --outfile=FILE specify output filename

-S, --skel=FILE specify skeleton file

-t, --stdout write scanner on stdout instead of lex.yy.c

--yyclass=NAME name of C++ class

--header-file=FILE create a C header file in addition to the scanner

--tables-file[=FILE] write tables to FILE

Scanner behavior:

-7, --7bit generate 7-bit scanner

-8, --8bit generate 8-bit scanner

-B, --batch generate batch scanner (opposite of -I)

-i, --case-insensitive ignore case in patterns

-l, --lex-compat maximal compatibility with original lex

-X, --posix-compat maximal compatibility with POSIX lex

-I, --interactive generate interactive scanner (opposite of -B)

--yylineno track line count in yylineno

Generated code:

-+, --c++ generate C++ scanner class

-Dmacro[=defn] #define macro defn (default defn is '1')

-L, --noline suppress #line directives in scanner

-P, --prefix=STRING use STRING as prefix instead of "yy"

-R, --reentrant generate a reentrant C scanner

--bison-bridge scanner for bison pure parser.

--bison-locations include yylloc support.

--stdinit initialize yyin/yyout to stdin/stdout

--noansi-definitions old-style function definitions

--noansi-prototypes empty parameter list in prototypes

--nounistd do not include <unistd.h>

--noFUNCTION do not generate a particular FUNCTION

Miscellaneous:

-c do-nothing POSIX option

-n do-nothing POSIX option

-?

-h, --help produce this help message

-V, --version report flex version

Задача: интерпретатор для управления роботом

Допустим, нам нужно написать простой интерпретатор, принимающий 6 команд:

help - выводит справку обо всех командах

up - направляет робота вверх

left - направляет робота влево

down - направляет робота вниз

right - направляет робота вправо

exit - выходит из программы

Команды читаются из стандартного потока ввода std::cin последовательно как слова, вывод и ошибки печатаются в потоки std::cin и std::cout соответственно.

Реализация на C++ с помощью iostream

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

#include <string>

#include <map>

#include <memory>

#include <iostream>

namespace

{

struct Interpreter

{

std::map<std::string, std::function<void()>> commands;

bool willExit = false;

};

decltype(auto) MakeRobotInterpreter()

{

auto interpreter = std::make_shared<Interpreter>();

interpreter->commands["up"] = [] {

std::cout << "Walking up..." << std::endl;

};

interpreter->commands["down"] = [] {

std::cout << "Walking down..." << std::endl;

};

interpreter->commands["left"] = [] {

std::cout << "Walking left..." << std::endl;

};

interpreter->commands["right"] = [] {

std::cout << "Walking right..." << std::endl;

};

interpreter->commands["help"] = [interpreter] {

std::cout << "Available commands:" << std::endl;

for (const auto &pair : interpreter->commands)

{

std::cout << pair.first << std::endl;

}

};

interpreter->commands["exit"] = [interpreter] {

interpreter->willExit = true;

std::cout << "Bye bye!" << std::endl;

};

return interpreter;

}

void ExecuteCommand(Interpreter &interpreter, const std::string &word)

{

auto foundIt = interpreter.commands.find(word);

if (foundIt != interpreter.commands.end())

{

foundIt->second();

}

else

{

std::cerr << "unknown command " << foundIt->first << std::endl;

}

}

void ReadInputInLoop(Interpreter &interpreter)

{

std::string word;

while (!interpreter.willExit && (std::cin >> word))

{

ExecuteCommand(interpreter, word);

}

}

}

int main()

{

auto interpreter = MakeRobotInterpreter();

ExecuteCommand(*interpreter, "help");

ReadInputInLoop(*interpreter);

}

Описание лексера на Flex

Flex получает описание лексического анализатора из входного файла на специальном языке. Этот файл состоит из трёх секций:

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

Обработчик правила — это вставка кода на языке C, которая будет помещена внутрь switch-case. Этот switch-case будет находиться в теле созданной генератором функции, выполняющей сканирование следующего токена. Внутри такой вставки можно выполнить return, чтобы функция вернула сопоставленную подстроку как токен, а можно ничего не делать, чтобы функция пропустила эту подстроку и продолжила выполнение.

GNU Flex предполагает, что набор типов токенов уже известен и предоставлен снаружи; дело в том, что этот набор обычно генерирует парсер контекстно-свободной грамматики, и он же проставляет числовое значение для каждого типа токена; генератору GNU Flex числовые значения типов токена безразличны. Ниже показан пример заголовка, определяющего типы токенов:

#pragma once

enum Token

{

// Token 0 reserved for the end of input.

TOKEN_HELP = 1,

TOKEN_UP,

TOKEN_LEFT,

TOKEN_DOWN,

TOKEN_RIGHT,

TOKEN_EXIT,

};

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

Flex использует функцию yywrap() для поддержки языков с препроцессором и директивой #include, таких как язык C. В нашем языке нет препроцессора, опция отключена.

%option noyywrap

%{

#include <stdio.h>

#include "RobotTokens.h"

// Flex использует макрос YY_DECL как основу объявления функции, сканирующей следующий токен.

// По умолчанию значение макроса YY_DECL равно `int yylex()`

// Но мы назовём функцию ScanToken.

#define YY_DECL int ScanToken()

%}

%%

[ \t\r\n]+ { /* игнорируем пробелы, табы и переносы строк */ }

"help" { return TOKEN_HELP; }

"up" { return TOKEN_UP; }

"left" { return TOKEN_LEFT; }

"down" { return TOKEN_DOWN; }

"right" { return TOKEN_RIGHT; }

"exit" { return TOKEN_EXIT; }

%%

Генерация кода сканера с помощью GNU Flex

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

#!/usr/bin/env python

import subprocess

# flex получает на вход RobotScanner.l и генерирует RobotScanner.c.

subprocess.check_call(['flex', '-o', 'RobotScanner.c', 'RobotScanner.l'])

Если скрип завершился успешно, откройте “RobotScanner.c” и исследуйте созданный код:

• поищите, куда попала строка #define YY_DECL int ScanToken() и где используется макрос YY_DECL
• посмотрите, где оказалась конструкция return TOKEN_EXIT;

Код в “RobotScanner.c” довольно запутанный, и на деле его можно было написать проще на современном языке C, но GNU Flex рассчитан на работу в любых условиях, включая очень необычные компиляторы и операционные системы.

Подключение сканера в main

GNU Flex сгенерировал только файл .c без заголовка, но это не мешает использовать объявленную в нём функцию ScanToken. Мы сделаем следующее:

• опишем функцию ScanToken без тела, т.е. объявим её без определения
• изменим тип поля commands в структуре Interpreter: теперь словарь команд хранит ещё и описания команд, а в роли ключа использует enum Token.

#include "RobotTokens.h"

#include <string>

#include <map>

#include <memory>

#include <iostream>

#include <functional>

// Объявим функции, которые линковщик найдёт в объектном файле, полученном при компиляции RobotScanner.c

extern "C" {

// Возвращает ID сопоставленного токена или 0, если достигнут конец ввода.

int ScanToken();

}

namespace

{

struct Command

{

std::string info;

std::function<void()> action;

};

struct Interpreter

{

std::map<Token, Command> commands;

bool willExit = false;

};

decltype(auto) MakeRobotInterpreter()

{

auto interpreter = std::make_shared<Interpreter>();

interpreter->commands[TOKEN_UP] = {

"up - moves robot up",

[] {

std::cout << "Walking up..." << std::endl;

}};

interpreter->commands[TOKEN_DOWN] = {

"down - moves robot down",

[] {

std::cout << "Walking down..." << std::endl;

}};

interpreter->commands[TOKEN_LEFT] = {

"left - moves robot left",

[] {

std::cout << "Walking left..." << std::endl;

}};

interpreter->commands[TOKEN_RIGHT] = {

"right - moves robot right",

[] {

std::cout << "Walking right..." << std::endl;

}};

interpreter->commands[TOKEN_HELP] = {

"help - outputs this help",

[interpreter] {

std::cout << "Available commands:" << std::endl;

for (const auto &pair : interpreter->commands)

{

std::cout << pair.second.info << std::endl;

}

}};

interpreter->commands[TOKEN_EXIT] = {

"exit - exits program",

[interpreter] {

interpreter->willExit = true;

std::cout << "Bye bye!" << std::endl;

}};

return interpreter;

}

void ExecuteCommand(Interpreter &interpreter, Token tokenId)

{

auto foundIt = interpreter.commands.find(tokenId);

if (foundIt != interpreter.commands.end())

{

foundIt->second.action();

}

else

{

std::cerr << "unknown command, type 'help' to see available commands " << std::endl;

}

}

void ReadInputInLoop(Interpreter &interpreter)

{

while (!interpreter.willExit)

{

int tokenId = ScanToken();

if (tokenId == 0)

{

return; // конец ввода

}

ExecuteCommand(interpreter, static_cast<Token>(tokenId));

}

}

}

int main()

{

auto interpreter = MakeRobotInterpreter();

ExecuteCommand(*interpreter, TOKEN_HELP);

ReadInputInLoop(*interpreter);

}

Добавляем обработку ошибок

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

Добавим два новых типа токена в enum Token:

// ...

TOKEN_UNEXPECTED_WORD, // неожиданная команда

TOKEN_ERROR, // символ, не входящий в алфавит языка

Добавим два новых правила сканера в “RobotScanner.l”:

// ...

"exit" { return TOKEN_EXIT; }

[a-zA-Z]+ { return TOKEN_UNEXPECTED_WORD; }

. { return TOKEN_ERROR; }

Модифицируем функцию ReadInputInLoop, чтобы обрабатывать TOKEN_ERROR. Обрабатывать TOKEN_UNEXPECTED_WORD в этой функции не надо, т.к. функция ExecuteCommand уже обрабатывает неопознанные команды.

void ReadInputInLoop(Interpreter &interpreter)

{

while (!interpreter.willExit)

{

int tokenId = ScanToken();

if (tokenId == 0)

{

return; // конец ввода

}

if (tokenId == TOKEN_ERROR)

{

std::cerr << "wrong character in input" << std::endl;

}

else

{

ExecuteCommand(interpreter, static_cast<Token>(tokenId));

}

}

}

После перекомпиляции и запуска программы введём “no!!!” и получим:

>no!!!

unknown command, type 'help' to see available commands

wrong character in input

wrong character in input

wrong character in input

Что делать дальше?

Поупражняйтесь с Flex: попробуйте описать правила для ключевых слов и операторов языка C, или сделать сканер для кода на Python. Не забывайте, что GNU Flex способен работать только с регулярными грамматиками, в которых нет рекурсивно определённых правил.

Если вы хотите использовать свой объект во вставках кода для правил, просто модифицируйте YY_DECL: #define YY_DECL int ScanToken(MyClass *myClass). Тогда сгенерированной функции будет параметр myClass, который сам Flex использовать не станет.

Для отладки правил сканера советуем использовать отладчики регулярных выражений, которые легко найти в поисковике по запросу “online regex debugger”.

Справку можно получить на stackoverflow по тегу flex-lexer: stackoverflow.com/questions/tagged/flex-lexer .

Избранные вопросы по интеграции GNU Flex в сборку проекта:

• How to compile LEX/YACC files on Windows?
• unistd.h related difficulty when compiling bison & flex program under vc++
• CMake and Flex/Bison

По интеграции сканера в код проекта:

• String input to flex lexer
• In lex how to make yyin point to a file with the main function in yacc?
• Configuring Bison and Flex without global or static variable
• bison/flex: print erroneous line

По составлению правил сканера:

• Regular expression for a string literal in flex/lex
• Difficulty getting c-style comments in flex/lex
• How to use indentation as block delimiters with bison and flex
• Is it possible to set priorities for rules to avoid the “longest-earliest” matching pattern?