応用情報技術者 2017年春期午前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＞）を置き、続く文字は英字か数字（＜letter＞または＜digit＞）のいずれかを識別子に連結する形で表現する。
差がつくポイント：再帰の位置と順序、先頭文字の制約を正しく理解し、選択肢の記述がBNFの文法規則に合致しているかを見極めること。

正解の理由

選択肢エは、識別子の定義を「＜letter＞」で始まり、その後に「＜identifier＞＜digit＞」または「＜identifier＞＜letter＞」が続く形で表現しています。
これは「先頭は英字（＜letter＞）」で、「以降は英字か数字（＜letter＞または＜digit＞）」が任意個続くという条件を満たす再帰的なBNF定義として正しいためです。

よくある誤解

「先頭に数字が来てもよい」と誤解し、＜digit＞を先頭に含める定義を選ぶことが多いです。
再帰の位置や順序を誤り、無限ループや誤った文字列を生成するBNFを選ぶことがあります。

解法ステップ

識別子の条件を確認：先頭は英字、以降は英数字が任意個続く。
BNFの基本構造を理解：再帰的に定義し、先頭の文字と続く文字を分ける。
選択肢の記述を比較し、先頭が＜letter＞であるかを確認。
続く部分が＜identifier＞＜digit＞または＜identifier＞＜letter＞の形で再帰的に表現されているかを検証。
条件に合致する選択肢を選ぶ。

選択肢別の誤答解説

ア：先頭に＜digit＞が含まれており、識別子の先頭が英字である条件に反する。
イ：先頭に＜digit＞が含まれているため誤り。また、再帰の順序も不適切。
ウ：先頭は＜letter＞で正しいが、続く部分が＜identifier＞＜digit＞のみで＜letter＞が抜けているため不完全。
エ：先頭が＜letter＞で、続く部分が＜identifier＞＜digit＞または＜identifier＞＜letter＞で再帰的に英数字を表現しており正しい。

補足コラム

BNF（Backus-Naur Form）は文法を形式的に表現するための記法で、プログラミング言語の構文定義に広く使われます。識別子のような文字列の定義では、再帰を用いて「任意個の繰り返し」を表現することが一般的です。
また、識別子の先頭文字に制約がある場合は、その部分を明確に分けて定義することが重要です。