問題
BNF（バッカス・ナウア記法）で <S> ::= a | b<S>c と定義されたとき、生成される文字列の形として正しいものはどれか。
選択肢
- 1a または bac または bbacc など（左に b、右に c が同数並び中心が a）
- 2a が任意個並んだもの
- 3b と c が交互に並んだもの
- 4a と b が交互に並ぶもの
正解
1. a または bac または bbacc など（左に b、右に c が同数並び中心が a）
詳しい解説を見る解説を閉じる
解説
再帰的定義 <S>::=a | b<S>c により、<S> は a に「b」を左に「c」を右に同数ずつ付加して得られる。具体的には a, bac, bbacc, bbbaccc, … のように b^n a c^n （n≧0）の形となる。これは文脈自由文法でしか表現できない代表例で、正規表現では b^n a c^n のような左右対応はカウントが必要なため記述できない。コンパイラの構文解析やプログラミング言語設計の基礎として頻出する。
一問一答
全400問を繰り返し学習