2020年国家一般職(電気・電子・情報) No.33解説

　問題　　　　　

次の生成規則の集合で定義される文脈自由文法がある。この文法において、S は開始記号、E は非終端記号、{if、then、else、end、while、do、print、(、)、x} は終端記号の集合である。

この文法により、例えば、「print ( x )」という終端記号列は、「S → print E → print ( E ) → print ( x )」のように生成される。次の㋐～㋓の終端記号列のうち、この文法により生成されるもののみを全て挙げているのはどれか。

1．㋐，㋑，㋒
2．㋐，㋓
3．㋑，㋒
4．㋑，㋓
5．㋒，㋓

正解 (2)

　解説　　　　　

例の「S → print E → print ( E ) → print ( x )」をよく見て、文の作り方を自分なりに把握してから、各終端記号列の生成にトライすれば判断できると思われます。

㋐ですが
「while」が入っているので、文法における S → while E do S end に注目します。すると、例から S の所を print (x) にできることはわかっています。後は E から (((x))) に生成できるかどうかがポイントです。

E → (E) → ((E)) → (((E))) → (((x))) の順にルールから置き換えていけば、(((x))) は作れます。㋐は本問の文法から生成できます。正解は 1 or 2 です。

㋑ですが
この文法では (x) は作れるのですが ( print x ) のように x 以外を ( ) の中に入れる変換は無理です。従って、㋑は生成できません。選択肢 1 は誤りです。余裕がある人はぜひ㋓が作れることを確認してみてください。

以上より、正解は 2 です。

コメント