次のBNFで定義される＜変数名＞に合致するものはどれか。
＜数字＞::=0|1|2|3|4|5|6|7|8|9
＜英字＞::=A|B|C|D|E|F
＜英数字＞::=＜英字＞|＜数字＞|_
＜変数名＞::=＜英字＞|＜変数名＞＜英数字＞
正答4
解説
正解は4です。
BNF（Backus-Naur Form：バッカス・ナウア記法）は、構文規則を再帰的に定義する記法です。
＜変数名＞::=＜英字＞|＜変数名＞＜英数字＞は、「英字1文字で始まり、その後ろに英数字が0個以上続くもの」を意味します。
英字はA〜Fの6文字、英数字は英字・数字・下線（_）のいずれかです。
【選択肢別解説】
1：× 先頭が下線（_）です。
下線は英数字には含まれますが英字ではないので、変数名の先頭には置けません。
2：× 先頭が数字の2です。
変数名は英字で始まる必要があるので誤りです。
3：× 先頭が数字の3です。
2文字目のEは英字ですが、先頭が英字でないので変数名になりません。
4：○ 先頭のFは英字です。
続く5、_、1はいずれも英数字なので、規則に合致します。
【計算】
選択肢4のF5_1を規則で組み立てます。
Fは＜英字＞なので＜変数名＞です。
F（変数名）と5（数字）を連結したF5は＜変数名＞です。
F5と_を連結したF5_は＜変数名＞です。
F5_と1を連結したF5_1は＜変数名＞です。
【ポイント】
左再帰の定義＜X＞::=＜A＞|＜X＞＜B＞は、「Aで始まり、Bが0回以上続く」と読み替えられます。
先頭文字に使える記号と、2文字目以降に使える記号の違いに注目しましょう。