情報・アルゴリズムのテーマ一覧へ

基礎科目・情報・アルゴリズム

BNFと構文図

大学

4問H24・H26・H29・R1

BNF（バッカス・ナウア記法）や構文図で書かれた決まりから、作れるもの・作れないものを選ぶ問題が出ます。

よく出る形

  • BNFで定義された「数値」の書き方から，表せない数値を選ぶ
  • ＜数値列＞::=01｜0＜数値列＞1 のような自分自身を使う（再帰的な）定義から，作れる 0 と 1 の並びを選ぶ
  • 英字と数字のくり返しを表す構文図から，表せない文字列を選ぶ
  • BNFか構文図かで，定義の中身が替わる。平成24と平成29は同じ定義

覚えること

  • 「A ::= B」は「A を B と定める」という意味
  • 「｜」は「または」。A ::= B｜C は「A は B か C のどちらか」
  • 並べて書いた A ::= B C は「B のあとに C を続けたもの」
  • 自分自身を使う定義（例：数字列 ::= 数字｜数字列 数字）は「くり返し」を表す。この例は「数字が1個以上並んだもの」
  • ＜数値列＞::=01｜0＜数値列＞1 で作れるのは 01，0011，000111 … のように「0 が n 個のあとに 1 が同じ n 個」の並びだけ
  • ＜列＞::=01｜0＜列＞1｜＜列＞＜列＞ のように「＜列＞＜列＞」を足すと，作った列を横につなげられる。0 を開きかっこ，1 を閉じかっこと読むと，正しく対応したかっこの並びになる
  • 式のBNF：先に計算したい演算（×）は内側の規則（＜項＞），後の演算（＋）は外側の規則（＜式＞）に置く
  • 構文図は，矢印の道をたどって通れる順に記号を並べたものが，表せる文字列

解き方

  • 選択肢を1つずつ，定義の中の部品（符号，整数，小数など）に分けられるか試す
  • 例：数値 ::= 整数｜小数｜整数 小数，整数 ::= 数字列｜符号 数字列，小数 ::= 小数点 数字列 のとき
  • －19.1 は 整数「－19」＋ 小数「.1」で作れる。.52 は小数として作れる
  • －.37 は，符号「－」のすぐ後ろに数字列がないので作れない
  • 再帰の定義は，短いものから順に 01 → 0011 → 000111 と実際に作って，選択肢と比べる
  • 「＜列＞＜列＞」がある定義は，左から読んで，途中で 1 の数が 0 の数より多くならず，最後に同じ数になれば作れる

ひっかけ

  • 部品がどこにしか出てこないかを見落とさない（例：符号が使えるのは「符号 数字列」の形だけ）
  • 0 と 1 の個数が同じでも，0101 のように交互に並ぶものは「0 が n 個のあとに 1 が n 個」の定義では作れない
  • 0 と 1 の個数が同じでも，途中で 1 が多くなる列（0110 など）は作れない
  • ＜式＞ ::= ＜項＞ のような「1つだけの形」を見落とさない（a×b は，そのまま＜式＞になれる）
このテーマの想定問題を解く

想定問題：1・2・3

このテーマの過去問（このサイトに解説がある 1問）

X で共有LINE で送る

平成に出た同じテーマ（3問）

このサイトにはまだ解説がありません。年度と題だけです。