re2c - компилятор регулярных выражений

Задача выделения из потока символов определенных лексем является весьма распространенной. Часто ее решают с помощью лексических анализаторов, конфигурируемых регулярными выражениями. Многие анализаторы построены по принципу генерации программного кода, который в свою очередь реализует логику регулярных выражений. Фактически, это компиляция языка регулярных выражений в код языка программирования.

Например, flex - это один из таких анализаторов. Старый, но проверенный годами.

Я много пользовался flex'ом, он имеет и плохие и хорошие стороны, но по большому счету, жаловаться не приходилось.

Но вчера наткнулся на интересный проект - re2c. По сути, на этой штуке можно писать лексические анализаторы прямо на коленке за несколько минут.

Сразу рассмотрим пример.

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

#include <stdio.h>
#include <stdlib.h>

enum {
  CMD, INT, FLOAT, SPACE, END
};

int scan(char** p, char** lex)
{
    char* marker;
    if (lex) *lex = *p;
/*!re2c
        re2c:define:YYCTYPE  = "unsigned char";
        re2c:define:YYCURSOR = *p;
        re2c:define:YYMARKER = marker;
        re2c:yyfill:enable   = 0;
        re2c:yych:conversion = 1;
        re2c:indent:top      = 1;
        "GET"|"PUT"|"EXIT" { return CMD; }
        [0-9]+             { return INT; }
        [0-9]+ '.' [0-9]*  { return FLOAT; }
        [ \t]+             { return SPACE; }
        [^]                { return END; }
*/
}

int main(int argc, char* argv[]) {
  char *p, *last;
  int token;
  if (argc < 2) return 1;

  p = argv[1];
  while ((token = scan(&p, &last)) != END) {
    int sz = p - last;
    switch (token) {
      case CMD: printf("Command: '%.*s'\n", sz, last); break;
      case INT: printf("Number: '%.*s'\n", sz, last); break;
      case FLOAT: printf("Float: '%.*s'\n", sz, last); break;
    }
  }

  return 0;
}

И все!

Понятно, что вся магия происходит в функции "scan()" между строками, ограниченных комментариями "/*!re2c" и "*/".

Итак, re2c - это компилятор регулярных выражений, который встраивает код прямо в текст программы.

Если прогнать наш исходник через re2c:

re2c.exe -is test.re2c >test.c

То получим вот такое:

/* Generated by re2c 0.13.5 on Tue Apr 19 21:08:57 2011 */
#include <stdio.h>
#include <stdlib.h>

enum {
  CMD, INT, FLOAT, SPACE, END
};

int scan(char** p, char** lex)
{
    char* marker;
    if (lex) *lex = *p;

    {
        unsigned char yych;

        yych = (unsigned char)**p;
        if (yych <= '9') {
            if (yych <= 0x1F) {
                if (yych == '\t') goto yy8;
                goto yy10;
            } else {
                if (yych <= ' ') goto yy8;
                if (yych <= '/') goto yy10;
                goto yy6;
            }
        } else {
            if (yych <= 'F') {
                if (yych == 'E') goto yy5;
                goto yy10;
            } else {
                if (yych <= 'G') goto yy2;
                if (yych == 'P') goto yy4;
                goto yy10;
            }
        }
yy2:
        yych = (unsigned char)*(marker = ++*p);
        if (yych == 'E') goto yy24;
yy3:
        { return END; }
yy4:
        yych = (unsigned char)*(marker = ++*p);
        if (yych == 'U') goto yy23;
        goto yy3;
yy5:
        yych = (unsigned char)*(marker = ++*p);
        if (yych == 'X') goto yy18;
        goto yy3;
yy6:
        ++*p;
        if ((yych = (unsigned char)**p) == '.') goto yy13;
        if (yych <= '/') goto yy7;
        if (yych <= '9') goto yy16;
yy7:
        { return INT; }
yy8:
        ++*p;
        yych = (unsigned char)**p;
        goto yy12;
yy9:
        { return SPACE; }
yy10:
        yych = (unsigned char)*++*p;
        goto yy3;
yy11:
        ++*p;
        yych = (unsigned char)**p;
yy12:
        if (yych == '\t') goto yy11;
        if (yych == ' ') goto yy11;
        goto yy9;
yy13:
        ++*p;
        yych = (unsigned char)**p;
        if (yych <= '/') goto yy15;
        if (yych <= '9') goto yy13;
yy15:
        { return FLOAT; }
yy16:
        ++*p;
        yych = (unsigned char)**p;
        if (yych == '.') goto yy13;
        if (yych <= '/') goto yy7;
        if (yych <= '9') goto yy16;
        goto yy7;
yy18:
        yych = (unsigned char)*++*p;
        if (yych == 'I') goto yy20;
yy19:
        *p = marker;
        goto yy3;
yy20:
        yych = (unsigned char)*++*p;
        if (yych != 'T') goto yy19;
yy21:
        ++*p;
        { return CMD; }
yy23:
        yych = (unsigned char)*++*p;
        if (yych == 'T') goto yy21;
        goto yy19;
yy24:
        ++*p;
        if ((yych = (unsigned char)**p) == 'T') goto yy21;
        goto yy19;
    }

}

int main(int argc, char* argv[]) {
  char *p, *last;
  int token;
  if (argc < 2) return 1;

  p = argv[1];
  while ((token = scan(&p, &last)) != END) {
    int sz = p - last;
    switch (token) {
      case CMD: printf("Command: '%.*s'\n", sz, last); break;
      case INT: printf("Number: '%.*s'\n", sz, last); break;
      case FLOAT: printf("Float: '%.*s'\n", sz, last); break;
    }
  }

  return 0;
}

Страшно? Да, код не для ручной правки, но это и не требуется.

Компилируем:

re2c.exe -is test.re2c >test.c && cl test.c

Запускаем:

test "GET 123.0 12344 PUT 10."

Результат:

Command: 'GET'
Float: '123.0'
Number: '12344'
Command: 'PUT'
Float: '10.'

Как говориться, быстро, дешево и сердито. Чтобы полностью овладеть re2c надо прочитать одну и единственную страничку документации.

Кстати, простота работы с re2c не означает, что на нем нельзя делать сложных анализаторов. В дистрибутиве есть примеры для грамматики токенов языков C и Rexx.

Если поиграться с флагами re2c, то можно вместо "if/else" генерировать код на основе "switch/case". Выбор стоит сделать на основе понимания, какой код ваш компилятор лучше оптимизирует.

Как я понимаю, анализатор, сгенерированный re2c должен быть весьма быстр, даже очень быстр. Хотя было бы интересно померить его против того же flex'а, ANTLR'а или Spirit'a.

Посты почти по теме:

• Обертка генератора парсеров грамматик Lemon для C++