応用情報技術者試験 応用情報技術者試験 平成29年度秋期 午前 問2: 次の BNF において非終端記号 〈A〉 から生成される文字列はどれか。 〈R0〉 ::= 0｜3｜6｜9 〈R1〉 ::= 1｜4｜7 〈R2〉 ::= 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〉

選択肢

• ア.123
• イ.124
• ウ.127
• エ.128

正解

ア. 123

解説

BNF(バッカス記法)は構文規則を定義する表記で，::= の左辺の非終端記号を右辺の並びに置き換えていける(｜は『または』)。〈R0〉は3で割り切れる数字{0,3,6,9}，〈R1〉は3で割って1余る{1,4,7}，〈R2〉は3で割って2余る{2,5,8}という分類になっている点に着目する。〈A〉から生成できるのは末尾を順にたどると『123』だけで，〈A〉⇒〈A〉〈R0〉('3'は R0)⇒〈B〉〈R2〉〈R0〉('2'は R2)⇒〈R1〉〈R2〉〈R0〉('1'は R1)＝『123』と導出できるため，アが正しい。

選択肢ごとの解説

• ア.正しい。末尾の3は〈R0〉，〈A〉::=〈A〉〈R0〉を使う。残る『12』は〈A〉::=〈B〉〈R2〉で2(R2)を分け，『1』は〈B〉::=〈R1〉で生成でき，全体を導出できる。
• イ.誤り。末尾の4は〈R1〉。〈A〉で末尾が〈R1〉になるのは〈C〉〈R1〉だけで，残る『12』を〈C〉から生成する必要があるが，〈C〉の各規則(末尾が R2/R1/R0)では『12』を作れず導出できない。
• ウ.誤り。末尾の7は〈R1〉なので〈A〉::=〈C〉〈R1〉となるが，イと同様に先頭の『12』を〈C〉から導けないため生成できない。
• エ.誤り。末尾の8は〈R2〉なので〈A〉::=〈B〉〈R2〉となり，先頭『12』を〈B〉から生成する必要があるが，〈B〉の規則では『12』を作れず導出できない。