平成23年秋期試験午前問題 問4

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
次の規則から生成することができる式はどれか。

〔規則〕
<式> ::=<変数>|(<式>+<式>)|<式>*<式>
<変数> ::=A|B|C|D

  • A+(B+C)*D
  • (A+B)+(C+D)
  • (A+B)*(C+D)
  • (A*B)+(C*D)
正解 問題へ
分野:テクノロジ系
中分類:基礎理論
小分類:情報に関する理論
問題文のような構文定義法は、BNF(Backus-Naur Form,バッカス・ナウア記法)と呼ばれ、XMLをはじめ多くのプログラム言語の構文定義に用いられています。
BNFで使われている各記号は、「::=」が左辺と右辺の区切り、「|」がor(または)、「<>」は非終端記号を表しています。

各式を規則に従って変換していき、最後に<式>の形になれば構文定義に則っていることになります。
  • A+(B+C)*D → <式>+<式>*<式> → <式>+<式>
  • (A+B)+(C+D) → <式>+<式>
  • 正しい。以下のように、これだけが<式>になります。
    (A+B)*(C+D) → <式>*<式> → <式>
  • (A*B)+(C*D) → (<式>)+(<式>)

Pagetop