問4 BNF記法

あるプログラム言語において、識別子(identifier)は、先頭が英字で始まり、それ以降に任意個の英数字が続く文字列である。これをBNFで定義したとき、aに入るものはどれか。

::= 0|1|2|3|4|5|6|7|8|9
::= A|B|C|･･･|X|Y|Z|a|b|c|･･･|x|y|z|
::= [ a ]

1. |||
2. |||
3. |
4. ||

バッカス・ナウアー記法はメタ言語の一種で、XMLまわりで利用されているそうです。私は試験勉強で初めて知りましたが、問題を解くだけならそれほど難しくありません。

=はis defined asの意味で、右辺によって左辺を定義しています。|はor（または）の意味です。

::= 0|1|2|3|4|5|6|7|8|9であれば、
「と書いてあったら0〜9のどれかの数字が1つ入るよ」という意味です。

ためしに、問題文の定義を使って、いくつか例をあげてみましょう。
の構文規則にあてはまるのは、1A、2B,3cなど、<数字><英語>という並び。
の構文規則にあてはまるのは、aB3,DC2など、<英語><英語><数字>という並びになります。

ここで重要なのが、BNF記法は入れ子にして定義できるということ。
::=|と定義すれば、123456や78722321など、任意の長さの数字列をとして表すこともできるのです。

さて、問題文で要求されている「先頭が英字で始まり、それ以降に任意個の英数字が続く文字列」は、たとえばA12aとか、Bac3などのことです。
ここではA12aを満たすBNF記法を探してみましょう。
A12aはと表記できます。

まず1と2は除外できます。というのも、||...とありますから。これでは一文字目が数字である並びも含んでしまいます。
3は「先頭が英字」という条件を満たしていますし、の入れ子部分を使えば好きなだけ長い英数字の並びを含むことができますが、しか入れ子がないことから、最後の文字がかならず数字になってしまいます。

4なら|ということで、最後の字を数字にも英文字にもできますね。というわけで、答えは4です。