応用情報技術者 2011年 春期 午前2 問04
問題文
あるプログラム言語において、識別子 (identifier) は、先頭が英字で始まり、それ以降に任意個の英数字が続く文字列である。これを BNFで定義したとき、a に入るものはどれか。
＜digit＞ ::=0|1|2|3|4|5|6|7|8|9
＜letter＞ ::=A|B|C|...|X|Y|Z|a|b|c||x|y|z
＜identifier＞ ::= [ a ]
選択肢
ア：＜letter＞|＜digit＞|＜identifier＞＜letter＞|＜identifier＞＜digit＞
イ：＜letter＞|＜digit＞|＜letter＞＜identifier＞|＜identifier＞＜digit＞
ウ：＜letter＞|＜identifier＞＜digit＞
エ：＜letter＞|＜identifier＞＜digit＞|＜identifier＞＜letter＞（正解）
識別子のBNF定義問題【午前2 解説】
要点まとめ
- 結論：識別子は「先頭が英字」で「その後に英数字が任意個続く」ため、BNFは＜letter＞|＜identifier＞＜digit＞|＜identifier＞＜letter＞となる。
- 根拠：BNFは再帰的定義で、先頭は必ず＜letter＞、続く部分は＜identifier＞に＜digit＞または＜letter＞を付加する形で表現する。
- 差がつくポイント：再帰の使い方と先頭文字の制約を正しく理解し、選択肢の構造を正確に読み解くことが重要。
正解の理由
選択肢エは、識別子の定義に合致しています。
- 先頭は必ず＜letter＞で始まるため、最初の選択肢に＜letter＞がある。
- その後は任意個の英数字（＜digit＞または＜letter＞）が続くため、再帰的に＜identifier＞に＜digit＞または＜letter＞を付け加える形で表現。
- これにより「先頭が英字で、その後に英数字が任意個続く」という条件を満たします。
よくある誤解
- 先頭に＜digit＞を許してしまう誤り。識別子は必ず英字から始まる。
- 再帰の方向や付け加える順序を誤解し、定義が無限ループや不正確になることがある。
解法ステップ
- 識別子の条件を確認：先頭は英字（＜letter＞）であること。
- 先頭の文字をBNFで表現：＜identifier＞ ::= ＜letter＞ ...
- 先頭以降は英数字（＜letter＞または＜digit＞）が任意個続くので、再帰的に定義。
- 再帰部分は＜identifier＞に＜digit＞または＜letter＞を付加する形で表す。
- 選択肢の中でこの形を満たすものを選ぶ。
選択肢別の誤答解説
- ア：先頭に＜digit＞を許しているため誤り。
- イ：＜letter＞＜identifier＞の形が誤りで、先頭が＜letter＞であることは正しいが、続く部分の再帰が不適切。
- ウ：＜identifier＞＜digit＞のみで、＜letter＞を続ける可能性を排除しているため不完全。
- エ：先頭が＜letter＞で、続く部分に＜identifier＞＜digit＞または＜identifier＞＜letter＞を許す正しい再帰定義。
補足コラム
BNF（Backus-Naur Form）は文法を形式的に表現する方法で、プログラミング言語の構文定義に広く使われます。再帰的定義を用いることで、任意の長さの文字列や構造を簡潔に表現可能です。識別子のように「先頭に特定の文字種、その後に任意の文字種が続く」パターンは典型的な再帰定義の例です。
FAQ
Q: なぜ先頭に＜digit＞を許してはいけないのですか？
A: 識別子の定義上、先頭は英字で始まる必要があり、数字で始まると識別子として認められません。
A: 識別子の定義上、先頭は英字で始まる必要があり、数字で始まると識別子として認められません。
Q: 再帰定義がなぜ必要なのですか？
A: 再帰を使うことで、任意の長さの文字列を簡潔に表現でき、BNFの記述が簡単かつ明確になります。
A: 再帰を使うことで、任意の長さの文字列を簡潔に表現でき、BNFの記述が簡単かつ明確になります。
関連キーワード: BNF, 識別子、再帰定義、文法定義、プログラミング言語
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！