AP 平成29年度春期問4

　あるプログラム言語において，識別子（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>
単独の<digit> があり、先頭が数字で始まる可能性があるため誤りです。
<letter> | <digit> | <letter><identifier> | <identifier><digit>
単独の<digit> があり、先頭が数字で始まる可能性があるため誤りです。
<letter> | <identifier><digit>
この2種類では、先頭が英字で始まり，それ以降に任意個の数字が続く文字列しか表現できません。
<letter> | <identifier><digit> | <identifier><letter>
正しいです。
例えば“A1B”という文字列を表現する場合、次の順序で実現できます。
①<identifier> = <identifier><letter> を選択：<identifier><letter>
②<letter> = B を選択：<identifier>B
③<identifier> = <identifier><digit> を選択：<identifier><digit>B
④<digit> = 1 を選択：<identifier>1B
⑤<identifier> = <letter> を選択：<letter>1B
⑥<letter> = A を選択：A1B