令和元年度(再試験) III-6

解説

この問題で問われていること

BNFの生成規則に従って、各式が導出可能かを調べる問題。

解き方

① 文法の形を確かめる: 「+」と「*」は右側に同じ記号(<S>、<T>)が来るので何度でも続けられる。「−」と「/」は両側が<T>・<F>なので1回しか使えない
② x/2/3 は「/」が2回続き、<F>"/"<F> では作れない。1+2−3 は「−」が1回なので作れる
③ ③

正解が正しい理由

規則は、<S>::=<T>"+"<S>|<T>"−"<T>|<T>、<T>::=<F>"*"<T>|<F>"/"<F>|<F>、<F>::="1"|"2"|"3"|"x"|"("<S>")"である。<T>の除算の規則は、<F>"/"<F>だけで、右辺が<F>1つに限られ、「/」を連続して使う形(x/2/3)は導出できない。したがって、1+x/2/3を含む③が導出できず、最も不適切である。

各選択肢について

• ① ((1))は、<F>→"("<S>")"を2重に適用し、最も内側の<S>→<T>→<F>→"1"と導出できる。
• ② 1+2−3は、<S>→<T>"+"<S>とし、後ろの<S>→<T>"−"<T>(2−3)として導出できる。
• ③ x/2/3は、<T>→<F>"/"<F>の規則では、「/」が1回しか使えず、導出できない。不適切で、これが正答。
• ④ 1+x*2+2は、<S>→<T>"+"<S>とし、後ろの<S>を<T>"+"<S>(x*2と2)と展開して導出できる。
• ⑤ 1+x*2*3は、<S>→<T>"+"<S>とし、後ろを<T>→<F>"*"<T>(x*(2*3))と展開して導出できる。

覚えるべきポイント

BNFの導出では、各非終端記号に許される右辺の形を厳密に当てはめる。この文法では、乗算は右結合に連続できるが、除算と減算は連続できない。