基本情報技術者

【基本情報技術者試験】BNF記法

本日のテーマはBNF記法、次の問題は基本情報技術者試験で出題された過去問です。
BNF記法?聞いたことない言葉ですね・・・

問題

次のBNFで定義される<変数名>に合致するものはどれか。

<数字>::= 0|1|2|3|4|5|6|7|8|9

<英字>::= A|B|C|D|E|F

<英数字>::=<英字>|<数字>|_

<変数名>::=<英字>|<変数名><英数字>

  • ア:_B39
  • イ:246
  • ウ:3E5
  • エ:F5_1

基本情報技術者令和元年秋期 午前問7

問題

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

〔規則〕

<式> ::=<変数>|(<式>+<式>)|<式>*<式>

<変数> ::=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記法について図解を利用して分かりやすく解説していきます。

本記事で学べること

  • BNF記法の文法を理解
  • BNF記法の再帰的定義を理解
  • 基本情報技術者試験の過去問の解き方を学ぶ

BNF記法

BNF記法とは、バッカス・ナウア記法(英:Backus-Naur form)を略した言葉であり、文脈自由文法を定義するのに用いられるメタ言語(言語を記述するための言語)のことです。

BNF記法では次の記号を用いて文法の定義を行います。

BNF記法で使用する記号

記号 意味
<記号> 置き換え可能である(非終端記号)ことをあらわす
::= 「左辺は右辺である」という意味をあらわす
| 「または」という意味をあらわす

スポンサーリンク

例えば次のようなBNF記法の定義があるとします。

<数字> ::= 1 | 2

上記の例では、<数字>は「1」または「2」であるということをあらわしています。

<数字> :: = 1 | 2

<英字> :: = A | B

<英数字> :: = <英字><数字>

上記の例では<数字>は「1」または「2」<英字>は「A」または「B」<英数字>は <英字><数字>であるということをあらわしています。

<英数字>の<英字><数字>は(「A」または「B」)(「1」または「2」)のことであり「A1」「A2」「B1」「B2」の英数字を表現することができます。

BNF記法の再帰的定義

BNF記法では次のように定義の中に自分自身を含むことができます。このような手法を再帰的定義といいます。

<数字> :: = 1 | 2

<英字> :: = A | B

<英数字> :: = <英字> | <英数字><数字>

上記の例の<英字> | <英数字><数字>は(「A」または「B」)または(<英字> | <英数字><数字>)(「1」または「2」)のことをあらわしています。(<英数字>は自分自身なので<英字> | <英数字><数字>をあらわす)

このように定義の中に再帰的定義を書くことで、同じパターンの繰り返しを表現することができます。

基本情報技術者試験 過去問の解説

スポンサーリンク

基本情報技術者令和元年秋期 午前問7

問題

次のBNFで定義される<変数名>に合致するものはどれか。

<数字>::= 0|1|2|3|4|5|6|7|8|9

<英字>::= A|B|C|D|E|F

<英数字>::=<英字>|<数字>|_

<変数名>::=<英字>|<変数名><英数字>

  • ア:_B39
  • イ:246
  • ウ:3E5
  • エ:F5_1

基本情報技術者令和元年秋期 午前問7

この問題は<変数名>がどういうルールで定義されているかを考えます。

<変数名>::=<英字>|<変数名><英数字>

解答のア~エは3文字か4文字です。ということは「<変数名><英数字>」の条件に2回もしくは3回入ることがわかります。

3文字の場合の例

<英字>|<変数名><英数字>

↓ <変数名><英数字>の条件を選択

<変数名><英数字>

↓ <変数名>は再帰的定義

<<英字>|<変数名><英数字>><英数字>

↓ <変数名><英数字>の条件を選択

<<変数名><英数字>><英数字>

↓ <変数名>は再帰的定義

<<<英字>|<変数名><英数字>><英数字>><英数字>

↓ <英字>の条件を選択

<<<英字>><英数字>><英数字>

上記より3文字の文字列が作られる

そして、先頭は必ず<英字>になることもわかります。(<英字>|<変数名><英数字>で繰り返しにならない条件は<英字>を選んだときしかない。)

ア:_B39 ・・・ 先頭が英字ではないので不正解

イ:246 ・・・ 先頭が英字ではないので不正解

ウ:3E5 ・・・ 先頭が英字ではないので不正解

エ:F5_1 ・・・ 先頭が英字なので正解

答えは「エ」の「F5_1」です。

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

問題

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

〔規則〕

<式> ::=<変数>|(<式>+<式>)|<式>*<式>

<変数> ::=A|B|C|D

  • ア:A+(B+C)*D
  • イ:(A+B)+(C+D)
  • ウ:(A+B)*(C+D)
  • エ:(A*B)+(C*D)

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

この問題は解答のア~エを問題の規則に従って変換していき<式>の形式になるものを探します。

〔規則〕

<式> ::=<変数>|(<式>+<式>)|<式>*<式>

<変数> ::=A|B|C|D

解答ア A+(B+C)*D

解答アを規則に従って変換していきます。

解答アの変換

A+(B+C)*D

※Aは<変数>に一致、(B+C)は(<式>+<式>)に一致、Dは<変数>に一致するので、いずれも<式>に変換できる

<式> + <式> * <式>

※<式> * <式>は<式>*<式>に一致するので<式>に変換できる

<式>+<式>

これ以上は変換できないので不正解

解答イ (A+B)+(C+D)

解答イを規則に従って変換していきます。

解答イの変換

(A+B)+(C+D)

※(A+B)は(<式>+<式>)に一致、(C+D)は(<式>+<式>)に一致するので、いずれも<式>に変換できる

<式> + <式>

これ以上は変換できないので不正解

解答ウ (A+B)*(C+D)

解答ウを規則に従って変換していきます。

解答ウの変換

(A+B)*(C+D)

※(A+B)は(<式>+<式>)に一致、(C+D)は(<式>+<式>)に一致するので、いずれも<式>に変換できる

<式> * <式>

※<式> * <式>は<式>*<式>に一致するので<式>に変換できる

<式>

<式>に変換できたので正解

解答エ (A*B)+(C*D)

解答エを規則に従って変換していきます。

解答イの変換

(A*B)+(C*D)

※A*Bは<式>*<式>に一致、C*Dは<式>*<式>に一致するので、いずれも<式>に変換できる

(<式>) + (<式>)

これ以上は変換できないので不正解

上記より<式> ::=<変数>|(<式>+<式>)|<式>*<式>の規則から生成できる式は「ウ」の(A+B)*(C+D)ということが分かりました。


チャンネル登録はこちら

フォローはこちら