BNFとはバッカス・ナウア記法（Backus-Naur form）のことです。
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が分かるよう精進します。
