平成29年度 春期 午前 問4
基礎理論
BNFに関する問題
あるプログラム言語において，識別子（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＞
答えと解説を見る
✓ これが正解エ＜letter＞ | ＜identifier＞＜digit＞ | ＜identifier＞＜letter＞
解説
英字 1 文字から始め、後ろに英数字を足す形です。
設問は、先頭が英字で、その後ろに任意個の英数字が続く文字列を BNF で定義させています。日本語の条件を 2 つに割ると見通しがよくなります。1 つ目は、先頭に置けるのは英字だけということです。したがって、1 文字だけの識別子は英字の規則だけで作られます。数字 1 文字を識別子と認めてしまう並びが混じっていたら、その定義は外れます。2 つ目は、2 文字目以降には英字も数字も置けるということです。すでに識別子である文字列の後ろに英字を足しても、数字を足しても、やはり識別子になります。自分自身を右辺に呼び出す再帰の形です。この 2 つをともに満たす並びが当てはまります。短い文字列で試すのが確実で、数字 1 文字が作れないことと、英字が 2 つ並んだ文字列が作れることを見れば決まります。
ほかの選択肢はなぜ違うのか
- ア＜letter＞ | ＜digit＞ |…：数字だけの規則を選べる並びの 1 つとして置いているので、数字 1 文字の文字列まで通してしまいます。先頭は英字に限るという条件に反しており、後半の並びが妥当でもこの一点で外れます。
- イ＜letter＞ | ＜digit＞ |…：同じく数字だけの規則を置いている上に、英字を左側へ付け足す並びが混じっています。先頭が数字の文字列を弾けない時点で、求められた定義になりません。
- ウ＜letter＞ | ＜identifi…：並んでいる規則が 2 つしかなく、後ろに足せるのが数字だけになっています。英字を続けて置く道がないため、英字が 2 つ並ぶ文字列を作り出せず、条件の後半を満たしません。
この問題の用語
- プログラム言語プログラムを書くための文法や記号の体系のこと。目的に合わせて多くの種類があり、Java、C、Pythonなどがよく使われます。
出典：平成29年度 春期 応用情報技術者試験 午前 問4
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）