バッカス・ナウア記法

問題

あるプログラム言語において，識別子(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>

答え

解説

バッカス・ナウア記法

バッカス・ナウア記法（英: Backus-Naur form）とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般にBNFやBN記法と略される。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

以下は簡潔にまとまっています。

バッカス・ナウア記法

以下は詳しい解説です。

2.3 バッカス記法

この問題の場合、 <letter>｜<digit>｜で始まる2つは、「先頭が英字で始まり」と矛盾するので誤りです。

<identifier><digit>と<identifier><letter> は、どちらも識別子(identifier)として用いることができます。定義中に含まれる <identifier> に再帰的に <identifier> を代入していくことで、「 <letter> で始まり、 <letter> か <digit> が任意個続いた後に、 <letter> で終わる」または「 <letter> で始まり、 <letter> か <digit> が任意個続いた後に、 <digit> で終わる」ということを表現できます。

よって、 <letter>｜<identifier><digit>｜<identifier><letter>が正解です。