GridStack-flex + bisonのケーススタディ

最近、表現の文法分析に関する いくつかの 記事がHabréに登場しました。

そしてこれは素晴らしい！ 私の謙虚な意見では、すべてのプログラマーは少なくとも一度は表現の分析を書くべきです。 私は共通の原因に貢献しようとします。



分析には多くの方法があります（ Dick Grune、Ceriel JH Jacobs-Parsing Techniques：A Practical Guide、ISBN 0-13-651431-6による以下のレビューをお勧めします）。 さらに、メソッドの実装は、完全に手動からバイソン、アントラー、レモンなどの自動ジェネレーターの使用にまで及びます。

字句および構文の手動記述（後で字句解析器および構文解析器を参照します）解析により最大速度と制御（特にエラーおよびそれらを克服する方法）を達成できますが、ジェネレーターの使用によりタスクに直接集中でき、文法の変更と保存が容易になります時間。 このようなツールを習得する機能により、DSL（ドメイン固有言語）に頼ることが多くなり、一般的にそれらのアプリケーションの可能性を確認できます。



実生活でのbison（パーサー）とflex（レクサー）の使用例：タスクの発生から解決まで。





GridMoveという素晴らしいプログラムがあります。これにより、バインディンググリッドごとにアプリケーションウィンドウを整理できます。 バインディンググリッドは通常のiniファイルで設定され、トリガー領域と対応するウィンドウサイズと位置が示されます。 一緒に、多くの素晴らしいグリッドが開発されました。 しかし、問題がありました。レイアウトに適合せず、いくつかのグリッドを手動で作成したため、プロセスを何らかの形で自動化したかったのです。



必要なメッシュを分析すると、単純な再帰構造でメッシュを記述できることに気付きました。

領域は、サマリーウィンドウ、垂直領域、または水平領域のいずれかです。 垂直領域は、同じ幅を持ち、指定された割合で高さを分割する領域で構成されます。 水平領域は、それぞれ同じ高さの領域で構成され、指定されたシェアで幅を分割します。



簡単な例を考えてみましょう。



モニター全体は、サブリージョンAとBで構成される水平リージョンとして表されます。リージョンAは、サブリージョンCとDの垂直リージョンです。リージョンCは、もはや分割されていない単なるウィンドウです。 領域Dは、3つの単純なウィンドウの水平領域です。 領域Bは、3つの単純なウィンドウの垂直領域です。

これはすべて、私が発明したDSLで次のように説明できます。

モニター1

HStack＃すべてのウィンドウ

（

VStack 3 ＃リージョンA

（

ウィンドウ2 ＃リージョンC

HStack＃リージョンD

（

ウィンドウ＃リージョンE

ウィンドウ＃リージョンF

ウィンドウ＃リージョンG

）

）

VStack＃リージョンB

（

ウィンドウ＃リージョンH

ウィンドウ＃リージョンI

ウィンドウ＃リージョンJ

）

）

Window、HStack、VStackはリージョンの説明です。 領域内の数値は、相対的な重みであり、supraregionの領域の割合です（デフォルト== 1）。 番号に「！」記号が付いている場合、これはピクセル単位の固定サイズです。



画面上のウィンドウの位置がこのように記述できることに気付いたとき、私はロシア語のみで紙の上に何かをスケッチしました。 次に、DSLを作成し、解析して処理する方が便利だと判断しました。

文法を作りましょう。 斜体は非終端文字を示します。

開始 :: = monitor_list

monitor_list :: = モニター | モニター monitor_list

monitor :: = MONITOR DIMENSION リージョン

region_list :: = 地域 | 地域 region_list

領域 :: = ウィンドウ | hstack | vstack

ウィンドウ :: = 窓の寸法 | ウィンドウFIX_DIMENTION | 窓

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ファイルを提供します。 大文字と小文字を区別する語彙の実装方法に特に注意を払ってはいけません。 -iスイッチでflexを呼び出すことはできましたが、大文字と小文字を区別しないようにしました。 最終的な形式がわからなかったため、ブラケット用の端末を起動しました。

/*<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/>



パーサーを作成するには、通常2つのアプローチがあります。

1. すぐにすべてのロジックの実装。
2. データ収集とその後の処理。 この場合、通常構築される構造はAST（Abstract Syntax Tree）と呼ばれます。

私は2番目の方法の支持者なので、すべてのデータを収集するだけでした。 追加の利点は、地域ディメンションを計算するための余分なロジックをクリアせずにコード全体を取り込むことができることです。

以下に、コメント付きのGridStack.yファイルを示します。

％ {

#include <stdio.h>

#include <malloc.h>

#include "common.h"

％ }

％ union / *これは、バイソンとフレックスが一緒になって結合するyylvalのタイプの定義です* /

{ / *はトークンの伝達に使用されます。 データ転送用のバイソン* /

int IntVal; / *ルール間。 フィールド名は割り当て可能なタイプです* /

TRegion *地域。 / *トークンと非端末。 * /

TListCage * RegionList; / *以下では、％tokenはトークンのタイプを設定し、%%-* /

TMonitor *モニター。 / *非端末。 $ 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

{

モニター= 1ドル。

}

;

monitor_list ：モニター

{

$$ = $ 1 ;

}

| モニターmonitor_list

{

$ 1- >次= $ 2 ;

$$ = $ 1 ;

}

;

モニター： MONITOR DIMENSIONリージョン

{

TMonitor * Monitor = （ TMonitor * ） malloc （ sizeof （ TMonitor ） ） ;

モニター->地域= 3ドル。

モニター->モニター= 2ドル。

モニター->次= NULL ;

$$ =モニター;

}

;

region_list ：地域

{

TListCage * Cage = （ TListCage * ） malloc （ sizeof （ TListCage ） ） ;

ケージ->地域= $ 1 ;

ケージ->次= NULL ;

$$ =ケージ;

}

| 地域region_list

{

TListCage * Cage = （ TListCage * ） malloc （ sizeof （ TListCage ） ） ;

ケージ->地域= $ 1 ;

ケージ->次= 2ドル

$$ =ケージ;

}

;

地域：窓

| hstack

| vstack

;

窓：窓の寸法

{

TRegion *ウィンドウ= （ TRegion * ） malloc （ sizeof （ TRegion ） ） ;

ウィンドウ-> RegionType = rtWindow;

ウィンドウ-> isFixed = 0 ;

ウィンドウ->寸法= $ 2 ;

ウィンドウ-> RegionList = NULL ;

$$ =ウィンドウ;

}

| ウィンドウFIX_DIMENTION

{

TRegion *ウィンドウ= （ TRegion * ） malloc （ sizeof （ TRegion ） ） ;

ウィンドウ-> RegionType = rtWindow;

ウィンドウ-> isFixed = 1 ;

ウィンドウ->寸法= $ 2 ;

ウィンドウ-> RegionList = NULL ;

$$ =ウィンドウ;

}

| 窓

{

TRegion *ウィンドウ= （ TRegion * ） malloc （ sizeof （ TRegion ） ） ;

ウィンドウ-> RegionType = rtWindow;

ウィンドウ-> isFixed = 0 ;

ウィンドウ->寸法= 1 ;

ウィンドウ-> RegionList = NULL ;

$$ =ウィンドウ;

}

;

hstack ： HSTACK OPEN region_list CLOSE

{

TRegion *ウィンドウ= （ TRegion * ） malloc （ sizeof （ TRegion ） ） ;

ウィンドウ-> RegionType = rtHorizo​​ntal;

ウィンドウ-> isFixed = 0 ;

ウィンドウ->寸法= 1 ;

ウィンドウ-> RegionList = $ 3 ;

$$ =ウィンドウ;

}

| HSTACK DIMENSION OPEN region_list CLOSE

{

TRegion *ウィンドウ= （ TRegion * ） malloc （ sizeof （ TRegion ） ） ;

ウィンドウ-> RegionType = rtHorizo​​ntal;

ウィンドウ-> isFixed = 0 ;

ウィンドウ->寸法= $ 2 ;

ウィンドウ-> RegionList = $ 4 ;

$$ =ウィンドウ;

}

| HSTACK FIX_DIMENTION OPEN region_list CLOSE

{

TRegion *ウィンドウ= （ TRegion * ） malloc （ sizeof （ TRegion ） ） ;

ウィンドウ-> RegionType = rtHorizo​​ntal;

ウィンドウ-> isFixed = 1 ;

ウィンドウ->寸法= $ 2 ;

ウィンドウ-> RegionList = $ 4 ;

$$ =ウィンドウ;

}

;

vstack ： VSTACK OPEN region_list CLOSE

{

TRegion *ウィンドウ= （ TRegion * ） malloc （ sizeof （ TRegion ） ） ;

ウィンドウ-> RegionType = rtVertical;

ウィンドウ-> isFixed = 0 ;

ウィンドウ->寸法= 1 ;

ウィンドウ<フォントの色