応用情報技術者平成29年秋期 午前2
次のBNFにおいて非終端記号＜A＞から生成される文字列はどれか。
＜R0＞ ::= 0｜3｜6｜9
＜R1＞ ::= 1｜4｜7
＜R2＞ ::= 2｜5｜8
＜A＞ ::= ＜R0＞｜＜A＞ ＜R0＞｜＜B＞ ＜R2＞｜＜C＞＜ R1＞
＜B＞ ::= ＜R1＞｜＜A＞ ＜R1＞｜＜B＞ ＜R0＞｜＜C＞＜ R2＞
＜C＞ ::= ＜R2＞｜＜A＞ ＜R2＞｜＜B＞ ＜R1＞｜＜C＞ ＜R0＞
１、＜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＞
・[＜B＞＜R2＞]
非終端記号＜B＞に、それぞれ3つの型を当てはめます。
＜A＞＜R1＞＜R2＞→＜R0＞＜R1＞＜R2＞
＜B＞＜R0＞＜R2＞→＜R1＞＜R0＞＜R2＞
＜C＞＜R2＞＜R2＞→＜R2＞＜R2＞＜R2＞
・[＜C＞＜R1＞]
非終端記号＜C＞に、それぞれ3つの型を当てはめます。
＜A＞＜R2＞＜R1＞→＜R0＞＜R2＞＜R1＞
＜B＞＜R1＞＜R1＞→＜R1＞＜R1＞＜R1＞
＜C＞＜R0＞＜R1＞→＜R2＞＜R0＞＜R1＞
２、
123→ ＜R1＞＜R2＞＜R0＞ 上記※のところですね。
124→ ＜R1＞＜R2＞＜R1＞
127→ ＜R1＞＜R2＞＜R1＞
128→ ＜R1＞＜R2＞＜R2＞
簡単に考えると、Aは＜A＞ ＜R0＞｜＜B＞ ＜R2＞｜＜C＞＜ R1＞ というふうに定義されているので、
最後の文字はR0ですね。
つまり、0｜3｜6｜9のいずれかですから、123でしょうね。
もうちょっと確かめとすると、
123→ ＜R1＞＜R2＞＜R0＞ の真ん中はR2ので、 つまり
＜A＞＜R0＞
-＞＜B＞＜R2＞＜R0＞
-＞＜R1＞＜R2＞＜R0＞
になりますね。
・BNFとは、
バッカス・ナウア記法（英: Backus-Naur form）とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般にBNFやBN記法と略される。
参照：
BNFで表現されたあるプログラム言語の構文
https://qiita.com/lymansouka2017/items/f0960106b6490d1abd4d