目次 †
BNF †
BNF（Backus-Naur Form：バッカス記法）とは、プログラム言語の文法を示す記法の一種である。アメリカの計算機科学者バッカス（J.W.Backus）が、Alogol60の構文規則のために提唱した記法である。文字の並び方の規則を文字で定義し、反復や選択なども適当な文字記号で表現する。文字だけで定義するので、簡潔に表現でき、最終的な分の記述形式に近い表現になる。
この記法は文脈自由文法と同等の記述能力を持つ。
BNFの構文規則のルール †
- 同じ左辺に対する右辺の対応を区切り記号で区切りながら、すべて並べていく。
- 非終端記号は「＜」と「＞」で囲む。
- 記号「::==」が左辺と右辺の区切りを表す。
- 右辺の中での区切りとして「|」が「または」の意味で使われる。
演習 †
例題：数値 †
あるプログラム言語の数値に関する構文がBNFで次のように定義されているとき、＜数値＞として扱われるものを選べ。
＜数値＞::==＜数字列＞|＜符号＞＜数字列＞|＜数字列＞.＜数字列＞
＜数字列＞::==＜数字＞|＜数字列＞＜数字＞
＜数字＞::==0|1|2|3|4|5|6|7|8|9
＜符号＞::==+|-
- ＜数値＞として扱われる例
- ＜数値＞として扱われない例
- 1.2E+1
- 指数を表していると思われるEが未定義なので、数値としては認められない。
- 12.
- 「＜数字列＞.＜数字列＞」という定義なので、ピリオドの前と後ろにも数字列が必要である。
- .5
- 「＜数字列＞.＜数字列＞」という定義なので、ピリオドの前と後ろにも数字列が必要である。
- +-1
- 符号が付く場合は「＜符号＞＜数字列＞」という定義から、符号が連続することはありえない。
例題：算術式 †
次のBNF形式で示された構文規則を満たすものを選べ【H7年PE午前問17】。
＜算術式＞::==＜項＞|＜算術式＞＜加減演算子＞＜項＞
＜加減演算子＞::==＋|−
＜項＞::==＜因子＞|＜項＞＜乗除演算子＞＜因子＞
＜乗除演算子＞::==*|/
＜因子＞::==＜定数＞|＜変数＞|(＜算術式＞)
＜変数＞::==x|y|z
＜定数＞::==5|10|12
- 算術式を満たす例
- 算術式を満たさない例
- x+log(y+10)
- y+10/xz
- −x+y/z*5
例題：式 †
次のBNFで示された構文規則で、式となるものを選べ【H9年PE午前問75】。
＜式＞::==＜項＞|＜式＞+＜項＞
＜項＞::==＜因子|(-＜因子＞)|＜項＞＜因子＞
＜因子＞::==0|1|(＜式＞)
- 式を満たす例
- 式を満たさない例
- (-10)
- ＜式＞→＜項＞→＜項＞＜因子＞→＜因子＞＜因子＞だから10はありえる。
- しかし、(-10)になるには、(-＜因子＞)であって欲しいが、定義からすると(-＜式＞)や(-＜項＞)でなければならない。
- −(1+0)
- マイナスは必ず括弧の中にあるはずだから、これは満たさない。
- (1-1)
例題：具体的な式からBNF記法の生成規則を特定する †
- 式：(A+B)*(X+Y)*C 【H8年PE午前問76】
- 生成規則：＜式＞::==＜変数＞|(＜変数＞+＜変数＞)|＜式＞*＜式＞
参考文献 †
- 『ソフトウェア開発技術者試験対策 コンピュータサイエンス補足資料＋午後演習問題』
