基本情報技術者 試験情報&徹底解説 -新制度に完全対応-

基本情報技術者 平成23年秋期 午前問4

午前問4

次の規則から生成することができる式はどれか。

〔規則〕
<式> ::=<変数>|(<式>+<式>)|<式>*<式>
<変数> ::=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)→(<式>)*(<式>)