GridStack ­— Пример практического применения flex+bison

    В последнее время на Хабре появились несколько статей, посвящённых грамматическому разбору выражений.
    И это замечательно! По моему скромному мнению, каждый программист должен хоть раз в жизни написать разбор выражения. Постараюсь и я внести свою лепту в общее дело.

    Методов разбора существует множество (рекомендую следующий обзор Dick Grune, Ceriel J. H. Jacobs — Parsing Techniques: A Practical Guide, ISBN 0-13-651431-6). Причём реализации методов варьируются от полностью ручных до использования автоматизированных генераторов, таких как bison, antlr, lemon и других.
    В то время, как ручное написание лексических и синтаксических (далее я буду называть из лексер и парсер) разборов позволяет достичь максимальной скорости и контроля (особенно над ошибками и способами их преодоления), использование генераторов позволяет сосредоточиться непосредственно на задаче, облегчает модификацию грамматики и бережёт время. Умение владеть такими инструментами позволяет чаще прибегать к DSL (Domain Specific Language) и вообще видеть возможность их применения.

    Я хочу привести пример использования bison (парсер) и flex (лексер) в реальной жизни: от возникновения задачи, до её решения.


    Есть замечательная программа GridMove, которая позволяет упорядочивать окна приложений по какой-либо сетке привязки. Сетки привязки задаются в обычном ini-файле, в котором указаны области-триггеры и соответствующие размеры и позиции окон. Совместными усилиями были разработаны многие замечательные сетки. Но возникла проблема: они под мои расклады не подходили, создав несколько сеток вручную, захотелось как-то автоматизировать процесс.

    Проанализировав необходимые мне сетки, я понял, что они могут быть описаны простой рекурсивной структурой.
    Регион — это или итоговое окно, или вертикальный регион, или горизонтальный регион. Вертикальный регион состоит из регионов, которые имеют одинаковую ширину и делят высоту в указанных долях. Горизонтальный регион, соответственно состоит из регионов, которые имеют одинаковую высоту и делят ширину в указанных долях.

    Рассмотрим простой пример.
    пример разбиения окна
    Весь монитор представлен в виде горизонтального региона, который состоит из подрегионов A и B. Регион A представляет собой вертикальный регион из подрегионов C и D. Регион C — это просто окно, которое дальше уже не делится. Регион D представляет собой горизонтальный регион из трёх простых окон. Регион B представляет собой вертикальный регион из трёх простых окон.
    Это всё можно описать так на придуманном мной DSL:
    Monitor 1
        HStack      #Всё окно
            (
             VStack 3       #Регион А
                (
                    Window 2  #Регион C
                    HStack    #Регион D
                        (
                            Window #Регион E
                            Window #Регион F
                            Window #Регион G
                        )
                )
             VStack  #Регион B
                (
                    Window  #Регион H
                    Window  #Регион I
                    Window  #Регион J
                )
            )
     

    Window, HStack, VStack — это описание регионов. Числа при региона — относительный вес, доля региона в надрегионе (по умолчанию ==1). Если число сопровождается знаком «!», то это жёстко заданный размер в пикселях.

    Когда я понял, что расположение окон на экране можно так описать, я набрасал на листочке что-то вышеупомянутое, только на русском. Тогда и решил, что мне будет удобнее создать DSL, разобрать его и обработать.
    Построим грамматику. Курсивом обозначены нетерминальные символы.
    start::= monitor_list
    monitor_list::= monitor | monitor monitor_list
    monitor::= MONITOR DIMENSION region
    region_list::= region | region region_list
    region::= window | hstack | vstack
    window::= WINDOW DIMENSION | WINDOW FIX_DIMENTION | WINDOW
    hstack::= HSTACK OPEN region_list CLOSE | HSTACK DIMENSION OPEN region_list CLOSE | HSTACK FIX_DIMENTION OPEN region_list CLOSE
    vstack::= VSTACK OPEN region_list CLOSE | VSTACK DIMENSION OPEN region_list CLOSE | VSTACK FIX_DIMENTION OPEN region_list CLOSE

    Терминальных символов, для которых необходимо построить лексический анализатор, совсем мало: MONITOR, HSTACK, VSTACK, WINDOW, OPEN, CLOSE, DIMENSION и FIX_DIMENTION. Для такого случая можно, конечно, написать лексический анализатор вручную, но даже для такого случая проще воспользоваться flex'ом. Я приведу готовый файл GridStack.lex. Просьба не обращать особого внимания на то, как реализована регистронезависимой лексика. Можно было вызвать flex с ключом -i, но я сделал регистронезависимость именно так. Терминалы для скобок я завёл, так как не был уверен в окончательном формате.
    /*<br/>
     * GridStack.lex<br/>
     */
    <br/>
     <br/>
    %{<br/>
    #include <stdio.h><br/>
    #include <string.h><br/>
    #include <malloc.h><br/>
    #include "common.h"<br/>
    #include "GridStack.tab.h"   <br/>
        /*"GridStack.tab.h"   Этот    файл   содержит    определение   констант */<br/>
        /*терминальных  символов  и  структуры yylval,  для  передачи  значений */<br/>
        /*терминальных символов его производит bison по грамматике              */<br/>
     <br/>
     <br/>
    #undef ECHO<br/>
    #define ECHO<br/>
    %}<br/>
     <br/>
    digit             [0-9]<br/>
     <br/>
    int_constant      {digit}+<br/>
     <br/>
    %option noyywrap           <--- эта опция отключает исполоьзование функции yywrap по достижении конца файла<br/>
     <br/>
    %%<br/>
    [Mm][Oo][Nn][Ii][Tt][Oo][Rr]            {<br/>
                                                yylval.IntVal=MONITOR;<br/>
                                                return MONITOR;<br/>
                                            }<br/>
    [Hh][Ss][Tt][Aa][Cc][Kk]                {<br/>
                                                yylval.IntVal=HSTACK;<br/>
                                                return HSTACK;<br/>
                                            }<br/>
    [Vv][Ss][Tt][Aa][Cc][Kk]                {<br/>
                                                yylval.IntVal=VSTACK;<br/>
                                                return VSTACK;<br/>
                                            }<br/>
    [Ww][Ii][Nn][Dd][Oo][Ww]                {<br/>
                                                yylval.IntVal=WINDOW;<br/>
                                                return WINDOW;<br/>
                                            }<br/>
    {int_constant}!                         {<br/>
                                                sscanf(yytext,"%d!",&yylval.IntVal);<br/>
                                                return FIX_DIMENTION;<br/>
                                            }<br/>
    {int_constant}                          {<br/>
                                                sscanf(yytext,"%d",&yylval.IntVal);<br/>
                                                return DIMENSION;<br/>
                                            }<br/>
    \(                                      {<br/>
                                                yylval.IntVal=OPEN;<br/>
                                                return OPEN;<br/>
                                            }<br/>
    \)                                      {<br/>
                                                yylval.IntVal=CLOSE;<br/>
                                                return CLOSE;<br/>
                                            }<br/>
    #.*$                                    /* Пропустим комментарии до конца строки */<br/>
    [\n\r\t ]+                              /* Пробелы для нас ничего не значат */<br/>
    .                                       {<br/>
                                                return *yytext;<br/>
                                            }<br/>
    %%<br/>
     <br/>
     


    При написании парсера обычно есть два подхода:
    1. Реализация всей логики сразу по месту.
    2. Сбор данных и последующая их обработка. При этом обычно построенную структуру называют AST (Abstract Syntax Tree).

    Я сторонник второго метода, поэтому всё, что сделал — это собрал все данные. Дополнительным преимуществом является то, что сейчас можно привести код целиком, не вычищая лишнюю логику расчёта размерностей регионов.
    Вот файл GridStack.y с комментариями.

    %{
    #include <stdio.h>
    #include <malloc.h>
    #include "common.h"
    %}
    %union                   /* Это определение типа объединения yylval,  которую совместно bison и flex */
     {                       /*используют  для передачи  значений лексем.  А bison  для передачи  данных */
      int       IntVal;      /*между  правилами. Имена  полей являются  типами, которые  можно присвоить */
      TRegion*  Region;      /*лексемам и нетерминалам.                                                  */
      TListCage*RegionList;  /* Ниже с помощью %token устанавливается тип лексемам, а с помощью %type -- */
      TMonitor* Monitor;     /*нетерминалам. При  использовании в  правилах структур  вида $1,..,n  и $$ */
     }                       /*используются соответствующие поля yylval.                                 */
     
    %token <IntVal> MONITOR WINDOW HSTACK VSTACK OPEN CLOSE
    %token <IntVal> DIMENSION FIX_DIMENTION
    %type  <Region> window hstack vstack region
    %type  <RegionList> region_list
    %type  <Monitor> monitor monitor_list
     
    %%
    start:          monitor_list
                                                {
                                                    Monitors=$1;
                                                }
            ;
    monitor_list:   monitor
                                                {
                                                    $$=$1;
                                                }
            |       monitor monitor_list
                                                {
                                                    $1->Next=$2;
                                                    $$=$1;
                                                }
            ;
    monitor:        MONITOR DIMENSION region
                                                {
                                                    TMonitor* Monitor=(TMonitor*)malloc(sizeof(TMonitor));
                                                    Monitor->Region=$3;
                                                    Monitor->Monitor=$2;
                                                    Monitor->Next=NULL;
                                                    $$=Monitor;
                                                }
            ;
    region_list:    region
                                                {
                                                    TListCage* Cage=(TListCage*)malloc(sizeof(TListCage));
                                                    Cage->Region=$1;
                                                    Cage->Next=NULL;
                                                    $$=Cage;
                                                }
            |       region region_list
                                                {
                                                    TListCage* Cage=(TListCage*)malloc(sizeof(TListCage));
                                                    Cage->Region=$1;
                                                    Cage->Next=$2;
                                                    $$=Cage;
                                                }
            ;
    region:         window
            |       hstack
            |       vstack
            ;
    window:         WINDOW DIMENSION
                                                {
                                                    TRegion* Window=(TRegion*)malloc(sizeof(TRegion));
                                                    Window->RegionType=rtWindow;
                                                    Window->isFixed=0;
                                                    Window->Dimension=$2;
                                                    Window->RegionList=NULL;
                                                    $$=Window;
                                                }
            |       WINDOW FIX_DIMENTION
                                                {
                                                    TRegion* Window=(TRegion*)malloc(sizeof(TRegion));
                                                    Window->RegionType=rtWindow;
                                                    Window->isFixed=1;
                                                    Window->Dimension=$2;
                                                    Window->RegionList=NULL;
                                                    $$=Window;
                                                }
            |       WINDOW
                                                {
                                                    TRegion* Window=(TRegion*)malloc(sizeof(TRegion));
                                                    Window->RegionType=rtWindow;
                                                    Window->isFixed=0;
                                                    Window->Dimension=1;
                                                    Window->RegionList=NULL;
                                                    $$=Window;
                                                }
            ;
    hstack:         HSTACK OPEN region_list CLOSE
                                                {
                                                    TRegion* Window=(TRegion*)malloc(sizeof(TRegion));
                                                    Window->RegionType=rtHorizontal;
                                                    Window->isFixed=0;
                                                    Window->Dimension=1;
                                                    Window->RegionList=$3;
                                                    $$=Window;
                                                }
            |       HSTACK DIMENSION OPEN region_list CLOSE
                                                {
                                                    TRegion* Window=(TRegion*)malloc(sizeof(TRegion));
                                                    Window->RegionType=rtHorizontal;
                                                    Window->isFixed=0;
                                                    Window->Dimension=$2;
                                                    Window->RegionList=$4;
                                                    $$=Window;
                                                }
            |       HSTACK FIX_DIMENTION OPEN region_list CLOSE
                                                {
                                                    TRegion* Window=(TRegion*)malloc(sizeof(TRegion));
                                                    Window->RegionType=rtHorizontal;
                                                    Window->isFixed=1;
                                                    Window->Dimension=$2;
                                                    Window->RegionList=$4;
                                                    $$=Window;
                                                }
            ;
    vstack:         VSTACK OPEN region_list CLOSE
                                                {
                                                    TRegion* Window=(TRegion*)malloc(sizeof(TRegion));
                                                    Window->RegionType=rtVertical;
                                                    Window->isFixed=0;
                                                    Window->Dimension=1;
                                                    Window<font color
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 10

      0
      В Windows тоже набирает популярность подход фреймовых оконных менеджеров? :) Вот уже и удобные средства конфигурации появляются.

      К сожалению, не знаю куда выложить на более долгое время.

      Google Code, например.
        +1
        Спасибо, выложил сюда
        0
        Там с левой/правой рекурсией не только удобство связано — помнится у универе рассказывали, что в YACC (а бизон, как я понимаю — совместимое средство) используется алгоритм разбора, который лучше разбирает выражения, если используется именно правая рекурсия.
          +2
          Скорее наоборот: левой рекурсией можно обработать неограниченное количество элементов, а правой — столько, сколько хватит стека.
            0
            Да-да, точно, вспомнилось!:)

            Кстати в википедии сейчас посмотрел — там вообще говорится что не произвольное количество, а просто что стек меньше юзается.
            • UFO just landed and posted this here
        • UFO just landed and posted this here
            0
            Это демонстрационный рабочий пример, которым я хотел показать, что DSL и синтаксический/лексический разбор — это не страшно, быстро и, в некотором роде, удобно.
            Этой статьёй я хотел привести несколько другой, чем стандартные калькуляторы, пример, показать как возникает из задачи возможность применить DSL, как увидеть грамматику, как воспользоваться flex/bison.
            Программа получилась маленькая, с очень небольшим довеском обвязывающих алгоритмов. Она выполняет конкретную задачу, и, на мой взгляд, идеальный обучающий пример.
            Зачем для такой мелкой задачи придумывать DSL со своим синтаксисом, если можно описать то же самое в рамках XML

            Можно, но исторически сложилось именно так :)
            • UFO just landed and posted this here
            0
            Обнаружил, что первое издание книги Dick Grune, Ceriel J. H. Jacobs — Parsing Techniques: A Practical Guide доступно с сайта авторов.

            Only users with full accounts can post comments. Log in, please.