BNFとは―情報処理のBNFの意味、記法例、問題、解説
トップ
情報処理の知識体系
テクノロジ系
基礎理論
情報に関する理論
形式言語
BNF
BNFとはどのような記法かをまとめています。情報処理のBNFとはどんなものか理解したい、意味はもちろん、記法例や問題つきで解説されていると助かるという方におすすめのコンテンツです。
プログラムの形態的な構造を構文といい、構文を規定する規則を構文規則といいます。 代表的な構文記述法として、BNF記法があります。
目次
以下は目次リンクになります。
1. BNFとは
BNFとは、Backus Nuaur Form（バッカス・ナウア記法）の略で、プログラム言語の構文などを定義する表現方法です。
2. BNFの記法
BNFでは、次のように記述します。
「::＝」は「左辺を右辺のように定義する」、「｜」は「または」という意味です。
3. BNF関連用語の意味
BNFでは以下のような用語が登場します。BNF関連用語の意味を補足していきます。
-
終端記号
これ以上分解できない要素で、変数や文字列定数のような記号です。
-
非終端記号
＜＞で示された要素で「::=」の右辺に現れ、されに分解できる記号です。
-
開始記号
「::=」の左辺を開始記号といいます。
4. BNFでプログラムの識別子の構文を表現する例
BNFで先頭が＜英字＞で始まり、それ以降に0個以上（任意個）の＜数字＞または＜英字＞（英数字）によって構成される（が続く）＜識別子＞（文字列）とプログラムの識別子の構文を定義します。
＜英字＞::＝0|1|2|3|4|5|6|7|8|9
＜英字＞::＝A|B|C|・・・|X|Y|Z|a|b|c|・・・|x|y|z
まず初めに＜英字＞で始まるので、その部分は次のように表現できます。
＜識別子＞::＝＜英字＞
次に0個以上の＜数字＞または＜英字＞によって構成される部分は、続くのが0個の場合＜識別子＞::＝＜英字＞。 続くのが1個の場合は＜識別子＞::＝＜英字＞＜数字＞|＜英字＞＜英字＞で表現できます。 ここまでを整理すると次のパターンがように表現できます。
＜識別子＞::＝＜英字＞
＜識別子＞::＝＜英字＞＜数字＞|＜英字＞＜英字＞
そして、2個以上続く場合は、＜数字＞または＜英字＞は1文字なので再帰的に用いて表現します。つまり、＜識別子＞::＝＜識別子＞＜数字＞|＜識別子＞＜英字＞のように表現します。 これは1個以上の＜識別子＞::＝＜英字＞＜数字＞|＜英字＞＜英字＞も表現できるので、ここまでを整理すると次のパターンがように表現できます。
＜識別子＞::＝＜英字＞
＜識別子＞::＝＜識別子＞＜数字＞|＜識別子＞＜英字＞
以上より、識別子の定義は次のように表現できます。
＜識別子＞::＝＜英字＞|＜識別子＞＜数字＞|＜識別子＞＜英字＞
BNFに関連したIPA情報処理試験の過去問
以下ではBNFに関連したIPA情報処理試験の過去問とその解説をまとめています。
BNFに関連した参考書籍
BNFに関連した参考書籍です。目次や参考いたしました内容をまとめています。
もっと知識を広げるための参考
-
情報に関する理論
情報に関する理論として、形式言語と有限オートマトンの状態遷移図などの解説や演習問題をまとめています。
-
テクノロジ系
情報処理試験対策用のサイトオリジナル教科書をテーマにテクノロジ系の知識をまとめています。
更新履歴
更新履歴になります。
- 2017年12月11日 BNFに関連した参考書籍について追記しました。
- 2017年07月07日 ページを作成しました。