В последнее время на Хабре появились несколько статей, посвящённых грамматическому разбору выражений.
И это замечательно! По моему скромному мнению, каждый программист должен хоть раз в жизни написать разбор выражения. Постараюсь и я внести свою лепту в общее дело.
Методов разбора существует множество (рекомендую следующий обзор 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:
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, но я сделал регистронезависимость именно так. Терминалы для скобок я завёл, так как не был уверен в окончательном формате.
При написании парсера обычно есть два подхода:
Я сторонник второго метода, поэтому всё, что сделал — это собрал все данные. Дополнительным преимуществом является то, что сейчас можно привести код целиком, не вычищая лишнюю логику расчёта размерностей регионов.
Вот файл GridStack.y с комментариями.
И это замечательно! По моему скромному мнению, каждый программист должен хоть раз в жизни написать разбор выражения. Постараюсь и я внести свою лепту в общее дело.
Методов разбора существует множество (рекомендую следующий обзор 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/>
При написании парсера обычно есть два подхода:
- Реализация всей логики сразу по месту.
- Сбор данных и последующая их обработка. При этом обычно построенную структуру называют 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
