基礎理論
平成23年度 秋期 基本情報技術者試験 午前 問4
次の規則から生成することができる式はどれか。
〔規則〕
<式> ::= <変数> | (<式>+<式>) | <式>*<式>
<変数> ::= A | B | C | D
- ア A+(B+C)*D
- イ (A+B)+(C+D)
- ウ (A+B)*(C+D)
- エ (A*B)+(C*D)
出典：平成23年度 秋期 基本情報技術者試験 午前 問4
答えと解説を見る
正解：ウ
覚える知識
BNF構文規則の適合判定
BNFは構文を生成規則(::=)と選択(|)で形式的に定義する記法である。
この問題で必要なこと
BNFの再帰規則に従い、各式が生成可能か展開して確かめる。(A+B)*(C+D)は<式>*<式>で生成できる。
ひっかけ
+は括弧付きの式でしか生成できない点を見落とすと、括弧なしの式や+が括弧で囲まれない式を選んでしまう。
この知識の出題：本試験系 2 回・免除試験 2 回（公開問題での観測値）