平成23年度 高度共通 午前I（PM試験） 問2
あるプログラム言語において，識別子（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>
解答・解説を見る
正解：エ
AI解説
「先頭が英字、以降に任意個の英数字」を再帰的なBNFで表すには、基底として<letter>(英字1文字)を置き、既にできた<identifier>の後ろに<digit>または<letter>を付け足す再帰規則を並べればよい。<letter> | <identifier><digit> | <identifier><letter>なら、必ず英字で始まり、2文字目以降に英字も数字も続けられる。 ア: 誤り。<digit>単独を許しているため、数字1文字(数字始まり)の文字列が識別子になってしまう。 イ: 誤り。同じく<digit>単独で数字始まりを許してしまう。また<letter><identifier>の形も定義の意図に合わない。 ウ: 誤り。<identifier><digit>しか再帰がなく、2文字目以降に英字を続けられない。英「数字」が続く定義を満たさない。 エ: 正しい。基底<letter>で英字始まりを保証し、<identifier><digit>と<identifier><letter>の再帰で以降に任意個の英数字を続けられる。 💡 BNFの再帰定義は「基底(最小の形)+再帰(後ろに1文字追加)」の構造で読む。検証は「数字1文字が導出できてしまわないか」「2文字目に英字・数字の両方を置けるか」の2チェックで機械的に判定できる。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。