バッカス・ナウア記法

問題

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

解説

バッカス・ナウア記法

バッカス・ナウア記法: 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>が正解です。