Лексический сканер на Си++: это очень просто

[vak]

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

Будем строить лексический анализатор в виде класса Scanner, с одним методом get_next_token(), выдающим следующий элемент (токен) из входного потока. Поместим определение класса в файл scanner.h:

#ifndef yyFlexLexer
#   define yyFlexLexer Scanner_FlexLexer
#   include <FlexLexer.h>
#endif

class Scanner : public yyFlexLexer {
public:
    // Types of input tokens.
    enum class Token {
        END,
        NUMBER,
        NAME,
        STRING,
    };

    Scanner() {}
    virtual ~Scanner() {}

    // This routine scans the input and returns a next token.
    Token get_next_token();
};

Хитрость с переопределением имени yyFlexLexer нужна, чтобы корректно подменить имена всех скрытых методов базового класса.

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

В файл scan.ll помещаем описание грамматики:

%option C++ noyywrap yylineno
%option yyclass="Scanner"
%option prefix="Scanner_"
%{
#include "scanner.h"
#undef YY_DECL
#define YY_DECL Scanner::Token Scanner::get_next_token()
#define yyterminate() return Scanner::Token::END;
%}

string	\"[^\n"]+\"
ws	[ \t]+
alpha	[A-Za-z]
dig	[0-9]
name	({alpha}|\$)({alpha}|{dig}|\_|\.|\-|\/|\$)*
num1	[-+]?{dig}+\.?([eE][-+]?{dig}+)?
num2	[-+]?{dig}*\.{dig}+([eE][-+]?{dig}+)?
number	{num1}|{num2}

%%

\n              // Skip newlines.
{ws}            // Skip blanks and tabs.
"//".*          // Skip one-line comments.
"/*"        {
                // Skip C-style comments.
		int c;

		while ((c = yyinput()) != 0) {
		    if (c == '*') {
                        c = yyinput();
                        if (c == '/')
                            break;
                        unput(c);
		    }
		}
            }
{number}	return Token::NUMBER;
{name}		return Token::NAME;
{string}	return Token::STRING;

%%

Командой %option устанавливаются нужные режимы, имя генерируемого класса и префикс для имён внутренних функций.

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

Определение yyterminate() сообщает действие по концу файла: вернуть токен END.

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

Вызывать полученный сканер можно следующим образом. Создаём объект scan и вызываем метод scan.get_next_token(), пока не дойдём до конца файла:

#include "scanner.h"

int main()
{
    Scanner scan;

    for (;;) {
        switch (scan.get_next_token()) {
        case Scanner::Token::END:
            break;
        case Scanner::Token::NUMBER:
            std::cout << scan.lineno() << ": number " << scan.YYText() << " (" << scan.YYLeng() << " bytes)\n";
            continue;
        case Scanner::Token::NAME:
            std::cout << scan.lineno() << ": name " << scan.YYText() << " (" << scan.YYLeng() << " bytes)\n";
            continue;
        case Scanner::Token::STRING:
            std::cout << scan.lineno() << ": string " << scan.YYText() << " (" << scan.YYLeng() << " bytes)\n";
            continue;
        }
        break;
    }
    return 0;
}

У сканера есть несколько дополнительных методов:

• scan.lineno() выдаёт номер строки, в которой был обнаружен токен;
• scan.YYText() содержит текстовое представление токена;
• scan.YYLeng() сообщает длину текстового представления.

Компилируем всё это в кучу:

$ flex -o scan.cpp scan.ll
$ g++ main.cpp scan.cpp -o scan

Вызываем:

$ cat input.txt 
    123 .4567e3
    /* comment
     * multi-line */
    ab c def
    "foo" // string
$ ./scan < input.txt 
1: number 123 (3 bytes)
1: number .4567e3 (7 bytes)
4: name ab (2 bytes)
4: name c (1 bytes)
4: name def (3 bytes)
5: string "foo" (5 bytes)

Таким макаром можно быстро лепить достаточно эффективные лексические сканеры на все случаи жизни.