次のようなBNFで定義された文法を考える。
<S> :: = <A><B>
<A> :: = a | a<A>
<B> :: = b | b<B> | c | c<B>
ここで、< > で囲まれたものは非終端記号、英小文字１文字は終端記号とし、
開始記号を <S> とする。この文法により生成される文を正規表現で表したものは
どれか。ただし、正規表現において * は直前のものの０回以上の繰り返しを表す。
| は選択を表すものとする。
① a*b*c
② a*(b | c)*
③ aa*(bb* | cc*)
④ aa*(bc)(bc)*
⑤ aa*(b | c)(b | c)*
① a * b * c * の正規表現では、 例えば a が０回、すなわち aがなくてもよいが、
BNFでは、<S> :: = <A><B> つまり、 (a | a<A>)<B>により、
a が少なくとも１つ以上は現れなければならない。
②①と同様であり、誤り。
③BNFでは、例えば abc が表現可能であるが、正規表現では生成できない。
④BNFでは、例えば abb や acc が表現可能であるが、正規表現では
生成できない。
⑤正しい。
EXCELのマクロのご相談なら ファーストマクロ へ
タグ：BNF
