平成23年度特別 応用情報技術者試験 午前 問4

正解：エ

AI解説

識別子は「先頭が英字、それ以降は任意個(0個以上)の英数字が続く」という定義である。BNFで再帰的に表現すると、基底として1文字の〈letter〉を置き、既存の識別子の末尾に〈letter〉または〈digit〉を1文字ずつ追加していく左再帰の形になる。 ア: 〈identifier〉〈letter〉と〈identifier〉〈digit〉に加え〈letter〉|〈digit〉も基底になっており、先頭が数字だけの識別子(単独の〈digit〉)も許容してしまうため誤り。 イ: 〈letter〉〈identifier〉のように識別子の前に英字を付加する右再帰的な定義であり、末尾に任意個の英数字が続くという定義とは異なるため誤り。 ウ: 〈identifier〉〈digit〉しか再帰規則がなく、英字を追加して識別子を延長するケースを表現できないため誤り。 エ: 基底が〈letter〉(先頭は必ず英字)のみで、既存の識別子の末尾に〈letter〉または〈digit〉を追加していく左再帰の定義になっており、仕様を正しく表現しているため正解。 💡 BNFの左再帰(〈X〉::=基底|〈X〉追加要素)は「末尾に要素を追加していく」構造になる点を意識する。基底に何を許すかが「先頭文字の制約」を決める。