BNF(バッカス)記法について

質問

次のBNFで定義されるビット列Sであるものは、どれか。
<S>::=01|0<S>1

ア、000111
イ、010010
ウ、010101
エ、011111

正解：ア

このように<変数>は、左辺と同じ変数を右辺で用いることが出来ます。
0<S>1を考えるには、まず<S>が使われていない「01」を代入します。
すると「0011」です。と記載されています。

自力で調べたのですが、
BNF(バッカス)記法で書かれた問題が読めません。
何故「01」を代入すると「0011」になるのでしょうか。
何故「ア」が正解になるのでしょうか。

お手数お掛けしますが、ご存知の方おられましたら、ご教授お願いします。

以上、よろしくお願い致します。

回答No.3

jjon-com · ベストアンサー

>「終端記号」と「非終端記号」は、何処を見て判断するのですか。

< > で囲まれているのが終端記号で，囲まれていないのが非終端記号。
非終端記号として < や > というメタキャラクタ自体を使いたければ '<' や '>' と表記する。

お礼

ご回答ありがとうございます。

「終端記号」と「非終端記号」の見分け方が分かりました。
これで再帰的に処理が出来るか出来ないかの判断が出来るのですね。

非常に丁寧に説明して頂き、ありがとうございました。

以上、ありがとうございました。

回答No.2

jjon-com

<S>::=01|0<S>1

上記のバッカス記法(BNF)が意味することは次のとおり。

非終端記号 <S> とは，
(規則a) 終端記号 01 である
または
(規則b) 非終端記号を含む定義 0<S>1 である
のどちらか。

終端記号とはその名のとおり定義はそこで終わるものでそれ以上展開されることはない。
非終端記号とはその名のとおり定義はそこで終わらずその中をさらに展開できるもので，(規則b)のように，自分の定義の中に自分自身が含まれている「再帰的な定義」ができることが特徴である。

よって<S>とは，
（以下，分かりやすさのために丸括弧を用いるが本来は不要）

(規則a)だけで得られる結果は【01】
(規則b)→(規則a)の順に展開した結果は，
　　0<S>1→【0(01)1】
(b)→(b)→(a)の順に規則が適用されたなら，
　　0<S>1 →0(0<S>1)1 →【0(0(01)1)1】
(b)→(b)→(b)→(a)という規則適用なら，
　　0<S>1 →0(0<S>1)1 →0(0(0<S>1)1)1 →【0(0(0(01)1)1)1)1】

以下，省略。このようなパターンに該当するのは，ア。

お礼

ご回答ありがとうございます。

お陰様で解釈することが出来ました。

「終端記号」は、それ以上展開されることはない。
「非終端記号」は、そこで終わらず更に展開が出来る。
「再帰的な定義」が出来る所がポイントなんですね。

更に質問で恐縮ですが、
「終端記号」と「非終端記号」は、何処を見て判断するのですか。

お手数お掛けしますが、ご教授お願いします。

以上、よろしくお願い致します。

回答No.1

Tacosan

「自力で調べた」結果として, 何が分かってどこが理解できないのですか?
「何故「01」を代入すると「0011」になるのでしょうか。」という疑問からすると, そもそも「0<S>1」が何を意味するかというところから理解できていないような気がするのですが.

お礼

ご回答ありがとうございます。

「0<S>1」の意味は分かりません。
BNF(バッカス)記法全体が分からないのです。

「<S>::=01|0<S>1」が、
「<S>」は「01」または「0<S>1」と解釈しました。
しかしその意味が全く分かりません。
それはどのような意味を持っているのでしょうか。

お手数お掛けしますが、解説お願いします。

以上、よろしくお願い致します。

補足

補足させて頂きます。

「<S>::=01|0<S>1」の右辺<S>に「01」を挿入すると、
「<S>::=01|0011」になります。そこまでは分かりました。
しかし何故それが「000111」になるかが分かりません。

お手数お掛けしますが、ご教授お願いします。

以上、よろしくお願い致します。