基本情報技術者 2011年 秋期 午前（科目A） 問04

次の規則から生成可能な式はどれか【午前2 解説】

要点まとめ

• 結論：与えられた生成規則から生成できる式は (A+B)*(C+D) のみで，外側の加算は必ず丸括弧で囲む必要があります。
• 根拠：$<式>::=<変数>|(<式>+<式>)|<式>\ast <式>$ のため，加算は常に丸括弧で包まれ，乗算は括弧なしで二項結合できます。
• 差がつくポイント：式を上から見る（トップレベル演算子の確認）と，括弧がどの生成規則由来かを見分けることが合否を分けます。

正解の理由

よくある誤解

• 「通常の算術と同じ優先順位で判断してよい」：今回の文法は演算子優先や任意の括弧挿入を許しておらず，文法規則に従う必要があります。
• 「丸括弧は任意に置ける」と思う誤り：丸括弧は加算 $(<式>+<式>)$ のためだけに出現し，任意の式を囲むための生成規則は存在しません。
• 「ABC は不可」と誤認する：乗算は再帰的に結合できるため生成可能（結合の仕方は文法で決まる）です。

解法ステップ

1. 式のトップレベル演算子（最外側で見える '+' または '*'）を確認する。
2. トップが '+' なら全体が丸括弧で囲まれているかを確認、囲まれていなければ生成不可。
3. トップが '*' なら左右の項がそれぞれ $<式>$ として生成可能か（特に $(<式>+<式>)$ であるか、単純変数か、さらに乗算でつながるか）を確認する。
4. 各部分について再帰的に同じ確認を行い，すべて文法に従うなら生成可能とする。

選択肢別の誤答解説

• ア: A+(B+C)*D
  • 誤り点：全体のトップレベル演算子は '+' であるが，その加算が丸括弧で囲まれていないため文法 $(<式>+<式>)$ に合致しません。よって生成不可です。
• イ: (A+B)+(C+D)
  • 誤り点：左辺・右辺の (A+B), (C+D) は $(<式>+<式>)$ で生成可能ですが，その二つを結ぶトップレベルの '+' が丸括弧で包まれていません。外側の加算も $(<式>+<式>)$ でなければならないため生成不可です。
• ウ: (A+B)*(C+D)
  • 正答。左は $(<式>+<式>)$（A と B の加算），右も同様で，それらを $<式>\ast <式>$ で結合すれば全体が $<式>$ として生成できます。具体的には $<式>\ast <式>\to (<式>+<式>)\ast (<式>+<式>)$ の形になります。
• エ: (AB)+(CD)
  • 誤り点：左の (AB) や右の (CD) は「丸括弧で囲まれた形」ですが，文法上は丸括弧は加算のための構文 $(<式>+<式>)$ の一部であり，乗算を丸括弧で囲む生成規則はありません。さらに，全体をつなぐ '+' も外側が丸括弧で包まれていないため二重に不適合です。

補足コラム

• 文法の見方：$<式>\ast <式>$ のように項同士を連結する生成規則がある場合，乗算は括弧なしで連続して現れ得ます（例：ABC は $(A\ast B)\ast C$ の形で生成可能）。一方，加算は必ず

  (<式>+<式>)

  のように括弧を伴って出現します。
• パーサ視点：この文法は文脈自由文法（BNF風）であり，AST（抽象構文木）を想定すると加算ノードは必ず括弧を示す内部ノードとして現れます。括弧の有無は構文的に重要な手がかりです。

FAQ