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.

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

    Подробнее
    Реклама
    Комментарии 15
    • 0
      Ого! Давненько я не видел goto :)
      • +3
        На goto мир стоит.
      • –1
        Интересно, есть ли развивающийся порт этой штуковины на Java?
        • 0
          А для чего?
          Проще использовать стандартные классы Java Regex, объём кода ни чуть не меньше, чем в re2c.
          • +1
            Этой — нету, но есть JLex
            Комментатор выше не прав, т.к. прийдётся писать сотни кода и отлаживать регулярки
          • 0
            мне вот интересно, код на метках работает быстрее чем таблица переходов в массиве?
            • 0
              Вообще-то да. Все-таки jmp 0x… попроще за вытаскивание адреса из массива (абсолютный адрес переменной + смещение) и переход по нему. Но вопрос всегда между удобочитаемостью и производительностью)
              • 0
                Зависит от компилятора и платформы.
                • +1
                  ну приведите пример платформы, в которой переход по константному адресу медленнее, чем такой же переход, но по адресу в памяти.
                • 0
                  покопался в файлах и нашел собственный сканер который еще в универе писал. govnokod.com/4398
                  табличка переходов конечно генерилась, правда не по регулярке, а забивалась в формочку руками, ну что с второкурсника возьмешь, глупый был :)
                • +1
                  Так это просто лексер? Вот это мне кажется более интересным практически для любых применений. По использованию памяти и скорости по-моему конкурентов нет.
                  • 0
                    Не знал. Спасибо за наводку.
                    • 0
                      На мой взгляд у re2c ниша немного другая — написание ad hoc лексеров, когда не требуется полная мощь лексеров и парсеров типа flex, bison, peg.
                      Сейчас, правда, эта ниша занята регулярными выражениями.
                    • +1
                      Есть неплохой пример использования re2c в большом проекте: функция unserialize() в PHP написана с использованием re2c.
                      В исходниках PHP это ext/standard/var_unserializer.re и соответствующий ext/standard/var_unserializer.c, ну и на сайте PHP есть указание на re2c.
                      • 0
                        boost::spirit наше всё! :)

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