平成29年度 春期 応用情報技術者試験 午前 問4
テクノロジ／アルゴリズムあるプログラム言語において，識別子（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
出典：平成29年度 春期 応用情報技術者試験 午前 問4
- ア<letter> ｜ <digit> ｜ <identifier><letter> ｜ <identifier><digit>
- イ<letter> ｜ <digit> ｜ <letter><identifier> ｜ <identifier><digit>
- ウ<letter> ｜ <identifier><digit>
- エ<letter> ｜ <identifier><digit> ｜ <identifier><letter>
正解：エ
解説
識別子は，先頭が英字1文字であるか，既存の識別子の後ろに英字または数字を1文字追加したものとして再帰的に定義できます。したがって <identifier> ::= <letter> ｜ <identifier><digit> ｜ <identifier><letter> という定義が適切です。
選択肢ごとの解説
- ア誤り。<digit>だけの選択肢が独立して含まれており，数字1文字だけの識別子（英字で始まらないもの）を許してしまいます。
- イ誤り。<digit>だけの選択肢が含まれるほか，<letter><identifier>は識別子の前に文字を追加する定義になっており，意図と異なります。
- ウ誤り。<identifier><letter>による再帰的な追加が定義されておらず，2文字目以降に英字を続けることができません。
- エ正しい。<letter>（先頭の英字）｜<identifier><digit>（数字追加）｜<identifier><letter>（英字追加）によって，英字で始まり英数字が続く識別子を過不足なく表せます。