Функция buildargv с помощью Ragel

    Забавное использование Ragel State Machine Compiler для создания функции разбора строки на int argc, char *argv[].


    Все началось с того, что понадобилась функция buildargv, чтобы разбирать строку для последующей передачи в


    int main (int argc, char *argv[]) { body }

    Ну ладно подумал я, не может быть, чтобы нигде нельзя было позаимствовать, сейчас найдем… И не нашёл...



    Ну не то что бы совсем не нашёл, вот например https://github.com/gcc-mirror/gcc/blob/master/libiberty/argv.c (GPLv2 — это всегда хорошо), брать сразу сходу на себя такие обязательства я был не готов. Точно есть такая функция в bash (GPLv3 — это еще лучше). zsh? — иди найди (я нашёл… — не хочу).


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


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


    В общем встречаем Ragel State Machine Compiler.


    Инструментарий


    • gcc ;)
    • ragel
    • make
    • lcov
    • libcheck

    С проектом можно ознакомиться тут: JOYFUL CMDLINE PARSER WRITTEN IN RAGEL


    Постановка задачи


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


    • Необходимо игнорировать любой символ следующий за символом экранирования \
    • Любые символы, который находятся между двумя парным " или ' должны
      считаться одним элементом
    • В случае незакрытых ' или " должна возвращаться ошибка

    В общем не так много условий. И Ragel вполне подходит для данной задачи.


    Реализация с разъяснениями


    Объявим машину с именем "buildargv" и попросим Ragel расположить свои данные в начале файла (5.8.1 Write Data).


    %%{
        machine buildargv;
        write data;
    }%%

    Далее объявим машину lineElement, которая в свою очередь состоит из объединения (2.5.1 Union) двух машин: arg и whitespace.


    lineElement = arg >start_arg %end_arg | whitespace;
    main := blineElements**;

    На входе и выходе машины arg выполняются действия start_arg и end_arg соответсвенно.


    action start_arg {
        argv_s = p;
    }
    
    action end_arg {
        nargv = (char**)realloc((*argv), (argc_ + 1)*sizeof(char*));
        (*argv) = nargv;
        (*argv)[argc_] = strndup(argv_s, p - argv_s);
        argc_++;
    }

    Причем задача start_arg сохранить позицию символа на входе, а задача end_arg добавить новый элемент в массив argv, в случае успешного выхода из машины arg.


    Теперь подробнее рассмотрим arg.


    arg = '\''> { fcall squote; } | '"'>{ fcall dquote; } | ( '\\'>{fcall skip;} | ^[ \t"'\\] )+;

    Он состоит из объединения трёх машин ', " и (\ | ^[ \t"'\]), последняя в свою очередь это объединение \ и ^[ \t"'\] соответвенно.


    При нахождении символа ' мы вызываем squote, " вызываем dquote, или если текущий символ равен \ вызываем skip, который пропускает любой следующий за ним символ, и любой символ не 0x20(пробел), 0x09(табуляция), ', " или \ считается правильным.


    Осталось рассмотреть совсем небольшую часть:


    skip := any @{ fret; };
    dquote :=  ( '\\'>{ fcall skip; } | ^[\\] )+ :> ["] @{ fret; } @err(dquote_err);
    squote :=  ( '\\'>{ fcall skip; } | ^[\\] )+ :> ['] @{ fret; } @err(squote_err);

    Со skip мы уже разобрались, что делает ^['\\] тоже не должно вызывать вопросов. А вот :> это Entry-Guarded Concatenation (4.2 Guarded Operators that Encapsulate Priorities) её смысл заключается в том, что машина ( '\\'>{ fcall skip; } | ^['\\] )+ завершает выполнение когда ["] переходит в начальное состояние.


    И наконец в случае ошибки конца строки при незакрытых ковычках вызываются dquote_err и squote_err для индикации и выставления соответсвующего кода ошибки.


    action dquote_err {
        ret = -1;
        errsv = BUILDARGV_EDQUOTE;
    }
    
    action squote_err {
        ret = -1;
        errsv = BUILDARGV_ESQUOTE;
    }

    Генерация кода осуществляется командой:


    ragel -e -L -F0 -o buildargv.c buildargv.rl

    Со списком тестовых строк можно ознакомиться в test_cmdline.c.


    Заключение


    Поставленная задача решена.


    Быстрее ли получилось? Сомневаюсь. Понятнее? Если только вы знаток Ragel.


    На абсолютизм не претендую, буду признателен за конструктивные замечания по коду Ragel.


    Список материалов:


    [^1]:Adrian Thurston. Ragel State Machine Compiler.

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 2

      +2
      Спасибо за статью. Тоже использую Ragel, очень неожиданно и приятно видеть, что ещё кто-то его тоже использует.
      У вас не самая простая для рагелевской грамматики задача — парные кавычки. Обычно всё проще и не требует ручных fcall и fret — больше описаний грамматики, меньше внутренностей.

      Про понятнее или нет — спорный вопрос. Безусловно, порог входа в него высокий. Понять написанное в общих чертах можно и без доки, но чтобы менять придётся освоить весь pdf документации. Зато потом начинаешь понимать, что это самый нормальный способ парсинга любого текстового формата. Поддерживаемость и возможность добавления фич по сравнению с ручным разбором кодом даже с регекспами и рядом не стояла. Есть опыт поддержки парсера, написанного полностью руками и другого на рагеле, написанных другими людьми — небо и земля. В первом поправить логику ничего не сломав практически невозможно, со вторым делай, что хочешь.

      И ещё хотел бы отметить безумную производительность. Есть разные режимы генерации, но тот, что через goto, создаёт нечто, что обогнать в бенчмарках руками написанным кодом не получается. Так что, если нужно распарсить текстовый протокол, Ragel — одновременно удобное и очень высокопроизводительное решение.
        +1

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

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

      Самое читаемое