応用情報技術者試験 - SE娘の剣 -

応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。少しずつ追記していきます

BNF(Backus-Naur Form)

 

1.BNF(Backus-Naur Form)

バッカスナウアーフォームと読みます。
我々が日常で話す言葉が自然言語ですが、そのコンピュータに理解しろというのは無理があります。そこで、ルール(形式)に基づいた言語を形式言語と言います。その代表がBNFです。

BNFでは、2つのルールだけ覚えましょう。

➀ ::= ⇒ 定義する
② |   ⇒ または

では、例を見ましょう。
bnf
上記のルールに従うと、<digit>には数字の0か1か2か3が入ります。

2.BNF(Backus-Naur Form)の過去問

(1)H29秋AP問2
問2 次のBNFにおいて非終端記号〈A〉から生成される文字列はどれか。
〈R0〉::=0|3|6|9
〈R1〉::=1|4|7
〈R2〉::=2|5|8
〈A〉 ::=〈R0〉|〈A〉〈R)〉|〈B〉〈R2〉|〈C〉〈R1〉
〈B〉 ::=〈R1〉|〈A〉〈R1〉|〈B〉〈R0〉|〈C〉〈R2〉
〈C〉 ::=〈R2〉|〈A〉〈R2〉|〈B〉〈R1〉|〈C〉〈R0〉
ア 123   イ 124   ウ 127   エ 128




【正解】ア

(2)平成29年春期 午前

問4 あるプログラム言語において,識別子(identifier)は,先頭が英字で始まり,それ以降に任意個の英数字が続く文字列である。これをBNFで定義したとき,aに入るものはどれか。

bnf

1行目から順に解説します。
・<digit>の右に::=がありますので、<digit>という言葉を定義しています。具体的な定義内容は右側にあり、|で区切られているので、0または1または2または・・・9のいずれかの値を取ります。つまり、<digit>は任意の1桁の数字が入ることがわかります。
 ・同様に、<letter>には大文字小文字を含めた任意のアルファベット1文字が入ります。
 ・<identifier>は、<letter>または <identifier><digit>または<identifier><letter>です。順に説明します。
①<letter>の場合
任意のアルファベット1文字が入ります。
② <identifier><digit>の場合
<identifier>が取りうる値+任意の数字1文字が入ります。
③ <identifier><letter>の場合
<identifier>が取りうる値+任意のアルファベット1文字が入ります。
①の法則にしたがうと、<identifier>は例えばA、②の法則にしたがうと、<identifier>は例えばA1、③の法則にしたがうと、<identifier>は例えばA1Bです。さらに、この値をもって②や③の法則に当てはめると、たとえばA1B2、A1BC、となります。ここに挙げた5個のいずれの場合でも、<identifier>は先頭が英字で始まり,それ以降に任意個の英数字が続く文字列となります。

正解:エ