Bison, dynamic linking и… обработка BMP изображений24.11.2020 08:47

В этом посте я постараюсь раскрыть тему написания несложного модульного приложения на языке C89 для обработки 24-битных BMP изображений, использующего в своей работе простой скриптовый язык.

Если вы заинтересованы в разработке языков или вам необходимо быстро разобраться как писать приложения, динамически загружающие исполняемый код, хранящийся в разделяемых библиотеках (dll, so), то возможно вам будет интересен данный материал.

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

Задача примерно следующая: разработать инструмент для обработки BMP (как самый простой формат) изображений с 24-битным кодированием цветов с возможностью расширения функционала без перекомпиляции и скриптовым языком для использования инструмента.

Разработка скриптового языка

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

Язык должен позволять в заданном порядке вызывать трансформации для обработки изображения, при этом должна быть возможность передавать трансформации параметры при вызове. Например, для поворота картинки это должен быть угол поворота, и т.п. Намечается следующий синтаксис (РБНФ):

script = { transformation ";" } ;
transformation = [ T_IDENTIFIER "." ] T_IDENTIFIER "(" transformation_args ")" ;
transformation_args = [ literal { "," literal } ] ;
literal = T_INTEGER | T_FLOATING | T_STRING | T_IDENTIFIER ;

Здесь я определяю весь скрипт как последовательность трансформаций, каждая из которых должна оканчиваться точкой с запятой, трансформация в свою очередь состоит из опционального идентификатора с точкой, что значит «имя модуля» трансформации, идентификатора самой трансформации и списка аргументов, окружённого круглыми скобками. Список аргументов представляет собой список литералов, идущих через запятую, каждый из которых может быть либо целым числом, либо дробным, либо строкой, либо идентификатором.

Я намерено оставил возможность использования идентификатора в качестве литерала для всяких трюков с трансформациями, типа передачи функции в функцию или использования констант, однако, можно заметить, что идентификаторный литерал не может содержать имя модуля, что ограничивает набор возможных идентификаторов модулем, трансформация которого вызывается.

По описанию синтаксиса сразу очевидно, какие типы узлов АСД нам необходимы: script, transformation, transformation_args и literal. Исходный код их определения ниже:

Определение узлов дерева

struct ast_position {
    uint32_t row;
    uint32_t col;
};

enum ast_literal_type {
    L_INTEGER,
    L_FLOATING,
    L_STRING,
    L_IDENTIFIER
};

struct ast_literal {
    enum ast_literal_type type;
    char * value;

    struct ast_position pos;
};

struct ast_transformation_args {
    struct ast_literal argument;
    struct ast_transformation_args * next;
};

struct ast_transformation {
    char * module;
    char * name;

    struct ast_transformation_args * args;

    struct ast_position pos;
};

struct ast_script {
    struct ast_transformation transformation;
    struct ast_script * next;
};

Структура ast_position потребуется позже и будет описана ближе к концу. Можно заметить, что структуры ast_script и ast_transformation_args являются односвязными списками, потому что так их удобнее конструировать и работать с ними.

Написание парсера

Писать парсер, как и было упомянуто в заголовке статьи, будем с помощью Bison, использоваться он будет в связке с GNU Flex, потому что они, по понятным причинам, хорошо совместимы друг с другом и их удобно использовать вместе. Несмотря на то, что кажется логичным начать написание парсера с описания лексики для Flex, на самом деле более простым будет начать с описания синтаксиса языка.

Синтаксис файла грамматики для Bison можно легко найти в интернете и в руководстве, поэтому перейду сразу к описанию нашего языка. Синтаксис секции правил файла очень похож на РБНФ и в некотором роде даже более простой для понимания, поэтому привожу получившийся список правил:

file
    : script YYEOF  { *result = ast_script_reverse($1); }
    ;

script
    : /* empty */               { $$ = NULL; }
    | script transformation ';' { $$ = ast_script_new($2, $1); }
    ;

transformation
    : T_IDENTIFIER '(' transformation_args ')'                  {
        $$ = ast_transformation_create(NULL, $1, ast_transformation_args_reverse($3),
                ast_position_create(@$.first_line, @$.first_column));
    }
    | T_IDENTIFIER '.' T_IDENTIFIER '(' transformation_args ')' {
        $$ = ast_transformation_create($1, $3, ast_transformation_args_reverse($5),
                ast_position_create(@$.first_line, @$.first_column));
    }
    ;

transformation_args
    : /* empty */               { $$ = NULL; }
    | transformation_args_req   { $$ = $1; }
    ;

transformation_args_req
    : literal                               { $$ = ast_transformation_args_new($1, NULL); }
    | transformation_args_req ',' literal   { $$ = ast_transformation_args_new($3, $1); }
    ;

literal
    : T_INTEGER     { $$ = ast_literal_create(L_INTEGER, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_FLOATING    { $$ = ast_literal_create(L_FLOATING, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_STRING      { $$ = ast_literal_create(L_STRING, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_IDENTIFIER  { $$ = ast_literal_create(L_IDENTIFIER, $1, ast_position_create(@$.first_line, @$.first_column)); }
    ;

Здесь кроме определения правил синтаксиса можно видеть также код на Си, заключённый в фигурные скобки. Для тех, кто не знаком с синтаксисом файла грамматики Bison, поясняю: это действия, которые выполняет сгенерированный парсер, когда сворачивает правило. Свёрткой я здесь и далее называю reduce, операцию объединения нескольких определённых в ходе парсинга символов в один нетерминальный символ, при этом все «семантические значения» символов, которые были свёрнуты доступны по именам $n, где n — это номер символа в описании, начиная с 1. Так, в определении правила script, в его второй строке, под номером 1 будет нетерминал script, использованный при рекурсивной свёртке, а под номером 2, соответственно, трансформация. Здесь же стоит обратить внимание на переменную $$, в которую записывается значение, соответствующее текущему сворачиваемому символу. Из кода можно понять, что переменная @$ означает текущее положение в анализируемом тексте, но об этом позже.

Отдельно стоит отметить наличие здесь правила file, единственным назначением которого является запись в переменную и разворачивание списка script. К сожалению, по умолчанию генерируемый Bison парсер ни в каком виде не возвращает семантическое значение последнего свёртного правила, поэтому приходится явно записывать его в переменную. Для того, чтобы записывать в переменную что-либо, необходимо сначала эту переменную получить, поэтому здесь мы пользуемся возможностями Bison, и указываем в первой секции файла (предполагается, что читатель ознакомлен с общим синтаксисом файла) директиву %parse-param с указанием определения аргумента функции yyparse, генерируемой Bison. Цельный код получившегося парсера будет представлен ниже.

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

Последнее, на чём здесь хотелось бы заострить внимание, это дополнительное правило transformation_args_req, которое необходимо для корректного парсинга списка, разделённого запятыми. Если его не вводить, не будет возможности построить правило таким образом, чтобы нельзя было оставить «висячую» запятую в начале или в конце списка (или я не знаю как, если есть решение, добро пожаловать в комментарии).

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

parser.y

%parse-param {struct ast_script ** result} {char ** error}

%{
#include 
#include 
#include 

#include "ast.h"

int yylex(void);

void yyerror(struct ast_script ** result, char ** error, const char * str);
%}

%code requires {
#include "ast.h"
}

%union {
    struct ast_script * script;
    struct ast_transformation transformation;
    struct ast_transformation_args * transformation_args;
    struct ast_literal literal;
    char * token;
}

%token T_IDENTIFIER T_INTEGER T_FLOATING T_STRING

%type