アーシの毎日インプット

毎日1つ以上学習する。学習した内容を公開する。を目標に自分のスキルアップを目指します。

BNF

スポンサードリンク

BNFとはバッカス・ナウア記法(Backus-Naur form)のことです。

 

ja.wikipedia.org

Wikipediaによると、文脈自由文法を定義するのに用いられるメタ言語のことであるとされています。

 

例としては、下記のように記述します。

 <a>::=<0>|<1>|<2>|<3>

 <b>::=<4>|<5>|<6>

 <c>::=<7>|<8>|<9>

 <d>::=<a>|<b><c>|<c><d>

 

 

BNF記法の意味を簡単に説明すると・・・

 aは0か1か2か3のいずれかである。

 bは4か5か6のいずれかである。

 cは7か8か9のいずれかである。

 

ここまではわかりやすいです。

 |がorを表し、<>内の文言が設定されるということですね。

 

続いて、<d>::=<a>|<b><c>|<c><d>

 dはaかbcかcdである

 

ありえるパターンとして、

 <d>::=<a>より、d=0,1,2,3

 <d>::=<b><c>より、d=47,48,49,57,58,59,67,68,69

 

ここからが難しいのですが、<d>::=<c><d>のように自分自身を参照するパターンの場合、そのパターンを再帰的に実施可能です。

1回目の再帰の場合、次のような値が設定されうることがわかります。

 70,71,72,73,747,748,749,757,758,759,767,768,769,

 80,81,82,83,847,848,849,857,858,859,867,868,869,

 90,91,92,93,947,948,949,957,958,959,967,968,969

2回目、3回目とどんどん左側に7,8,9のいずれかの数字を足していくことができます。

 

ここら辺までならなんとかなるのですが、変数が増えると難しい・・・

 

もう少しBNFが分かるよう精進します。

【アーシの原点】

こちら

【頭を鍛える迷路集】

こちら

スポンサードリンク