HOME»応用情報技術者試験掲示板»BNF記法の解き方について
投稿する

BNF記法の解き方について [1929]

 arikoさん(No.1) 
https://www.ap-siken.com/kakomon/29_aki/q2.html

BNF問題が理解できず苦しんでいます。
どうにか私のカチカチつるつるな脳みそにご助言を
お願いします。

例問として上述URLの問題ですが、
応用情報技術者平成29年秋期 午前問2

解き方として、まず回答選択肢をBNFに変換することは理解出来ます。

ア)123  =  <R1><R2><R0>
イ)124  =  <R1><R2><R1>
ウ)127  =  <R1><R2><R1>
エ)128  =  <R1><R2><R2>

BNFが重複しているイ、ウを答えから除外出来ることは理解できます。
ここから先の考え方がわかりません。
解説文の
------------------------------------------------
次に<A>の定義にある「<A><R0>」「<B><R2>」「<C><R1>」の3つの型から導出されるBNFのパターンを考えます。

[<A> <R0>]
非終端記号<A>に、それぞれ3つの型を当てはめます。
<A><R0><R0>→<R0><R0><R0>
<B><R2><R0>→<R1><R2><R0>
<C><R1><R0>→<R2><R1><R0>
…(省略)
------------------------------------------------
という部分が、どういう導き方をしているのかわかりません。

解説中「<A>の定義」とは、以下のことですね。
<A> ::= <R0>|<A> <R0>|<B> <R2>|<C>< R1>

確かに<A>の定義の中に「<A><R0>」「<B><R2>」「<C><R1>」があることはわかります。
次に、<A>に3つの型を当てはめる、というところで頭に"?"が出てきます。


2020.03.02 15:13
助け人さん(No.2) 
AP ゴールドマイスター
この解説は、定義の風呂敷をどんどん広げていき、表せるパターンを全て洗い出し、当てはまるものを見つけるやり方です。汎用的な解き方と言えますが、手間はかかります。

<A> ::= <R0>|<A> <R0>|<B> <R2>|<C> <R1>
を見ると、
<A>は、
<R0>であれば1文字、
<A> <R0>であれば<A>の文字数+1文字、
<B> <R2>であれば<B>の文字数+1文字、
<C> <R1>であれば<C>の文字数+1文字、
であり、
上記の<A>や<B>や<C>が1文字であれば、<A>は(<B>も<C>も)2文字になり、
上記の<A>や<B>や<C>が2文字であれば、<A>は(<B>も<C>も)3文字になり、
というように、無限に文字数が増えていきます。

ちょっと簡略化して書きます。

A=R0 or AR0 or BR2 or CR1
ですが、選択肢はいずれも3文字ですから、このうちR0は省かれます。
A=AR0 or BR2 or CR1
右辺のAに右辺を代入、右辺のBに問題文のBの定義の右3通りを代入、右辺のCに問題文のCの定義の右3通りを代入すると、
A=(AR0 or BR2 or CR1)R0 or (AR1 or BR0 or CR2)R2 or (AR2 or BR1 or CR0)R1
=AR0R0 or BR2R0 or CR1R0 or AR1R2 or BR0R2 or CR2R2 or AR2R1 or BR1R1 or CR0R1
ここで、右辺のAにR0、BにR1、CにR2を代入すると、
A=R0R0R0 or R1R2R0 or R2R1R0 or R0R1R2 or R1R0R2 or R2R2R2 or R0R2R1 or B1R1R1 or R2R0R1
あとは、解説通りです。

ここで、私の解き方です。この問題に特化した解き方ですが、他の問題でも使えるかもしれません。

選択肢のそれぞれが正解、つまりAで定義できるなら、
アは、最後の3がR0だから、AR0の形式であり、そのAは上2桁の12
イは、最後の4がR1だから、CR1の形式であり、そのCは上2桁の12
ウは、最後の7がR1だから、CR1の形式であり、そのCは上2桁の12
エは、最後の8がR2だから、BR2の形式であり、そのBは上2桁の12
となります。
12がA、B、Cで定義できるかを考えると、
12の最初の1はR1(つまりB)、最後の2はR2だから、BR2はAでしか定義できず、アが正解
2020.03.02 16:20
助け人さん(No.3) 
AP ゴールドマイスター
もっと早い解き方です。

選択肢3文字のうち、先頭2文字はいずでも12であり、12を定義できるのは、BR2を含むAだけです。

次に、Aの定義で、Aの次に来るのはR0であり、選択肢の最後の桁としてR0に該当するのは、3のアです。
2020.03.02 16:48
 arikoさん(No.4) 
TO:助け人さん
ご回答ありがとうございます。

> 無限に文字数が増えていきます。
そうですよね!
「再帰的に呼び出すから無限に増えるよな~」という
ところだけ頭にひっかかり、そこが問題の解説文で触れられておらず
思考停止してしまっていました。

後半のご説明も理解できました。
BNFの問題に取り組んで、慣れていきたいと思います!
2020.03.02 21:43

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop