次の規則から生成することができる式はどれか。
〔規則〕
<式> ::= <変数> | (<式>+<式>) | <式>*<式>
<変数> ::= A | B | C | D
正答3
解説
正解は3です。
BNF（バッカス・ナウア記法）で書かれた生成規則から作れる式を判定します。
規則では、加算は必ず「(<式>+<式>)」のように括弧で囲まれた形でしか現れません。
一方、乗算は「<式>*<式>」の形で、括弧は付きません。
【選択肢別解説】
1：× 「A+(B+C)*D」は、最も外側の加算が括弧で囲まれていません。
規則には括弧なしの「<式>+<式>」がないため、生成できません。
2：× 「(A+B)+(C+D)」は、中央の加算が外側の括弧で囲まれていません。
全体を「((A+B)+(C+D))」とすれば生成できますが、この形では生成できません。
3：○ 「(A+B)」と「(C+D)」は、それぞれ「(<式>+<式>)」の規則で作れます。
その二つを「<式>*<式>」の規則でつなぐと「(A+B)*(C+D)」になります。
4：× 「(A*B)」のように乗算を括弧で囲む規則はありません。
また、中央の加算も括弧で囲まれていないため、生成できません。
【ポイント】
BNFの問題は、式の最も外側の演算子から規則に当てはめて分解していきます。
「|」は「または」を表し、どの規則にも当てはまらない部分が一つでもあれば生成できません。